Exploiting Path Refinement Abstraction in Domain Transition Graphs

Authors

  • Peter Gregory University of Strathclyde
  • Derek Long University of Strathclyde
  • Craig McNulty University of Strathclyde
  • Susan Murphy University of Strathclyde

DOI:

https://doi.org/10.1609/aaai.v25i1.8012

Abstract

Partial Refinement A-Star (PRA* is an abstraction technique, based on clustering nearby nodes in graphs, useful in large path-planning problems. Abstracting the underlying graph yields a simpler problem whose solution can be used, by refinement, as a guide to a solution to the original problem. A fruitful way to view domain independent planning problems is as a collection of multi-valued variables that must perform synchronised transitions through graphs of possible values, where the edges are defined by the domain actions. Planning involves finding efficient paths through Domain Transition Graphs (DTGs). In problems where these graphs are large, planning can be prohibitively expensive. In this paper we explore two ways to exploit PRA* in DTGs.

Downloads

Published

2011-08-04

How to Cite

Gregory, P., Long, D., McNulty, C., & Murphy, S. (2011). Exploiting Path Refinement Abstraction in Domain Transition Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 971-976. https://doi.org/10.1609/aaai.v25i1.8012

Issue

Vol. 25 No. 1 (2011): Twenty-Fifth AAAI Conference on Artificial Intelligence

Section

Reasoning about Plans, Processes and Actions