Subgoal Graphs for Eight-Neighbor Gridworlds

Authors

  • Tansel Uras University of Southern California
  • Sven Koenig University of Southern California
  • Carlos Hernandez University  Catolica de la Ssma, Concepcion

DOI:

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

Keywords:

Search, Gridworlds, Subgoals

Abstract

We propose a method for preprocessing an eight-neighbor gridworld to generate a subgoal graph and a method for using this subgoal graph to find shortest paths faster than A*, by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the high-level path.

SoCS 2012 Proceedings Cover

Downloads

Published

2021-08-20

How to Cite

Uras, T., Koenig, S., & Hernandez, C. (2021). Subgoal Graphs for Eight-Neighbor Gridworlds. Proceedings of the International Symposium on Combinatorial Search, 3(1), 213–214. https://doi.org/10.1609/socs.v3i1.18253

Issue

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

Section

Grid-Based Path Planning Competition