Вероятностная дорожная карта
Вероя́тностная доро́жная ка́рта (вероятностная карта маршрутов, PRM, от англ. probabilistic roadmap) — алгоритм планирования движения в робототехнике, предназначенный для поиска траектории между начальной и целевой конфигурациями робота с учётом препятствий[1].
Основная идея PRM заключается в случайной выборке из конфигурационного пространства робота, проверке попадания точек в свободное пространство и использовании локального планировщика для попытки соединения этих конфигураций с другими ближайшими точками. Начальная и целевая конфигурации также добавляются в граф, после чего для поиска пути между ними применяется алгоритм поиска в графе.
PRM состоит из двух фаз: построения карты и поиска пути (query-фазы). На этапе построения формируется дорожная карта (граф), аппроксимирующая допустимые перемещения в заданной среде. Сначала генерируется случайная конфигурация; затем она соединяется с некоторыми соседними точками — обычно со k ближайшими или со всеми, расстояние до которых меньше заданного порога. Конфигурации и соединения продолжают добавляться до тех пор, пока карта маршрутов не станет достаточно плотной. На этапе поиска начальная и конечная конфигурации подключаются к этому графу, и путь между ними находится с помощью алгоритма кратчайшего пути Дейкстры.
При выполнении некоторых сравнительно слабых условий на форму свободного пространства PRM гарантированно является вероятностно полным: по мере увеличения числа сэмплов вероятность того, что алгоритм не найдёт путь при его существовании, стремится к нулю. Скорость сходимости зависит от свойств видимости свободного пространства, под которой понимается возможность соединения пар конфигураций локальным планировщиком. Грубо говоря, если каждая точка «видит» большую часть пространства, а также если большая часть любых подмножеств пространства может соединяться с их дополнением, планировщик найдёт путь быстрее.
Метод был предложен в 1996 году Лидией Э. Кавраки, Петром Швесткой, Жан-Клодом Латомбом и Марком Овермарсом[1]. При этом его изобретение часто приписывается в первую очередь Кавраки[2][3]. Существует множество модификаций базового метода PRM, различающихся стратегиями выборки и соединения с целью повышения эффективности.
Модификации и развитие
В 2000-е годы исследования в области вероятностных дорожных карт были направлены на устранение ключевого недостатка базового алгоритма — низкой эффективности в сценах с «узкими проходами». При равномерной случайной выборке вероятность сгенерировать узлы в таких критически важных для построения пути областях была крайне мала[4]. Основные усовершенствования были сосредоточены на двух направлениях: разработке более интеллектуальных стратегий выборки и оптимизации процесса проверки на столкновения.
Для повышения плотности узлов в труднодоступных областях были предложены различные подходы. Метод Obstacle-Based PRM (OBPRM) генерирует конфигурации робота вблизи поверхностей препятствий, исходя из того, что пути через узкие проходы неизбежно пролегают близко к ним[5][6][7]. Стратегия Gaussian Sampling (гауссово сэмплирование), предложенная в 1999 году, добавляет в карту свободную конфигурацию, если вторая сгенерированная конфигурация попала в столкновение, что также увеличивает плотность узлов у препятствий[8]. Техника Bridge Test (тест «моста») была специально разработана для соединения разрозненных участков карты: она генерирует точки внутри препятствия и, если их середина оказывается в свободном пространстве, добавляет её в граф как «мост»[4]. В свою очередь, сэмплирование по серединной оси (Medial Axis Sampling) генерирует узлы, максимально удалённые от препятствий (вблизи серединной оси свободного пространства), что обеспечивает пути с большим зазором безопасности[4].
Другим важным направлением стала оптимизация проверок на столкновения, которые являются наиболее вычислительно затратной частью алгоритма[9]. В 2000 году была предложена модификация Lazy PRM («ленивый PRM»), кардинально изменившая подход к этой проблеме[10]. Её основной принцип — откладывать проверку на столкновения до последнего момента. Алгоритм сначала строит дорожную карту, в которой все узлы и соединения считаются валидными, и находит в этом «оптимистичном» графе кратчайший путь. Только после этого узлы и рёбра, входящие в найденный путь, проверяются на реальные столкновения. Если обнаруживается коллизия, невалидный элемент удаляется из графа, и выполняется новый поиск пути. Такой подход оказался особенно эффективным для однократных запросов, так как позволяет избежать большого количества ненужных проверок для тех частей карты, которые не входят в итоговый маршрут[11].
В этот же период метод PRM и его модификации начали адаптировать для решения более сложных задач, таких как планирование в динамических средах, для деформируемых объектов и систем с замкнутыми кинематическими цепями[5].
В 2010-е годы развитие вероятностных дорожных карт было направлено на устранение двух фундаментальных недостатков базового алгоритма: отсутствия гарантий оптимальности найденного пути и низкой эффективности при решении однократных задач (single-query), когда требуется найти только один маршрут[12].
Ключевым шагом к решению проблемы оптимальности стало появление асимптотически оптимальных планировщиков, таких как PRM*[13]. В отличие от классического PRM, который гарантирует только вероятностную полноту (нахождение любого существующего пути), PRM* обеспечивает сходимость к кратчайшему возможному пути по мере увеличения числа сэмплов. Это достигается за счёт изменения стратегии соединения узлов: вместо соединения с k ближайшими соседями, каждый новый узел пытается соединиться со всеми соседями в пределах определённого радиуса. Такой подход создаёт более плотный граф, что позволяет находить более короткие и гладкие траектории[13].
Для повышения эффективности при однократных запросах получила дальнейшее развитие концепция «ленивой» оценки, а также были предложены гибридные подходы для работы в пространствах с узкими проходами. Вариант Toggle PRM был разработан для улучшения картирования таких областей путём одновременного построения карт как в свободном пространстве, так и в пространстве препятствий[14]. В 2013 году был представлен метод Lazy Toggle PRM, объединивший оба подхода. Он откладывает дорогостоящую проверку на столкновения до момента запроса и, если путь не найден, использует методологию Toggle PRM для дополнения карты. Это делает его эффективным как для быстрых однократных запросов, так и для сред со сложной геометрией[14].
Среди других разработок этого периода выделяется Visibility-PRM — вариант, предназначенный для нахождения топологически различных путей (например, для обхода препятствия с разных сторон), что может быть полезно для последующей оптимизации траекторий[15].
В 2020-е годы развитие вероятностных дорожных карт было направлено на адаптацию алгоритма к динамическим средам, гибридизацию с другими методами для решения проблемы «узких проходов» и повышение общей эффективности.
Ключевой разработкой стала адаптация для сред с движущимися препятствиями. В 2022 году был предложен метод T-PRM (Temporal Probabilistic Roadmap), который вводит в дорожную карту временное измерение. Это позволяет планировать траектории с уклонением от динамических объектов в режиме реального времени, сохраняя при этом возможность многократных запросов[16].
Для повышения эффективности в узких проходах были предложены гибридные подходы. Один из них — комбинация PRM с методом искусственных потенциальных полей (APF), который используется для увеличения плотности узлов в труднодоступных каналах[17]. Также исследовались комбинированные стратегии выборки, сочетающие случайное сэмплирование с гауссовым[18].
Продолжилось развитие асимптотически оптимальных версий, таких как Lazy-PRM*[19]. Для борьбы с избыточностью графа были предложены методы построения разреженных графов (спаннеров), например SPARS, которые сохраняют возможность находить пути, близкие к оптимальным[19]. Для ускорения поиска по построенной карте стали применять двунаправленный алгоритм A*, а для сглаживания и сокращения итогового пути — техники его «обрезки»[17].
Метод также начали активно адаптировать для задач планирования в многороботных системах с целью координации действий нескольких агентов[20].