Биард Р.У., МакЛэйн Т.У. Малые БЛА - теория и практика (2015) (1245764), страница 40
Текст из файла (страница 40)
12.5. (a) Поле с неточечными препятствиями. (б) В первую очередь при построенииметодом Вороного маршрута через поле препятствий необходимо вставить точкипо периметру препятствий. (в) Результирующий граф Вороного включает многоневыполнимых соединений, находящихся внутри препятствий или заканчивающихся на них. (г) После того как невыполнимые соединения были удалены, результирующий граф можно использовать для планирования маршрутов через полепрепятствийвключающий соединения с начальной и конечной вершинами, показан нарис.
2.5(в). Однако из рис. 12.5(в) становится очевидным, что граф Вороноговключает много невыполнимых соединений, которые находятся внутри препятствия или заканчиваются на них. Конечный шаг состоит в удалении невыполнимых соединений, как показано на рис. 12.5(г), на котором представлен результирующий оптимальный маршрут.12.1.2. Ìåòîä áûñòðîãî èññëåäîâàíèÿñ ïîìîùüþ ñëó÷àéíûõ äåðåâüåâДругой метод для планирования траекторий через поле препятствий из начальной вершины в конечную носит название метода быстрого исследованияс помощью случайного дерева (RRT). RRT является алгоритмом случайного12.1. Поточечные алгоритмы223исследования, который равномерно, но случайным образом исследует областьпоиска.
Его преимуществом является то, что его можно обобщить на летательные аппараты со сложной нелинейной динамикой. На протяжении всего этогораздела главы предполагается, что все препятствия содержатся на карте местности, которую можно запрашивать для обнаружения возможных столкновений.Алгоритм RRT реализуется с помощью структуры данных, названной деревом. Дерево является специальным случаем ориентированного графа. На рис.12.6 приведено графическое представление дерева. Ребра в дереве направленыот дочерней вершины к своему родителю.В дереве каждая вершина имеет в точности одного родителя, за исключениемкорня графа, который вообще не имеетродителей.
В структуре RRT вершиныпредставляют физические состояния иликонфигурации, а ребра представляют собой приемлемые траектории перемещения между состояниями. Издержки, свяРис. 12.6. Дерево — это специальныйзанные с каждым ребром, cij, являются граф, в котором каждая вершина, за искиздержками, связанными с прокладкой лючением корня, имеет в точности одноприемлемого маршрута между состояния- го родителями, представленными вершинами.Основная идея алгоритма RRT состоит в построении дерева, которое быравномерно исследовало пространство поиска. Равномерность достигается засчет случайной выборки из равномерного распределения вероятности.
Для иллюстрации основной идеи предположим, что вершины представляют собойположения в восточных и северных координатах при постоянной высоте, ипусть издержки ребра между вершинами будут определяться длиной прямолинейной траектории между вершинами.На рис. 12.7 представлен базовый алгоритм RRT. Как показано на рис. 12.7(a),входными данными для алгоритма RRT является начальная ps- и конечнаяpe-конфигурации, а также карта местности. Первый шаг алгоритма состоит вслучайном выборе конфигурации p в рабочем пространстве. Как показано нарис.
12.7(б), новая конфигурация v1 выбирается на фиксированном расстоянииD от ps вдоль линии pp s и вставляется в дерево. На каждом последующем шаге врабочем пространстве создается случайная конфигурация p и просматриваетсядерево для нахождения вершины, которая ближе всего находится к p. Как показано на рис. 12.7(в), новая конфигурация создается фиксированным расстоянием D от ближайшей вершины дерева вдоль линии, соединяющей p с ближайшейвершиной. Прежде чем сегмент маршрута будет добавлен в дерево, его необходимо проверить на наличие возможных столкновений с объектами рельефаместности.
При обнаружении столкновения, как показано на рис. 12.7(г),224Глава 12. Планирование траекторииа)б)Столкновениев)г)д)е)Рис. 12.7. (a) Алгоритм RRT инициализируется с помощью карты рельефа местности и начальной и конечной вершинами. (б) и (в) Граф RRT расширяется за счет случайно создаваемой точки p рельефа местности и планированием маршрута длиной Dв направлении к p. (г) Если результирующая конфигурация неосуществима, тогдаона не добавляется в граф RRT и процесс продолжается, как это показано насегменте рисунка (д).
(е) Алгоритм RRT завершается, когда конечная вершинадобавляется в граф RRTсегмент удаляется и процесс повторяется снова. Когда добавлена новая вершина, проверяется ее расстояние от конечной вершины pe. Если оно меньше, чемD, тогда в дерево добавляется сегмент из pe, как показано на рис. 12.7(е), указывая на то, что найден весь маршрут с учетом рельефа местности.Пусть T — карта рельефа местности и пусть ps и pe будут начальной и конечной конфигурацией на карте.
Приведенный ниже алгоритм 10 основан набазовом алгоритме RRT.12.1. Поточечные алгоритмы225Алгоритм 10. Планирование маршрута алгоритмом RRT: W = planRRT(T, ps, pe)Входные данные: карта рельефа местности T, начальная конфигурация ps, конечная конфигурация pe1: Инициализировать граф G = (V, E) по V = {ps}, E = 0/2: while Конечная вершина pe не присоединена к G, т.e. pe Î/ V do3: p ¬ generateRandomConfiguration(T) (создать случайную конфигурацию)4: v* ¬ findClosestConfiguration(p, V) (найти ближайшую конфигурацию):5: v+ ¬ planPath(v*, p, D)6: if existFeasiblePath(T, v*, v+) (существует осуществимый маршрут), тогда7: Обновить граф G = (V, E) по V ¬ V U{v+}, E ¬ E U{(v*, v+)}8: Обновить издержки ребра в виде C[(v*, v+)] ¬ pathLength(v*, v+) (длина маршрута)9: end if10: if existFeasiblePath(T , v+, pe) (существует осуществимый маршрут), then11: Обновить граф G = (V, E) в виде V ¬ V U{pe} E ¬ E U{(v*, pe)}12: Обновить издержки ребер в виде C[(v*, pe)] ¬ pathLength(v*, pe)(длина маршрута)13: end if14: end while15: W = findShortestPath(G, C) (найти кратчайший маршрут).16: return WВ строке 1 инициализируется граф G RRT, содержащий только начальнуювершину.
Цикл с условием продолжения в строках 2—14 добавляет вершины вграф RRT, пока в него не будет включена конечная вершина, указывая на то,что маршрут от ps к pe был обнаружен. В 3-й строке из рельефа местности в соответствии с равномерным распределением по карте берется случайная конфигурация. В 4-й строке обнаруживается ближайшая вершина v* Î G к случайным образом выбранной точке p. Поскольку расстояние между p и v* можетбыть большим, то в строке 5 планируется маршрут фиксированной длины Dиз v* в направлении к p. Результирующая конфигурация обозначается как v+.Если результирующая траектория осуществима, согласно выполненной в 6-йстроке проверке, тогда в 7-й строке v+ добавляется в G, а в 8-й строке обновляется матрица издержек. В 10-й строке оператор «если» проверяет, можно линовую вершину v+ напрямую соединить с конечной вершиной pe.
Если да, то встроках 11—12 pe добавляется в граф G и алгоритм заканчивается в 15-й строкевозвращением наикратчайшего маршрута G.Результат использования алгоритма 10 для четырех различных случайнымобразом сгенерированных полей препятствий и случайным образом сгенери-226Глава 12. Планирование траекторииа)б)в)г)Рис. 12.8. Результаты алгоритма 10 для четырех случайным образом сгенерированных полейпрепятствий и случайным образом созданных начальной и конечной вершинуказаны пунктирными линиями. Сглаженные траектории, созданные алгоритмом11, указаны сплошными линиямированных начальных и конечных вершин отображается на рис. 12.8 с помощью пунктирной линии. Обратите внимание, что маршруты, созданные алгоритмом 10, иногда бесполезно блуждают и что исключение некоторых вершинможет привести к более эффективным маршрутам.
Алгоритм 11 обеспечиваетпростую схему для сглаживания маршрутов, созданных с помощью алгоритма 10. Основная идея состоит в том, чтобы удалить промежуточные вершины,если осуществимый маршрут все же существует. Результат применения алгоритма 11 показан сплошной линией на рис. 12.8.Имеется множество расширений базового алгоритма RRT. Простое расширение, которое было описано в [74], состоит в расширении дерева одновременно от начальной и конечной вершины и в попытке соединить два деревавместе в конце каждого расширения. В следующих двух подразделах будутприведены два простых расширения, которые представляют интерес дляМБЛА: планирование путевых точек над 3-мерным рельефом местности и использование маршрутов Дубинса для планирования кинематически выполнимых маршрутов в сложном 2-мерном рельефе местности.12.1.
Поточечные алгоритмы227Алгоритм 11. Сглаженная траектория RRT: (Ws, Cs) = smoothRRT(T , W, C)(сглаженная RRT)Входные данные: Карта рельефа местности T, траектория по путевым точкамW = {w1, . . . , wN}, матрица издержек C1: Инициализированная сглаженная траектория Ws ¬ {w1}2: Инициализировать указатель на текущую вершину в Ws: i ¬ 13: Инициализировать указатель на следующую вершину в W: j ¬ 24: while j < N do5: ws ¬ getNode(Ws, i)6: w+ ¬ getNode(W, j + 1)7: if existFeasiblePath (T , ws, w+) = FALSE, тогда (если утверждениео существовании осуществимой траектории неверно, тогда):8: Взять последнюю вершину: w ¬ getNode(W, j)9: Добавить неконфликтную вершину, чтобы сгладить траекторию:Ws ¬ Ws U {w}10: Обновить издержки сглаживания: Cs[(ws, w)] ¬ pathLength(ws, w)(длина маршрута)11: i ¬ i + 112: end if13: j ¬ j + 114: end if15: Добавить последнюю вершину из W: Ws ¬ Ws U {wN}16: Обновить издержки сглаживания: Cs[(wi, wN)] ¬ pathLength(wi, wN)(длина маршрута)17: return WsПланирование путевых точек алгоритмом RRT над 3-мерным рельефомместностиВ этом разделе будет рассмотрено расширение базового алгоритма RRTдля планирования путевых точек траектории над 3-мерным рельефом местности.
Предположим, что карту местности T можно в любом положении опрашивать относительно высоты рельефа. Первостепенный вопрос, на который следует дать ответ при расширении алгоритма RRT до 3-мерного варианта, — какгенерировать высоту в случайных вершинах. Например, один из вариантов состоит в случайном выборе высоты из равномерного распределения высоты надземлей вплоть до максимального предела.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
