4: Path Planning

Path-planning is an important primitive for autonomous mobile robots that lets robots find the shortest—or otherwise optimal— path between two points. Optimal paths could be paths that minimize the amount of turning, the amount of braking or whatever a specific application requires. Algorithms to find a shortest path are important not only in robotics, but also in network routing, video games and understanding protein folding.

Path-planning requires a map of the environment and the robot to be aware of its location with respect to the map. We will assume for now that the robot is able to localize itself, is equipped with a map, and capable of avoiding temporary obstacles on its way. How to create a map, how to localize a robot, and how to deal with uncertain position information will be major foci of the reminder of this book. The goals of this chapter are to

• introduce suitable map representations,
• explain basic path-planning algorithms ranging from Dijkstra, to A*, D* and RRT,
• introduce variations of the path-planning problem, such as coverage path planning.

---