Cette thèse s'inscrit dans le cadre de la planification de tâches en intelligence artificielle. Après avoir introduit le domaine et les principaux algorithmes de planification dans le cadre classique, nous présentons un état de l'art de la planification SAT. Nous analysons en détail cette approche qui permet de bénéficier directement des améliorations apportées régulièrement aux solveurs SAT. Nous proposons de nouveaux codages qui intègrent une stratégie de moindre engagement en retardant le plus possible l'ordonnancement des actions. Nous présentons ensuite le système TSP que nous avons implémenté pour comparer équitablement les différents codages puis nous détaillons les résultats de nombreux tests expérimentaux qui démontrent la supériorité de nos codages par rapport aux codages existants. Nous présentons ensuite un état de l'art de la planification temporelle en analysant les algorithmes et l'expressivité de leurs langages de représentation. La très grande majorité de ces planificateurs ne permet pas de résoudre des problèmes réels pour lesquels la concurrence des actions est nécessaire. Nous détaillons alors les deux approches originales de notre système TLP-GP permettant de résoudre ce type de problèmes. Ces approches sont comparables à la planification SAT, une grande partie du travail de recherche étant déléguée à un solveur SMT. Nous proposons ensuite des extensions du langage de planification PDDL qui permettent une certaine prise en compte de l'incertitude, du choix, ou des transitions continues. Nous montrons enfin, grâce à une étude expérimentale, que nos algorithmes permettent de résoudre des problèmes réels nécessitant de nombreuses actions concurrentes.

Un des challenges actuels de la planification est la résolution de problèmes pour lesquels on cherche à optimiser la qualité d'une solution telle que le coût d'un plan-solution. Dans cette thèse, nous développons une méthode originale pour la planification de coût optimal dans un cadre classique non temporel et avec des actions valuées.<br /><br />Pour cela, nous utilisons une structure de longueur fixée appelée graphe de planification. L'extraction d'une solution optimale, à partir de ce graphe, est codée comme un problème de satisfaction de contraintes pondérées (WCSP). La structure spécifique des WCSP obtenus permet aux solveurs actuels de trouver, pour une longueur donnée, une solution optimale dans un graphe de planification contenant plusieurs centaines de nœuds. <br /><br />Nous présentons ensuite plusieurs méthodes pour déterminer la longueur maximale des graphes de planification nécessaire pour garantir l'obtention d'une solution de coût optimal. Ces méthodes incluent plusieurs notions universelles comme par exemple la notion d'ensembles d'actions indispensables pour lesquels toutes les solutions contiennent au moins une action de l'ensemble. <br /><br />Les résultats expérimentaux effectués montrent que l'utilisation de ces méthodes permet une diminution de 60% en moyenne de la longueur requise pour garantir l'obtention d'une solution de coût optimal. La comparaison expérimentale avec d'autres planificateurs montre que l'utilisation du graphe de planification et des CSP pondérés pour la planification optimale est possible en pratique même si elle n'est pas compétitive, en terme de temps de calcul, avec les planificateurs optimaux récents.