next up previous
Next: Path Planning for a Up: No Title Previous: The Path Planning Problem

Principle of the Ariadne's Clew Algorithm


As we have seen in the previous section, the computation of the configuration space tex2html_wrap_inline1298 is a very time-consuming task. The main idea behind the Ariadne's clew algorithm is to avoid this computation. In order to do this, the algorithm searches directly for a feasible path in the trajectory space. The configuration space tex2html_wrap_inline1298 is never explicitly computed.

As will be shown, in the trajectory space, path planning may be seen as an optimization problem and solved as such by an algorithm called SEARCH. It is possible to build an approximation of free space by another algorithm called EXPLORE that is also posed as an optimization problem. The Ariadne's clew algorithm is the result of the interleaved execution of SEARCH and EXPLORE.

Path Planning as an Optimization Problem: SEARCH

Given a robot with k DOF, a trajectory of length l may be parameterized as a sequence of n=k*l successive movements. A starting point tex2html_wrap_inline1416 along with such a parameterized trajectory implicitly define a path and a final configuration tex2html_wrap_inline1418 in the configuration space. For example, for a holonomic mobile robot the trajectory ( tex2html_wrap_inline1308 ) can be interpreted as making a tex2html_wrap_inline1422 degree turn, moving straight tex2html_wrap_inline1424 , making a tex2html_wrap_inline1426 degree turn and so on. Given the starting configuration tex2html_wrap_inline1416 , this trajectory leads to the final configuration tex2html_wrap_inline1418 (see Figure 3).

Figure 3: A parameterized trajectory ( tex2html_wrap_inline1308 ) and a starting point tex2html_wrap_inline1350 implicitly define a path (in the operational space) for a holonomic mobile robot.

Given a distance function d on the configuration space, if we find a trajectory such that it does not collide with any obstacles and such that the distance between tex2html_wrap_inline1418 and the goal tex2html_wrap_inline1462 is zero, then we have a solution to our path planning problem. Therefore, the path planning problem may be seen as a minimization problem where:

  1. The search space is a space of suitably parameterized trajectories, the trajectory space.
  2. The function to minimize is tex2html_wrap_inline1464 if the path is collision-free, and tex2html_wrap_inline1466 otherwise ( tex2html_wrap_inline1468 being the first collision point).gif

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.

Figure 4: Reactive replanning in a changing environment

Figure 5: A problem leading to a local minimum. In such a case, a solution path has first to move away from the goal. The goal's ``attraction'' based on the minimization of the Euclidean distance prevents SEARCH from finding such a path.

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 tex2html_wrap_inline1416 to tex2html_wrap_inline1462 , the purpose of EXPLORE is to compute an approximation of the region of the configuration space accessible from tex2html_wrap_inline1416 .

The EXPLORE algorithm builds an approximation of the accessible space by placing landmarks in the configuration space tex2html_wrap_inline1298 in such a way that a path from the initial position tex2html_wrap_inline1416 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.

Figure 6: The first picture represents the initial position and the first landmark. The subsequent landmarks are then uniformly spread over the search space while the method keeps track of all paths joining the landmarks to the initial position. The algorithm is named after Ariadne because by placing landmarks, EXPLORE unwinds as if it were using a thread as Theseus did.

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

  1. The search space is the set of all paths starting from one of the previously placed landmarks.
  2. The function to maximize is tex2html_wrap_inline1492 , where tex2html_wrap_inline1494 is the set of landmarks already placed.

The Ariadne's Clew Algorithm: EXPLORE + SEARCH

In order to have a planner that is both complete and efficient, we combined the two previous algorithms SEARCH and EXPLORE to obtain the Ariadne's clew algorithm.

The principle of the Ariadne's clew algorithm is very simple:

  1. Use the SEARCH algorithm to find whether a ``simple'' path exists between tex2html_wrap_inline1416 and tex2html_wrap_inline1462 .
  2. If no ``simple'' path is found by step 1, then continue until a path is found.
    1. Use EXPLORE to generate a new landmark.
    2. Use SEARCH to look for a ``simple'' path from that landmark to tex2html_wrap_inline1462 .

The Ariadne's clew algorithm will find a path if one exists. In an overwhelming number of cases, just a few landmarks are necessary for the Ariadne's clew algorithm to reach the target and stop.

A Major Improvement: Bouncing on tex2html_wrap_inline1298 -Obstacles


A typical difficulty for a path planning algorithm is to find a collision-free path through a small corridor in the configuration space. This is also the case for the basic version of the Ariadne's clew algorithm, presented above. The problem is that very few trajectories encode such paths and therefore they are very difficult to find. Most trajectories collide with the obstacles. We propose a very simple idea to deal with this problem: going backwards at each collision point. If, for a given trajectory, a collision is detected along the corresponding path, then we simply consider transforming that trajectory so that it encodes a new path, one that is found by bouncing off the obstacle at the collision point (see Figure 7). Note that this construction is applied recursively until the entire trajectory corresponds to a collision-free path.

Figure 7: Bouncing against tex2html_wrap_inline1298 -obstacles. Figure (a) presents the original path in the configuration space. Figure (b) shows the same path after two bounces along the second segment on obstacle 2 and on obstacle 1. Figure (c) is the result obtained after a bounce of segment 3 against obstacle 2. Finally, Figure (d) presents a valid path obtained after a final bounce of segment 4 against obstacle 2.

Using this technique, all trajectories are so transformed that they encode valid paths. This improved version of the Ariadne's clew algorithm no longer cares about obstacles. From the point of view of a search in the trajectory space, it is as if the obstacles have simply vanished. This method is especially efficient for narrow corridors in the configuration space. Without bouncing, the mapping of a corridor in the configuration space to the trajectory space is a set of very few points. With bouncing, every single trajectory going through a part of the corridor is ``folded'' into the corridor (see Figure 7). The resultant mapping of the corridor in the trajectory space is consequently a much larger set of points, and therefore it is much easier to find a member of this set. This empirical improvement has a major practical impact because it makes the proposed algorithm faster (fifteen times) in the problem considered below.

The Algorithm

We can now give a final version of the Ariadne's clew algorithm. It has three inputs: tex2html_wrap_inline1416 (the initial position), tex2html_wrap_inline1462 (the goal position), and tex2html_wrap_inline1516 (the maximum allowed distance for a path to the tex2html_wrap_inline1322 ). It returns a legal path or terminates if no path exists at the given resolution.

Figure 8: The Ariadne's Clew Algorithm

The algorithm is based on the following optimization problems:



tex2html_wrap_inline1550 denotes the extremity of a legal path parameterized with tex2html_wrap_inline1552 real parameters and starting either from each of the previously placed landmarks (EXPLORE) or from the latest placed landmark (SEARCH).

The algorithm is resolution-complete under the following assumptions:

In practice, the first condition cannot be met with a randomized optimization algorithm in a bounded time, and only local maxima are found. However, the landmarks placed according to the new algorithm are better distributed over the free space than landmarks placed randomly, leading to better performances. The goal of the next section is to justify this claim, experimentally.

next up previous
Next: Path Planning for a Up: No Title Previous: The Path Planning Problem

Emmanuel Mazer
Tue Nov 10 17:28:31 MET 1998