Диссертация (Планирование маршрута полета легкого беспилотного летательного аппарата с учетом действия ветра), страница 10

Математически решение обсуждаемой задачиотыскания замкнутого маршрута облета максимального количества точек сучетом ограничения на время полета сводится к нахождению n(n1)72булевых переменных x ∊ {0,1}, (i, j = 1, n; i ≠ j), которые максимизируют(3.1) при выполнении условий (3.2) – (3.7), дополненных условием,исключающим в решении возможные подциклы. Найденные в результатепеременные однозначно опишут искомый оптимальный маршрут полета.3.1.3. Процедура и анализ решения основной задачи планированиямаршрута облета равноценных точек с учетом ограничения напродолжительность полетаПолучение точного решения задачи, математическая постановкакоторой была сформулирована выше, с ростом ее размера быстропревращается в достаточно сложную проблему.

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

Исключать следует только те подциклы,которые не содержат точку «старт – финиш». Соответственно условиемзавершения расчетов является нахождение подцикла, который является врешении единственным и содержит точку «старт – финиш».Рассмотрим в качестве иллюстративного примера нахождениезамкнутого маршрута облета 10 точек, расположение которых в зоне полета,73имеющей размер 10 × 10 километров, было сгенерировано с помощьюдатчика равномерно распределенных случайных чисел. Координаты этихточек в системе координат, жестко связанной с земной поверхностью,приведены в таблице 3.1.

В качестве точки старта – финиша была заданаточка с номером s = 1. Воздушная скорость БПЛА при расчетахпринималась равной 18,05 м/с, а скорость юго-западного ветра равной 9,72м/с.Таблица 3.1. Координаты точек маршрута облета (n = 10)Координатыx (м)y (м)197006300290001700353009900Номер точки45672700 300 4300 1700700 7700 7700 5000830047009600040001070009700Размещение точек в зоне полета, направление ветра и результатырешения рассматриваемой основной задачи планирования маршрута длянескольких значений допустимого времени полета Tдоп.

приведены нарисунке 3.2. Там же для каждого варианта маршрута указано время полетаT по этому маршруту.Как следует из рисунка 3.2 при допустимом времени полета равном2500 с, удалось найти маршрут, который связал все заданные точки. Но ужепри допустимом времени полета равном 2200 с, ни одного маршрута,связывающего все точки, не оказалось. Одной из них пришлось«пожертвовать».

Дальнейшее уменьшение допустимого времени полетаприводит к «потере» в маршруте все большего количества точек.74Тдоп. = 1900 с.Тдоп. = 2500 с.Тдоп. = 2200 с.Т = 2460 с.Т = 2105 с.Тдоп. = 1800 с.Тдоп. = 1700 с.Т = 1729 с.Т = 1849 с.Т = 1461 с.Рис. 3.2. Результаты решения основной задачи при различных значенияхдопустимой продолжительности полетаИнтересно отметить, что если число точек, которые удается включитьв маршрут, с уменьшением допустимого времени полета постоянноуменьшается,товобщемслучаененаблюдаетсяопределеннойзакономерности по отношению к номерам точек, исключаемых измаршрута. Например, когда допустимое время полета уменьшаясь сталоравным 1700 с, одна точка, ранее исключенная из маршрута, вернулась внего снова, но была исключена одна точка, которая до этого всегда входилав маршрут.

Это означает, что процесс выбывания точек из маршрута по мереуменьшения допустимого времени полета в общем случае не являетсярегулярным.Вполнеестественнопредположить,чтоосновнаязадачапланирования маршрута имеет множество решений. Действительно,применительно к рассматриваемому примеру, при допустимом времени75полета равном 1800 с, значение критерия n∗ = 7 достигается на несколькихмаршрутах (рисунок 3.3).T=1729 с.T=1735 с.T=1793сT=1732 сT=1785 с.Рис. 3.3. Все маршруты, на которых обеспечивается значение критерияn* = 7, при допустимом времени полета Tдоп.

