Planification d'actions en environnement incertain : une approche fondee sur la theorie des possibilites

La plupart des travaux existants dans le domaine de la planification sous incertitude utilise la theorie des probabilites. Cependant, un obstacle majeur est rencontre lorsqu'on ne dispose que de donnees qualitatives et pas d'un modele probabiliste permettant de decrire les aspects incertains du probleme de planification a resoudre. L'approche developpee au cours de cette these repose sur la theorie des possibilites et constitue une reponse a ce type de probleme. Nous avons tout d'abord defini un cadre formel de representation permettant de decrire l'incertitude possibiliste sur l'effet des actions et sur l'etat initial. Cela a aboutit a la construction d'un formalisme pour la planification possibiliste inspire de celui developpe par kusmerick et al. Pour le planificateur probabiliste buridan. Dans un deuxieme temps, nous avons developpe et implemente un algorithme qui permet de generer, sous l'hypothese de non-observabilite a l'execution, un plan solution dont la necessite qu'il satisfasse l'objectif est superieure a un seuil. Cet algorithme est base sur un resultat important qui montre que la resolution d'un probleme de planification possibiliste peut se ramener a la resolution d'un probleme de planification non-deterministe dans lequel les actions ont plusieurs effets possibles mais non differencies. Nous avons ensuite etendu la notion de plan solution afin de pouvoir discriminer entre plusieurs plans de meme necessite. Deux solutions ont alors ete proposees. La premiere concerne le cas ou tous les plans solutions ont une necessite nulle. Dans ce cas nous avons propose une methode qui consiste a primer le plan ayant la plus grande mesure de possibilite d'atteindre un etat but. Le deuxieme cas est celui dans lequel il existe plusieurs plans solutions de meme necessite non nulle. On utilise alors une methode de choix basee sur un critere lexicographique qui exploite l'incertitude sur le changement d'etat cause par chaque action du plan. Enfin, nous avons etendu la notion d'objectif afin de rendre possible la prise en compte de la flexibilite. Pour cela, nous avons associe des degres d'importance aux litteraux representant le but et des degres de faisabilite aux actions, ce qui nous permet d'evaluer, de facon graduelle, le niveau de satisfaction d'un plan. Parallelement, l'exploitation d'utilites additives sur les actions a ete consideree.