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

Зависимость среднегоРис. 4.6. Зависимость среднего объемавремени расчета от количестваиспользуемой памяти от количествамаршрутных точек - вариант 2маршрутных точек - вариант 24.1.3. Совместное применение процедуры последовательногозапрета подциклов и функции оптимизации cplexbilp пакета CPLEX(вариант 3)Третий вариант программно-алгоритмического обеспечения такжеиспользует процедуру последовательного исключения подциклов, но вотличие от первых двух для решения задачи булева линейногопрограммирования в нем применяется функция cplexbilp пакета CPLEX.Как следует из графика, приведенного на рисунке 4.7, резкий роствремени, необходимого для решения задачи планирования маршрута,начинается в районе 150-160 точек. Таким образом, третий из исследуемыхвариантов по этому показателю оказывается наиболее эффективным.

Объемпамяти, используемой при расчетах, постепенно растет с увеличениемколичества точек в маршруте. При решении задачи с одинаковым104количеством точек в маршруте третий вариант использует примерно на 15%больший объем памяти (рисунок 4.8). Однако это обстоятельство непредставляется существенным, поскольку для современных компьютеровограничения по ресурсу оперативной памяти не является критичным.Рис. 4.7. Зависимость среднегоРис. 4.8.

Зависимость среднего объемавремени расчета от количестваиспользуемой памяти от количествамаршрутных точек - вариант 3маршрутных точек - вариант 34.1.4. Сравнение эффективности вариантовДля удобства сравнения графики, приведенные на рисунках 4.2, 4.5 и4.7, изобразим совместно на рисунке 4.9, а графики, приведенные нарисунке 4.3, 4.6 и 4.8, совместим на рисунке 4.10. Из графиков, приведенныхна рисунке 4.9, хорошо видно, что характер увеличения времени расчета сростомколичестваточек,связываемыхмаршрутом,длявсехрассмотренных вариантов аналогичен.

Когда количество точек достигаетопределенного значения начинается резкий рост времени решения задачи.Это сопровождается неустойчивой работой программного обеспечения,когда решение при некоторых исходных данных получить уже не удается.Для первого варианта программно-алгоритмического обеспечения такойэффект встречается уже начиная с 11 точек, для второго с 45, а для третьегосо 165 точек.105Рис.

4.9. Зависимость среднегоРис. 4.10. Зависимость среднего объемавремени расчета от количестваиспользуемой памяти от количествамаршрутных точекмаршрутных точек4.2. Общая характеристика и архитектура программногокомплекса «UAVRouting»Программно-алгоритмическое обеспечение планирования маршрутаполета БПЛА должно обеспечить выполнение двух основных группопераций. Во-первых, на основе исходных данных задачи планированиямаршрута надо сформировать соответствующую запись задачи булевалинейного программирования.

А, во-вторых, обеспечить решение этойзадачи.Соответственновпрограммноеобеспечениепланированиямаршрута входят две группы программ. Одна из них отвечает заформирование задачи булева линейного программирования, а другаяотвечает за ее решение. Рациональной архитектурой прикладногопрограммного обеспечения в такой ситуации будет программное ядро,обеспечивающеесобственнорешениезадачибулевалинейногопрограммирования и периферийное программное обеспечение обработкиисходных данных для формирования записи указанной задачи (рисунок4.11). Для реализации ядра целесообразно использовать стандартноепрограммное обеспечение. Это позволяет существенно экономить время на106написание программ, упрощает их верификацию и обеспечивает высокуювычислительную производительность.Модуль формирования записизадачи булева линейногопрограммированияМодульвизуализациирешения задачимаршрутизацииЯдроМодуль решения задачибулева линейногопрограммированияМодуль проверкиналичия подцикловв полученномрешенииМодуль формирования дополнительногоограничения для исключения одного изподцикловРис.

