Planification heuristique avec les processus de décision markovien et création d'un environnement de programmation

Abstract

Dans ce mémoire, nous présentons un environnement de programmation nommé JIP pour «Java Intelligent Planning» et l’implémentation de l’algorithme LAO* que nous avons appelé LAOPlan. LAO* est un algorithme de planification conçu pour supporter la recherche guidée par heuristique dans un graphe non déterministe possédant des cycles. Ce mémoire explique le fonctionnement de LAO* et présente des tests de performance faits avec LAOPlan en le comparant au planificateur non déterministe et non probabiliste MBP. Nous exposons aussi des extensions intéressantes à intégrer dans JIP ou LAOPlan. Dans ce cadre, nous expliquons l’algorithme A2Ways qui est un algorithme bidirectionnel de recherche guidé par heuristique dans un graphe déterministe. Nous exposons aussi le concept de LAOBack qui est un LAO* par l’arrière, ce qui permettrait de créer un LAO* bidirectionnel.