= 1800с.Все эти маршруты и фактическое время полета по ним приведены втаблице 3.2.Таблица 3.2. Все маршруты, на которых обеспечивается значение критерияn* = 7, при допустимом времени полета Tдоп. = 1800с.№12345Маршруты1-9-7-5-6-3-10-11-9-8-7-6-3-10-11-2-9-7-6-3-10-11-10-3-5-8-7-9-11-10-3-6-8-7-9-1Факт. время полета (с)17291735178517931732Для наглядности эти пять маршрутов удобно изобразить в виде точеккак это показано на рисунке 3.4.76Рис. 3.4.

Множество маршрутов, на которых обеспечивается значениекритерия n* = 7, при допустимом времени полета Tдоп. = 1800с.При этом хорошо видно, что продолжительность полета T по каждомуиз этих маршрутов имеет свое конкретное значение, которое естественно непревышает допустимого. Общую картину влияния значения допустимоговремени полета на величину достигаемого значения критерия можноувидеть на графике n∗ Tдоп. ,приведенном на рисунке 3.5. Располагая такимграфиком, построенным для конкретной целевой обстановки, значенийпараметров ветра и воздушной скорости БПЛА можно без дополнительныхрасчетов определить максимальное количество точек n∗, которое можносвязатьмаршрутомприконкретномзначениидопустимойпродолжительности полета.

Наискорейшее время облета для каждого извозможных значений n∗ отражено на рисунке 3.5.77246021051849172914611205978782573Рис. 3.5. Зависимость величины достигаемого критерия в основной задачепланирования маршрута от допустимой продолжительности полета.Однако в конечном итоге при решении задачи планирования маршрутаинтерес представляет только один маршрут из множества маршрутов,обеспечивающих экстремум основной задачи планирования маршрута. Этонаискорейший маршрут из этого множества. Для определения этогомаршрута не требуется знать все множество маршрутов, являющихсярешением основной задачи планирования маршрута.

Искомый, то естьнаискорейший маршрут можно определить в результатерешениявспомогательной задачи планирования маршрута используя значение n∗,найденное при решении основной задачи.3.1.4. Математическая постановка вспомогательной задачиВспомогательная задача планирования маршрута представляет собойзадачу поиска маршрута наискорейшего облета n∗точек из n заданных. Вкачестве критерия для этой задачи выступает время полета, которое следуетминимизировать:78x t → min (i ≠ j). (3.8)Искомое множество переменных x ∊ { , 1}, (i, j = 1, n; i ≠ j) должноудовлетворять ограничениямx = n∗ (i ≠ j), (3.9)x ≤ 1(j = 1, n; j ≠ s),(3.10)x ≤ 1(i = 1, n; i ≠ s),(3.11)x = 1(i ≠ s),(3.12)x = 1(j ≠ s),(3.13)x −x = 0(j = 1, n; j ≠ s).(3.14)Ограничение (3.9) обеспечивает включение в маршрут ровно n∗ точек.Смыслограничений(3.10)–(3.14)аналогиченсоответствующимограничениям (3.3) – (3.7).3.1.5.

Решение вспомогательной задачи для модельного примераПроцедура решения вспомогательной задачи аналогична процедуререшения основной задачи планирования маршрута. Устранение подцикловпри решении вспомогательной задачи осуществляется так же, как и в79основной задаче планирования маршрута. Маршрут, найденный врезультате решения вспомогательной задачи, является одновременноискомым решением задачи оптимального планирования маршрута с учетомограничения на время полета. На рисунке 3.6 показан оптимальныймаршрут для допустимого времени полета, равного 1800 с.

При этоммаршрутом удается связать семь точек из десяти заданных.T=1729 с.Рис. 3.6. Оптимальный маршрут при Tдоп. = 1800с.3.1.6. Пример составления оптимального маршрута облетаравноценных точек с учетом ограничения на продолжительностьполетаДля демонстрации работоспособности алгоритма рассматриваетсявторойпримеррасчетазамкнутогомаршрутаоблета50точек,расположенных в зоне полета размером 30 × 30 километров. Координатыточек приведены в таблице 3.3. В качестве точки старта – финиша былазадана точка с номером s = 1. Воздушная скорость БПЛА при расчетахпринималась равной 18,05 м/с, а скорость юго-западного ветра равной 9,72м/с. Допустимое время полета Tдоп = 10300с.80Таблица 3.3.