Segmentation et évolution pour la planification : le système Divide-And-Evolve
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
An Artificial Intelligence (AI) planning problem is specified by the description of an initial state, a goal state, and a set of possible actions. An action modifies the current state, and can be applied only if certain conditions in the current state are met. A solution to a planning problem is an ordered set of actions, whose execution from the initial state transforms it into a state that includes the goal state. Divide-and-Evolve (D&E) 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, the total cost of actions, or the makespan, 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. This thesis explores in depth for the first time D&E approach and clearly demonstrates his interest. Compared to the results of the best specialized planners, the results of our work are competitives and D&E became the first evolutionary hybrid planner equal or better than the best planner in all types of problems. Our work was awarded a silver medal at ACM GECCO-2010 Humies Awards, a first in France and in the world of planning.
Abstract FR:
Un problème de planification (ou raisonnement artificiel) est défini par une situation (ou état) initiale I et une situation finale, ou but B, du système, ainsi que par la liste d’actions possibles (ou connaissances expertes de la situation), avec pour chacune les conditions nécessaires à leur application, éventuellement leur durée (ou coût), et leur effet sur l'état du système. Une solution au problème est une suite d'actions qui amène de la situation initiale au but en un minimum de temps (ou de coûts et ou d’actions). L’approche Divide-and-Evolve (D&E) tente de diminuer la complexité d'un problème de planification en définissant une série de situations E0=I, E1,. . . , En=B, et en résolvant successivement les sous-problèmes (Ei, Ei+1), dont on espère qu'ils sont plus simples à résoudre que le problème global (I,B). La solution du problème initial est alors la concaténation des solutions des sous-problèmes. La suite d'états E1,. . . , En-1 est optimisée par un algorithme évolutionnaire, chaque sous-problème étant résolu par un planificateur « embarqué ». Cette thèse étudie pour la première fois en profondeur l’approche D&E et démontre clairement son intérêt. Comparés aux résultats des meilleurs planificateurs spécialisés, les résultats de nos travaux rivalisent très favorablement et D&E devient ainsi le tout premier planificateur évolutionnaire hybride capable d’atteindre ou de surpasser les meilleurs actuels pour tous les types de problèmes. L’ensemble de nos travaux a été récompensé par une médaille d’argent aux ACM-GECCO 2010 Humies awards, une première en France, et dans le monde de la planification.