An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning

摘要

DaE_x is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DaE_x is based on a state decomposition strategy, driven by an evolutionary algorithm, which benefits from the use of a classical planning heuristic to maintain an ordering of atoms within the individuals. The proof of concept is achieved by embedding the domain-independent satisficing YAHSP planner and using the critical path h~1 heuristic. Experiments with the resulting algorithm are performed on a selection of IPC benchmarks from classical, cost-based and temporal domains. Under the experimental conditions of the IPC, and in particular with a universal parameter setting common to all domains, DaEyaiisp is compared to the best planner for each type of domain. Results show that DaEyaiisp performs very well both on coverage and quality metrics. It is particularly noticeable that DaE_x improves a lot on plan quality when compared to YAHSP, which is known to provide largely sub-optimal solutions, making it competitive with state-of-the-art planners. This article gives a full account of the algorithm, reports on the experiments and provides some insights on the algorithm behavior.