Главная arrow Робототехника arrow Методы скелетирования
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Методы скелетирования Печать

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

Пример применения метода скелетирования приведен на рисунке: это — линия Вороного для свободного пространства, которая представляет собой геометрическое место всех точек, равноудаленных от двух или нескольких препятствий. Для того чтобы осуществить планирование пути с помощью линии Вороного, робот вначале переходит из текущей конфигурации в точку на линии Вороного. Можно легко показать, что такую операцию всегда можно выполнить с помощью передвижения по прямой в пространстве конфигураций. Затем робот следует по линии Вороного до тех пор, пока не достигнет точки, ближайшей к целевой конфигурации. Наконец, робот покидает линию Вороного и движется к цели. И на этом последнем этапе снова выполняется движение по прямой в пространстве конфигураций.

Один из примеров метода скелетирования: линия Вороного — это геометрическое место точек, равноудаленных от двух или нескольких препятствий в пространстве конфигураций (а); вероятностная дорожная карта, состоящая из 400 случайно выбранных точек в свободном пространстве (б)

Таким образом, первоначальная задача планирования пути сводится к поиску пути на линии Вороного, которая обычно является одномерной (за исключением некоторых частных случаев) и имеет конечное количество таких точек, в которых  пересекаются три или большее количество одномерных кривых. Движение по линии Вороного может не обеспечить получение кратчайшего пути, но обнаруженные пути будут отличаться наличием максимальных расстояний от препятствий. Недостатки методов, основанных на использовании линии Вороного, состоят в том, что их сложно применять в пространствах конфигураций с большими размерностями, кроме того, при их использовании приходится совершать слишком большие обходные маневры, если пространство конфигураций характеризуется широким размахом. К тому же может оказаться сложным вычисление линии Вороного, особенно в пространстве конфигураций, характеризующемся сложной формой препятствий.

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