4.11. Архитектура программного комплекса «UAVRouting»При выборе конкретного стандартного обеспечения необходимокроме его функциональных возможностей учесть его фактическуюдоступность. С учетом сказанного весьма перспективными представляютсятакие программные продукты как MATLAB и CPLEX. Однако следуетотметить, что процедуры bintprog и cplexbilp, входящие в эти продукты,обеспечивают решение задачи о назначениях. Для решения с их помощьюзадач планирования маршрута необходимо обеспечить исключение извозможных решений задачи о назначениях решений, соответствующих такназываемым подциклам, то есть маршрутам короче гамильтонова контура.А при рассмотрении более сложных постановок задач планированиямаршрута с дополнительными ограничениями необходимо не простоисключить подциклы, а предусмотреть их специальную обработку.

Задачи,решаемые периферийным программным обеспечением, являются восновном высоко специализированными, поэтому использовать для его107реализации стандартные программы затруднительно. Однако и требования,предъявляемые к нему, например, в части быстродействия, объективноявляются менее жесткими.Архитектура разработанного программного комплекса являетсяоткрытой и предполагает дальнейшее расширение функциональныхвозможностей.Программный комплекс состоит из блоков, выполняющих следующиеосновные операции: Вычисление минимального времени перелета между точками сучетом наличия ветра в зоне полета; Формирование записи задачи булева линейного программирования;Решение задачи булева линейного программирования сиспользованием функции cplexbilp; Проверка наличия подциклов в полученном решении;Формирование дополнительного ограничения для исключенияподциклов; Визуализация решения задачи планирования маршрута.Программный комплекс «UAVRouting» реализован с помощьювстроенного языка программирования пакета MATLAB, являющегосявесьма удобным инструментом для решения технических и научных задач.Комплекс «UVARouting» включает в себя ряд подпрограмм, совместнаяработа которых обеспечивает проведение расчетов оптимального маршрутаполета БПЛА.

Программно-алгоритмическое обеспечение разработано наоснове совместного применения процедуры последовательного запретаподциклов и функции оптимизации cplexbilp пакета CPLEX.Программный комплекс обеспечивает решение следующих задач:- Задача планирования замкнутого маршрута полета без ограниченияна продолжительность полета;108-Задачапланированияразомкнутогомаршрутаполетабезограничения на продолжительность полета, если точки начала и окончаниямаршрута заданы;-Задачапланированияразомкнутогомаршрутаполетабезограничения на продолжительность полета, если точка начала маршрутазадача, а точка окончания выбирается;-Задачапланированияразомкнутогомаршрутаполетабезограничения на продолжительность полета, если точка окончания маршрутазадача, а точка начала выбирается;-Задачапланированияразомкнутогомаршрутаполетабезограничения на продолжительность полета, если точки начала и окончаниямаршрута не заданы и выбираются;- Задача планирования замкнутого маршрута полета с ограничениемна продолжительность полета для равноценных точек;-Задачапланированияразомкнутогомаршрутаполетасограничением на продолжительность полета для равноценных точек, еслиточки начала и окончания маршрута заданы.-Задачапланированияразомкнутогомаршрутаполетасограничением на продолжительность полета для равноценных точек, еслиточка начала маршрута задача, а точка окончания выбирается;-Задачапланированияразомкнутогомаршрутаполетасограничением на продолжительность полета для равноценных точек, еслиточка окончания маршрута задача, а точка начала выбирается;-Задачапланированияразомкнутогомаршрутаполетасограничением на продолжительность полета для равноценных точек, еслиточки начала и окончания маршрута не заданы и выбираются.4.3.

Графический интерфейс пользователя программного комплекса«UAVRouting»Графический интерфейс пользователя делится на 3 части:1091. Часть для ввода входных данных2. Часть для выбора типа решаемой задачи маршрутизации3. Часть для вывода информации об оптимальном маршруте.Входными данными для программного комплекса UVARoutingявляются количество точек (Amount of points), параметры ветра, а именномодуль скорости ветра (wind speed) и угол направления ветра (wind directionangle), воздушная скорость БПЛА (UAV speed), координаты точек(coordinates of points), которые желательно включить в маршрут испециальные ограничения, например, точка начала (start point), точкаокончания (finish point) и допустимое время полета (allowable time).

