Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Планировщик вероятностной дорожной карты [1] - это алгоритм планирования движения в робототехнике, который решает проблему определения пути между начальной конфигурацией робота и целевой конфигурацией, избегая столкновений.

Пример алгоритма вероятностной случайной карты, исследующего возможные пути вокруг ряда многоугольных препятствий.

Основная идея PRM ​​состоит в том, чтобы взять случайные выборки из конфигурационного пространства робота, проверить их, находятся ли они в свободном пространстве, и использовать локальный планировщик, чтобы попытаться связать эти конфигурации с другими соседними конфигурациями. Добавляются начальная и конечная конфигурации, и алгоритм поиска по графу применяется к полученному графу для определения пути между начальной и целевой конфигурациями.

Планировщик вероятностной дорожной карты состоит из двух этапов: этапа построения и этапа запроса. На этапе строительства строится дорожная карта (график), аппроксимирующая движения, которые могут совершаться в окружающей среде. Сначала создается случайная конфигурация. Затем он соединяется с некоторыми соседями, обычно либо с k ближайшими соседями, либо со всеми соседями, находящимися на расстоянии меньше некоторого заранее определенного расстояния. Конфигурации и связи добавляются к графу, пока дорожная карта не станет достаточно плотной. На этапе запроса начальная и конечная конфигурации связаны с графом, а путь получается запросом кратчайшего пути Дейкстры .

При определенных относительно слабых условиях на форму свободного пространства PRM доказуемо вероятностно завершен, что означает, что по мере неограниченного увеличения количества точек выборки вероятность того, что алгоритм не найдет путь, если он существует, приближается к нулю. Скорость сходимости зависит от определенных свойств видимости свободного пространства, где видимость определяется местным планировщиком. Грубо говоря, если каждая точка может «видеть» большую часть пространства, а также если большая часть каждого подмножества пространства может «видеть» большую часть своего дополнения, то планировщик быстро найдет путь.

Авторство изобретения метода PRM принадлежит Лидии Е. Кавраки . [2] [3] Существует множество вариантов базового метода PRM, некоторые из которых довольно сложные, которые изменяют стратегию выборки и стратегию соединения для достижения более высокой производительности. См., Например, Geraerts & Overmars (2002) [4] для обсуждения.

Ссылки [ править ]

  1. ^ Кавраки, LE ; Свестка, П .; Латомбе, Ж.-К. ; Овермарса, MH (1996), "Вероятностные дорожные карты для планирования траектории в многомерных конфигурационных пространствах", IEEE Transactions по робототехнике и автоматизации , 12 (4): 566-580, DOI : 10,1109 / 70,508439 , ЛВП : 1874/17328.
  2. ^ Erbland, Кейт (2013-10-14). «Доктор Лидия Е. Кавраки: женщина, заставляющая роботов работать» . Умственная нить . Проверено 7 октября 2019 .
  3. ^ "Лидия Е. Кавраки назначена лектором Афины ACM 2017-2018" . www.acm.org . Проверено 7 октября 2019 .
  4. ^ Geraerts, R .; Overmars, MH (2002), "Сравнительное исследование вероятностных планировщиков дорожной карты", Proc. Семинар по алгоритмическим основам робототехники (WAFR'02) (PDF) , стр. 43–57 .