Вероятностная дорожная карта
Вероятностная дорожная карта [1] Планировщик — алгоритм планирования движения в робототехнике, который решает задачу определения пути между стартовой конфигурацией робота и целевой конфигурацией, избегая при этом столкновений.
Основная идея PRM состоит в том, чтобы взять случайные образцы из пространства конфигурации робота, проверить их на предмет того, находятся ли они в свободном пространстве, и использовать локальный планировщик, чтобы попытаться соединить эти конфигурации с другими близлежащими конфигурациями. Добавляются стартовая и целевая конфигурации, и алгоритм поиска применяется к полученному графу для определения пути между начальной и целевой конфигурациями.
Вероятностный планировщик дорожной карты состоит из двух этапов: этапа построения и этапа запроса. На этапе строительства строится дорожная карта (график), аппроксимирующая движения, которые можно совершать в окружающей среде. Сначала создается случайная конфигурация. Затем он подключается к некоторым соседям, обычно либо к k ближайших соседей, либо ко всем соседям, расположенным на некотором заранее определенном расстоянии. Конфигурации и соединения добавляются в граф до тех пор, пока дорожная карта не станет достаточно плотной. На этапе запроса начальная и целевая конфигурации подключаются к графу, а путь получается с помощью кратчайшего пути Дейкстры запроса .
При определенных относительно слабых условиях на форму свободного пространства PRM является доказуемо вероятностно полным, а это означает, что по мере неограниченного увеличения количества выбранных точек вероятность того, что алгоритм не найдет путь, если он существует, приближается к нулю. Скорость сходимости зависит от определенных свойств видимости свободного пространства, где видимость определяется локальным планировщиком. Грубо говоря, если каждая точка может «видеть» большую часть пространства, а также если большая часть каждого подмножества пространства может «видеть» большую часть своего дополнения, то планировщик быстро найдет путь.
Изобретение метода ФРМ приписывают Лидии Э. Кавраки . [2] [3] Существует множество вариантов базового метода PRM, некоторые из них довольно сложные, которые различают стратегию выборки и стратегию соединения для достижения более высокой производительности. См., например, Герертс и Овермарс (2002). [4] для обсуждения.
Ссылки [ править ]
- ^ Кавраки, LE ; Свестка, П.; Латомбе, Ж.-К. ; Овермарс, М.Х. (1996), «Вероятностные дорожные карты для планирования путей в многомерных конфигурационных пространствах», IEEE Transactions on Robotics and Automation , 12 (4): 566–580, doi : 10.1109/70.508439 , hdl : 1874/17328 .
- ^ Эрбланд, Кейт (14 октября 2013 г.). «Доктор Лидия Э. Кавраки: женщина, заставляющая роботов работать» . Ментальная нить . Проверено 7 октября 2019 г.
- ^ «Лидия Э. Кавраки назначена лектором ACM Athena 2017–2018» . www.acm.org . Проверено 7 октября 2019 г.
- ^ Герертс, Р.; Овермарс, М.Х. (2002), «Сравнительное исследование вероятностных планировщиков дорожных карт», Proc. Семинар по алгоритмическим основам робототехники (WAFR'02) (PDF) , стр. 43–57 .
 | Эта статья, посвященная робототехнике, незавершена . Вы можете помочь Википедии, расширив ее . |