The algorithm SEARCH, based on this very simple technique and a randomized optimization method, is already able to solve quite complex problems of robot motion planning. For example, Figure 4 represents the two paths found for the holonomic mobile robot.  Each path was computed on a standard workstation ( SPARC 5 ) in less than 0.5 second without using any pre-computation of the configuration space. Thus, it is possible, albeit slowly, to get a planner that can be used in a dynamic environment (where the obstacles may move)
by "dropping" a new world into the system every 0.5 second. SEARCH is very efficient but it is not complete, since it may fail to find a path even if one exists for two different reasons:
1. Due to the optimization-based formulation, SEARCH can get trapped by local minima

of the objective function, which in turn may place the robot far away from the goal
(see Figure 5).

2. The length l of the trajectories considered may be too short to reach all the accessible regions of the configuration space.

![0_image_0.png](0_image_0.png)

## 3.2  Exploring As An Optimization Problem: Explore

In order to build a complete planner, we propose a second algorithm called EXPLORE . While the purpose of SEARCH was to look directly for a path from ˆ α to ˆ α , the purpose of EXPLORE is to compute an approximation of the region of the configuration space accessible from ˆ α .

The EXPLORE algorithm builds an approximation of the accessible space by placing landmarks in the configuration space in such a way that a path from the initial position ˆo to any landmark is known. In order to learn as much as possible about the free space, the EXPLORE algorithm tries to spread the landmarks uniformly over the space (see Figure 6).

To do this, it tries to put the landmarks as far as possible from one another by maximizing the distances between them.

Therefore, EXPLORE may be seen as a maximization problem where: