A Guide to Heuristic-based Path Planning

Dave Ferguson, Maxim Likhachev and Anthony Stentz

School of Computer Science, Carnegie Mellon University



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.


Keywords: planning, search, heuristic search, anytime planning, incremental planning, replanning, anytime replanning