Du morcellement de l'espace de recherche en planification d'actions

Other literature type French OPEN
Meiller, Yannick (2003)
  • Subject: Intelligence artificielle | Planification d'actions | Optimisation | Incertitudes | Représentation de l'information | Espace de recherche | TokenPlan | Outils décisionnels | 658

Diverses approches en planification d’actions consistent à produire un plan solution après avoir construit à partir du problème de planification, puis parcouru, un espace de recherche plus ou moins morcelé en sous-espaces. En formalisant cette notion de morcellement de l'espace de recherche, nous montrons que des approches en apparence très différentes ne se distinguent en fait que du morcellement qu’elles mettent en œuvre. Nous montrons aussi que la diversité des morcellements est largement sous-exploitée par les planificateurs actuels, ouvrant ainsi la voie à la conception de nouvelles approches, en créant de nouveaux morcellements de l'espace de recherche. Pour valider expérimentalement notre propos, nous avons développé un planificateur : TokenPlan. Nous avons aussi conçu et expérimenté un nouveau morcellement de l’espace de recherche qui permet d’obtenir une approche hybride entre un algorithme Branch and Bound et un planificateur disjonctif. Various action planning approaches lead to output a solution plan after the building and exploring of a search space that can be more or less split into sub-spaces. Formalizing the idea of such a splitting of the search space, we show that apparently very different approaches only display different ways of splitting their search space. In addition, we show that current planners take advantage of few different ways of splitting the search space in comparison with the vast possibilities. This highlights oppportunities to create new approaches, through the design of new ways of splitting the search space. In order to carry out an experimental validation of our work, we developed a new planner named TokenPlan. We also designed and used a new way of splitting the search space. It makes it possible to take advantage of both a Branch and Bound algorithm and disjunctive planning.
Share - Bookmark