This strategy is backtrack-free due to the fact that the original p.c. plan is correct. All (pre)
conditions of all actions in Ppc are satisfied and thus for any precondition p of an action A, we can always find an action A′that satisfies the three constraints listed above to support p. Moreover, one of the temporal constraints that lead to the consistent ordering between two interfering actions
(logical or resource interference) will always be satisfied because the p.c. plan is consistent and no pair of interfering actions overlap each other in Ppc. Thus, the search is backtrack-free and we are guaranteed to find an o.c. plan due to the existence of one legal dispatch of the final o.c. plan Poc
(which is the starting p.c. plan Ppc). The final o.c. plan is valid because there is a causal-link for every action's precondition, all causal links are safe, no interfering actions can overlap, and all the resource-related (pre)conditions are satisfied. Moreover, this strategy ensures that the orderings on Poc are consistent with the original Ppc. Therefore, because the p.c plan Ppc is one among multiple p.c plans that are consistent with the o.c plan Poc, the makespan of Poc is guaranteed to be equal or better than the makespan of Ppc.

The algorithm discussed in this section is a special case of the partialization problem in metric temporal planning. In our related work (Do & Kambhampati, 2003), we do a systematic study of the general partialization problem and give CSOP (Constraint Satisfaction Optimization Problem)
encodings for solving them. The current algorithm can be seen as a particular greedy variable/value ordering strategy for the CSOP encoding.

## 7. Implementation Of Sapa

The Sapa system with all the techniques described in this paper has been implemented in Java. The implementation includes:
1. The forward chaining algorithm (Section 2).

2. The cost sensitive temporal planning graph and the routines to propagate the cost information and extract the heuristic value from it (Section 3).

3. The routines to extract and adjust the relaxed plan using static mutex and resource information
(Section 4.2).

4. Greedy post-processing routines to convert the p.c. plan into an o.c plan with better makespan and execution flexibility (Section 6).
By default Sapa uses the sum-propagation rule, infinite lookahead termination, resource-adjusted heuristics, and converts the solutions into o.c. plans. Besides the techniques described in this paper, we also wrote a JAVA-based parser for PDDL2.1 Level 3, which is the highest level used in the Third International Planning Competition (IPC3).

To visualize the plans returned by Sapa and the relations between actions in the plan (such as causal links, mutual exclusions, and resource relations), we have developed a Graphical User Interface (GUI)12 for Sapa. Figure 11 and 12 shows the screen shots of the current GUI. It displays the time line of the final plan with each action shown with its actual duration and starting time in the final plan. There are options to display the causal relations between actions (found using the greedy approach discussed in Section 6), and logical and resource mutexes between actions. The specific times at which individual goals are achieved are also displayed.