On the Benefit of Sub-optimality within the Divide-and-Evolve Scheme

摘要

Divide-and-Evolve (DaE) is an original "memeticization" of Evolutionary Computation and Artificial Intelligence Planning. DaE optimizes either the number of actions, or the total cost of actions, or the total makespan, by generating ordered sequences of intermediate goals via artificial evolution, and calling an external planner to solve each subproblem in turn. DaE can theoretically use any embedded planner. However, since the introduction of this approach only one embedded planner had been used: the temporal optimal planner CPT. In this paper, we propose a new version of DaE, using time-based Atom Choice and embarking the sub-optimal planner YAHSP in order to test the robustness of the approach and to evaluate the impact of using a sub-optimal planner rather than an optimal one, depending on the type of planning problem.