Постоянное планирование A*
term_id: lifelong_planning_a
Category: application_paradigms
Definition
Постоянное планирование A* (LPA*) является расширением алгоритма поиска A*, предназначенным для сред, где затраты изменяются со временем. Вместо перезапуска поиска LPA* поддерживает очередь приоритетов и обновляет только те части дерева поиска, которые затронуты изменениями, что обеспечивает высокую эффективность в динамических условиях.
Summary
Инкрементальный алгоритм поиска пути, который эффективно обновляет кратчайшие пути в динамических графах без пересчета с нуля после изменения весов ребер.
Key Concepts
- Инкрементальный поиск
- Поиск пути
- Динамические графы
- Навигация роботов
Use Cases
- Маршрутизация автономных транспортных средств в трафике
- Навигация роботов в меняющихся складах
- Движение ИИ в стратегических играх реального времени