

![0_image_0.png](0_image_0.png)

parallel plans in AltAltp**. Section 4 presents extensive empirical evaluation of** AltAltp**. The**
evaluation includes both comparison and ablation studies. **Finally, Section 5 discusses some** related work in classical as well as metric temporal planning. Section 6 summarizes our contributions.

## 2. Altalt **Background Architecture And Heuristics**

The AltAlt planning system is based on a combination of Graphplan (Blum **& Furst, 1997;**
Long & Fox, 1999; Kautz & Selman, 1999) and heuristic state space search (Bonet et al.,
1997; Bonet & Geffner, 1999; McDermott, 1999) technology. AltAlt **extracts powerful**
heuristics from a planning graph data structure to guide a regression search in the space of states. 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 (in our case, STAN from Long & Fox, 1999), which constructs a planning graph for that problem in polynomial time (we assume the reader is familiar with the Graphplan algorithm of Blum & Furst, 1997). This planning graph structure is then fed to a **heuristic extractor module**
that is capable of extracting a variety of effective heuristics (Nguyen & Kambhampati, 2000; Nguyen et al., 2002). These heuristics, 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.

To explain the operation of AltAlt **at a more detailed level, we need to provide some**
further background on its various components. We shall start with the regression search module. Regression search is a process of searching in the space of potential plan suffixes. The suffixes are generated by starting with the goal state and regressing it over the set of relevant action instances from the domain. The resulting states are then (nondeterministically) regressed again over relevant action instances, and this process is repeated until we reach a state (set of subgoals) which is satisfied by the initial state. A state S **in our**
framework is a set of (conjunction of) literals that can be seen as "subgoals" that need to be made true on the way to achieving the top level goals. An action instance a **is considered** relevant to a state S if the effects of a give at least one element of S **and do not delete**