A Guide to Heuristic-based Path Planning
Dave Ferguson, Maxim Likhachev and Anthony Stentz
School of Computer Science, Carnegie Mellon University
Abstract
We describe a family of recently developed heuristic-based algorithms used for path planning in the real world. We discuss the fundamental similarities between static algorithms (e.g. A*), replanning algorthmcs (e.g. D*), anytime algorithms (e.g. ARA*), and anytime replanning algorithms (e.g. AD*). We introduce the motivation behind each class of algorithms, discuss their use on real robotic systems, and highlight their practical benefits and disadvantages.