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.

Downloads

Published

2021-08-20

Issue

Section

Grid-Based Path Planning Competition