Вероятностная маршрутная карта (PRM) - сетевой график возможных путей в данной карте на основе свободных и занятых пространств. mobileRobotPRM объект случайным образом генерирует узлы и создает соединения между этими узлами на основе параметров алгоритма PRM. Узлы соединяются на основе мест препятствий, указанных в Map, и на указанном ConnectionDistance. Можно настроить количество узлов, NumNodes, чтобы соответствовать сложности карты и желанию найти наиболее эффективный путь. Алгоритм PRM использует сеть подключенных узлов для поиска пути без препятствий от начала до конца. Для эффективного планирования пути через среду настройте NumNodes и ConnectionDistance свойства.
При создании или обновлении mobileRobotPRM расположение узлов генерируется случайным образом, что может повлиять на конечный путь между несколькими итерациями. Этот выбор узлов происходит при указании Map сначала измените параметры или update вызывается. Чтобы получить непротиворечивые результаты с одним и тем же размещением узла, используйте rng для сохранения состояния генерации случайных чисел. Пример использования см. в разделе Настройка расстояния соединения rng.
Используйте NumNodes свойство на mobileRobotPRM объект для настройки алгоритма. NumNodes определяет количество точек или узлов, размещенных на карте, которое используется алгоритмом для создания маршрутной карты. Использование ConnectionDistance свойство как порог расстояния, алгоритм соединяет все точки, не имеющие препятствий, блокирующих прямой путь между ними.
Увеличение числа узлов может повысить эффективность тракта, предоставляя более осуществимые пути. Однако повышенная сложность увеличивает время вычислений. Чтобы получить хороший охват карты, может потребоваться большое количество узлов. Из-за случайного размещения узлов некоторые области карты могут иметь недостаточно узлов для подключения к остальной части карты. В этом примере в маршрутной карте создается большое и малое количество узлов.
Загрузите файл карты в виде логической матрицы, simpleMapsи создайте сетку занятости.
load exampleMaps.mat
map = binaryOccupancyMap(simpleMap,2);Создайте простую маршрутную карту с 50 узлами.
prmSimple = mobileRobotPRM(map,50); show(prmSimple)
Создайте плотную маршрутную карту с 250 узлами.
prmComplex = mobileRobotPRM(map,250); show(prmComplex)
Дополнительные узлы увеличивают сложность, но дают больше возможностей для улучшения пути. Учитывая эти две карты, можно рассчитать путь с помощью алгоритма PRM и увидеть эффекты.
Вычислите простой путь.
startLocation = [2 1]; endLocation = [12 10]; path = findpath(prmSimple,startLocation,endLocation); show(prmSimple)
Вычислите сложный путь.
path = findpath(prmComplex, startLocation, endLocation); show(prmComplex)
Увеличение узлов позволяет получить более прямой путь, но добавляет больше вычислительного времени для поиска возможного пути. Из-за случайного размещения точек траектория не всегда является более прямой или эффективной. Использование небольшого числа узлов может сделать пути хуже изображенных и даже ограничить возможность поиска полного пути.
Используйте ConnectionDistance свойство на PRM объект для настройки алгоритма. ConnectionDistance - верхний порог для точек, связанных в маршрутной карте. Каждый узел соединен со всеми узлами в пределах этого расстояния соединения, которые не имеют препятствий между ними. Уменьшая расстояние соединения, можно ограничить количество соединений, чтобы сократить время вычислений и упростить карту. Однако уменьшенное расстояние ограничивает количество доступных путей, по которым можно найти полный путь без препятствий. При работе с простыми картами можно использовать большее расстояние соединения с небольшим количеством узлов для повышения эффективности. Для сложных карт с большим количеством препятствий большее количество узлов с пониженным расстоянием соединения увеличивает вероятность нахождения решения.
Загрузите карту как логическую матрицу, simpleMapи создайте сетку занятости.
load exampleMaps.mat
map = binaryOccupancyMap(simpleMap,2);Создайте маршрутную карту со 100 узлами и рассчитайте путь. Дефолт ConnectionDistance имеет значение inf. Сохраните настройки генерации случайных чисел с помощью функции rng. Сохраненные настройки позволяют воспроизвести те же точки и увидеть эффект изменения ConnectionDistance.
rngState = rng; prm = mobileRobotPRM(map,100); startLocation = [2 1]; endLocation = [12 10]; path = findpath(prm,startLocation,endLocation); show(prm)
Перезагрузите настройки генерации случайных чисел, чтобы в PRM использовались одни и те же узлы. Ниже ConnectionDistance до 2 м. Показать расчетный путь.
rng(rngState); prm.ConnectionDistance = 2; path = findpath(prm,startLocation,endLocation); show(prm)
При использовании mobileRobotPRM объект и изменение свойств, при каждом вызове новой функции объект инициирует точки маршрутной карты и соединения, которые должны быть пересчитаны. Поскольку пересчет карты может быть интенсивным с точки зрения вычислений, можно повторно использовать ту же маршрутную карту, вызвав findpath с различными начальными и конечными расположениями.
Загрузите карту, simpleMap, из .mat файл в виде логической матрицы и создать сетку занятости.
load('exampleMaps.mat')
map = binaryOccupancyMap(simpleMap,2);Создайте маршрутную карту. Узлы и соединения могут выглядеть по-разному из-за случайного размещения узлов.
prm = mobileRobotPRM(map,100); show(prm)
Звонить update или измените параметр для обновления узлов и соединений.
update(prm) show(prm)
Алгоритм PRM пересчитывает размещение узлов и генерирует новую сеть узлов.
[1] Кавраки, Л.Е., П.Свестка, Ж.-С. Латомбе и М.Х. Овермарс. «Вероятностные маршрутные карты для планирования путей в пространствах конфигурации больших размеров», IEEE Transactions on Robotics and Automation. Том 12, № 4, авг. 1996, стр. 566 - 580.