Окновизуализации входных данных приведено на рисунке 4.12. Предусмотренотри варианта ввода координат маршрутных точек. Ввод вручную (inputmanually), ввод из excel-файла (input excel data) и ввод с помощью датчикаслучайных чисел (input random).Рис. 4.12. Окно ввода данныхВыбор вида решаемой задачи выполняется с помощью панелиуправления «Control panel», которая изображена на рисунке 4.13.110Рис.

4.13. Панель управленияВыходныеданныепрограммногокомплексапредставляемыеграфически выводятся в двух окнах. В них показывается распределениезаданных маршрутных точек (Distribution of given points and wind direction)и оптимальный маршрут полета (Optimal flight route). В качестве выходныхданных также отображается маршрут в виде последовательности номеровмаршрутных точек (Optimal flight route), продолжительность полета пооптимальному маршруту (Flight time of optimal route) и время расчетамаршрута (Calculation time of software). Визуализация этой частиизображена на рисунке 4.14.Рис.

4.14. Окно вывода данных111Общий вид графического интерфейса пользователя программногокомплекса «UAVRouting» представлен на рисунке 4.15.Рис. 4.15. Общий графический интерфейс пользователя программногокомплекса «UAVRouting»4.4. Описание основных функций программного комплекса«UAVRouting»В данном разделе описаны все функции программного комплекса«UAVRouting», их назначение, входные и выходные параметры.Функция flot_routeОбщие сведения о программеПрограмма-функция «flot_route» позволяет вывести оптимальныймаршрут на графике. Не используются подпрограммы.

Используетсянесколько стандартных программ-функции (if, else, for, isempty, axis, plot,xlabel, ylabel, hold on).112Функциональное назначениеПрограмма-функция «flot_route» позволяет вывести оптимальныймаршрут на графике.Описание обращения к программеflot_route(xy,N,p1,p2,s1,f1,Td)Описание входных данныхxy - матрица координат точек;N - количество точек;p1 - индекс по строке полученного решения;p2 - индекс по столбцу полученного решения;s1 – номер точки начала маршрута;f1 – номер точки окончания маршрута;Td - допустимое время полета.Описание выходных данныхИзображение оптимального маршрутаФункция formogr1Общие сведения о программеПрограмма-функция «formogr1» предназначена для формированияматрицы ограничений типа неравенств A и вектора правых частей типанеравенств b.

Подпрограммы не используются. Используется стандартныепрограммы-функции (for, if, elseif, zeros).Функциональное назначениеПрограмма-функция «formogr1» дает возможность формироватьматрицу ограничений типа неравенств A и вектора правых частей типанеравенств b.Описание обращения к программеformogr1 (nshag, Anew, c, c2, x0, n, A, b)Описание входных данных113nshag - номер шага;Anew - массив хранения матриц учета подциклов;c - матрица учета завершения обработки подциклов;c2 - матрица обозначения заполнения матриц;x0 - исходный массив, созданный в процессе работы функцииsozdmatr1;n - количество точек;A - матрица с коэффициентами линейных ограничений типанеравенств A * x  b ;b - вектор правой части линейных ограничений типа неравенств.Ввод значений входных данных осуществляется в командном окнеMATLAB перед обращением к процедуре, либо при обращении к ней путемуказания фактических значений входных параметров. Возможно обращениек процедуре formogr1 из внешней по отношению к ней программе.Описание выходных данныхВыходные параметры программы-функции:- A1 - матрица с коэффициентами линейных ограничений типанеравенств A * x  b ;- b1 - вектор правой части линейных ограничений типа неравенств.Функция matr_timeОбщие сведения о программеПрограмма-функция «matr_time» позволяет рассчитать матрицунаискорейшеговремениперелетамеждуточкамисизвестнымикоординатами, с учетом постоянного ветра в зоне полета.