Вероятностная дорожная карта (PRM) является сетевым графиком возможных путей в заданной карте, основанным на свободных и занятых пространствах. The 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 по робототехнике и автоматизации. Том 12, № 4, авг. 1996 с. 566 - 580.