Magazine article AI Magazine

ALTALT: Combining Graphplan and Heuristic State Search

Magazine article AI Magazine

ALTALT: Combining Graphplan and Heuristic State Search

Article excerpt

We briefly describe the implementation and evaluation of a novel plan synthesis system, called ALTALT. ALTALT is designed to exploit the complementary strengths of two of the currently popular competing approaches for plan generation: (1) GRAPHPLAN and (2) heuristic state search. It uses the planning graph to derive effective heuristics that are then used to guide heuristic state search. The heuristics derived from the planning graph do a better job of taking the subgoal interactions into account and, as such, are significantly more effective than existing heuristics. ALTALT was implemented on top of two state-of-the-art planning systems: (1) STAN3.0, a GRAPHPLAN-style planner, and (2) HSP-R, a heuristic search planner.

ALTALT^sup 1^ combines the complementary strengths of two of the currently popular competing approaches for plan generation: (1) GRAPHPLAN and (2) heuristic state search. The planner has evolved from the initial version fielded in the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00) planning competition with better default heuristics and rigorous debugging.

Architecture of ALTALT

The high-level architecture of ALTALT is shown in figure 1. The problem specification and the action template description are first fed to a GRAPHPLAN-style planner, which constructs a planning graph for that problem in polynomial time. We use the publicly available STAN implementation (Long and Fox 1999) for this purpose because it provides a highly memoryefficient implementation of a planning graph. This planning graph structure is then fed to a heuristic extractor module that is capable of extracting a variety of effective and admissible heuristics, based on our recent theory (Nguyen and Kambhampati 2000). This heuristic, along with the problem specification, and the set of ground actions in the final action level of the planning graph structure are fed to a regression state search planner. The regression planner code is adapted from HSP-R (Bonet and Geffner 1999) because it provides an optimized state search engine. The crux of controlling the regression search involves providing a heuristic function that can estimate the relative goodness of the states on the fringe of the current search tree and guide the search in most promising directions. Such heuristics can be tricky to develop. The main problem consists of taking interactions into account. Fortunately, our recent work (Nguyen and Kambhampati 2000) provides an interesting way of leveraging the GRAPHPLAN technology to generate effective heuristics. In the next section, we briefly introduce the default heuristic in ALTALT.

Default Heuristic in ALTALT

To guide a regression search in the state space, a heuristic function needs to evaluate the cost of some set S of subgoals, comprising a regression state from the initial state, in terms of the number of actions required to achieve S from the initial state. One of the best heuristics according to our analysis in Nguyen and Kambhampati (2000) is called hAdjSum2M We adopted this heuristic as the default heuristic in ALTALT. The basic idea of hAdjSu2M is to calculate an adjusted sum value, taking positive and negative interactions into account. This heuristic approximates the cost of a set S as the length of a "relaxed plan" for supporting S, ignoring all the mutex relations, plus the penalty for ignoring these negative interactions. For a more detailed explanation on this heuristic, see our recent work (Nguyen and Kambhampati 2000; Nguyen, Kambhampati, and Nigenda 2000). …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.