(1) An Evolutionary Metaheuristic for Domain-Independent Satisficing Planning (2) Jacques Bibai, Projet TAO, INRIA Saclay île-de France & LRI, Bât 490 Université Paris-Sud 11, 91405 Orsay Cedex France. Jacques.bibai@inria.fr, +33 (0)1 69 41 56 82 Pierre Savéant, Thales Research & Technology France, Campus Polytechnique, 1,avenue Augustin Fresnel, 91767 Palaiseau cedex France. Pierre.saveant@thalesgroup.com, +33 (0) 1 69 41 56 95 Marc Schoenauer, Projet TAO, INRIA Saclay île-de-France & LRI, Bât 490 Université Paris-Sud 11, 91405 Orsay Cedex France. Marc.schoenauer@inria.fr, +33 (0)1 69 15 66 26 Vincent Vidal, ONERA — DCSD, 2, avenue Edouard Belin, BP 74025, 31055 Toulouse Cedex 4, France. Vincent.vidal@onera.fr, +33 (0)5 62 25 27 74 (3) Jacques Bibai, Jacques.bibai@inria.fr (4) DAEX is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DAEX 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, DAEYAHSP is compared to the best planner for each type of domain. Results show that DAEYAHSP performs very well both on coverage and quality metrics. It is particularly noticeable that DAEX improves a lot on plan quality when compared to YAHSP, which is known to provide largely suboptimal 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. (5) B - The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. D - The result is publishable in its own right as a new scientific result ¾ independent of the fact that the result was mechanically created. E - The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. G - The result solves a problem of indisputable difficulty in its field. (6) We have built the Divide-and-Evolve planning system. Divide-and-Evolve is a sequential Hybridization Strategy using Evolutionary Algorithms designed to improve the quality of the plan and the scalability of an encapsulated planning system. It optimizes either the number of actions (for classical STRIPS problems), the total cost of actions (for domains where the actions have costs), or the makespan (for temporal domains), by generating ordered sequences of intermediate goals via artificial evolution. It does this by calling an external planner to solve each sub problem in turn. The last results, published in the premier forum for researchers and practitioners in planning and scheduling, the ICAPS 2010 conference (International Conference on Automated Planning and Scheduling, Toronto, May 2010), showed that it is competitive with state-of-the-art planners even when it uses a universal parameter setting common to all domains. The paper at GECCO further demonstrates that tuning the parameters of the algorithms anew for each instance enhances those results even more. (7) Bibai, J. , Savéant, P. , Schoenauer, M. and Vidal, V.. An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning. In Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS 2010) , Edited by Ronen Brafman, Héctor Geffner, Jörg Hoffmann and Henry Kautz, pages 18—25, Toronto, Ontario, Canada, May 12–16, 2010. Published by The AAAI Press, Menlo Park, California. (8) Any prize money, if any, is to be divided equally among the co-authors (9) The current version of Divide-and-Evolve planner (DAE) is an outstanding satisficing planner for the following reasons. a. DAE is the only planner whose results are at least as good as those of its state-of-the-art (man-made) competitors on all three types of problems, classical, cost and temporal. All man-made planner are specialized on a particular type of problems, while the flexibility of Evolutionary Algorithms allows DAE to be excellent on all 3 types. b. DAE obtains the best overall results on temporal planning problems. c. DAE improves a lot the average quality of solutions of the non optimal embedded planner (YAHSP) for all types of planning problems. d. DAE provides solutions that are equal or very close to the optimal (when known) or best-so-far solutions: more than 90% in quality according to the quality measure defined for the International Planning Competition.