Mazer, E., Ahuactzin, J.M., and Bessiere, P. (1998) "The Ariadne's Clew Algorithm", Volume 9, pages 295-316.

* PostScript article mazer98a.ps (1.29M)
* Compressed PostScript article mazer98a.ps.Z (288K)
* PDF article mazer98a.pdf (825K)
* Hypertext (HTML) version
* Online appendix1 mazer98a-appendix1.tar (421K) Source code
* Online appendix2 mazer98a-appendix2.tar (12.9M) Quicktime movies

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