Title :
On the expected complexity of random path planning
Author :
Lamiraux, F. ; Laumond, J.P.
Author_Institution :
Lab. d´´Autom. et d´´Anal. des Syst., CNRS, Toulouse, France
Abstract :
This paper gives an account of the convergence property of potential field based path planning algorithms that use random motions to escape local minima. Their probabilistic convergence is proved and we provide a finite estimate of the convergence time. The proof is based on the study of Markov chains and diffusion processes
Keywords :
Brownian motion; Markov processes; computational complexity; convergence of numerical methods; matrix algebra; path planning; probability; Brownian motion; Markov chains; convergence time; diffusion processes; local minima; potential field; probabilistic convergence; random path planning; transition matrix; Convergence; Diffusion processes; Laplace equations; Optimization methods; Orbital robotics; Path planning; Performance analysis; Probability density function; Process planning; Random processes;
Conference_Titel :
Robotics and Automation, 1996. Proceedings., 1996 IEEE International Conference on
Conference_Location :
Minneapolis, MN
Print_ISBN :
0-7803-2988-0
DOI :
10.1109/ROBOT.1996.509170
