An AI planning problem is defined by
  • a set of boolean atoms, instantiated predicates that define all possible states of a system
  • a set of actions, with, for each action, the atoms that are required for the action to be triggered, and the consequences of triggering the action on the state of the system (some atoms change their values)
  • an initial and a goal state of the system
A plan is a sequence of actions, and a feasible plan is a plan that, if all actions are executed in turn from the initial state, will put the system in the goal state.

The goal of AI planning is to find the optimal feasible plan with respect to some criterion, that define the type of the planning problem: "STRIP problems" aim at minimising the number of actions in the plan, and the prototype of planning problem is the so-called "block world" where the system is a set of cubes that can be stacked, the actions are movements of one cube (that can be stacked or unstacked from any other cube), and the goal and the final states are particular configurations of the cubes. When the actions can have different costs, the problem is referred to as a "cost problems". When all actions have a duration, and several actions can be executed in parallel, the problem pertains to "temporal planning".

DaE works by transforming an AI planning problem into a sequence of (hopefully) simpler problems. It embeds a classical planner, and uses it to solve each sub-problem of the sequence in turn, the initial state of problem i+1 being the final state after solving problem i.
The evolutionary algorithm is responsible for finding the sequence of intermediate states, and the embedded planner for solving the corresponding planning problems.

DaE has demonstrated that it can solve (i.e. find feasible plans) more problems than the embedded planner, and of better quality, in particular when embedding an exact planner (exact planners rapidly fail to solve problems as their size increases): this was demonstrated using the constraint-based planner CPT(external link).

More interestingly (and this was the reason for the Silver Humies), when embedding a satisficing planner like YAHSP(external link), DaE performed well against the state-of-the-art planners: it is the only planner that competes with the best known results in all 3 categories (STRIP, cost and temporal problems), as reported in the paper describing DaE published at ICAPS 2010 conference(external link) (International Conference on Automated Planning and Scheduling). Furthermore, the most recent version of DaE-YAHSP won Deterministic Temporal Satisficing track(external link) at the the Seventh International Planning Competition in 2011.