State Agnostic Planning Graphs and the application to belief-space planning

William Cushing, Daniel Bryce

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states. The naive technique enumerates the graphs individually. This is equivalent to solving an all-pairs shortest path problem by iterating a single-source algorithm over each source. We introduce a structure, the state agnostic planning graph, that directly solves the all-pairs problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in classical planning. The more prominent application of this technique is in belief-space planning, where an optimization results in drastically improved theoretical complexity. Our experimental evaluation quantifies this performance boost, and demonstrates that heuristic belief-space progression planning using our technique is competitive with the state of the art.

Content Area: 16. Planning and Scheduling

Subjects: 1.11 Planning

Submitted: May 10, 2005

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.