La planification s'attache à la génération d'une séquence d'actions (ou plus généralement d'un "arbre d'actions" comportant des actions de perception) dont l'exécution permet d'atteindre un état compatible avec les objectifs spécifiés. Lorsqu'il s'agit de traiter des problèmes réalistes, les plans générés doivent bien souvent être optimisés - soit que l'utilisateur ait une certaine mesure de qualité et désire le "meilleur plan", soit que l'incertitude inhérente aux modèles utilisés forcent à trouver des plans maximisant les chances de réussite malgré les inconnues. La robotique, par exemple, regorge de problèmes de planification combinant ces contraintes.
Sous cet angle particulier, planification classique d'actions (issue de l'IA) et théorie des jeux apparaissent complémentaires. La première offre des méthodes de recherche très puissantes dans le cadre déterministe pour des problèmes de satisfaction, capables en particulier de manipuler en même temps tous les états partageant une même propriété. La seconde en revanche, est un cadre bien adapté à la prise en compte de l'incertitude et de l'optimisation, grâce en particulier à l'utilisation d'une fonction d'utilité qui associe à chaque état une valeur réelle. Intuitivement, il apparait clairement qu'une solution prometteuse serait de traiter groupés (comme en planification classique) tous les états équivalents du point de vue de leur valeur d'utilité (calculée en théorie des jeux).
Cette approche hybride nécessite de pouvoir contrôler le "morcellement" de l'espace de recherche sous-jacent. Les "morceaux" doivent pouvoir être plus gros qu'un seul état (contrairement à ce que l'on trouve en théorie des jeux), mais plus petits et autrement découpés que ceux construits en planification classique (car basés sur des critères d'appartenance issus eux de la théorie des jeux).
Cet exposé se focalisera sur cette idée, définissant le "morcellement de l'espace de recherche", présentant les bénéfices attendus de son contrôle, ainsi que la mise en oeuvre que nous sommes en train d'implémenter. De fait, il abordera des aspects liés aux représentations, aux algorithmes de recherche, et des exemples jouets pour illustrer le propos.