Planification d'actions concurrentes sous contraintes et incertitude

Cette these presente des contributions dans le domaine de la planification en intelligence artificielle, et ce, plus particulierement pour une classe de problemes qui combinent des actions concurrentes (simultanees) et de l'incertitude. Deux formes d'incertitude sont prises en charge, soit sur la duree des actions et sur leurs effets. Cette classe de problemes est motivee par plusieurs applications reelles dont la robotique mobile, les jeux et les systemes d'aide a la decision. Cette classe a notamment ete identifiee par la NASA pour la planification des activites des rovers deployes sur Mars.;Mots-cles: Intelligence artificielle ; planification ; actions concurrentes ; incertitude.;Les algorithmes de planification presentes dans cette these exploitent une nouvelle representation compacte d'etats afin de reduire significativement l'espace de recherche. Des variables aleatoires continues sont utilisees pour modeliser l'incertitude sur le temps. Un reseau bayesien, qui est genere dynamiquement, modelise les dependances entre les variables aleatoires et estime la qualite et la probabilite de succes des plans. Un premier planificateur, ACTUP LANnc base sur un algorithme de recherche a chainage avant, prend en charge des actions ayant des durees probabilistes. Ce dernier genere des plans non conditionnels qui satisfont a une contrainte sur la probabilite de succes souhaitee. Un deuxieme planificateur, ACTUP LAN, fusionne des plans non conditionnels afin de construire des plans conditionnels plus efficaces. Un troisieme planificateur, nomme QUANPLAN, prend egalement en charge l'incertitude sur les effets des actions. Afin de modeliser l'execution simultanee d'actions aux effets indetermines, QUANP LAN s'inspire de la mecanique quantique ou des etats quantiques sont des superpositions d'etats classiques. Un processus decisionnel de Markov (MDP) est utilise pour generer des plans dans un espace d'etats quantiques. L'optimalite, la completude, ainsi que les limites de ces planificateurs sont discutees. Des comparaisons avec d'autres planificateurs ciblant des classes de problemes similaires demontrent l'efficacite des methodes presentees. Enfin, des contributions complementaires aux domaines des jeux et de la planification de trajectoires sont egalement presentees.