Hierarchical path planning for multi-size agents in heterogeneous environments

Daniel Harabor, Adi Botea

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

28 Citations (Scopus)

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 gridmap.

Original languageEnglish
Title of host publication2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008
Pages258-265
Number of pages8
DOIs
Publication statusPublished - 1 Dec 2008
Externally publishedYes
Event2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008 - Perth, WA, Australia
Duration: 15 Dec 200818 Dec 2008

Conference

Conference2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008
CountryAustralia
CityPerth, WA
Period15/12/0818/12/08

Cite this