Loading...
 

DESCARWIN (ANR-09-COSI-002)

DESCARWIN, the marriage of Descartes (for the Divide-and-Conquer strategy) and Darwin (for Artificial Evolution), falls into the “Design and Optimization” axis within the basic research category of the ANR 2009 COSINUS Programme.

Planning, as the search for the optimal sequence of actions to reach a set of goals, is ubiquitous in the fields involving critical systems: security (crisis management, surveillance), air traffic management, space missions, industry (supply chain management, logistics and planning), transportation (traffic optimization). This class of problems is usually hard to model and to solve due to the intricacy of constraints and the difficulty of finding the best solutions when multiple objectives are conflicting. For more than 20 years, the research in Automated Planning and Scheduling has provided mathematical models, description languages and algorithms to solve these kinds of problems. Nevertheless, most of domain-independent solvers have put an emphasis on runtime rather than on plan quality and usually consider single-objective problems.
The starting point for DESCARWIN is a stochastic method for planning decomposition, called Divide-and-Evolve, that was introduced recently and which focuses on plan quality. The basic principle is to search the space of state decompositions of the planning problem at hand by means of artificial evolution: candidate solutions are sequences of intermediate goals which define consecutive planning subproblems that are hopefully easier to solve than the global problem. The scope of Divide-and-Evolve is temporal planning as defined by PDDL2.1 (the widely adopted planning domain description language standard) where the problems are described using durative actions and where plan quality is the total makespan.
The objectives of DESCARWIN are:
  1. to refine and validate the Divide-and-Evolve method w.r.t. state-of-the art planners,
  2. to extend the scope with features required by real-world planning problems.

Image


Links