Глоссарий ИИ
Полный словарь искусственного интеллекта
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.
Сглаживание траектории
Постобработка, применяемая к полученному дискретному пути для генерации непрерывной и дифференцируемой кривой, устраняющей резкие углы с учётом ограничений столкновения.
Искусственное потенциальное поле
Альтернативный метод планирования, при котором робот привлекается к цели и отталкивается от препятствий, создавая градиент потенциала, по которому следует для достижения пункта назначения.
Любовремённой A*
Вариант A*, способный быстро предоставлять субоптимальное решение, а затем итеративно улучшать его с доступным временем, адаптированный для приложений реального времени.
Взвешенный A*
Модификация A*, придающая эвристике больший вес для ускорения поиска в ущерб оптимальности, используется, когда предпочтительны быстрые решения.
Поиск точек прыжка (JPS)
Оптимизация A* для однородных сеток, которая устраняет симметричные узлы и определяет 'прыжки' напрямую к релевантным точкам принятия решений, значительно сокращая пространство поиска.
Иерархический поиск путей (HPA*)
Техника иерархического планирования, предварительно вычисляющая пути между регионами высокого уровня, а затем уточняющая их локально, ускоряя поиск на очень больших сетках.
Пожизненное планирование A* (LPA*)
Инкрементальный алгоритм поиска, оптимизирующий последовательные перепланирования путём повторного использования информации из предыдущих поисков при изменении среды.