The Effects of Inferring Macro-Actions

Supporting ADL natively in Marvin allows lifted macro-action schemata to be inferred during search: in the compiled STRIPS domain formulations presented in IPC 4, the actions in the plateau-escaping action sequences have few or no parameters, removing the opportunity to infer parameterised action sequences to use as the basis for macro-actions. Reusable macro-actions can be inferred in STRIPS domains, as in many of the domains discussed in Section 6.1; but the compilation from ADL to STRIPS produces a domain in which the macro-actions cannot, in practice, ever be reused.

To assess the effects of plateau-escaping macro-actions when using the ADL domain formulation, tests were run in the Philosophers, Optical Telegraph and PSR domains using the ADL domain formulation with macro-actions enabled and disabled. Results for the Airport domain are presented in Section 6.1, and results in the other domains will now be discussed.

The plan shown in Figure 16 was produced by Marvin for problem four in the Philosophers domain (before the translation of the macro-actions back into sequences of single-step actions). The first five steps are found easily through guidance from the heuristic; the following eleven are found during a period of exhaustive search which are, upon exiting the plateau, used to form a macro-action, macro-action A. Macro-action B is formed in a similar manner later in the planning process, and is subsequently used to avoid further exhaustive search. In solution plans for problems involving more philosophers, the two macro-actions are used several times: macro-action A is used once for each consecutive pair of philosophers, and macro-action B once for each odd-numbered philosopher (and once for philosopher-0). The graph in Figure 17 shows the performance of Marvin when the macro-actions are not inferred during search compared to that when the macro-actions are inferred; both configurations produce identical solution plans. It can be seen that the performance is consistently improved when the macro-actions are used, as exhaustive plateau search is avoided.

Figure 16: Plan for the Philosophers problem before macro-action expansion.

Figure 17: Time taken to find a solution plan in the Philosophers domain with the STRIPS domain encoding and the ADL domain encoding, with and without macro-actions.

As can be seen in Figure 18, using macro-actions provides improved performance in the PSR domain: 23 rather than 15 problems can be solved, and in the majority of the cases solved by the two configurations, a solution can be found in less time when macro-actions are used.

Figure 18: Time taken to solve problems in the PSR domain with and without macro-actions.

As shown in Figure 19, Marvin is only able to solve a few of the first 10 problems in the promela/optical-telegraph domain. Nonetheless, when macro-actions are enabled, a net of two additional problems can be solved.

Figure 19: Time taken to solve problems in the Optical Telegraph domain with and without macro-actions.