We have presented a forward search heuristic planner called Marvin, which introduces several modifications to the search strategy of FF. These are:
- The use of learned macro-actions for escaping plateaux.
- A least-bad-first search strategy for search on plateaux.
- A greedy best-first search strategy when EHC fails.
- The addition of native support for both ADL and derived predicates, without relying on a domain preprocessor.
Results presented indicate that the effects of these modifications varies depending on the domain with which the planner is presented, but can be summarised as:
- The inference and use of plateau-escaping macro-actions:
- Provides improved performance in the Philosophers, Depots, Driverlog and Pipestankage-nontemporal domains, in terms of planner execution time.
- Although performance did not improve in the other domains, it did not significantly degrade, with the exception of FreeCell.
- The makespan of the plans found in the majority of domains was not degraded by the use of macro-actions.
- The use of least-bad-first search:
- Provides substantial improvements in planner performance in the Philosophers domain.
- Reduces planner execution time in the Satellite, Driverlog and Pipestankage-nontemporal domains, sometimes at the expense of increased solution plan makespans.
- Provides worse performance in the FreeCell and Pipesnotankage-nontemporal domains.
- Greedy best-first search does not perform significantly differently from best-first search in the evaluation domains considered.
- Other than in the Airport domain, where no difference in performance is observed, the native support for derived predicates and ADL improves the performance of the planner; either by allowing a more-compact higher-level domain formulation to be used, or by improving the effectiveness of the macro-actions inferred.
Andrew Coles and Amanda Smith