Any‐Angle Path Planning
Abstract
In robotics and video games, one often discretizes continuous terrain into a grid with blocked and unblocked grid cells and then uses a path‐planning algorithms to find a shortest path on the resulting grid graph. This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path‐planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Any‐angle path‐planning algorithms are variants of the heuristic path‐planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 01, 2013
- Source ID
- 10.1609/aimag.v34i4.2512
Entities
People
- Alex Nash
- Sven Koenig
Organizations
- Army Research Office
- National Science Foundation
- Office of Naval Research