The Ariadne's clew algorithm

We present a new approach to path planning, called the "Ariadne's clew algo rithm" It is designed to find paths in high-dimensional continuous spaces a nd applies to robots with many degrees of freedom in static, as well as dyn amic environments - ones where obstacles may move. The Ariadne's clew algor ithm comprises two sub-algorithms, called SEARCH and EXPLORE, applied in an interleaved manner. EXPLORE builds a representation of the accessible spac e while SEARCH looks for the target. Both are posed as optimization problem s. We describe a real implementation of the algorithm to plan paths for a s ix degrees of freedom arm in a dynamic environment where another six degree s of freedom arm is used as a moving obstacle. Experimental results show th at a path is found in about one second without any pre-processing.