KI-Glossar
Das vollständige Wörterbuch der Künstlichen Intelligenz
A* (A-Star) Algorithm
Graph pathfinding algorithm that combines Dijkstra's uniform cost exploration with a heuristic to guide the search toward the goal, guaranteeing an optimal path if the heuristic is admissible.
Dijkstra's Algorithm
Classic algorithm for finding the shortest path in a weighted graph, systematically exploring nodes in order of increasing distance from the starting point without using any heuristic.
D* (D-Star) Algorithm
Dynamic and incremental path planning algorithm capable of efficiently replanning paths when costs or environment topology change during execution.
Admissible Heuristic
Cost estimation function that never overestimates the actual minimal cost to reach the goal, an essential property guaranteeing the optimality of the A* algorithm.
Discretization Grid
Representation of continuous space as discrete cells or nodes enabling the application of pathfinding algorithms on continuous environments.
Theta* (Theta-Star)
Variant of A* allowing straight-line paths between non-adjacent nodes when no obstacle interferes, generating more realistic and shorter trajectories than staircase paths.
Open List
Data structure containing discovered but not yet fully explored nodes, typically implemented as a priority queue based on the estimated total cost f(n).
Closed List
Set of nodes already explored by the search algorithm, preventing re-evaluations and cycles in the pathfinding process.
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.