[Ahuactzin94a] Juan-Manuel Ahuactzin; Planification et heuristique en robotique; Thèse de troisième cycle INPG (Institut National Polytechnique de Grenoble); Grenoble, France, 1994;
Abstract: The ultimate goal of a path planner is to find a path in the configurationspace from the initial position to the target. However, whilesearching for this path, an interesting sub-goal to consider may be totry to collect information about the free space and about thepossible paths to go about in that space. The ARIADNE'S CLEW algorithmtries to do both at the same time. An EXPLORE algorithm collectsinformation about the free space with an increasingly fine resolution,while, in parallel, a SEARCH algorithm opportunistically checks if thetarget can be reached. The EXPLORE algorithm works by placinglandmarks in the search space in such a way that a path from theinitial position to any landmark is known. In order to learn as muchas possible about the free space the EXPLORE algorithm tries to spreadthe landmarks all over this space. To do so, it tries to put thelandmarks as far as possible from one another. For each new landmarkproduced by the EXPLORE algorithm, the SEARCH algorithm checks with alocal method if the target may be reached from that landmark. TheARIADNE'S CLEW algorithm is fast in most cases, in addition, it is acomplete planner which will find a path if one exists. The resolution at which the space is scanned and the time spend to doso, automatically adapts to the difficulty of the problem. Both theEXPLORE and the SEARCH algorithms are expressed as optimizationproblems.
A massively parallel implementation of our method has been implementedfor a six degree-of-freedom arm in a parallel machine (The Mega-Node). In our experimental setup two robots are used. The first robot namedMOBILE ROBOT is under the control of the Mega-Node running theparallel implementation of the Ariadne's Clew algorithm. The secondrobot named OBSTACLE ROBOT is used as a dynamical obstacle: it iscontrolled by our robot simulation package ACT which generates randommoves in order to disturb the MOBILE ROBOT.
First we use our robot simulation package ACT to describe the scenewith the two robots. We place the static obstacles giving an initialposition for the OBSTACLE ROBOT. Then, we compile automatically this representation into a special one which is downloaded into the Mega Node. A final positionis then specified to the MOBILE ROBOT, the Mega-node quickly (2 seconds)produces a plan which assumes that the OBSTACLE ROBOT is standing still.When the position of the OBSTACLE ROBOT changes under the control ofACT the MOBILE ROBOT stops and the Mega-Node (re)computes anotherpath using the new position of the OBSTACLE ROBOT. This loop continuesuntil the MOBILE ROBOT has reached the specified final position. Atthis moment, a new goal can be specified.