Recherche et résolution de problèmes
La recherche et la résolution de problèmes constituent la branche de l'intelligence artificielle qui s'intéresse à la formulation de tâches comme l'exploration d'un espace d'états ou de configurations, et à la découverte de séquences d'actions, d'affectations ou de déplacements permettant d'atteindre un objectif.
Definition
La résolution de problèmes basée sur la recherche représente une tâche comme un état initial, un ensemble d'actions qui transforment les états, un test d'objectif et un coût de chemin, et la résout en explorant systématiquement les états atteignables jusqu'à ce qu'un état objectif (ou un chemin de moindre coût vers celui-ci) soit trouvé.
Scope
Ce domaine couvre la formulation des problèmes en tant qu'espaces d'états et les algorithmes qui les explorent : la recherche non informée (aveugle) comme la recherche en largeur d'abord et en profondeur d'abord, la recherche informée (heuristique) comme A* et la recherche gloutonne du meilleur d'abord, la recherche adversariale pour les jeux à deux joueurs, et la satisfaction de contraintes. Il aborde la manière dont les problèmes sont modélisés en tant qu'états, actions et tests d'objectif, et comment la complétude, l'optimalité, le temps et l'espace sont analysés. Il exclut l'apprentissage des heuristiques de recherche ou des fonctions d'évaluation à partir de données, ce qui relève du sous-domaine distinct de l'apprentissage automatique.
Sub-topics
Core questions
- Comment une tâche du monde réel est-elle formulée comme un espace d'états avec des états, des actions et un test d'objectif ?
- Quand un algorithme de recherche est-il complet (garanti de trouver une solution si elle existe) et optimal (garanti de trouver une solution de moindre coût) ?
- Comment une fonction heuristique guide-t-elle la recherche vers l'objectif tout en préservant l'optimalité ?
- Comment l'explosion combinatoire de l'espace d'états peut-elle être contrôlée par l'élagage ou un ordonnancement informé ?
- Comment la recherche est-elle modifiée lorsqu'un adversaire choisit certains des mouvements ?
Key concepts
- espace d'états
- arbre de recherche et graphe de recherche
- recherche non informée (aveugle)
- fonction heuristique
- admissibilité et cohérence
- recherche A*
- facteur de branchement et profondeur de recherche
- complétude et optimalité
- satisfaction de contraintes
Key theories
- Heuristiques admissibles et optimalité de A*
- Si une heuristique ne surestime jamais le coût réel jusqu'à l'objectif (est admissible), la recherche A* développe les nœuds dans l'ordre du meilleur d'abord de f = g + h et est garantie de renvoyer une solution optimale ; la cohérence garantit en outre qu'aucun nœud n'est ré-étendu.
- Compromis entre recherche non informée et informée
- Les stratégies aveugles (recherche en largeur d'abord, à coût uniforme, en profondeur d'abord, approfondissement itératif) ne diffèrent que par l'ordonnancement des nœuds et offrent des garanties sans connaissance du domaine, tandis que les estimations heuristiques du coût restant peuvent réduire considérablement l'espace exploré, au risque de perdre l'optimalité si l'heuristique est inadmissible.
- Formulation de problèmes comme recherche dans l'espace d'états
- Une vaste gamme de tâches devient traitable une fois formulée comme une recherche sur des états connectés par des actions, faisant du choix de la représentation des états et des opérateurs une décision de conception centrale qui détermine le facteur de branchement et la profondeur de la solution.
Clinical relevance
La recherche est à la base d'une vaste gamme de systèmes pratiques : la planification d'itinéraires et la navigation (A* sur les réseaux routiers), les moteurs de puzzles et de jeux, la configuration et la planification automatisées, la planification de mouvement de robots, et constitue l'épine dorsale de la planification automatisée et des solveurs de contraintes utilisés en logistique et en recherche opérationnelle.
History
La recherche a été centrale en IA dès ses débuts, le General Problem Solver de Newell et Simon (fin des années 1950) ayant conceptualisé l'intelligence comme une recherche à travers des espaces de problèmes. L'algorithme A* (Hart, Nilsson, Raphael, 1968) a conféré à la recherche heuristique une base rigoureuse en matière d'optimalité, et la monographie de Pearl de 1984 a systématisé la théorie de la recherche heuristique. Ce cadre demeure une lentille d'organisation standard dans les manuels d'IA.
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- Quelle est la différence entre la recherche non informée et la recherche informée ?
- La recherche non informée (aveugle), telle que la recherche en largeur d'abord ou en profondeur d'abord, n'utilise aucune information sur la proximité d'un état par rapport à l'objectif et explore purement selon la structure de l'espace d'états. La recherche informée (heuristique) utilise une estimation du coût restant jusqu'à l'objectif pour prioriser les états à développer, ce qui peut être beaucoup plus efficace.
- Pourquoi A* est-il si largement utilisé ?
- A* combine le coût réel depuis le départ (g) avec une estimation heuristique jusqu'à l'objectif (h), et lorsque l'heuristique est admissible, il est garanti de trouver une solution optimale tout en explorant généralement beaucoup moins d'états que la recherche non informée. Cet équilibre entre optimalité et efficacité en fait un choix par défaut pour la recherche de chemin.