State Queue: SQ={S**init**}
while SQ6={}
S:= *Dequeue*(SQ)
Nondeterministically select A applicable in S
/* A can be advance-time action */
S' := *Apply*(A,S)
if S' satisfies G **then** *PrintSolution* else *Enqueue(S'*,SQ)
end while; Figure 3: Main search algorithm applying this action, the state S gets updated according to all the events in the event queue that are scheduled to occur at te. Note that we can apply multiple non-interfering actions at a given time point before applying the special advance-time action. This allows for concurrency in the final plan.

Search algorithm: The basic algorithm for searching in the space of time stamped states is shown in Figure 3. We proceed by applying each applicable action to the current state and put each resulting state into the sorted queue using the **Enqueue**() function. The **Dequeue**() function is used to take out the first state from the state queue. Currently, Sapa employs the A* search. Thus, the state queue is sorted according to some heuristic function that measures the difficulty of reaching the goals from the current state. Next several sections of the paper discuss the design of these heuristic functions.

Example: To illustrate how different data structures in the search state S = (P, M, Π**, Q, t**) are maintained during search, we will use a (simpler) variation of our ongoing example introduced at the end of Section 2.1. In this variation, we eliminate the route from Tucson to Los Angeles (LA) going through Las Vegas. Moreover, we assume that there are too many students to fit into one car and they had to be divided into two groups. The first group rents the first car, goes to Phoenix (Phx),
and then flies to LA. The second group rents the second car and drives directly to LA. Because the trip from Tucson to LA is very long, the second car needs to be refueled before driving. To further make the problem simpler, we eliminate the boarding/un-boarding actions and assume that the students will reach a certain place (e.g. Phoenix) when their means of transportation (e.g. Car1) arrives there. Figure 4 shows graphically the plan and how the search state S's components change as we go forward. In this example, we assume the ref uel(car) action refuels each car to a maximum of 20 gallons. Drive(**car, T ucson, P hoenix**) takes 8 gallons of gas and Drive(**car, T ucson, LA**)
takes 16 gallons. Note that, at time point t1, event e1 increases the fuel level of car2 to 20 gallons.

However, the immediately following application of action A3 reduces f uel(car2) back to the lower level of 4 gallons.

## 3. Propagating Time-Sensitive Cost Functions In A Temporal Planning Graph

In this section, we discuss the issue of deriving heuristics, that are sensitive to both time and cost, to guide Sapa's search algorithm. An important challenge in finding heuristics to support multiobjective search, as illustrated by the example below, is that the cost and temporal aspects of a plan are often inter-dependent. Therefore, in this section, we introduce the approach of tracking the