An approach to solving the path planning problem for a mobilerobot operating in an unknown, three dimensional environment containingobstacles of arbitrary shape is presented. The main contributions are ananalysis of the type of sensing information that is necessary andsufficient for solving the path planning problem in such environments,and the development of a framework for designing a provably correctalgorithm to solve this problem. Working from first principles, withoutany assumptions about the environment of the robot or its sensingcapabilities, the analysis shows that the ability to explore theobstacle surfaces (i.e., to make all their points visible) isintrinsically linked to the ability to plan the motion of the robot. Itis argued that current approaches to the path planning problem withincomplete information simply do not extend to the generalthree-dimensional case, and that qualitatively different algorithms areneeded
展开▼
