Вычисление пути¶
Вычисление пути — совокупность алгоритмов и методов определения траектории движения объекта (транспортного средства, робота, персонажа компьютерной игры, летательного аппарата) между начальной и конечной точками с учётом ограничений среды. Задача относится к области теории графов, вычислительной геометрии и искусственного интеллекта и решается в навигационных системах, робототехнике, компьютерной графике и логистике.
¶Постановка задачи
Вычисление пути формулируется как поиск кратчайшего (или допустимого) маршрута в графе или в непрерывном пространстве. Исходные данные обычно включают:
- начальную и целевую точки;
- описание препятствий или запрещённых зон;
- метрику стоимости (длина, время, энергозатраты, риск);
- дополнительные ограничения (ширина проезжей части, допустимые углы поворота, уклон).
В общем случае задача NP-полна, поэтому на практике применяются приближённые методы и эвристики.
¶Основные алгоритмы
¶Поиск на графе
Для дискретных пространств (сеток, дорожных графов) применяются классические алгоритмы поиска:
| Алгоритм | Гарантия кратчайшего пути | Особенности |
|---|---|---|
| Поиск в ширину | Да (в невзвешенном графе) | Обходит граф слоями, не использует эвристику |
| Алгоритм Дейкстры | Да (в графе с неотрицательными весами) | Полный обход, высокая вычислительная сложность на больших графах |
| Алгоритм A* | Да (при адмиссионной эвристике) | Использует оценку оставшегося расстояния, быстрее Дейкстры |
| Лучший поиск (Greedy) | Нет | Жадно выбирает узел, ближайший к цели |
Алгоритм A* наиболее широко применяется в компьютерных играх и робототехнике: он объединяет стоимость пройденного пути и эвристическую оценку оставшегося расстояния (например, расстояние по прямой или манхэттенское расстояние).
¶Непрерывные пространства
В непрерывном пространстве (например, для робота с непрерывными координатами) применяются:
- Пробные пути (Probabilistic Roadmap, PRM) — случайное построение графа конфигураций с последующим поиском маршрута;
- Дерево случайных направлений (RRT) — итеративное расширение дерева от стартовой точки в сторону случайных целей, эффективное для пространств с препятствиями;
- Волновой алгоритм (алгоритм Ли) — построение волны от цели, определяющее кратчайший путь в растровой карте;
- Метод потока (Flow field) — вычисление поля направлений для множества агентов одновременно.
¶Оптимизация траектории
После нахождения дискретного пути выполняется его сглаживание и оптимизация: интерполяция сплайнами, минимизация кривизны, учёт динамических ограничений (максимальное ускорение, скорость поворота). Для автономных транспортных средств дополнительно применяется локальное избегание препятствий (алгоритм динамического окна, Velocity Obstacles).
¶Применение
¶Навигационные системы
Автомобильные навигаторы и картографические сервисы строят маршруты по дорожным графам с учётом дорожной обстановки, ограничений скорости и профиля дороги. Для России наиболее развиты системы Яндекс.Навигатор, 2ГИС и «Яндекс.Карты», использующие собственные дорожные графы и данные о пробках.
¶Робототехника
Мобильные роботы (включая промышленные AGV и роботов-пылесосы) используют вычисление пути для перемещения по помещению. Методы PRM и RRT применяются в планировании движения манипуляторов в конфигурационном пространстве.
¶Компьютерные игры
В играх с открытым миром и стратегиях вычисление пути реализуется через навигационные сетки (navmesh) и алгоритмы A* или JPS (Jump Point Search). Для массовых сражений применяются потоковые поля, позволяющие вычислить направление для тысяч юнитов одновременно.
¶Логистика и транспорт
Задача коммивояжёра и связанные с ней задачи оптимизации маршрутов (Vehicle Routing Problem) решаются методами ветвей и границ, имитационного отжига и генетическими алгоритмами. В России эти методы применяются в службах доставки и распределительной логистике.
¶Историческая справка
Алгоритм Дейкстры опубликован в 1959 году нидерландским математиком Эдсгером Дейкстрой. Алгоритм A* предложен Питером Хартом, Нильсом Нильссоном и Бертрамом Рафаэлем в 1968 году для планирования пути в искусственном интеллекте. Волновой алгоритм Ли описан в 1961 году С. Э. Ли как метод поиска кратчайшего пути в растровых картах.
¶Источники
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — «Алгоритмы: построение и анализ»
- ЛаВаль С. М. — «Планирование алгоритмов для автономных роботов»
- Харт П., Нильссон Н., Рафаэл Б. — «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» (1968)
- Дейкстра Э. — «A Note on Two Problems in Connexion with Graphs» (1959)
- Русскоязычные справочные материалы по навигационным системам и робототехнике