Вероятностные дорожные карты (PRM)

Вероятностная дорожная карта (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)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 3 objects of type image, line, scatter.

Создайте плотную дорожную карту с 250 узлами.

prmComplex = mobileRobotPRM(map,250);
show(prmComplex)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 3 objects of type image, line, scatter.

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

Вычислите простой контур.

startLocation = [2 1];
endLocation = [12 10];
path = findpath(prmSimple,startLocation,endLocation);
show(prmSimple)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 4 objects of type image, line, scatter.

Вычислите сложный контур.

path = findpath(prmComplex, startLocation, endLocation);
show(prmComplex)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 4 objects of type image, line, scatter.

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

Настройте расстояние связи

Используйте 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)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 4 objects of type image, line, scatter.

Перезагрузите настройки генерации случайных чисел, чтобы иметь использование PRM те же узлы. Более низкий ConnectionDistance к 2 м. Покажите расчетный путь.

rng(rngState);
prm.ConnectionDistance = 2;
path = findpath(prm,startLocation,endLocation);
show(prm)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 4 objects of type image, line, scatter.

Создайте или обновите PRM

При использовании mobileRobotPRM объект и свойства изменения, с каждым новым вызовом функции, объект инициировал точки дорожной карты и связи, которые будут повторно вычислены. Поскольку перевычисление карты может быть в вычислительном отношении интенсивным, можно снова использовать ту же дорожную карту путем вызова findpath с различным запуском и конечными местоположениями.

Загрузите карту, simpleMap, от .mat файл как логическая матрица и создает сетку заполнения.

load('exampleMaps.mat')
map = binaryOccupancyMap(simpleMap,2);

Создайте дорожную карту. Ваши узлы и связи могут выглядеть по-другому из-за случайного размещения узлов.

prm = mobileRobotPRM(map,100);
show(prm)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 3 objects of type image, line, scatter.

Вызовите update или измените параметр, чтобы обновить узлы и связи.

update(prm)
show(prm)

Figure contains an axes. The axes with title Probabilistic Roadmap contains 3 objects of type image, line, scatter.

Алгоритм PRM повторно вычисляет размещение узла и генерирует новую сеть узлов.

Ссылки

[1] Kavraki, L.E., П. Свестка, J.-C. Latombe и М.Х. Овермарс. "Вероятностные дорожные карты для планирования пути на высоко-размерных пробелах настройки", Транзакции IEEE на Робототехнике и Автоматизации. Издание 12, № 4, стр августа 1996 566 — 580.

Смотрите также

|

Для просмотра документации необходимо авторизоваться на сайте