Hierarchical path planning for multi-size agents in heterogeneous environments

Abstract

Path planning is a central topic in games and other research areas, such as robotics. Despite this, very little research addresses problems involving agents with multiple sizes and terrain traversal capabilities. In this paper we present a new planner, Hierarchical Annotated A* (HAA*), and demonstrate how a single abstract graph can be used to plan for agents with heterogeneous sizes and terrain traversal capabilities. Through theoretical analysis and experimental evaluation we show that HAA* is able to generate near-optimal solutions to a wide range of problems while maintaining an exponential reduction in effort over low-level search. HAA* is also shown to require just a fraction of the storage space needed by the original grid map.