Содержание к диссертации
Введение
ГЛАВА 1. Анализ современных методов и алгоритмов распределенного исследования территории 15
1.1. Методы организации взаимодействия членов группы 15
1.2. Разбиение территории
1.2.1. Алгоритмы кластеризации территории 20
1.2.2. Алгоритм наложения прямоугольной сетки 25
1.2.3. Структуры данных для представления информации о зонах 28
1.3. Задача о назначениях 34
1.3.1. Алгоритмы решения задачи о назначениях 34
1.3.2. Алгоритм последовательного выбора
1.4. Задача коммивояжёра 43
1.5. Выводы 44
ГЛАВА 2. Разработка математической модели БПЛА с видеодатчиком на борту 46
2.1. Состояния БПЛА и видеодатчика 46
2.1.1. Состояния БПЛА 46
2.1.2. Состояния видеодатчика 48
2.1.3. Состояния БПЛА с видеодатчиком 49
2.2. БПЛА с видеодатчиками на борту 51
2.2.1. БПЛА с одним видеодатчиком 51
2.2.2. Описание кадра 53
2.2.3. БПЛА с несколькими видеодатчиками 55
2.3. Сведение задачи обследования территории к задаче о
назначениях 59
2.3.1. Требования к разбиению территории на зоны 59
2.3.2 Сведение задачи обследования территории к задаче о назначениях 61
2.4. Выводы 63
ГЛАВА 3. Разработка системы предполетного квазиоптимального определения маршрутов группы БПЛА 64
3.1. Алгоритм последовательного выбора 64
3.1.1. Представление территории в виде клеточного автомата 64
3.1.2. Время работы БПЛА 67
3.1.3. Расход энергоресурса 70
3.1.4. Алгоритм последовательного выбора 71
3.2. Сравнение функций приемлемости 75
3.2.1. Максимизация ценности 75
3.2.2. Минимизация расстояния 77
3.2.3. Обобщенная функция приемлемости 80
3.3. Двухэтапная оптимизация 82
3.3.1. Идея метода 82
3.3.2. Сначала ценность потом расстояние 83
3.3.3. Сначала расстояние потом ценность 88
3.3.4. Сравнение методов 92
3.4. Минимизация пересечений траекторий 94
3.4.1. Недопущение пересечения траекторий 94
3.4.2. Недопущение прохождения через реперные точки других БПЛА 96
3.4.3. Модифицированный алгоритм последовательного выбора 99
3.5. Метод идентификации столкновений 105
3.5.1. Определение положения БПЛА в произвольный момент времени 105
3.5.2. Идея метода 112
3.5.3. Реализация метода 1 3.6. Алгоритм синхронизации 117
3.7. Обобщенный алгоритм предполетного определения маршрутов группы БПЛА 122
3.8. Структура системы предполетнего определения маршрутов 124
3.9. Выводы 127
ГЛАВА 4. Проверка системы предполетного определения маршрутов группы БПЛА 129
4.1. Логическая структура системы моделирования 129
4.2. Функциональная модель системы 131
4.3. Программное моделирование системы 134
4.4. Моделирование алгоритмов 137
4.5. Экспериментальная проверка 141
4.6. Выводы 143
Заключение 144
Список литературы
- Структуры данных для представления информации о зонах
- БПЛА с видеодатчиками на борту
- Алгоритм последовательного выбора
- Программное моделирование системы
Введение к работе
Актуальность темы. Сборочные работы являются важной составляющей технического процесса выпуска промышленных изделий особенно при массовом их производстве. Установлено, что ручная сборка изделий в машиностроении составляет 80% от общего объема сборочных работ. Поэтому увеличение доли автоматизированной и автоматической сборки в общем объеме сборочных работ является актуальной научно-технической и производственной задачей.
В настоящее время для автоматизации сборочных работ в основном используются системы автоматического распознавания (САР) с одной видеокамерой. Эти САР работают при жестко фиксированном расположении деталей в поле зрения системы и в заданных положениях, что требует много ручной подготовительной работы. Кроме того, в них применяются для распознавания объектов наборы признаков с различными единицами измерения, что затрудняет их совместное использование для повышения надежности распознавания. Однокамерные САР, в основном, предназначены для распознавания плоских объектов и с их помощью не могут быть решены задачи распознавания и определения координат, произвольно расположенных в поле зрения системы объемных деталей. Поэтому, для распознавания и определения координат, произвольно расположенных в поле зрения системы как плоских, так и объемных деталей целесообразно применение САР с двумя видеокамерами.
Наиболее известными фирмами, занимающимися созданием и выпуском САР для распознавания трехмерных объектов (ТО), являются Balluff (Германия), Omron (Япония), IFM Electronic (Германия), SICK (Германия). Стоимость технической части выпускаемых этими фирмами САР составляет от 14 до 50 тыс. долларов США, а программное обеспечение часто оказывается специализированным и его стоимость больше стоимости технической части системы. Кроме того, при использовании этих систем возникают сложные задачи стыковки их с роботами манипуляторами. В связи с этим, у нас в стране во многих учреждениях, таких, как ЮЗГУ (г. Курск), ПТУ (г. Пенза), МГУ имени М. В. Ломоносова (г. Москва), университет ИТМО (г. Санкт-Петербург), ПГТУ (г. Йошкар-Ола), ИПМ имени М.В. Келдыша РАН (г. Москва), ГУАП (г. Санкт-Петербург), НГТУ (г. Новосибирск), и др., ведутся научно-технические работы по созданию более дешевых и удобных при эксплуатации САР ТО, однако, на данный момент пока еще не было выпущено их коммерческих образцов.
Таким образом, разработка нового подхода к решению задачи распознавания и определения координат как плоских, так и объемных деталей, новых алгоритмов выделения безразмерных признаков изображений проекций ТО, создание макета САР и экспериментальное исследование ее возможностей является актуальной научно-технической задачей.
Большой вклад в разработку и развитие теоретических основ в задачах обработки, анализа и распознавания изображений для решения вопросов автоматизации отдельных производственных процессов и операций внесли СВ. Абламейко,
B.C. Титов, Е.П. Путятин, B.C. Киричук, В.А. Сойфер, В.В. Сергеев, Я.А. Фурман, С.С. Садыков, А.Л. Жизняков и другие. Из иностранных ученых следует упомянуть А. Розенфельда, Р. Гонсалеса, У. Прэтта, К. Фу, Т. Павлидиса, Р. Дуда и других. Исследования автора опираются на результаты этих ученых.
Цель диссертационной работы - разработка нового подхода к решению задачи распознавания ТО и определения их координат, новых алгоритмов определения безразмерных признаков изображений проекций ТО, создание макета САР и экспериментальное исследование ее возможностей.
Для достижения поставленной цели необходимо выделить следующие задачи:
-
Анализ состояния задачи распознавания отдельно расположенных ТО.
-
Разработка нового подхода к распознаванию ТО с использованием двух камер, одна из которых располагается над сценой, вторая - под углом к сцене.
-
Разработка алгоритма сопоставления изображений проекций на двух снимках, полученных с камер, при наличии в поле зрения САР нескольких ТО.
-
Разработка новых алгоритмов выделения признаков и предварительной обработки изображений, позволяющих решать задачи автоматического распознавания и классификации произвольно и отдельно расположенных ТО.
-
Разработка структуры эталона объекта, включающей в себя информацию о его признаках шести ортогональных проекций, и позволяющей использовать известные алгоритмы вычисления оценок для распознавания ТО.
-
Разработка макета экспериментальной САР ТО с использованием двух камер и проведение исследований по распознаванию тестовых и реальных ТО.
Объект исследования - системы автоматического распознавания ТО.
Предмет исследования - алгоритмы выделения признаков изображений произвольно расположенных на плоскости ТО и их распознавание.
Научная новизна. Новые научные результаты, полученные в работе, состоят в следующем:
предложен новый подход к распознаванию произвольно расположенных ТО, заключающийся в использовании: 1) двух видео-датчиков, позволяющих получать как ортогональные, так и косоугольные проекции объектов под любым ракурсом; 2) трехмерных моделей ТО; 3) набора безразмерных признаков формы изображений двух проекций объектов; и 4) алгоритма вычисления оценок;
предложен новый алгоритм определения принадлежности ортогональной и косоугольной проекции на двух снимках к каждому из трехмерных объектов, обеспечивающий возможность распознавания ТО по двум снимкам проекций;
предложены алгоритмы вычисления безразмерных диагональных признаков формы изображений проекций ТО инвариантных к переносу, изменению масштаба и повороту ТО в поле зрения системы;
проведенными исследованиями на реальных ТО доказана перспективность применения предложенного подхода и разработанных алгоритмов для построения САР ТО с повышенной точностью распознавания ТО в сложных ситуациях.
Теоретическая значимость исследования обусловлена тем, что:
- доказана применимость комбинированного подхода (на основе использования
плоских изображений и трехмерных моделей) для распознавания произвольно
расположенных ТО;
изложены доказательства необходимости применения трехмерных моделей для формирования косоугольных проекций распознаваемых объектов в случаях наличия одинаковых проекций у разных ТО;
выявлены закономерности в значениях диагональных признаков плоских выпуклых геометрических фигур, позволяющие создать проекции ТО по их форме.
Практическая ценность работы. Значение полученных результатов исследования для практики подтверждается тем, что:
-
Разработаны алгоритмы вычисления диагональных признаков формы, инвариантных к пространственному расположению бинарных изображений проекций ТО.
-
Создана САР нескольких отдельно расположенных на сцене ТО, находящихся в произвольном порядке.
-
Проведены вычислительные эксперименты по оценке точности разработанных алгоритмов, результаты которых позволили выявить их возможности при распознавании единичных и нескольких отдельно расположенных тестовых и реальных ТО.
-
Разработанные алгоритмы применяются в учебном процессе кафедры информационных систем МИВлГУ в лабораторных и практических работах.
-
Полученные научные результаты приняты к использованию на промышленных предприятиях.
-
По результатам исследований, проведенных автором в рамках диссертации, получены два свидетельства об официальной регистрации на разработанные с его участием программные продукты, и один патент на полезную модель.
Методы исследования. В работе использованы методы геометрии, тригонометрии, алгебры логики, математической статистики, цифровой обработки изображений, планирования экспериментов и распознавания образов.
На защиту выносятся:
-
Алгоритм сопоставления пар изображений, позволяющий отнести ортогональные и косоугольные проекции, полученные с разных камер, к каждому распознаваемому ТО.
-
Алгоритмы вычисления диагональных признаков формы проекций ТО, использование которых позволяет с высокой точностью распознавать тестовые и реальные ТО.
-
САР нескольких отдельно расположенных ТО, которая может использоваться как основа для построения систем машинного зрения промышленного назначения.
-
Результаты экспериментальных исследований на САР по распознаванию нескольких произвольно расположенных реальных ТО, подтвердившие высокую точность идентификации объектов разработанной системой.
Степень достоверности результатов исследований обусловлена тем, что: 1. Теоретическая составляющая диссертации построена на известных и проверяемых данных и согласуется с опубликованными экспериментальными результатами по теме диссертации и смежным отраслям в изданиях, рекомендованных Высшей аттестационной комиссией РФ;
-
Подход базируется на анализе существующих решений в области распознавания объектов, а так же развитии алгоритмов анализа плоских изображений;
-
Использованы современные методики сбора и обработки информации с применением средств вычислительной техники.
Личный вклад соискателя состоит в:
участии автора на всех этапах процесса исследований по реализации темы диссертации;
личном участии в теоретических разработках, связанных с созданием и реализацией алгоритмов выделения безразмерных признаков проекций ТО, подготовке основных публикаций по алгоритмам вычисления диагональных признаков;
непосредственном участии соискателя в получении исходных изображений тестовых и реальных снимков ТО, а также научных экспериментальных исследованиях;
личном участии в создании макета экспериментальной САР ТО;
личном участии по внедрению результатов диссертационной работы на предприятиях ОАО ПО «Муроммашзавод» и ОАО «Муромский радиотехнический завод», а так же в учебном процессе кафедры «Информационные системы» МИ (филиала) ФГБОУ ВПО ВлГУ.
Апробация работы. Материалы диссертационной работы докладывались и обсуждались на: Международном симпозиуме «Надежность и качество» (г. Пенза, 2012г., 2013 г.); Международной конференции «Распознавание 2013» (г. Курск, 2013г.); «Перспективы развития информационных технологий» (г. Новосибирск, 2013 г.), «Наука и современность 2013» (г. Новосибирск, 2013 г.), 11-th International Conference on Pattern Recognition and Image Analysis (г. Самара, 2013 г.), Всероссийские научные «Зворыкинские чтения». Регионы России (г. Муром, 2014 г.).
Публикации. Основные результаты диссертации опубликованы в 28 печатных работах, в том числе в 8 статьях в журналах из списка ВАК. Получены 1 патент на полезную модель и 2 свидетельства о регистрации программы для ЭВМ.
Реализация результатов исследований. Разработанные алгоритмы и САР отдельно расположенных ТО приняты к внедрению на промышленных предприятиях ОАО «ПО Муроммашзавод» и ОАО «Муромский радиозавод», а так же используются в учебном процессе по дисциплине «Методы и системы цифровой обработки изображений» в МИ (филиал) ФГБОУ ВПО ВлГУ, о чем свидетельствуют акты, приведенные в приложении к диссертации.
Структура работы. Диссертация состоит из оглавления, введения, четырех глав с выводами по каждой из них, заключения, списка использованных источников и приложений. Основная часть диссертации изложена на 155 страницах машинописного текста и 32 страниц приложения. Работа содержит ПО рисунков, 49 таблиц. Библиографический список включает 142 наименования.
Структуры данных для представления информации о зонах
При исследовании большой территории её удобно разбить на небольшие зоны и последовательно изучить их. Существует несколько алгоритмов разбиения территории на зоны [43]. Мы остановимся на следующих: алгоритм кластеризации Ллойда на основе разбиения Вороного [1, 75], алгоритм Morse Decomposition [66] и наложение прямоугольной сетки на исследуемую территорию [25, 27]. Рассмотрим их подробнее.
Алгоритм кластеризации Ллойда является итерационным алгоритмом. Первоначально для исходной территории строится диаграмма Вороного [50], которая разбивает исходную территорию на конечное число непересекающихся зон. Затем данное разбиение последовательно улучшается. На рисунке 1.5 представлена схема этого алгоритма.
Алгоритм кластеризации Ллойда Главным достоинством этого алгоритма является возможность разбиения исходной территории на количество зон, соответствующее числу агентов в группе. При этом зоны не будут пересекаться.
Недостатки алгоритма Ллойда [43]: данный алгоритм основывается на заранее известном количестве зон. К сожалению, если геометрия исследуемой территории нам не известна, а число агентов в группе может изменяться во время работы системы, то число зон, на которые следует разбивать исходную территорию, заранее неизвестно; если геометрия территории S нам заранее не известна, то построить для неё диаграмму Вороного невозможно; если территория S велика, а количество агентов мало, то размер зон, полученных в результате работы алгоритма, будет превышать размер области видимости отдельного агента.
Алгоритм Morse Decomposition [66], так же, как и алгоритм кластеризации Ллойда исходит из предположения о том, что нам известна геометрия исследуемой территории. Алгоритм Morse Decomposition состоит из двух шагов:
Недостатки алгоритма Morse Decomposition [43]: если геометрия исследуемой территории нам не известна, то разбить её на зоны нельзя; размер зон может превышать размер области видимости отдельного агента; если исследуемая территория имеет выпуклую форму и не имеет внутри препятствий, то она будет воспринята как одна большая зона.
Идея алгоритма наложения прямоугольной сетки на исследуемую территорию [25, 27] состоит в том, что исследуемая территория разбивается на прямоугольные зоны одинакового размера. Количество таких зон зависит от размера исходной территории и размера прямоугольных зон.
Достоинства алгоритма: количество и размер зон не зависит от количества агентов в группе; позволяет устанавливать размер зон в зависимости от размера области видимости отдельного агента; нет необходимости в первоначальной инициализации центров зон, как в алгоритме кластеризации Ллойда.
Недостатки алгоритма: если размер исследуемой территории велик, а размер зон мал, то количество зон будет большим; необходимо указание начальной зоны, от которой будут отсчитываться другие зоны; если территорию нельзя охватить целым количеством зон, то появляются «лишние» зоны. В работе [57] предлагается алгоритм покрытия исследуемой территории без разбиения последней на зоны. Данный алгоритм исходит из предположения о том, что каждый отдельный агент имеет область видимости бесконечного размера. Единственное, что мешает отдельному агенту самостоятельно «покрыть» всю территорию, являются препятствия, которые скрывают от него часть территории. На рисунке 1.7 показана последовательность расстановки агентов для обеспечения полного покрытия территории.
Данный алгоритм работает следующим образом. На первом шаге своё место занимает агент 0. Его область видимости ограничивается отрезками A и B (см. рис. 1.7 (а)). На втором шаге в середины этих отрезков встают агенты 1 и 2 (см. рис. 1.7 (б)). Теперь общая область видимости ограничивается отрезками A, B и C. На третьем шаге по аналогии с шагом 2 в середины этих отрезков встают агенты 3, 4 и 5 (см. рис. 1.7 (в)). Этот процесс повторяется до тех пор, пока не будет достигнуто покрытие всей территории (см. рис. 1.7 (г)). Таким образом, для покрытия всей территории понадобилось всего 7 агентов. Достоинства данного алгоритма: позволяет определить необходимое количество агентов для покрытия всей территории; не требуется хранить информацию о зонах и их состоянии (проверена, не проверена); перемещения агентов минимальны. Это позволяет более экономно расходовать энергоресурсы.
Недостатки данного алгоритма: алгоритм не работает, если количество агентов меньше необходимого количества; предполагает, что размер области видимости отдельного агента бесконечен. На практике это не так. Поэтому понадобятся дополнительные агенты; не устойчив к возможному выходу из строя одного или нескольких агентов группы; размер доверенной области видимости одного отдельного агента может быть очень большим. Это предъявляет высокие требования к его аппаратному и программному обеспечению. После рассмотрения всех вышеперечисленных алгоритмов кластеризации было решено использовать алгоритм наложения прямоугольной сетки. Причины, обусловившие данный выбор перечислены ниже: невысокая сложность данного алгоритма; позволяет устанавливать размер зон в зависимости от размера области видимости отдельного агента. 1.2.2. Алгоритм наложения прямоугольной сетки
БПЛА с видеодатчиками на борту
БПЛА не может охватить всю территорию с помощью имеющегося у него оборудования. Поэтому территория представляется в виде множества зон. Каждая зона охватывается отдельным кадром. Для того чтобы сделать снимок, соответствующий кадру, БПЛА должен достичь некоторой фиксированной реперной точки, остановиться в ней, сделать снимок, продолжить движение.
Положение реперной точки определяется на основе положения и размеров зоны, технических характеристик видеодатчика, установленного на борту БПЛА, и его крепления. Остановка в реперной точке необходима для того, чтобы сделать качественный снимок. Если её не сделать, то снимок может получиться смазанным. Количество реперных точек и их положение определяются центром управления для каждого отдельного БПЛА группы. Он же задает траекторию движения БПЛА. Таким образом, при решении задачи обследования территории БПЛА может находиться в одном из состояний: «покой», «движение», «съемка». На рисунке 2.2 показана диаграмма состояний БПЛА. Она уточняет диаграмму, представленную на рисунке 2.1. Движение Съемка
Состояние «Покой» является начальным, в нём БПЛА не выполняет поставленную задачу. При этом первые шесть элементов вектора (2.1) постоянны, а седьмой элемент (запас хода) монотонно увеличивается. Это связано с зарядкой аккумуляторных батарей, установленных на борту БПЛА. Он находится в этом состоянии до тех пор, пока перед ним не будет поставлена задача (в виде множества реперных точек и траектории движения по их обходу) и имеющийся запас хода не будет достаточен для выполнения поставленной задачи.
В состоянии «Движение» БПЛА перемещается к очередной реперной точке или к базовой точке, из которой стартовала вся группа. В этом состоянии изменяются все элементы вектора (2.1). Имеющийся запас хода уменьшается. По достижении реперной точки БПЛА переходит в состояние «Съемка». По достижении базовой точки он переходит в состояние «Покой». Достижение базовой точки означает, что либо БПЛА посетил все заданные реперные точки, либо он получил команду на досрочное завершение работы. Также БПЛА может вернуться на базовую точку при обнаружении дефицита энергоресурса.
В состоянии «Съемка» БПЛА осуществляет съемку с помощью установленного на его борту видеодатчика. Теоретически в этом состоянии должен меняться только уровень энергоресурса. Остальные элементы вектора (2.1) должны оставаться константными. На практике же это не так. Данные элементы могут изменяться вследствие воздействия на БПЛА таких факторов, как ветер, несогласованность серводвигателей, удерживающих БПЛА в фиксированном положении, и др. Уровень энергоресурса уменьшается вследствие работы серводвигателей и видеодатчика. После того как БПЛА сделал снимок, он возобновляет движение к следующей реперной точке или базовой точке. Когда БПЛА посетит все заданные реперные точки, он возвращается на базу.
Рассмотрим случай, когда на борту БПЛА установлен один видеодатчик. Обычно его устанавливают под некоторым фиксированным углом к нормали плоскости БПЛА так, как показано на рисунке 2.3. Предположим, что видеодатчик направлен по курсу БПЛА. Установим ориентацию координатных осей так, как показано на рисунке 2.4. Линейные координаты фотоаппарата определяются соотношением (2.3) на основе линейных координат БПЛА.
Каждый сделанный кадр удобно представлять в виде вектора: С = (Хс, Yc, Н, De, Д у, а, %х, %у, t), (2.9) где Хс и Yc - координаты центра кадра в плоскости XOY; Н - высота БПЛА, во время снимка, равная его координате Z ; De - половина диагонали кадра (2.8); /3 - угол, значение тангенса которого равно отношению сторон кадра; у - угол крена видеодатчика во время фотоснимка; а - «ценность» кадра; Хх и ХУ - отношение размера фотографируемого участка (в метрах) к размеру кадра (в пикселях) в направлении сторон кадра; t - время фотоснимка. На рисунке 2.5 представлено схематичное изображение кадра.
Половина диагонали кадра De и угол /? позволяют однозначно определить размеры кадра с помощью соотношений: Нс =2De sin/?, гч г, (2.10) W = 2D cosp, с в / где Нс - высота кадра; Wc - его ширина. «Ценность» кадра - характеристика, используемая при установлении порядка обхода кадров и построении траектории. Отношения Хх и Ху выражаются следующим образом: W Нс Rx , ЛУ Ry , (2.11) где Wc - ширина кадра в метрах; Rx - разрешение кадра вдоль оси X в пикселях; Нс - высота кадра в метрах; Ry - разрешение кадра вдоль оси Y в пикселях.
Для обеспечения качественной обработки собранной информации значения отношений Хх и Ху должны удовлетворять условию:
ХХ Х, ХУ Х, (2.12) где х – пороговое значение отношения размера, снимаемого с помощью видеодатчика участка (в метрах) к размеру кадра (в пикселях). Его точное значение зависит от характера последующей обработки собранной информации.
Из выражений (2.10) и (2.8) видно, что размеры участка территории, охватываемой одним кадром, прямо пропорциональны высоте БПЛА. Условие (2.12) накладывает ограничение на высоту БПЛА.
На БПЛА может быть установлено несколько видеодатчиков. Обозначим через SCti - множество точек плоскости XOY, составляющих кадр /-го видеодатчика. Хотя данное множество является функцией времени и набора переменных видеодатчика и БПЛА (например, текущие координаты и углы ориентации БПЛА, изменяющиеся во времени) будем рассматривать одиночные кадры в фиксированном положении БПЛА (и, соответственно, видеодатчиков). Также полагаем, что все установленные видеодатчики делают снимок одновременно. Суммарный кадр, полученный всеми видеодатчиками, будет: Sc = Scj uScj u... oiS , (2.13) где Sc - множество точек, составляющих суммарный кадр; SCti - множество точек, составляющих кадр /-го видео датчика; п - количество видеодатчиков.
Алгоритм последовательного выбора
В алгоритме, изображенном на рисунке 3.3, каждый БПЛА выбирает новую зону с помощью алгоритма, изображенного на рисунке 3.2. Вспомогательная переменная C в алгоритме последовательного выбора используется для выявления случаев, когда решение не может быть найдено. Это происходит, когда на очередной итерации цикла выбора зон ни один БПЛА группы не выбирает зону при условии, что не все зоны распределены между членами группы. В этом случае решение не может быть найдено с помощью алгоритма последовательного выбора. Для решения задачи нужно либо уменьшить обследуемую территорию, либо увеличить количество БПЛА входящих в состав группы.
Оценим вычислительную сложность алгоритма. При условии хранения результата расчета функции (3.16) к моменту времени t, сложность расчета функции (3.18) составит O(1). Так же при условии хранения в памяти результата расчета затрачиваемого энергоресурса (3.12) для имеющегося набора зон, выбранных БПЛА, сложность проверки условия (3.14) при возможном добавлении новой зоны составит O(1). Тогда вычислительная сложность алгоритма, изображенного на рисунке 3.2, составит O(M), где M – количество зон.
Тело цикла в алгоритме, изображенном на рисунке 3.3, исполняется M раз. На каждой итерации исполняется алгоритм, изображенный на рисунке 3.2 и имеющий сложность O(M). Отсюда сложность всего алгоритма составит O(M2). (3.19) Алгоритм последовательного выбора позволяет за полиномиальное время находить квазиоптимальное решение. Но, как показывает проведенное моделирование, поиск экстремума функции (3.17) приводит к не самому лучшему решению. 3.2. Сравнение функций приемлемости
Для исследования поведения алгоритма последовательного выбора при условии максимизации функции приемлемости (3.18) было проведено программное моделирование. На рисунке 3.4 представлен пример траекторий, построенных этим алгоритмом.
При моделировании использовались следующие параметры: размер обследуемой территории 30 на 20 реперных точек, реперные точки располагаются равномерно вдоль горизонтальной и вертикальной границ территории, образуя регулярную «сетку», количество БПЛА в группе равно 3. Сама программа моделирования была разработана на языке C++.
Большой красный кружок в левом верхнем углу обозначает стартовую точку, из которой стартуют и в которую должны вернуться все члены группы. Реперные точки обозначены кружками меньшего диаметра. Траектории БПЛА обозначены различным цветом. Траектория движения первого БПЛА – красным, второго – синим, третьего – зеленым цветами. Цвет каждой реперной точки соответствует тому БПЛА, который делает в ней снимок.
На рисунке 3.5 представлен график нарастания суммарной ценности с течением времени. На графике по оси абсцисс откладывает время, в условных единицах времени, по оси ординат - значение функции (3.17). Ценность каждой реперной точки рассчитывалась по формуле: 100 aj =т , (3.20) где Lj - расстояние между стартовой точкой, из которой стартует группа, и координатами 7-й реперной точки. Число 100 в формуле (3.20) взято произвольным образом и используется для компенсации ошибок округления при работе с вещественными числами.
Изменим функцию приемлемости и будем теперь не максимизировать суммарную ценность, а минимизировать проходимое БПЛА расстояние. Функция приемлемости (1.5) запишется в виде: /2(,,/) = ЙР . ( ., (3.21) где (Xitk; Yt,k) - координаты последней реперной точки z-го БПЛА; (X/; Yj) -координаты потенциальной 7-й реперной точки.
На рисунке 3.6 представлены траектории БПЛА, построенных при тех же начальных условиях, что и в предыдущем подразделе, но с условием, что функция приемлемости каждой реперной точки записывается в виде функции (3.21).
На рисунке 3.7 приведены графики нарастания накопленной ценности (3.17) с течением времени для обоих рассматриваемых случаев. Для удобства сравнения они размещены в одной координатной плоскости. Зеленым цветом обозначен график для случая максимизации ценности, красным - для случая использования функции приемлемости (3.21). Рис. 3.6. Траектории БПЛА при использовании функции приемлемости (3.21)
Допустим, что в направлении стрелки, изображенной на рисунке 3.8, наступает потенциальный противник, вдоль первых нескольких колонок. Все члены группы в это время обследуют участки территории, расположенные правее центральной точки (левый верхний угол). Если противник располагается достаточно близко и имеет достаточную скорость движения, то он может достигнуть центральной точки до того, как какой-либо БПЛА вернется к обследованию реперных точек из первых колонок. Таким образом, он оказывается незамеченным. При осуществлении разведки на поле боя, такое недопустимо.
Программное моделирование системы
Функция T(i, i+1) (3.6) вычисляется за время O(1). Следовательно, функции (3.37) и (3.38) также вычисляются за время O(1).
Состояние БПЛА определяется алгоритмом, изображенным на рисунке 3.30, сложность которого составляет O(M) (3.29). Тогда сложность алгоритма, изображенного на рисунке 3.31, составит: O(M) + O(1) = O(M). (3.39) Как говорилось выше, алгоритм, изображенный на рисунке 3.30, может, при определенных условиях, иметь сложность O(1). В этом случае суммарная сложность (3.39) составит: O(1). (3.40) Алгоритм, изображенный на рисунке 3.30, конечен. Алгоритм, изображенный на рисунке 3.31, не содержит циклов, поэтому он также конечен.
Алгоритм, изображенный на рисунке 3.31, позволяет определять положение БПЛА в произвольный момент времени. Благодаря этому появляется возможность оценивать расстояния между членами группы в произвольный момент времени. Метод идентификации столкновений заключается в следующем: если существует два БПЛА Bt и Bj (jj), для которых система неравенств (3.41) имеет минимум одно решение, то имеет место столкновение между ними: где Xi(t), Yi(t), Xj(t), Yj(t) – функции, реализующие алгоритм, изображенный на рисунке 3.31, и возвращающие координаты i-го и j-го БПЛА в момент времени t; Xmin, Ymin – минимальное предельно допустимое расстояние между двумя БПЛА по осям координат X и Y соответственно.
Значение констант Xmin и Ymin зависит от конструктивных особенностей БПЛА и меры «доверия» к качеству систем управления, установленных на борту БПЛА. Под качеством понимается способность системы не допускать отклонения БПЛА от заданного маршрута. Малое значение констант Xmin и Ymin приведет к сохранению сравнительно высокой вероятности столкновений из-за возможных случайных отклонений БПЛА от своей траекторий вследствие воздействия на него случайных внешних и внутренних факторов. С другой стороны, большое значение констант Xmin и Ymin негативно скажется на времени работы всей группы.
В системе неравенств (3.41) рассматривается две координаты, так как все БПЛА работают на одной высоте. Поэтому включать в рассмотрение третью координату (высоту) не имеет смысла.
Оценим вероятность столкновения между двумя БПЛА при условии, что система неравенств (3.41) не имеет решений. Для простоты будем рассматривать только одну координату X. Учет других координат снизит вероятность столкновений. Допустим, что значение константы Xmin равно 30м. Также будем считать, что система управления, установленная на борту БПЛА, имеет следующие характеристики в контексте удержания БПЛА на заданном маршруте: СКО – 6.6м [54] и ошибка имеет нормальный законный распределения.
В таких условиях столкновение между двумя БПЛА произойдет, если два БПЛА, вследствие ошибок позиционирования, одновременно отклонятся на 15м. (Xmin/2) от своего корректного положения. Вероятность того, что отклонение БПЛА от своей заданной позиции не превысит 15м. составит:
Оценка (3.42) является условной. Существует целый ряд факторов, не учтенных при расчете этой оценки, которые могут, как уменьшить, так и увеличить вероятность столкновения при использовании предлагаемого метода идентификации столкновений. Вот некоторые факторов, приводящие к уменьшению вероятности (3.42): БПЛА должны отклоняться навстречу друг другу. Если БПЛА отклоняются в одном направлении, то столкновение не произойдет; БПЛА должны находиться близко друг к другу и по другим координатным осям. Если два БПЛА недопустимо сблизились по одной координатной оси, но достаточно удалены друг от друга по другой координатной оси, то столкновение не произойдет; вполне вероятна такая ситуация, при которой фактическое минимальное расстояние между двумя БПЛА превосходит значение X min. Такое может произойти при построении траекторий алгоритмом последовательного выбора. С другой стороны существуют факторы, которые могут привести как к увеличению вероятности (3.42), так и к ее уменьшению. Вот лишь некоторые из них. СКО ошибки отклонения от заданного маршрута может отличаться от значения 6.6м. Распределение ошибки может иметь закон отличный от нормального.
Данные факторы целиком и полностью зависят от установленной на борту БПЛА системы управления. Уменьшить вероятность столкновения можно путём использования более надежных систем управления [61] и увеличения значения констант Хmin и Ymin.
Поиск аналитического решения системы неравенств (3.41) представляет собой NP-трудную задачу [36]. Но для предотвращения столкновений БПЛА необязательно иметь аналитическое решение системы неравенств (3.41). Если в какой-то момент времени нам известны положения всех членов группы, то проверка истинности системы неравенств (3.41) выполняется за время (9(1). Именно этот факт и используется при реализации метода идентификации столкновений.
На рисунке 3.32 представлена блок-схема алгоритма, реализующего метод идентификации столкновений. На этом рисунке используются следующие обозначения: t - время; Tmin - минимальное время, необходимое для достижения первой реперной точки группы; dt - шаг, с которым просматривается положение членов группы.
Идея этого алгоритма заключается в просмотре положения БПЛА в разные моменты времени. Для каждого такого момента проверяется истинность системы неравенств (3.41). Если она истинна, то имеет место столкновение.