Search-Based Planning and Replanning in Robotics and Autonomous Systems

In this chapter, we present one of the most crucial branches in motion planning: search-based planning and replanning algorithms. This research branch involves two key points: first, representing traverse environment information as discrete graph form, in particular, occupancy grid cost map at arbitrary resolution, and, second, path planning algorithms calculate paths on these graphs from start to goal by propagating cost associated with each vertex in graph. The chapter will guide researcher through the foundation of motion planning concept, the history of search-based path planning and then focus on the evolution of state-of-the-art incremental, heuristic, anytime algorithm families that are currently applied on practical robot rover. The comparison experiment between algorithm families is demonstrated in terms of performance and optimality. The future of search-based path planning and motion planning in general is also discussed