SOLUTION: solution found (length = 9) Time 1: load-truck(obj13,tru1,pos1) Level: 1 Time 1: load-truck(obj12,tru1,pos1) Level: 1 Time 1: load-truck(obj11,tru1,pos1) Level: 1 Time 2: drive-truck(tru1,pos1,apt1,cit1) Level: 1 Time 3: unload-truck(obj12,tru1,apt1) Level: 3 Time 3: fly-airplane(apn1,apt2,apt1) Level: 1 Time 3: unload-truck(obj11,tru1,apt1) Level: 3 Time 4: load-airplane(obj12,apn1,apt1) Level: 4 Time 4: load-airplane(obj11,apn1,apt1) Level: 4 Time 5: load-truck(obj21,tru2,pos2) Level: 1 Time 5: fly-airplane(apn1,apt1,apt2) Level: 2 Time 6: drive-truck(tru2,pos2,apt2,cit2) Level: 1 Time 6: unload-airplane(obj11,apn1,apt2) Level: 6 Time 7: load-truck(obj11,tru2,apt2) Level: 7 Time 7: unload-truck(obj21,tru2,apt2) Level: 3 Time 8: drive-truck(tru2,apt2,pos2,cit2) Level: 2 Time 9: unload-airplane(obj12,apn1,apt2) Level: 6 Time 9: unload-truck(obj13,tru1,apt1) Level: 3 Time 9: unload-truck(obj11,tru2,pos2) Level: 9 Total Number of actions in Plan: 19
(a) AltAltp **Solution**
POST PROCESSED PLAN ... Time: 1 : load-truck(obj13,tru1,pos1)
Time: 1 : load-truck(obj12,tru1,pos1)
Time: 1 : load-truck(obj11,tru1,pos1)
Time: 1 : fly-airplane(apn1,apt2,apt1)
Time: 1 : load-truck(obj21,tru2,pos2)
Time: 2 : drive-truck(tru1,pos1,apt1,cit1) Time: 2 : drive-truck(tru2,pos2,apt2,cit2) Time: 3 : unload-truck(obj12,tru1,apt1) Time: 3 : unload-truck(obj11,tru1,apt1) Time: 3 : unload-truck(obj21,tru2,apt2) Time: 3 : unload-truck(obj13,tru1,apt1)
Time: 4 : load-airplane(obj12,apn1,apt1) Time: 4 : load-airplane(obj11,apn1,apt1)
Time: 5 : fly-airplane(apn1,apt1,apt2)
Time: 6 : unload-airplane(obj11,apn1,apt2)
Time: 6 : unload-airplane(obj12,apn1,apt2) Time: 7 : load-truck(obj11,tru2,apt2) Time: 8 : drive-truck(tru2,apt2,pos2,cit2)
Time: 9 : unload-truck(obj11,tru2,pos2) END OF POST PROCESSING: Actions= 19 Length: 9
(b) AltAltp **plus Post-processing**

Figure 17: Plots showing that AltAltp**solutions cannot be improved anymore by Postprocessing.**

## 4.2 Comparison To Post-Processing Approaches

As we mentioned earlier (see Section 1), one way of producing **parallel plans that has been** studied previously in the literature is to post-process sequential plans (Backstrom, 1998). To compare online parallelization to post-processing, we have **implemented Backstrom (1998)'s** "Minimal De-ordering Algorithm", and used it to post-process **the sequential plans produced**
by AltAlt (running with its default heuristic hAdjSum2M **using a serial planning graph). In**
this section we will compare our online parallelization procedure to this offline method.

The first set of experiments is on the Logistics domain (Bacchus, 2001). The results are shown in Figure 15. As expected, the original AltAlt **has the longest plans since it allows**
only one action per time step. The plot shows that post-processing techniques do help in reducing the makespan of the plans generated by AltAlt**. However, we also notice that**
AltAltp **outputs plans with better makespan than either** AltAlt or AltAlt **followed by postprocessing. This shows that online parallelization is a better approach than post-processing**
sequential plans. Moreover, the plot in Figure 15(b) shows that the time taken by AltAltp is largely comparable to that taken by the other two approaches. In fact, there is not much additional cost overhead in our procedure.

Figure 16 repeats these experiments in the ZenoTravel domain (Long & Fox, 2002). Once again, we see that AltAltp **produces better makespan than post-processing the sequential**
plans of AltAlt**. Notice that this time,** AltAlt **plus post-processing is clearly less efficient**