Plateau-Escaping Macro-Actions

To assess the effect of plateau-escaping macro-actions on planner performance, tests were run across a range of planning domains with macro-actions enabled and disabled. The results of these tests are shown in Figures 7 and 8, illustrating the time taken to find a solution plan and the makespan of the plan found respectively.

Figure 7: CPU time showing the results of planning with and without plateau-escaping macro-actions on a range of domains (from left to right: Airport, Philosophers, Depots, Driverlog, Pipestankage-nontemporal, Satellite, FreeCell, Pipesnotankage-nontemporal).

$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/airport}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/philosophers}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/depots}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/driverlog}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/pipestankage-nontemporal}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/satellite}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/FreeCell}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacros/pipesnotankage-nontemporal}$

Figure 8: Makespan of the solution plans found when planning with and without plateau-escaping macro-actions on a range of domains (from left to right: Airport, Philosophers, Depots, Driverlog, Pipestankage-nontemporal, Satellite, FreeCell, Pipesnotankage-nontemporal).

$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/airport}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/philosophers}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/depots}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/driverlog}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/pipestankage-nontemporal}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/satellite}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/FreeCell}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/macrosvsnomacrosmakespan/pipesnotankage-nontemporal}$

In the Airport domain the time taken to find plans and the makespans of the plans found were almost identical. A strictly better successor can usually be found to each state when using EHC, and it is clear in this domain that the addition of macro-actions from the occasional plateau has not degraded the performance of the planner. The performance of the two configurations deviates at problem 47, where planning with macro-actions was able to find a solution plan but planning without macro-actions was not. Closer inspection of the output from the planner reveals that in this case, some way into EHC search, a plateau is encountered and escaped; in the configuration using macro-actions, this leads to the formation of a macro-action. Later in search, another plateau is encountered. At this point, the earlier macro-action can be used to lead to a strictly better state, from which a solution plan can ultimately be found using EHC. If the macro-action is not available, however, the sequence of actions found to escape the plateau leads to a different exit point, from which a solution plan cannot be found using EHC.

In the Philosophers domain neither the makespans of the plans found nor the coverage differs between the two configurations tested. Using macro-actions, however, leads consistently to improved performance as the plateaux encountered during search require the application of the same action sequence. Consistently, across the problems, searching with macro-actions is faster by a factor of two; and furthermore, the factor is increasing with problem size, suggesting it has better scalability.

In the Depots domain, using macro-actions improves coverage, allowing 18 problems to be solved within the time limit rather than 15. Further, in many cases, the time taken to find a plan is reduced. In one case, problem file 6, planning without macro-actions is able to find a plan where planning with macro-actions cannot. Here, planning without macro-actions is unable to find an exit point from one of the plateaux encountered later in search, and resorts to best-first search. Planning with macro-actions, however, is able to reach a greater number of successor states from the nodes on the plateau and is unable to exhaust the reachable possibilities and terminate EHC search within the 30-minute time limit.

In the Driverlog domain, using macro-actions generally increases the time taken to find plans and has an adverse effect on the makespan. In this domain, macro-actions containing varying-length action sequences consisting of repeated walk or drive actions are inferred. In practice, these are detrimental in two ways: they have a large number of instantiations and dramatically increase the branching factor, reducing performance; and they are only usefully reusable in situations where the prescribed number of walk or drive actions are needed. Despite this, planning with macro-actions is able to find solution plans in 18 of the problems, whereas planning without the macro-actions is only able to solve 17 of the problems. In the problem in question, problem 17, the increased number of successor states visible from the nodes on plateaux due to the presence of macro-actions allows EHC to find a solution plan rather than resorting to best-first search, which would ultimately fail within the time limit set.

In the Pipestankage-nontemporal domain, it is not clear at first whether macro-actions are beneficial or not. The number of problems solved by both configurations is the same, 34, and the impact on makespan appears to be insignificant, improving it in some cases but making it worse in others. However, looking at the harder problems from problem 25 upwards, planning with macro-actions is able to solve 13 rather than 11 problems, suggesting it is able to scale better to larger problems compared to searching without macro-actions.

In the Satellite domain both configurations exhibit similar performance, in terms of both the time taken to find a solution plan and the makespan of the plan found, as the relaxed planning graph heuristic is generally able to provide good search guidance. The exception is problem 36: here, the inference of a macro-action allows search to be completed using EHC rather than resorting to best-first search, reducing the time taken to find a plan.

In the FreeCell domain, macro-actions appear to lead to improved makespans and have negligible impact on the time taken to find solution plans. Intuitively, however, in a strongly directed search space (such as that in FreeCell, where it is possible to move a card from one location to another but often not to move it back) using a non-backtracking search strategy such as EHC should reduce the effectiveness of macro-actions, as the introduction of redundant action steps as part of a macro-action instantiations can lead search towards unpredicted dead-ends. The illustrated results, contradicting this intuition, can be ascribed to the nature of the FreeCell problems used in IPC 3. The problem files all have the four suits of cards, and from problem file 7 upwards have four free cells. The number of cards in each suit and the number of columns are gradually increased from 2 to 13 and 4 to 8 respectively. The effect of this, however, is that all but the hardest problems have a favourable free cells to cards ratio. When macro-actions are used, the impact of needlessly moving a card into a free cell is not significant as there is a generous allocation of free cells compared to the number of cards that might need to be stored there.

To provide a more reasonable test of whether macro-actions are beneficial in the FreeCell domain, twenty full-sized problem instances were generated and tests run to compare the performance of Marvin with and without macro-actions on these problems. The results of these tests can be seen in Figure 9 - clearly, the number of problems solvable within the 30 minute time limit and, generally, the time taken to find a solution plan is improved when macro-actions are not used.

In the Pipesnotankage-nontemporal domain the results obtained do not show a significant advantage or disadvantage to using macro-actions: the planner is faster on some of the problems when using macro-actions, but is slower on others; similarly, the planner produces plans with shorter makespans on some problems when using macro-actions, but longer makespans on others. Two results are obtained when macro-actions are not used that are very close to the 30-minute cut-off. The first of these is solved in around 10 seconds when macro-actions are used; the second can be solved using macro-actions if an extra 5 minutes of CPU time are allowed, or if a slightly faster computer is used.

Overall, it can be seen that the effect of plateau-escaping macro-actions on the execution time of the planner varies depending on the domain in question:

Furthermore, with the exception of the Driverlog and FreeCell domains (where the makespan of solution plans is generally increased when using macro-actions) the use of macro-actions does not significantly affect the makespan.