ABSTRACT
A key trait of an autonomous robot is the ability to plan its own motion in order to accomplish specified tasks. Often, the objective of motion planning is to change the state of the world by computing a sequence of admissible motions for the robot. In path planning, people are given a complete description of the geometry of a robot and a static environment populated with obstacles. An important consideration for path planning algorithms is completeness. A path planning algorithm is complete, if it finds a path whenever one exists and reports none exists otherwise. The configuration of a robot is a set of parameters that uniquely determine the position of every point in the robot. The cell decomposition approach first divides a robot’s free space into simple, canonical regions called cells. In general, path planning algorithms based on random sampling cannot detect whether any path exists.
