Principle of the Ariadne's Clew Algorithm

 

As we have seen in the previous section, the computation of the configuration space 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 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 along with such a parameterized trajectory implicitly define a path and a final configuration in the configuration space. For example, for a holonomic mobile robot the trajectory ( ) can be interpreted as making a degree turn, moving straight , making a degree turn and so on. Given the starting configuration , this trajectory leads to the final configuration (see Figure 3).

  
Figure 3: A parameterized trajectory ( ) and a starting point 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 and the goal 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 if the path is collision-free, and otherwise ( being the first collision point).

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 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 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 , where 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 and .
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 .

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 -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 -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: (the initial position), (the goal position), and (the maximum allowed distance for a path to the ). 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:

denotes the extremity of a legal path parameterized with 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:

• ``Space filling completeness'': The global maximum distance can be found by the optimization algorithm used in EXPLORE; the configuration space is a compact set.
• `` completeness'': The optimization procedure used in SEARCH always find a complete path (or returns 0) when the starting and the goal positions are located within a ball of radius of the free space.

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.