Hierarchical path planning for multi-size agents in heterogeneous environments

Daniel Harabor, Adi Botea

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

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

Harabor, D., & Botea, A. (2008). Hierarchical path planning for multi-size agents in heterogeneous environments. In 2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008 (pp. 258-265). [5035648] https://doi.org/10.1109/CIG.2008.5035648
Harabor, Daniel ; Botea, Adi. / Hierarchical path planning for multi-size agents in heterogeneous environments. 2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008. 2008. pp. 258-265
@inproceedings{9ba5f673daf443a48d517a1eba6fdf85,
title = "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 gridmap.",
author = "Daniel Harabor and Adi Botea",
year = "2008",
month = "12",
day = "1",
doi = "10.1109/CIG.2008.5035648",
language = "English",
isbn = "9781424429745",
pages = "258--265",
booktitle = "2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008",

}

Harabor, D & Botea, A 2008, Hierarchical path planning for multi-size agents in heterogeneous environments. in 2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008., 5035648, pp. 258-265, 2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008, Perth, WA, Australia, 15/12/08. https://doi.org/10.1109/CIG.2008.5035648

Hierarchical path planning for multi-size agents in heterogeneous environments. / Harabor, Daniel; Botea, Adi.

2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008. 2008. p. 258-265 5035648.

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

TY - GEN

T1 - Hierarchical path planning for multi-size agents in heterogeneous environments

AU - Harabor, Daniel

AU - Botea, Adi

PY - 2008/12/1

Y1 - 2008/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=70349271123&partnerID=8YFLogxK

U2 - 10.1109/CIG.2008.5035648

DO - 10.1109/CIG.2008.5035648

M3 - Conference Paper

SN - 9781424429745

SP - 258

EP - 265

BT - 2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008

ER -

Harabor D, Botea A. Hierarchical path planning for multi-size agents in heterogeneous environments. In 2008 IEEE Symposium on Computational Intelligence and Games, CIG 2008. 2008. p. 258-265. 5035648 https://doi.org/10.1109/CIG.2008.5035648