Glossaire IA
Le dictionnaire complet de l'Intelligence Artificielle
Algorithme A* (A-Star)
Algorithme de recherche de chemin sur graphe qui combine l'exploration à coût uniforme de Dijkstra avec une heuristique pour guider la recherche vers le but, garantissant un chemin optimal si l'heuristique est admissible.
Algorithme Dijkstra
Algorithme classique de recherche du plus court chemin dans un graphe pondéré, explorant systématiquement les nœuds par ordre de distance croissante depuis le point de départ sans utiliser d'heuristique.
Algorithme D* (D-Star)
Algorithme de planification de chemin dynamique et incrémentiel capable de réorganiser efficacement les chemins lorsque les coûts ou la topologie de l'environnement changent pendant l'exécution.
Heuristique Admissible
Fonction d'estimation du coût restant qui ne surestime jamais le coût réel minimal vers le but, propriété essentielle garantissant l'optimalité de l'algorithme A*.
Grille de Discrétisation
Représentation de l'espace continu sous forme de cellules ou nœuds discrets permettant l'application d'algorithmes de recherche de chemin sur des environnements continus.
Theta* (Theta-Star)
Variante de A* autorisant les chemins en ligne droite entre nœuds non-adjacents lorsque aucun obstacle n'interfère, générant des trajectoires plus réalistes et plus courtes que les chemins en escalier.
Liste Ouverte (Open List)
Structure de données contenant les nœuds découverts mais non encore complètement explorés, typiquement implémentée comme une file de priorité basée sur le coût estimé total f(n).
Liste Fermée (Closed List)
Ensemble des nœuds déjà explorés par l'algorithme de recherche, permettant d'éviter les réévaluations et les cycles dans le processus de recherche de chemin.
Lissage de Trajectoire
Post-traitement appliqué au chemin discret obtenu pour générer une courbe continue et dérivable, éliminant les angles vifs tout en respectant les contraintes de collision.
Champ de Potentiel Artificiel
Méthode alternative de planification où le robot est attiré par le but et repoussé par les obstacles, créant un gradient de potentiel suivi pour atteindre la destination.
Anytime A*
Variante de A* capable de fournir rapidement une solution sous-optimale puis de l'améliorer itérativement avec le temps disponible, adaptée aux applications temps-réel.
Weighted A*
Modification de A* surpondérant l'heuristique pour accélérer la recherche au détriment de l'optimalité, utilisée lorsque des solutions rapides sont privilégiées.
Jump Point Search (JPS)
Optimisation de A* pour les grilles uniformes qui élimine les nœuds symétriques et identifie des 'sauts' directs vers les points de décision pertinents, réduisant drastiquement l'espace de recherche.
Hierarchical Path-Finding (HPA*)
Technique de planification hiérarchique précalculant des chemins entre régions de haut niveau puis affinant localement, accélérant la recherche sur de très grandes grilles.
Lifelong Planning A* (LPA*)
Algorithme de recherche incrémental optimisant les replanifications successives en réutilisant les informations des recherches précédentes lorsque l'environnement évolue.