Precomputed-direction heuristics for suboptimal grid-based path-finding

Álvaro Parra; Álvaro Torralba; Carlos Linares López

Precomputed-direction heuristics for suboptimal grid-based path-finding

Álvaro Parra, Álvaro Torralba, Carlos Linares López

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

Abstract

This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.

Original language	English
Title of host publication	Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012
Number of pages	2
Publisher	AAAI Press
Publication date	2012
Pages	211-212
ISBN (Print)	9781577355847
Publication status	Published - 2012
Externally published	Yes
Event	5th International Symposium on Combinatorial Search, SoCS 2012 - Niagara Falls, ON, Canada Duration: 19 Jul 2012 → 21 Jul 2012

Conference

Conference	5th International Symposium on Combinatorial Search, SoCS 2012
Country/Territory	Canada
City	Niagara Falls, ON
Period	19/07/2012 → 21/07/2012

Series	Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012

Bibliographical note

Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

Cite this

@inproceedings{f4bd7248af7c4c69908f18af2526de06,

title = "Precomputed-direction heuristics for suboptimal grid-based path-finding",

abstract = "This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.",

author = "{\'A}lvaro Parra and {\'A}lvaro Torralba and L{\'o}pez, {Carlos Linares}",

year = "2012",

language = "English",

isbn = "9781577355847",

series = "Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012",

pages = "211--212",

booktitle = "Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012",

publisher = "AAAI Press",

address = "United States",

}

Parra, Á, Torralba, Á & López, CL 2012, Precomputed-direction heuristics for suboptimal grid-based path-finding. in Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012. AAAI Press, Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012, pp. 211-212, 5th International Symposium on Combinatorial Search, SoCS 2012, Niagara Falls, ON, Canada, 19/07/2012.

Precomputed-direction heuristics for suboptimal grid-based path-finding. / Parra, Álvaro; Torralba, Álvaro; López, Carlos Linares.

Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012. AAAI Press, 2012. p. 211-212 (Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - Precomputed-direction heuristics for suboptimal grid-based path-finding

AU - Parra, Álvaro

AU - Torralba, Álvaro

AU - López, Carlos Linares

PY - 2012

Y1 - 2012

N2 - This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.

AB - This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.

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

M3 - Article in proceeding

AN - SCOPUS:84893390260

SN - 9781577355847

T3 - Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012

SP - 211

EP - 212

BT - Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012

PB - AAAI Press

T2 - 5th International Symposium on Combinatorial Search, SoCS 2012

Y2 - 19 July 2012 through 21 July 2012

ER -

Precomputed-direction heuristics for suboptimal grid-based path-finding

Abstract

Conference

Bibliographical note

Other files and links

Fingerprint

Cite this