Биард Р.У., МакЛэйн Т.У. Малые БЛА - теория и практика (2015) (1245764), страница 39
Текст из файла (страница 39)
Реактивное планирование перемещений, с другой стороны, хорошо подходит длядинамических сред, особенно для исключения столкновений, когда информация неполная и неопределенная, но ему не хватает способности задавать и вести схему перемещений.В этой главе акцент делается на методе совещательного планирования, которое представляется эффективным для малых летательных аппаратов. В совещательных подходах траектории МБЛА планируются в явном виде. Недостатком совещательных подходов является то, что они сильно зависят от моделей,используемых для описания состояния окружающего мира и движения летательного аппарата.
К сожалению, точное моделирование динамики атмосферы илетательного аппарата невозможно. В целях компенсации этой неотъемлемойнеопределенности алгоритмы планирования маршрута должны регулярно запускаться во внешнем контуре обратной связи. Поэтому важно, чтобы алгоритмы планирования были эффективны в вычислительном плане. Для сокращения требуемых расчетов будут использоваться простые навигационныемодели низкого порядка для летательного аппарата и моделями с постояннымветром для атмосферы.
Предполагается, что для работы алгоритмов планирования перемещений можно использовать карту возвышенностей местности.Препятствия, которые известны априори, представлены на карте возвышенностей местности.В этой главе описываются несколько простых и эффективных алгоритмовпланирования траектории полета, которые подходят для МБЛА.
Методы, которые здесь представляены, ни к коей мере не являются исчерпывающими имогут не быть наилучшими из всех возможных методов. Однако известно, что12.1. Поточечные алгоритмы217они обеспечивают приемлемое введение в область планирования траекторий.Что касается приведенной на рис. 1.1 архитектуры, то в этой главе представлена разработка планировщика траекторий. Описаны алгоритмы планированиятраекторий для решения проблем двух типов. В разделе 12.1 будет рассмотрено поточечное решение проблем, когда целью является планирование маршрута по путевым точкам из одной точки в другую через поле препятствий.В разделе 12.2 будут рассмотрены проблемы охвата, когда целью является планирование маршрута по любым точкам так, чтобы МБЛА охватил всю площадь определенной территории.
Выходными данными алгоритмов планирования траекторий, разработанных в этой главе, будет либо последовательностьпутевых точек, либо последовательность конфигураций (путевая точка плюсориентация), и поэтому они будут стыковаться с алгоритмами управления траекторией, разработанными в гл. 11.12.1. Ïîòî÷å÷íûå àëãîðèòìû12.1.1. Ãðàôû ÂîðîíîãîГраф Вороного особенно хорошо подходит для решения задач, требующих маневрирования МБЛА через густозаселенное воздушное пространство с препятствиями, которые малы по сравнению с радиусом поворота летательного аппарата.
Относительный размер позволяет моделировать препятствия как точки снулевой площадью. Метод Вороного в основном ограничен планированиемтраекторий в 2,5-мерном пространстве (или в трехмерном пространстве с постоянной предварительно заданной высотой полета), где высота в каждой вершине графа зафиксирована на карте.При условии конечного набора точек (множества) Q в R2 граф Вороногоделит R2 на Q выпуклых ячеек, каждая из которых содержит в точности однуточку множества Q. Граф Вороного составляется таким образом, что внутренняя часть каждой выпуклой ячейки ближе всего к привязанной к ней точке,чем к любой другой точке множества Q. Пример графа Вороного показан нарис.
12.1.Основной особенностью графа Вороного, который делает ее полезным дляпланирования траектории МБЛА, является то, что ребра графа представляютсобой перпендикулярные биссектрисы между точками множества Q. Поэтомуследование по ребрам графа Вороного потенциально создает траектории,которые исключают столкновение с точками набора Q. Однако на рис. 12.1показано несколько потенциальных ловушек, которые возникают при использовании графа Вороного.
Прежде всего, ребра графа, которые тянутся до бесконечности, очевидно, не являются хорошими потенциальными траекториямиГлава 12. Планирование траекторииСеверная координата (км)218Восточная координата (км)Рис. 12.1. Пример графа Вороного с множеством Q из 20 точек препятствийпо путевым точкам. Во-вторых, даже для ячеек Вороного с конечной площадью следование по ребрам графа Вороного может привести к неоправданнодлинным путешествиям. И, наконец, обратите внимание, что для двух точек внижнем правом углу рис.
2.1 граф Вороного создает ребро между двумя этимиточками; однако, поскольку вершина находится так близко к этим точкам,соответствующая траектория, проходящая по путевым точкам, может оказаться неосуществимой.Имеются хорошо зарекомендовавшие себя и широкодоступные алгоритмыдля построения графов Вороного. Например, Matlab имеет встроенную функцию Вороного, а C++-реализации этой функции имеют свободный доступ вИнтернете. При условии доступности программы Вороного не будет описано использование этого алгоритма.
Для получения дополнительных сведенийсм. [70, 71, 72].Для использования графа Вороного для поточечного планирования траектории положим, что G = (V, E) является графом, созданным алгоритмом Вороного на множестве Q. Множество вершин V дополняется требуемыми начальным и конечным положениямиV+ = V U {ps, pe},где ps — начальное положение и pe — конечное положение. Множество ребер Eзатем дополняется ребрами, которые соединяют начальную и конечную вершины с тремя ближайшими вершинами множества V. Соответствующий графпоказан на рис. 12.2.219Северная координата (км)12.1. Поточечные алгоритмыВосточная координата (км)Рис. 12.2.
Диаграмма Вороного для множества Q, дополненного начальной и конечной вершинами с ребрами, которые соединяют начальную и конечную вершину QСледующий шаг — назначить издержки каждому ребру графа Вороного.Издержки ребра могут быть оценены различными способами. Для иллюстративных целей предположим, что издержки обхода каждой точки зависят отдлины траектории и расстояния от этой траектории до точек множества Q.Геометрия получения метрики приведена на рис. 12.3.Рис. 12.3. Штрафные санкции, назначаемые каждому ребру графа Вороного, пропорциональны длине траектории| | v1 v2 | | и обратной величине минимального расстоянияот траектории до точки множества QОбозначим вершины ребра графа через v1 и v2. Длина ребра задается | | v1 v2 | |. Любая точка отрезка линии может быть записана какw(у) = (1 у)v1 + уv2,где у Î [0, 1]. Минимальное расстояние между p и ребром графа может бытьвыражено какD(v 1 , v 2 , p) @ min p - w(s) = minsÎ[ 0,1 ]sÎ[ 0,1 ](p - w(s)) T (p - w(s)) == minp T p - 2 (1 - s)sp T v 1 - sp T v 2 + (1 - s) 2 v 1T v 1 + 2 (1 - s)sv 1T v 2 + s 2 v T2 v 2 == minp - v 1 | | 2 +2 s(p - v 1 ) T (v 1 - v 2 ) + s 2 v 1 - v 2sÎ[ 0,1 ]sÎ[ 0,1 ]2.220Глава 12.
Планирование траекторииЕсли у не ограничена, тогда ее оптимизирующая величина равнаs* =(v 1 - p) T (v 1 - v 2 )v1 - v 22иw(s* ) =p - v12-((v 1 - p) T (v 1 - v 2 )) 2v1 - v 22.Если задатьì w(s* )ïD¢ (v 1 , v 2 , p) = í p - v 1ïî p -v2при s* Î [0,1]при s* < 0 ,при s* > 1тогда расстояние между точкой множества Q и отрезком прямой линии v 1 v 2дается выражениемD(v 1 , v 2 ,Q) = min D¢ (v 1 , v 2 , p).pÎQИздержки для этого ребра, задаваемого (v1, v2), назначаются какJ (v 1 , v 2 ) = k1 v 1 - v 2 +k2,D(v 1 , v 2 ,Q)(12.1)где k1 и k2 являются положительными весовыми множителями.
Первый членуравнения (12.1) является длиной ребра, а второй член — обратная величинарасстояния от ребра до ближайшей точки множества Q.На конечном шаге следует найти граф Вороного, чтобы установить самыенизкие издержки траектории из начальной до конечной вершины. Имеетсямножество методов поиска графа, который мог бы подойти для завершенияэтого задания [72]. Хорошо известным алгоритмом с легкодоступной программой является алгоритм Дейкстры [73], который имеет вычислительную сложность, равную O (|V |). Пример траектории, которую можно найти с помощьюалгоритма Дейкстры при k1 = 0,1 и k2 = 0,9, показан на рис.
12.4.Псевдопрограмма для метода планирования маршрута Вороного приведенав алгоритме 9. Если в множестве Q недостаточно точечных препятствий, результирующий граф Вороного будет разреженным и может потенциальноиметь много ребер, стремящихся в бесконечность. Для исключения подобныхситуаций в алгоритме 9 требуется, чтобы Q имело не менее 10 точек. Это число, безусловно, произвольное. В 1-й строке выполняется построение графаВороного с использованием стандартного алгоритма.
В строке 2 в граф Вороного добавляются начальная и конечная точки, а ребра между начальной и конечной точками и ближайшими вершинами множества Q добавляются в 3—4-й строках. Издержки ребра назначаются в 5—7-й строках в соответствиис уравнением (12.1), а траектория с путевыми точками задается с помощьюпоиска алгоритмом Дейксты в 8-й строке.221Северная координата (км)12.1. Поточечные алгоритмыВосточная координата (км)Рис.
12.4. Оптимальный маршрут через граф ВороногоАлгоритм 9. Планирование маршрута Вороного: W = planVoronoi(Q, ps, pe)(планирование маршрута графом Вороного)Входные данные: Точки препятствий Q, начальное положение ps, конечное положение peТребование: |Q| ³ 10, при необходимости, случайным образом добавляемыеточки.1: (V, E) = constructVoronoiGraph(Q) (построить граф Вороного)2: V+ = VU{ps}U{pe}3: Найти {v1s, v2s, v3s}, три ближайшие точки в V к ps, и {v1e, v2e, v3e}, три ближайшие токи в V к pe4: E+ = E U i = 1, 2, 3 (vis, ps) U i = 1, 2, 3 (vie, pe)5: for каждого элемента (va, vb) Î E выполнить6: Присвоить издержки ребра Jab = J (va, vb) согласно уравнению (12.1).7: end for8: W = DijkstraSearch(V+, E+, J) (поиск методом Дейкстры)9: return WОдним из недостатков метода Вороного, представленного алгоритмом 9, является то, что он ограничен точечными препятствиями.
Однако существует прямое обобщение для неточечных препятствий. Например, представим поле препятствий, показанное на рис. 12.5(a). Граф Вороного может быть построенпутем добавления точек по периметру препятствия, которое превышает определенный размер, как показано на рис. 12.5(б). Связанный с этим граф Вороного,222Северная координата (м)Северная координата (м)Глава 12. Планирование траекторииб)Северная координата (м)Восточная координата (м)а)Северная координата (м)Восточная координата (м)Восточная координата (м)Восточная координата (м)в)г)Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
