Precomputed-Direction Heuristics for Suboptimal Grid-Based Path-finding

Authors

  • Álvaro Parra Universidad Carlos III de Madrid
  • Álvaro Torralba Universidad Carlos III de Madrid
  • Carlos Linares López Universidad Carlos III de Madrid

DOI:

https://doi.org/10.1609/socs.v3i1.18252

Keywords:

Path Planning, Heuristics

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.

SoCS 2012 Proceedings Cover

Downloads

Published

2021-08-20

How to Cite

Parra, Álvaro, Torralba, Álvaro, & Linares López, C. (2021). Precomputed-Direction Heuristics for Suboptimal Grid-Based Path-finding. Proceedings of the International Symposium on Combinatorial Search, 3(1), 211–212. https://doi.org/10.1609/socs.v3i1.18252

Issue

Vol. 3 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Section

Grid-Based Path Planning Competition