Биард Р.У., МакЛэйн Т.У. Малые БЛА - теория и практика (2015) (1245764), страница 41
Текст из файла (страница 41)
Другой вариант состоит в предварительном выборе нескольких уровней высоты с последующим случайным выбором одного из этих уровней.228Глава 12. Планирование траекторииВ этом разделе высота полета будет выбрана фиксированной над уровнемземли hАВНП. Поэтому граф RRT без сглаживания будет по существу 2-мернымграфом, который следует по контуру рельефа местности. На выходе алгоритма10 будет маршрут следования на фиксированной высоте hАВНП над уровнемземли.
Однако с этапом сглаживания, представленным алгоритмом 11, маршруты получаются со значительно меньшими вариациями высоты. Для 3-мерного рельефа местности скорость набора высоты и скорость снижения МБЛАобычно ограничены определенными предельными значениями. Функция existFeasiblePath в алгоритме 10 и 11 может быть изменена так, чтобы удовлетворять требуемой скорости набора высоты и скорости снижения и чтобы былиисключены возможные столкновения.Результаты 3-мерного RRT-алгоритма показаны на рис. 12.9 и 12.10, гдетонкие линии представляют дерево RRT, толстые пунктирные линии представляют траектории RRT, созданные алгоритмом 10, а толстые сплошные линии — сглаженные траектории, созданные алгоритмом 11.а)б)Рис. 12.9.
(a) Вид сверху результатов 3-мерного планирования маршрута на основе алгоритма RRT. (б) Вид сбоку результатов 3-мерного планирования маршрута по путевым точкам с помощью алгоритма RRT. Тонкие линии представляют граф RRT,толстые пунктирные линии представляют маршрут RRT, который возвращает алгоритм 10, и, наконец, толстая сплошная линия соответствует сглаженной траектории. Граф RRT создается при фиксированной высоте над рельефом местностиПланирование траекторий Дубинса с помощью алгоритма RRT в 2-мерномполе препятствийВ этом разделе рассмотрим расширение базового алгоритма RRT для планирования траекторий при условии ограничений на повороты.
Предполагая,что транспортное средство передвигается с постоянной скоростью, оптимальные маршруты между конфигурациями задаются траекториями Дубинса согласно описанию, приведенному в разделе 11.2. Траектории Дубинса планируются между двумя различными конфигурациями, где конфигурация задаетсятремя числами, представляющими северную и восточную координаты и курсо-12.2. Алгоритмы охватаа)229б)Рис. 12.10. (a) Вид сверху результатов 3-мерного планирования маршрута на основе алгоритма RRT.
(б) Вид сбоку результатов 3-мерного планирования маршрута попутевым точкам с помощью алгоритма RRT. Тонкие линии представляют графRRT, толстые пунктирные линии представляют маршрут RRT, который возвращает алгоритм 10, и, наконец, толстая сплошная линия соответствует сглаженной траектории. Граф RRT создается при фиксированной высоте над рельефомместностивой угол в этом положении. Для применения к этому сценарию алгоритмаRRT потребуется метод генерации случайных конфигураций.Будем следующим образом создавать случайную конфигурацию:1.
Случайным образом создается положение в координатах север-восток.2. В графе RRT находим ближайшую вершину до новой точки.3. Выбираем положение на расстоянии L от ближайшей вершины RRT и используем это положение как координаты север-восток новой конфигурации.4. Выбираем курсовой угол для этой конфигурации как угол на линии, которая соединяет новую конфигурацию с деревом RRT.Затем применяется алгоритм RRT, соответствующий приведенному вышеалгоритму 10, где функция pathLength (длина траектории) возвращает длинутраектории Дубинса между конфигурациями.Результаты алгоритма RRT для траекторий Дубинса показаны на рис. 12.11и 12.12, где тонкие линии представляют дерево RRT, толстые сплошные линии — маршрут RRT, созданный алгоритмом 10, а толстая сплошная линия является сглаженным маршрутом, созданным алгоритмом 11.12.2.
Àëãîðèòìû îõâàòàВ этом разделе будут кратко описаны алгоритмы охвата, целью которых является не переход из начальной конфигурации в конечную, а охват как можно большей площади. Алгоритмы охвата используются, например, в проблемах поиска,когда летательный аппарат ищет представляющие интерес объекты в пределах заданного района. Поскольку положение объекта может быть неизвестно, то230Глава 12.
Планирование траекторииа)б)Рис. 12.11. (a) Вид сверху результатов 3-мерного планирования траекторий Дубинса наоснове алгоритма RRT. (б) Вид сбоку результатов 3-мерного планирования маршрута Дубинса с помощью алгоритма RRT. Тонкие линии представляют графRRT, толстые пунктирные линии представляют маршрут RRT, который возвращает алгоритм 10, и, наконец, толстая сплошная линия соответствует сглаженной траектории. Граф RRT создается при фиксированной высоте над рельефомместностиа)б)Рис.
12.12. (a) Вид сверху результатов 3-мерного планирования маршрута на основе алгоритма RRT. (б) Вид сбоку результатов 3-мерного планирования маршрута по путевым точкам с помощью алгоритма RRT. Тонкие линии представляют граф RRT,толстые пунктирные линии представляют маршрут RRT, который возвращает алгоритм 10, и, наконец, толстая сплошная линия соответствует сглаженной траектории. Граф RRT создается при фиксированной высоте над рельефом местностипоиск по заданному району следует выполнять с максимальной степенью однородности.
Конкретный алгоритм, который представлен в этом разделе главы, позволяет использовать априорную информацию о возможном положенииобъектов.Основная идея состоит в использовании двух карт в памяти: карты рельефаместности и возвращаемой карты. Карта рельефа местности используется дляобнаружения возможных столкновений с предметами окружающей среды. Возможность находиться в определенном месте будет смоделирована для возвращаемой величины Yi, где i являются индексами положений на местности.
Для12.2. Алгоритмы охвата231обеспечения однородного охвата области возвращаемая карта инициализируется так, что все местоположения на местности имеют одну и ту же начальнуювозвращаемую величину. По мере посещения мест возвращаемая величина снижается на фиксированную величину в соответствии с выражениемYi [k] = Yi [k 1] c,(12.2)где c — положительная константа. Планировщик маршрута ищет траектории,которые бы обеспечивали максимально возможную возвращаемую величину,получаемую через ограниченное и направленное вперед окно.Базовый алгоритм охвата представлен алгоритмом 12. На каждом шаге алгоритма из текущей конфигурации МБЛА создается дерево просмотра вперед, которое используется для поиска участков местности с большой возвращаемой величиной. В строке 1 с помощью начальной конфигурации инициализируетсядерево просмотра вперед ps, а в строке 8 производится повторная установка дерева для просмотра вперед в текущую конфигурацию.
Можно разработать современные алгоритмы для удержания частей дерева просмотра вперед, которыеуже были исследованы. Возвращаемая карта инициализируется во 2-й строке.Возвращаемая карта будет инициализирована как большое постоянное числоплюс аддитивный шум. Аддитивный шум облегчает выборы на начальных шагахалгоритма, когда необходимо производить поиск по всем участкам местности, ипоэтому он создает равные возвращаемые значения.
После перемещения МБЛАв новый участок местности в соответствии с уравнением (12.2) в строке 9выполняется обновление возвращаемой карты Y. В 5-й строке создается дерево просмотра вперед, которое начинается с текущей конфигурации. ДеревоАлгоритм 12. Планирование траектории охвата: planCover(T, Y, p) (планирование охвата)Входные данные: карта рельефа местности T, возвращаемая карта Y, начальнаяконфигурация ps1: Инициализировать дерево просмотра вперед G = (V, E) в виде V = {ps}, E = 0/2: Инициализировать возвращаемую карту Y = {Yi : i — индексы местности}3: p = ps4: for каждого цикла планирования do5: G = generateTree(p, T , Y) (содать дерево)6: W = highestReturnPath(G) (траектория с максимальной возвращаемой величиной)7: Обновить p, перемещаясь вдоль первого сегмента W8: Переустановить G = (V, E) в виде V = {p}, E = 0/9: Y = updateReturnMap(Y, p) (обновить возвращаемую карту)10: end for232Глава 12.
Планирование траекториипросмотра вперед создается таким образом, чтобы исключить препятствия наместности. В 6-й строке по дереву просмотра вперед G выполняется поиск траектории, которая дает самую большую возвращаемую величину.Имеется несколько методов, которые можно использовать для созданиядерева просмотра вперед (они фигурируют в 5-й строке алгоритма 12); здесьбудут кратко описаны два подходящих метода. В первом методе траектория задается путевыми точками, и дерево просмотра вперед создается конечнымишагами длиной L и, в конце каждого шага позволяет МБЛА переместитьсявперед или менять угол полета на ±J в каждой конфигурации.
Трехступенчатое дерево просмотра вперед для J = р/6 показано на рис. 12.13.Рис. 12.13. Дерево просмотра вперед дерева с глубиной, равной трем, строится из положения (0, 0), в котором L = 10 и J = p/6Результаты использования дерева просмотра вперед в алгоритме 12 приведены на рис. 12.14. На рис. 12.14(a) представлен маршрут через поле препятствий, где дерево просмотра вперед имеет длину L = 5, допустимый выбор направления полета на каждом шаге составляет J = р/6 и глубина просмотровогодерева равна трем. Соответствующая возвращаемая карта после 200 итерацийалгоритма показана на рис.
12.14(a). На рис. 12.14(б) приведены маршруты через поле препятствий, где длина просмотра вперед L = 5, допустимое изменение угла полета на каждом шаге J = р/3 и глубина дерева просмотра впередравна трем. Соответствующая возвращаемая карта после 200 итераций алгоритма показана на рис. 12.14(в). Обратите внимание, что участок охвачен примерно равномерно, но что траектории через отдельные участки часто повторяются, особенно при пересечении плотно заселенных участков.Для создания дерева просмотра вперед в 5-й строке алгоритма 12 использовался алгоритм RRT с траекториями Дубинса.
Для создания дерева просмотра вперед при условии заданной текущей конфигурации используется N шагов12.3. Краткое содержание главыа)б)в)г)233Рис. 12.14. Графики (a) и (в) дают вид сверху результатов работы алгоритма охвата с применением треугольного расширения дерева. Соответствующие возвращаемые карты после 200 циклов планирования (итераций) показаны на графиках (б) и (г).В (a) и (б) допустимое изменение угла полета J = р/6, а в (в) и (г) допустимоеизменение угла полета J = р/3алгоритма расширения дерева RRT. Результаты использования этого алгоритма в 3-мерной городской среде показаны на рис. 12.15. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
