Une des principales caractéristiques
des planificateurs optimaux modernes tels Graphplan et Blackbox est
leur capacité d'élaguer de larges parts de l'espace de
recherche. D'un autre côté, les planificateurs plus
anciens effectuant une recherche dans les espaces de plans partiels
offrent des possibilités d'exploration de l'espace de recherche
intéressantes mais ne disposent pas de mécanismes
d'élagage aussi performants.
Une formulation de la planification temporelle
indépendante du domaine basée sur la programmation par
contraintes a été proposée dans [VG04a,VG04b], qui
combine avec succès les possibilités d'exploration de
l'espace de recherche de la planification dans les espaces de plans
partiels avec des règles d'élagage puissantes et saines.
La principale innovation de cette formulation est la capacité de
raisonner autour des supports, des relations de
précédence et des liens causaux, en faisant intervenir
les actions qui n'appartiennent pas encore à un plan partiel.
Un planificateur temporel optimal nommé
CPT, basé sur cette formulation, a été
développé au CRIL, et présenté à la
4ème
compétition internationale de planification (IPC-2004). Il a
été récompensé par un deuxième prix
dans la catégorie planification optimale. Ces résultats
encourageants nous invitent donc à améliorer CPT, avec
comme ligne de mire la prochaine compétition, qui aura lieu en
2006.
Sujet
Lors du développement de CPT, un
effort très important a été dévolu à
la définition de règles d'élagage puissantes. Ces
règles expliquent à elles seules les bonnes performances
actuelles de CTP. Cependant, les aspects "techniques de recherche" on
été négligés pour l'instant : l'algorithme
de recherche est un branch-and-bound des plus basiques, et les
heuristiques pour le choix des points de branchement sont des
variations d'heuristiques simples connues depuis longtemps.
Par ailleurs, de nouvelles
heuristiques de recherche ont été proposées
récemment par [BHLS04] dans le contexte de la programmation par
contraintes. La caractéristique principale de ces heuristiques
est de pouvoir exploiter non seulement l'état courant de la
recherche mais également tous les états passés. En
conséquence, le phénomène dit de
thrashing (le fait de
redécouvrir sans cesse les mêmes impasses lors de la
recherche) peut être évité. Il a même
été montré expérimentalement dans [LBH04]
que ces heuristiques avaient un comportement supérieur aux
techniques de retour-arrière sophistiquées.
L'étude proposée
est l'exploitation de ce type d'heuristiques afin d'améliorer le
comportement de CPT.
Encadrement
Frédéric Boussemart, Christophe Lecoutre, Lakhdar
Saïs, Vincent Vidal.
Références
[VG04a] V. Vidal, H. Geffner,
Branching and Pruning: An Optimal
Temporal POCL Planner based on Constraint Programming, dans
Proceedings of the Nineteenth National Conference on Artificial
Intelligence (AAAI-2004), San José, Californie, 2004, pp.
570-577.
[VG04b] V. Vidal, H. Geffner,
Un planificateur temporel optimal
basé sur la programmation par contraintes, dans Actes des
Dixièmes Journées Nationales sur la résolution de
problèmes NP-Complets (JNPC-2004), Angers, France, 2004, pp.
347-362.
[BHLS04] F. Boussemart, F. Hemery, C. Lecoutre, L. Sais,
Boosting
systematic search by weighting constraints, dans Proceedings of the
16th European Conference on Artificial Intelligence (ECAI-2004),
Valencia, Spain, 2004, pp. 482-486.
[LBH04] C. Lecoutre, F. Boussemart, F. Hemery,
Backjump-based
techniques versus conflict-directed heuristics, dans Proceedings of
the 16th International Conference on Tools with Artificial Intelligence
(ICTAI-2004), Boca Raton, Florida, 2004.