Построение оптимальных маршрутов движения БЕСПИЛОТНЫХ АППАРАТОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ В ГРУППОВОМ РЕЖИМЕ
|
Введение 4
Используемые определения 7
Постановка задачи 8
Обзор литературы 9
1 Основные понятия и инструменты 12
1.1 Понятие агента 12
1.2 Взаимодействие и координация агентов 16
1.3 Фреймворк JADE для моделирования МАС 18
2 Реализация поставленной задачи 25
2.1 Оптимальное покрытие области 26
2.1.1 Кривые Дубина в задачах исследования областей 26
2.1.2 Оптимальное покрытие области 27
2.2 Оптимальное разбиения области с использованием генетического алгоритма 29
3 Анализ результатов в среде MATLAB 31
3.1 Результаты исследования 31
3.2 Анализ влияния оптимизации покрытия области на скорости поиска объекта 33
Заключение 34
Приложение А 35
Приложение В 37
Список литературы 38
Используемые определения 7
Постановка задачи 8
Обзор литературы 9
1 Основные понятия и инструменты 12
1.1 Понятие агента 12
1.2 Взаимодействие и координация агентов 16
1.3 Фреймворк JADE для моделирования МАС 18
2 Реализация поставленной задачи 25
2.1 Оптимальное покрытие области 26
2.1.1 Кривые Дубина в задачах исследования областей 26
2.1.2 Оптимальное покрытие области 27
2.2 Оптимальное разбиения области с использованием генетического алгоритма 29
3 Анализ результатов в среде MATLAB 31
3.1 Результаты исследования 31
3.2 Анализ влияния оптимизации покрытия области на скорости поиска объекта 33
Заключение 34
Приложение А 35
Приложение В 37
Список литературы 38
В связи с развитием теории искусственного интеллекта, значительно возросло количество задач, к которым применима: научные разработки и достижения, полученные за последние десятилетия в данной области. Программное обеспечение на базе искусственного интеллекта оказывает существенное влияние на человеческий труд по всему миру, упрощая выполнение повседневных задач. Неугасающий интерес со стороны исследователей к такого рода задачам объясняется наличием широкого спектра спорных вопросов, которые связаны с данной активно развивающейся областью.
В традиционной теории искусственного интеллекта, отвхскание решения любой задачи сводится к изобретению интеллектуалвной системы, которую назвхвают агентом.
С течением научно-технического прогресса, искусственнвхй интеллект, как научная отрасли знания, охватил широкие круги задач. Первыми оказались экспертные системы, которые были способны решать практические задачи только в узкоспециализированных областях. В 1960-70-х гг. в Стэнфорде были разработаны такие системы Dendral и Mycin [13]. Первая из которых на основе заложенных в неё эвристических знаний эксперта была способна находить верное решение среди огромного количества возможных за короткий промежуток времени, в то время как вторая система на основе сомнительных, ограниченных данных рассуждала, основываясь на логике, присущей выбранной предметной области. Впоследствии были выявлены существенные недостатки экспертных систем, например, получение знаний от специалистов, которые бы охватывали всю предметную область, отсутствие способности к самообучению, что может приводить к быстрой потере актуальности без регулярной поддержки со стороны разработчика. Необходимость создания более универсального подхода к решению прикладных задач привела к смещению интереса в сторону нейронных сетей и генетических алгоритмов, чьи термины на тот момент были уже введены. Ещё в середине XX века в области нейронных сетей Мак-Каллоком и Питтсом были получены основные результаты и разработана первая модель, в которой нейроны имели способность к самообучению путём подстройки параметров. Первые опыты связанные с моделированием процесса эволюции и симбиогенеза были проведены в 1954 году Нильсом Баричелли в Институте перспективных исследований Принстонского университета, а в 1957 году была выпущена его первая публикация “Symbiogenetic evolution processes realised by artificial methods “. Несмотря на все достоинства данных систем, принятие решений в таких системах характеризуется высокой степенью неопределённости, невозможностью работы в реальном времени, а также часто специалистам трудно объяснить почему система пришла к тем или иным результатам из-за стохастичности процессов принятия решений.
В современном обществе перспективными считаются задачи, требующие разделения заданий между несколькими вычислительными потоками, то есть применения распределённых систем.
В связи с вышеобозначенным трендом, характерено замещение одноагентных систем на мультиагентные в качестве вычислительной модели исследования. Для последних характерным отличием является наличие группы агентов, внутри которой происходит декомпозиция глобальной задачи и распределение ролей разной сложности исходя из потенциала (т.е вычислительных ресурсов, знаний) каждого члена группы. При данном подходе внутреннее распределение подзадач может осуществляться различными способами, включая организационное структурирование, многоагентное планирование и переговоры. Существует ряд работ, в которых приводятся результаты, демонстрирующие преимущество применения мультиагентного подхода к различным областям знания, начиная от небольших задач персонального назначения до масштабных, комплексных задач, предназначенных для промышленного применения. В качестве примера можно привести ряд сфер человеческой деятельности, в которых продуктивно используется данный подход: биология (анализ распространения эпидемий [6], динамика популяций [8] , когнитивное моделирование, изучение биологических систем на молекулярном уровне [11], [32], [62]), бизнес и технологии (моделирование поведения потребителей, контроль процессов, оптимизация цепочек производства, транспортная логистика, анализ пробок [24], системная диагностика и управление сетью), а также социальные науки (изучение конфликтов, моделирование социальных структур) и экономика (онлайн-торговля).
Несмотря на то, что мультиагентные системы (МАС) являются интенсивно развивающимся направлением искусственного интеллекта в течение уже не одного десятка лет, в настоящее время исследователи занимаются вопросом интеграции знаний из смежных областей и активно применяют их в решении практических задач. В первую очередь стоит упомянуть о важности способа организации компьютерных вычислений в таких системах. Поскольку основной парадигмой МАС является возможность разделения круга задач для оптимизации общего процесса поиска решения и реализации параллельной обработки данных на нескольких вычислительных узлах одновременно, необходимым является привлечение новых технологий и алгоритмов связанных с параллелизмом в программировании.
На сегодняшний день задача организации управления группой беспилотных летательных аппаратов (БПЛА) является одной из наиболее актуальных, для которой применим мультиагентный подход. История развития БПЛА начинается с конца XIX века, а именно с 1899 года, когда инженер и физик Никола Тесла изобрёл радиоуправляемый корабль [39]. Наиболее влиятельным и амбициозным открытием XX века считается БПЛА неоднократного пользования, разработанный в 1933 году, которым можно было управлять удалённо с корабля по радио [13]. Несмотря на то, что возникновение БПЛА было связано в основном с решением военных целей, сегодня они привлекают внимание многих исследователей благодаря своим перспективам применения в гражданских областях. В современном обществе можно видеть их использование в медицине [51], нефтегазовых, коммерческих, научных, сельскохозяйственных областях [57], также аппараты используются для охраны и наблюдения за территориями заповедников, лесов. Современные беспилотники умеют выполнять задачи различной сложности, от аэрофотосъёмки и до поиска решений в сфере топографии, тепловизионного обследования. С недавнего времени, такие компании, как Amazon, UPS и Deutsche Post AG и Google начали использовать автономные БПЛА для доставки посылок [45], [50].
Для групп БПЛА одной из исследовательских областей является планирование пути. В данной работе рассматриваются фундаментальные проблемы, связанные с планированием пути группы БПЛА [33]. Развитие данной темы позволяет решать экономические вопросы, например, снижение затрат как на разработку летательных аппаратов в связи с заменой габаритных размеров ЛА, так и на обучение пилотов для управления. В будущем планируется разработка полностью автономных БПЛА, не требующих постоянного контроля вышестоящего звена.
В традиционной теории искусственного интеллекта, отвхскание решения любой задачи сводится к изобретению интеллектуалвной системы, которую назвхвают агентом.
С течением научно-технического прогресса, искусственнвхй интеллект, как научная отрасли знания, охватил широкие круги задач. Первыми оказались экспертные системы, которые были способны решать практические задачи только в узкоспециализированных областях. В 1960-70-х гг. в Стэнфорде были разработаны такие системы Dendral и Mycin [13]. Первая из которых на основе заложенных в неё эвристических знаний эксперта была способна находить верное решение среди огромного количества возможных за короткий промежуток времени, в то время как вторая система на основе сомнительных, ограниченных данных рассуждала, основываясь на логике, присущей выбранной предметной области. Впоследствии были выявлены существенные недостатки экспертных систем, например, получение знаний от специалистов, которые бы охватывали всю предметную область, отсутствие способности к самообучению, что может приводить к быстрой потере актуальности без регулярной поддержки со стороны разработчика. Необходимость создания более универсального подхода к решению прикладных задач привела к смещению интереса в сторону нейронных сетей и генетических алгоритмов, чьи термины на тот момент были уже введены. Ещё в середине XX века в области нейронных сетей Мак-Каллоком и Питтсом были получены основные результаты и разработана первая модель, в которой нейроны имели способность к самообучению путём подстройки параметров. Первые опыты связанные с моделированием процесса эволюции и симбиогенеза были проведены в 1954 году Нильсом Баричелли в Институте перспективных исследований Принстонского университета, а в 1957 году была выпущена его первая публикация “Symbiogenetic evolution processes realised by artificial methods “. Несмотря на все достоинства данных систем, принятие решений в таких системах характеризуется высокой степенью неопределённости, невозможностью работы в реальном времени, а также часто специалистам трудно объяснить почему система пришла к тем или иным результатам из-за стохастичности процессов принятия решений.
В современном обществе перспективными считаются задачи, требующие разделения заданий между несколькими вычислительными потоками, то есть применения распределённых систем.
В связи с вышеобозначенным трендом, характерено замещение одноагентных систем на мультиагентные в качестве вычислительной модели исследования. Для последних характерным отличием является наличие группы агентов, внутри которой происходит декомпозиция глобальной задачи и распределение ролей разной сложности исходя из потенциала (т.е вычислительных ресурсов, знаний) каждого члена группы. При данном подходе внутреннее распределение подзадач может осуществляться различными способами, включая организационное структурирование, многоагентное планирование и переговоры. Существует ряд работ, в которых приводятся результаты, демонстрирующие преимущество применения мультиагентного подхода к различным областям знания, начиная от небольших задач персонального назначения до масштабных, комплексных задач, предназначенных для промышленного применения. В качестве примера можно привести ряд сфер человеческой деятельности, в которых продуктивно используется данный подход: биология (анализ распространения эпидемий [6], динамика популяций [8] , когнитивное моделирование, изучение биологических систем на молекулярном уровне [11], [32], [62]), бизнес и технологии (моделирование поведения потребителей, контроль процессов, оптимизация цепочек производства, транспортная логистика, анализ пробок [24], системная диагностика и управление сетью), а также социальные науки (изучение конфликтов, моделирование социальных структур) и экономика (онлайн-торговля).
Несмотря на то, что мультиагентные системы (МАС) являются интенсивно развивающимся направлением искусственного интеллекта в течение уже не одного десятка лет, в настоящее время исследователи занимаются вопросом интеграции знаний из смежных областей и активно применяют их в решении практических задач. В первую очередь стоит упомянуть о важности способа организации компьютерных вычислений в таких системах. Поскольку основной парадигмой МАС является возможность разделения круга задач для оптимизации общего процесса поиска решения и реализации параллельной обработки данных на нескольких вычислительных узлах одновременно, необходимым является привлечение новых технологий и алгоритмов связанных с параллелизмом в программировании.
На сегодняшний день задача организации управления группой беспилотных летательных аппаратов (БПЛА) является одной из наиболее актуальных, для которой применим мультиагентный подход. История развития БПЛА начинается с конца XIX века, а именно с 1899 года, когда инженер и физик Никола Тесла изобрёл радиоуправляемый корабль [39]. Наиболее влиятельным и амбициозным открытием XX века считается БПЛА неоднократного пользования, разработанный в 1933 году, которым можно было управлять удалённо с корабля по радио [13]. Несмотря на то, что возникновение БПЛА было связано в основном с решением военных целей, сегодня они привлекают внимание многих исследователей благодаря своим перспективам применения в гражданских областях. В современном обществе можно видеть их использование в медицине [51], нефтегазовых, коммерческих, научных, сельскохозяйственных областях [57], также аппараты используются для охраны и наблюдения за территориями заповедников, лесов. Современные беспилотники умеют выполнять задачи различной сложности, от аэрофотосъёмки и до поиска решений в сфере топографии, тепловизионного обследования. С недавнего времени, такие компании, как Amazon, UPS и Deutsche Post AG и Google начали использовать автономные БПЛА для доставки посылок [45], [50].
Для групп БПЛА одной из исследовательских областей является планирование пути. В данной работе рассматриваются фундаментальные проблемы, связанные с планированием пути группы БПЛА [33]. Развитие данной темы позволяет решать экономические вопросы, например, снижение затрат как на разработку летательных аппаратов в связи с заменой габаритных размеров ЛА, так и на обучение пилотов для управления. В будущем планируется разработка полностью автономных БПЛА, не требующих постоянного контроля вышестоящего звена.
В процессе выполнения данной работы разработана мультиагентная система БПЛА, которая оптимально покрывает заданную область. Разработана программная среда (с помощью языка Java и распределенной Java- платформы JADE) для симуляции движения агентов мультиагентной системы по разработанному алгоритму в выделенных секторах действия с учетом следующих параметров системы:
• количество агентов в системе;
• количество топлива агента;
• возможный радиус кривизны поворота БПЛА.
Проведена оптимизация (с помощью генетического алгоритм) разбиения исходной области на сектора действия агентов. Получены результаты для различных распределений плотности вероятности значения мутации. Проведен сравнительный анализ результатов оптимизации разбиения области на сектора действия агентов. Произведено сравнение сходимости алгоритмов оптимизации для различных распределений плотности вероятности значения мутации. В ходе анализа полученных результатов в среде MATLAB был использован инструмент CFTool (Curve Fitting Tool). Продемонстрированно улучшение эффективности поиска объекта (уменьшено время поиска случайно заданного объекта) мультиагентной системой в результате оптимизации разбиения области на сектора действия агентов.
Перспективы развития. Дальнейшим развитием данной работы является разработка алгоритма поиска группой БПЛА движущегося объекта внутри заданной области. Также одной из перспективных задач для МАС является реализация слежения за обнаруженным объектом, в случае, если тот является динамическим.
На защиту выносятся следующие положения
1) модель агента мультиагентной системы и системы взаимодействия агентов внутри системы БПЛА;
2) алгоритм покрытия области, разделённой на сектора действия в зависимости от порядкового номера БПЛА в МАС;
3) алгоритм оптимизации разделения исследуемой области на сектора.
• количество агентов в системе;
• количество топлива агента;
• возможный радиус кривизны поворота БПЛА.
Проведена оптимизация (с помощью генетического алгоритм) разбиения исходной области на сектора действия агентов. Получены результаты для различных распределений плотности вероятности значения мутации. Проведен сравнительный анализ результатов оптимизации разбиения области на сектора действия агентов. Произведено сравнение сходимости алгоритмов оптимизации для различных распределений плотности вероятности значения мутации. В ходе анализа полученных результатов в среде MATLAB был использован инструмент CFTool (Curve Fitting Tool). Продемонстрированно улучшение эффективности поиска объекта (уменьшено время поиска случайно заданного объекта) мультиагентной системой в результате оптимизации разбиения области на сектора действия агентов.
Перспективы развития. Дальнейшим развитием данной работы является разработка алгоритма поиска группой БПЛА движущегося объекта внутри заданной области. Также одной из перспективных задач для МАС является реализация слежения за обнаруженным объектом, в случае, если тот является динамическим.
На защиту выносятся следующие положения
1) модель агента мультиагентной системы и системы взаимодействия агентов внутри системы БПЛА;
2) алгоритм покрытия области, разделённой на сектора действия в зависимости от порядкового номера БПЛА в МАС;
3) алгоритм оптимизации разделения исследуемой области на сектора.
