Главная arrow книги arrow Копия Глава 25. Робототехника arrow Методы скелетирования
Методы скелетирования

Альтернативным по отношению к методу на основе линии Вороного является метод с использованием вероятностной дорожной карты. Он представляет собой такой подход к скелетированию, который позволяет определить больше возможных маршрутов и поэтому лучше подходит для пространств с широким размахом. Пример вероятностной дорожной карты показан на рис. 25.15, б. Линия, приведенная на этом рисунке, создана путем формирования случайным образом большого количества конфигураций и удаления тех из них, которые не укладываются в свободное пространство. После этого любые два узла соединяются какой-то линией, если одного из них можно "легко" достичь из другого; например, если в свободном пространстве можно перейти из одного узла в другой по прямой. Конечным итогом выполнения всех этих операций становится создание рандомизированного графа в свободном пространстве робота. Если к этому графу будут добавлены позиции начальной и целевой конфигураций робота, то задача планирования пути сведется к поиску в дискретном графе. Теоретически этот подход является неполным, поскольку при неудачном выборе случайно заданных точек может оказаться, что нельзя найти ни одного пути от начального узла до целевого. Но вероятность такой неудачи можно ограничить за счет регламентации количества формируемых точек и с учетом определенных геометрических свойств пространства конфигураций. Возможно также направить процесс выработки опорных точек в те области, где частично выполненный поиск показывает хорошие перспективы поиска приемлемого пути, действуя одновременно в двух направлениях, от начальной и от целевой позиций. После внесения всех этих усовершенствований метод планирования с помощью вероятностной дорожной карты показывает лучшую масштабируемость в условиях многомерных пространств конфигураций по сравнению с большинством других альтернативных методов планирования путей.