Aller au contenu

« Planification (intelligence artificielle) » : différence entre les versions

Un article de Wikipédia, l'encyclopédie libre.
Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Fschwarzentruber (discuter | contributions)
8 070 modifications
Fschwarzentruber (discuter | contributions)
8 070 modifications
Ligne 17 : Ligne 17 :
[[Fichier:Atari 5200 - trojandan 14871272.jpg|vignette|Jeux Atari.]]
[[Fichier:Atari 5200 - trojandan 14871272.jpg|vignette|Jeux Atari.]]
[[Fichier:HST-SM4.jpeg|vignette|Téléscope spatial Hubble.]]
[[Fichier:HST-SM4.jpeg|vignette|Téléscope spatial Hubble.]]
En 2015, la planification a été utilisée pour construire des programmes qui jouent automatiquement aux jeux Atari<ref>{{Article|prénom1=Nir|nom1=Lipovetzky|prénom2=Miquel|nom2=Ramirez|prénom3=Hector|nom3=Geffner|titre=Classical planning with simulators: results on the Atari video games|éditeur=AAAI Press|date=2015-07-25|isbn=9781577357384|lire en ligne=http://dl.acm.org/citation.cfm?id=2832415.2832473|consulté le=2018-06-01|pages=1610–1616}}</ref>. Le [[Hubble (télescope spatial)|téléscope spatial Hubble]] utilise le planificateur Spike<ref>{{Lien web|langue=Anglais|titre=Spike Planning and Scheduling System|url=http://www.stsci.edu/institute/software_hardware/spike/|site=|date=|consulté le=}}</ref>, développé par le [[Space Telescope Science Institute]].
En 2015, la planification a été utilisée pour construire des programmes qui jouent automatiquement aux jeux Atari<ref>{{Article|prénom1=Nir|nom1=Lipovetzky|prénom2=Miquel|nom2=Ramirez|prénom3=Hector|nom3=Geffner|titre=Classical planning with simulators: results on the Atari video games|éditeur=AAAI Press|date=2015-07-25|isbn=9781577357384|lire en ligne=http://dl.acm.org/citation.cfm?id=2832415.2832473|consulté le=2018-06-01|pages=1610–1616}}</ref>. Le système SHPE basé sur de la planification dite hiérarchique permet de faire de la planification pour des jeux vidéos, en particulier des [[Jeu de tir tactique|jeux de tir tactique]] (FPS pour first-person shooter ; ils ont des benchmarks appelés SimpleFPS pour ce type de jeu)<ref>{{Ouvrage|langue=en|prénom1=Alexandre|nom1=Menif|prénom2=Éric|nom2=Jacopin|prénom3=Tristan|nom3=Cazenave|titre=Communications in Computer and Information Science|passage=119–132|éditeur=Springer International Publishing|date=2014|isbn=9783319149226|isbn2=9783319149233|doi=10.1007/978-3-319-14923-3_9|lire en ligne=https://link.springer.com/chapter/10.1007/978-3-319-14923-3_9|consulté le=2018-06-13}}</ref>. Le [[Hubble (télescope spatial)|téléscope spatial Hubble]] utilise le planificateur Spike<ref>{{Lien web|langue=Anglais|titre=Spike Planning and Scheduling System|url=http://www.stsci.edu/institute/software_hardware/spike/|site=|date=|consulté le=}}</ref>, développé par le [[Space Telescope Science Institute]].


== Planification classique ==
== Planification classique ==

Version du 13 juin 2018 à 11:53

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

Exemple de plan pour un robot qui déplace des blocs : prendre B, poser B sur la table, prendre C, poser C sur A.

En intelligence artificielle, la planification automatique (automated planning en anglais) ou plus simplement planification, vise à développer des algorithmes pour produire des plans typiquement pour l'exécution par un robot ou tout autre agent. Les logiciels de planification qui incorporent ces algorithmes s'appellent des planificateurs. La difficulté du problème de planification dépend des hypothèses de simplification qu'on tient pour acquis, par exemple un temps atomique, un temps déterministe, une observabilité complète, etc. La compétition IPC (international planning competition) a lieu tous les ans durant le congrès ICAPS (International Conference on Planning and Scheduling)[1].

Principe

Un planificateur typique manipule trois entrées décrites dans un langage formel (tel que STRIPS[2] ou PDDL) qui utilise des prédicats logiques :

  • une description de l'état initial d'un monde,
  • une description d'un but à atteindre et
  • un ensemble d'actions possibles (parfois appelés opérateurs).

Chaque action est spécifiée par des préconditions qui doivent être satisfaites dans l'état actuel pour qu'elle puisse être appliquée, et des postconditions (effets sur l'état actuel).

Description de l'exemple

Applications

Jeux Atari.
Téléscope spatial Hubble.

En 2015, la planification a été utilisée pour construire des programmes qui jouent automatiquement aux jeux Atari[3]. Le système SHPE basé sur de la planification dite hiérarchique permet de faire de la planification pour des jeux vidéos, en particulier des jeux de tir tactique (FPS pour first-person shooter ; ils ont des benchmarks appelés SimpleFPS pour ce type de jeu)[4]. Le téléscope spatial Hubble utilise le planificateur Spike[5], développé par le Space Telescope Science Institute.

Planification classique

La planification classique repose sur deux hypothèses :

  • le déterminisme des actions. Par exemple, l'action "poser un cube sur la table" est déterministe. En l'exécutant, on passe d'un état à un autre. Au contraire, "jeter un dé" est non-déterministe car il y a 6 valeurs possibles. L'action "jeter un dé" ne rentre donc pas dans le cadre de la planification classique.
  • l'observation parfaite. L'agent (le robot, le programme, etc.) connaît complétement l'état du monde.

En planification classique, il s'agit de chercher une séquence d'actions (par exemple, "prendre une casserole", "mettre de l'eau", "mettre des pâtes", "allumer le feu", "atteindre", "éteindre le feu"). L'algorithme A* est un exemple typique d'algorithme de planification classique, souvent employé dans les cours d'introduction pour sa simplicité. Voici quelques techniques algorithmiques utilisées dans les planificateurs classiques :

  • la recherche avant dans un espace d'états : algorithme heuristic search planning (HSP)[6], algorithme Fast-Forward (FF)[7],
  • la recherche arrière dans un espace d'états,
  • la recherche avant dans un espace de plans, graphplan[8]
  • la relaxation d'un problème de planification : on calcule un problème relaxé, pour lequel il est plus simple de savoir s'il existe un plan, qui aide à résoudre le problème initial[9]
  • la transformation vers un problème de satisfiabilité d'une formule de la logique propositionnelle.

Bylander a démontré en 1994 que la planification classique est PSPACE-complète[10].

Autres types de planification

Résultats de complexité théorique obtenus par Rintanen[11] des différents types de planification.

En pratique, on ne vérifie que très rarement les hypothèses de la planification classique. C'est pourquoi bon nombre d'extensions ont vu le jour.

Planification conformante

On parle de planification conformante (conformant planning) où le système est dans un état incertain, mais aucune observation n'est possible. L'agent a alors des croyances sur le monde réel. Ces problèmes sont résolus par des techniques semblables à celles de la planification classique, mais où l'espace des états est exponentiel dans les dimensions du problème, à cause de l'incertain sur l'état actuel. Une solution pour un problème de conformant planning est une séquence d'actions.

Planification contingente

On parle de planification contingente (contingent planning) où l'environnement est observable grâce à des senseurs. Pour un problème de planification contingente, un plan n'est plus une séquence d'actions mais un arbre de décision.

Rintanen a démontré en 2004 que si on ajoute du branchement (planification contingente), le problème de planification devient EXPTIME-complet. Si au contraire, on ajoute de l'incertain à la planification classique (i.e. planification conformante), il devient EXPSPACE-complet. Si on ajoute à la fois du branchement et de l'incertain (planification à la fois conformante et contingente), il devient 2EXPTIME-complet[11].

Planification probabiliste

Kushmerick et al. ont introduit la planification probabiliste[12]. Dans leurs travaux, l'effet des actions est décrite avec des probabilistes. Il donne l'exemple de l'action `le robot prend un bloc' décrite de la manière suivante : si la pince du robot est sèche, alors le robot tient le bloc avec une probabilité 0.95 ; si la pince est humide, alors le robot ne tient le bloc qu'avec une probabilité de 0.5.

Ceci mène au problème de la génération de politique (ou stratégie) pour un Processus de décision markovien (MDP) ou (dans le cas général) un Processus de décision markovien partiellement observable (POMDP).

Planification non linéaire

La planification classique résout les sous-buts dans un ordre donné. Le problème est que cela amène parfois à détruire ce qui a déjà été construit. Ce phénomène est connu sous le nom d'anomalie de Sussman.

Supposons qu'un individu pieds nus doive se retrouver dans l'état ou il porte sa chaussure droite, sa chaussure gauche, sa chaussette droite et sa chaussette gauche. S'il cherche à réaliser les buts dans l'ordre de l'énoncé, il échouera.

Pour résoudre ce type de problème, on peut passer à des plans partiellement ordonnés dans lesquels l'ordre entre les actions n'est fixé que lorsque c'est nécessaire (engagement au plus tard ou least commitment planning).

Dans l'exemple précédent, mettre la chaussure gauche doit se faire après avoir mis la chaussette gauche. Idem pour la droite. En revanche l'exécution du plan pour la gauche est indépendante de l'exécution pour la droite. Le plan global est donc partiellement ordonné.

Les planificateurs capable de gérer cette catégorie de problème sont dits à ordre partiel (POP, NOAH, etc).

Planification hiérarchique

Certains problèmes sont difficilement solubles en l'état du fait de leur complexité. On peut gagner en efficacité en effectuant une abstraction des détails et en changeant la granularité des opérateurs de planification. On peut par exemple commencer à planifier à haut niveau puis descendre dans le détail au besoin (comme le fait ABSTRIPS par exemple).

Planification temporelle

La planification temporelle permet d'exprimer des durées d'actions, des conditions au début, à la fin et pendant l'action et des effets au début et à la fin des actions. Le langage PDDL 2.1 inclut la planification temporelle[13]. La méthode TLP-GP 1[14] construit un graphe, puis on résout des contraintes temporelles en utilisant un solveur SMT. On backtracke en cas d'inconsistance. Rintanen a démontré que la planification temporelle concurrente (plusieurs instances d'une même action en parallèle est possible) est EXPSPACE-complète. Par contre, si on relâche ces conditions, on peut se ramener à de la planification classique et donc la planification temporelle avec ces restrictions devient PSPACE-complète[15].

Planification multi-agents

La planification multi-agents étudie la réalisation d'une tâche par plusieurs agents, par exemple plusieurs robots. La génération du plan et son exécution est alors souvent distribuée/décentralisée[16],[17],[18]. Un aspect important dans les plans est la coopération entre agents. Il existe aussi un algorithme de planification centralisé, qui s'appuie sur une généralisation de STRIPS au cadre multi-agents, appelée MA-STRIPS[19]. L'algorithme a ensuite été rendu distribué, en utilisant un solveur CSP distribué pour gérer la coordination entre agents[20]. Les auteurs, Nissim, Brafman et Domshlak, ont expérimentalement vérifié que leur algorithme est meilleur qu'une planification centralisée lorsque les agents ont peu d'interactions entre eux.

Une difficulté majeure de la planification multi-agent est l'explosion combinatoire de l'ensemble des actions, qui est exponentiel en le nombre d'agents. En 2011, Jonsson et Rovatsos propose une solution pour contrecarrer ce problème et se ramène à de la planification classique mono-agent[21]. Il y a aussi un regain à utiliser des techniques de parallélisation pour que les algorithmes de planification passer à l'échelle[22].

Planification épistémique

Le problème de planification épistémique consiste à prendre en compte les connaissances des agents dans la description des états et des actions[23]. Typiquement, l'objectif est une formule de la logique modale épistémique, comme "l'agent a sait que l'agent b que le bloc C est sur le bloc A" et les actions sont représentées avec des modèles d'actions de la logique épistémique dynamique[23]. Le problème de planification est indécidable dans toute sa généralité[24].

Voir aussi

Bibliographie

  • Algorithmique de la planification en IA, Pierre Régnier, Editions Cépaduès, (ISBN 2-85428-658-8)
  • (en) Automated planning", 2004, Malik Ghallab, Dana nau et Paolo Traverso, Morgan Kaufman, (ISBN 1-55860-856-7)
  • (en) Michael R. Genesereth and Nils J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann, [détail de l’édition], chap. 12 Planning, pp. 285-306

Articles connexes

Références

  1. ↑ (en) « IPC2018 »
  2. ↑ Richard E. Fikes et Nils J. Nilsson, « STRIPS: a new approach to the application of theorem proving to problem solving », {{Article}} : paramètre « périodique » manquant, Morgan Kaufmann Publishers Inc.,‎ , p. 608–620 (lire en ligne, consulté le )
  3. ↑ Nir Lipovetzky, Miquel Ramirez et Hector Geffner, « Classical planning with simulators: results on the Atari video games », {{Article}} : paramètre « périodique » manquant, AAAI Press,‎ , p. 1610–1616 (ISBN 9781577357384, lire en ligne, consulté le )
  4. ↑ (en) Alexandre Menif, Éric Jacopin et Tristan Cazenave, Communications in Computer and Information Science, Springer International Publishing, (ISBN 9783319149226 et 9783319149233, DOI 10.1007/978-3-319-14923-3_9, lire en ligne), p. 119–132
  5. ↑ (en) « Spike Planning and Scheduling System »
  6. ↑ (en) « Planning as heuristic search », Artificial Intelligence, vol. 129, nos 1-2,‎ , p. 5–33 (ISSN 0004-3702, DOI 10.1016/S0004-3702(01)00108-4, lire en ligne, consulté le )
  7. ↑ Jörg Hoffmann et Bernhard Nebel, « The FF planning system: fast plan generation through heuristic search », Journal of Artificial Intelligence Research, vol. 14, no 1,‎ , p. 253–302 (ISSN 1076-9757, lire en ligne, consulté le )
  8. ↑ (en) « Fast planning through planning graph analysis », Artificial Intelligence, vol. 90, nos 1-2,‎ , p. 281–300 (ISSN 0004-3702, DOI 10.1016/S0004-3702(96)00047-1, lire en ligne, consulté le )
  9. ↑ Martin Cooper, Frédéric Maris et Pierre Régnier, « Relaxation of Temporal Planning Problems », {{Article}} : paramètre « périodique » manquant, IEEE Computer Society,‎ , p. 37–44 (ISBN 9781479922413, DOI 10.1109/TIME.2013.28, lire en ligne, consulté le )
  10. ↑ (en) « The computational complexity of propositional STRIPS planning », Artificial Intelligence, vol. 69, nos 1-2,‎ , p. 165–204 (ISSN 0004-3702, DOI 10.1016/0004-3702(94)90081-7, lire en ligne, consulté le )
  11. ↑ a et b (en) Jussi Rintanen, « Complexity of Planning with Partial Observability », ICALP,‎ (lire en ligne)
  12. ↑ (en) « An algorithm for probabilistic planning », Artificial Intelligence, vol. 76, nos 1-2,‎ , p. 239–286 (ISSN 0004-3702, DOI 10.1016/0004-3702(94)00087-H, lire en ligne, consulté le )
  13. ↑ « Compilation d’un langage de planification temporelle de haut niveau en PDDL2.1 »
  14. ↑ (en-US) « TLP-GP: Solving Temporally-Expressive Planning Problems - IEEE Conference Publication », sur ieeexplore.ieee.org (consulté le )
  15. ↑ Jussi Rintanen, « Complexity of concurrent temporal planning », {{Article}} : paramètre « périodique » manquant, AAAI Press,‎ , p. 280–287 (ISBN 9781577353447, lire en ligne, consulté le )
  16. ↑ (en) Edmund H. Durfee, Multi-Agent Systems and Applications, Springer Berlin Heidelberg, (ISBN 9783540423126 et 9783540477457, DOI 10.1007/3-540-47745-4_6, lire en ligne), p. 118–149
  17. ↑ (en-US) Marie E. desJardins, Edmund H. Durfee, Jr Charles L. Ortiz et Michael J. Wolverton, « A Survey of Research in Distributed, Continual Planning », AI Magazine, vol. 20, no 4,‎ , p. 13 (ISSN 0738-4602, DOI 10.1609/aimag.v20i4.1475, lire en ligne, consulté le )
  18. ↑ (en-US) M. Tambe, « Towards Flexible Teamwork », Journal of Artificial Intelligence Research, vol. 7,‎ , p. 83–124 (ISSN 1076-9757, DOI 10.1613/jair.433, lire en ligne, consulté le )
  19. ↑ Ronen I. Brafman et Carmel Domshlak, « From one to many: planning for loosely coupled multi-agent systems », {{Article}} : paramètre « périodique » manquant, AAAI Press,‎ , p. 28–35 (ISBN 9781577353867, lire en ligne, consulté le )
  20. ↑ Raz Nissim, Ronen I. Brafman et Carmel Domshlak, « A general, fully distributed multi-agent planning algorithm », {{Article}} : paramètre « périodique » manquant, International Foundation for Autonomous Agents and Multiagent Systems,‎ , p. 1323–1330 (ISBN 9780982657119, lire en ligne, consulté le )
  21. ↑ Anders Jonsson et Michael Rovatsos, « Scaling up multiagent planning: a best-response approach », {{Article}} : paramètre « périodique » manquant, AAAI Press,‎ , p. 114–121 (lire en ligne, consulté le )
  22. ↑ Akihiro Kishimoto, Alex Fukunaga et Adi Botea, « Scalable, parallel best-first search for optimal sequential planning », {{Article}} : paramètre « périodique » manquant, AAAI Press,‎ , p. 201–208 (ISBN 9781577354062, lire en ligne, consulté le )
  23. ↑ a et b Thomas Bolander, « A Gentle Introduction to Epistemic Planning: The DEL Approach », Electronic Proceedings in Theoretical Computer Science, vol. 243,‎ , p. 1–22 (ISSN 2075-2180, DOI 10.4204/EPTCS.243.1, lire en ligne, consulté le )
  24. ↑ (en) Thomas Bolander et Mikkel Birkegaard Andersen, « Epistemic planning for single- and multi-agent systems », https://www.tandfonline.com/doi/abs/10.3166/jancl.21.9-34,‎ , Pages 9-34 (lire en ligne)
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Planification_(intelligence_artificielle)&oldid=149481651 ».