Plus d'inférence et moins de reherche pour la résolution de problèmes de planification simples

Overview & Synopsis

De nombreux problèmes utilisés en planification de tâches dans le domaine de l'intelligence artificielle comme Blocks, Logistics, Gripper, Satellite et d'autres, ne possèdent pas les interactions qui caractérisent les puzzles. Ils peuvent être résolus rapidement mais non optimalement en temps polynomial. Ce sont en effet des problèmes faciles pour les humains, mais comme beaucoup d'autres problèmes en intelligence artifcielle, difficiles pour les machines. Dans ce travail, nous étudions le type d'inférences requises dans un planificateur indépendant du domaine pour résoudre des problèmes simples en évitant au maximum de faire des retours arrière, en ajoutant uniquement quelques opérations polynomiales à chaque noeud de l'arbre de recherche. A cette fin, nous utilisons le planificateur temporel optimal CPT qui combine un schéma de branchement de type POCL avec des mécanismes d'inférence puissants, et montrons que l'ajout de quelques règles d'inférence simples et générales suffisent pour éliminer les retours arrière pour de nombreux domaines. Il s'agit là d'un résultat empirique intéressant, à notre avis, qui pourrait contribuer au développement de planificateurs automatiques plus robustes, et à une meilleure compréhension de la façon des planifier des humains. Nous apportons aussi une amélioration des performances significative par rapport à CPT.