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