Le fil d'ariane : une méthode de planification générale. Application à la planification automatique de trajectoires

Abstract

The ultimate goal of a path planner is to find a path in the configuration<br />space from the initial position to the target. However, while<br />searching for this path, an interesting sub-goal to consider may be to<br />try to collect information about the free space and about the<br />possible paths to go about in that space. The ARIADNE'S CLEW algorithm<br />tries to do both at the same time. An EXPLORE algorithm collects<br />information about the free space with an increasingly fine resolution,<br />while, in parallel, a SEARCH algorithm opportunistically checks if the<br />target can be reached. The EXPLORE algorithm works by placing<br />landmarks in the search space in such a way that a path from the<br />initial position to any landmark is known. In order to learn as much<br />as possible about the free space the EXPLORE algorithm tries to spread<br />the landmarks all over this space. To do so, it tries to put the<br />landmarks as far as possible from one another. For each new landmark<br />produced by the EXPLORE algorithm, the SEARCH algorithm checks with a<br />local method if the target may be reached from that landmark. The<br />ARIADNE'S CLEW algorithm is fast in most cases, in addition, it is a<br />complete planner which will find a path if one exists. <br />The resolution at which the space is scanned and the time spend to do<br />so, automatically adapts to the difficulty of the problem. Both the<br />EXPLORE and the SEARCH algorithms are expressed as optimization<br />problems. <br />A massively parallel implementation of our method has been implemented<br />for a six degree-of-freedom arm in a parallel machine (The Mega-Node)<br />. In our experimental setup two robots are used. The first robot named<br />MOBILE ROBOT is under the control of the Mega-Node running the<br />parallel implementation of the Ariadne's Clew algorithm. The second<br />robot named OBSTACLE ROBOT is used as a dynamical obstacle: it is<br />controlled by our robot simulation package ACT which generates random<br />moves in order to disturb the MOBILE ROBOT.<br />First we use our robot simulation package ACT to describe the scene<br />with the two robots. We place the static obstacles giving an initial<br />position for the OBSTACLE ROBOT. Then, we compile automatically this representation <br />into a special one which is downloaded into the Mega Node. A final position<br />is then specified to the MOBILE ROBOT, the Mega-node quickly (2 seconds)<br />produces a plan which assumes that the OBSTACLE ROBOT is standing still.<br />When the position of the OBSTACLE ROBOT changes under the control of<br />ACT the MOBILE ROBOT stops and the Mega-Node (re)computes another<br />path using the new position of the OBSTACLE ROBOT. This loop continues<br />until the MOBILE ROBOT has reached the specified final position. At<br />this moment, a new goal can be specified.