Using Domain-Configurable Search Control for Probabilistic Planning

AAAI Conferences

We describe how to improve the performance of MDP planning algorithms by modifying them to use the search-control mechanisms of planners such as TLPlan, SHOP2, and TALplanner. In our experiments, modified versions of RTDP, LRTDP, and Value Iteration were exponentially faster than the original algorithms. On the largest problems the original algorithms could solve, the modified ones were about 10,000 times faster. On another set of problems whose state spaces were more than 14,000 times larger than the original algorithms could solve, the modified algorithms took only about 1/3 second.


A Comparison of Greedy Search Algorithms

AAAI Conferences

We discuss the relationships between three approaches to greedy heuristic search: best-first, hill-climbing, and beam search. We consider the design decisions within each family and point out their oft-overlooked similarities.


Using Memory to Transform Search on the Planning Graph

AAAI Conferences

The Graphplan algorithm for generating optimal make-span plans containing parallel sets of actions remains one of the most effective ways to generate such plans. However, despite enhancements on a range of fronts, the approach is currently dominated in terms of speed, by state space planners that employ distance-based heuristics to quickly generate serial plans. We report on a family of strategies that employ available memory to construct a search trace so as to learn from various aspects of Graphplan's iterative search episodes in order to expedite search in subsequent episodes. The planning approaches can be partitioned into two classes according to the type and extent of search experience captured in the trace. The planners using the more aggressive tracing method are able to avoid much of Graphplan's redundant search effort, while planners in the second class trade off this aspect in favor of a much higher degree of freedom than Graphplan in traversing the space of'states' generated during regression search on the planning graph. The tactic favored by the second approach, exploiting the search trace to transform the depth-first, IDA* nature of Graphplan's search into an iterative state space view, is shown to be the more powerful. We demonstrate that distance-based, state space heuristics can be adapted to informed traversal of the search trace used by the second class of planners and develop an augmentation targeted specifically at planning graph search. Guided by such a heuristic, the step-optimal version of the planner in this class clearly dominates even a highly enhanced version of Graphplan. By adopting beam search on the search trace we then show that virtually optimal parallel plans can be generated at speeds quite competitive with a modern heuristic state space planner.


Using Memory to Transform Search on the Planning Graph

Journal of Artificial Intelligence Research

The Graphplan algorithm for generating optimal make-span plans containing parallel sets of actions remainsone of the most effective ways to generate such plans. However, despite enhancements ona range of fronts, the approach is currently dominated in terms of speed, by state space planners that employ distance-based heuristics to quickly generate serial plans. We report on a family ofstrategies that employ available memory to construct a search trace so as to learn from various aspects of Graphplan's iterative search episodes in order to expedite search in subsequent episodes. The planning approaches can be partitioned into two classes according to the type and extent of search experience captured in the trace. The planners using the more aggressive tracing method are able to avoid much of Graphplan's redundant search effort, while planners in the second class trade off this aspect in favor of a much higher degree of freedom than Graphplan in traversing the space of'states' generated during regression search on the planning graph. The tactic favored by the second approach,exploiting the search trace to transform the depth-first, IDA* nature of Graphplan's search into an iterative state space view, is shown to be the more powerful. We demonstrate that distance-based, state space heuristics can be adapted to informed traversal of the search trace used by the second class of planners and develop an augmentation targeted specifically at planning graph search. Guided by such a heuristic, the step-optimal version of the planner in this class clearly dominates even a highly enhanced version of Graphplan. By adopting beam search on the search trace we then show that virtually optimal parallel plans can be generated at speeds quite competitive with a modern heuristic state space planner.


The Effect of Planning State Space Topology on Search Performance

AAAI Conferences

The topological characteristics of the state space graph for a planning problem are related to the internal structure of the underlying problem, and can affect the efficiency of planning. We outline a proposed approach for using this knowledge to build a novel type of plan library (which we call a planning backbone) that organizes states hierarchically based on their connectivity.