Handling Derived Predicates

It is possible to reason with domains involving derived predicates by precompiling the domain, adding additional actions to support the derived predicates, and then planning in the usual manner (see Section 5). The necessary compilation, however, causes a large increase in the size of the domain. If the planner performs the compilation itself, generating the confirm actions and segregating them from the normal actions internally, it can avoid the search overhead the compiled domain would incur.

Three IPC 4 domains make use of derived predicates: PSR (Power Supply Restoration), Philosophers and Optical Telegraph. To assess the impact the native support of derived predicates was having on planner performance, tests were run in these domains using the original domains containing derived predicates, and using the compiled domains. The results of these tests are shown in Figures 1314 and 15.

In the PSR domain, the support of derived predicates substantially reduces the time taken to find solution plans. This improvement in efficiency allows 23 rather than 12 problems to be solved within the 30 minute time limit.

Marvin is only able to solve a few of the problems in the promela/optical-telegraph domain. On the smaller problems, the performance is better without derived predicates; nonetheless, two of the larger problems (problems 8 and 9) can be solved when working with the original domain where previously they could not, and overall one additional problem is solved with derived predicates.

In the Philosophers domain, supporting derived predicates natively yields substantial reductions in planning time. Using the compiled ADL domain formulation, only the first nine problems can be solved. With native derived predicate support, all 48 problems can be solved.

Figure 13: Time taken to solve problems in the PSR domain with and without Derived Predicates.

Figure 14: Time taken to solve problems in the Optical Telegraph domain with and without Derived Predicates.

Figure 15: Time taken to solve problems in the Philosophers Domain with and without Derived Predicates.
Image newdp-phil

Andrew Coles and Amanda Smith 2007-01-09