Exploiting Symmetry in the Planning-Graph via Explanation-Guided Search

Terry Zimmerman and Subbarao Kambhampati, Arizona State University

We present a method for exploting the sym-metry in the planning-graph structure of Graphplan algorithm to improve its backward search. The main insight underlying our method is that due to the inherent symmetry of the planning-graph the backward search conducted at level k + 1 of the graph is es-sentially a replay of the search conducted at the previous level k with certain well-defined extensions. Our method consists of main-taining a pilot explanation structure capturing the failures encountered at previous levels of the search, and using it in an intelligent way to guide the search at the newer levels. The standard EBL and DDB techniques can be employed to control the size of the pilot ex-planation. The technique has been imple-mented in the EGBG system, and we present a preliminary empirical study.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.