Интеграционный подход к задаче выбора маршрута группы БПЛА

В статье рассматривается три похода к задаче планирования маршрута беспилотных летательных аппаратов. Проводится сравнительный анализ поисковых методов на графах и мультиагентные алгоритмы: муравьиный алгоритм и алгоритм «запрос-ответ-соглашение». На основе проведенного анализа предлагается интег...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Искусственный интеллект
Datum:	2013
Hauptverfasser:	Козуб, А.Н., Кучеров, Д.П.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2013
Schlagworte:	Интеллектуальные системы планирования, управления, моделирования и принятия решений
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/84968
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Интеграционный подход к задаче выбора маршрута группы БПЛА / А.Н. Козуб, Д.П. Кучеров // Искусственный интеллект. — 2013. — № 4. — С. 333–343. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-84968
record_format	dspace
spelling	Козуб, А.Н. Кучеров, Д.П. 2015-07-17T17:23:46Z 2015-07-17T17:23:46Z 2013 Интеграционный подход к задаче выбора маршрута группы БПЛА / А.Н. Козуб, Д.П. Кучеров // Искусственный интеллект. — 2013. — № 4. — С. 333–343. — Бібліогр.: 9 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/84968 519.6:004.93 В статье рассматривается три похода к задаче планирования маршрута беспилотных летательных аппаратов. Проводится сравнительный анализ поисковых методов на графах и мультиагентные алгоритмы: муравьиный алгоритм и алгоритм «запрос-ответ-соглашение». На основе проведенного анализа предлагается интеграция поисковых походов на графах и мультиагентного, работающих на параллельной основе. У статті розглядається три походи до задачі планування маршруту безпілотних літальних апаратів. Проводиться порівняльний аналіз пошукових методів на графах і мультиагентні алгоритми: мурашиний алгоритм та алгоритм «запит-відповідь-угода». На основі проведеного аналізу пропонується інтеграція пошукових походів на графах і мультиагентного, що працюють на паралельній основі. In these paper three approaches to the problem of planning a route of unmanned aerial vehicles is discussed. A comparative analysis of search methods on graphs and multi-agent algorithms: the ant algorithm and the algorithm of the "request-reply-agreement" is given. Based on the analysis the integration of methods running on a parallel basis is proposed. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеграционный подход к задаче выбора маршрута группы БПЛА Інтеграційний підхід до задачі вибору маршруту групи БПЛА Integrated approach to the problem of planning the route of UAV Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Интеграционный подход к задаче выбора маршрута группы БПЛА
spellingShingle	Интеграционный подход к задаче выбора маршрута группы БПЛА Козуб, А.Н. Кучеров, Д.П. Интеллектуальные системы планирования, управления, моделирования и принятия решений
title_short	Интеграционный подход к задаче выбора маршрута группы БПЛА
title_full	Интеграционный подход к задаче выбора маршрута группы БПЛА
title_fullStr	Интеграционный подход к задаче выбора маршрута группы БПЛА
title_full_unstemmed	Интеграционный подход к задаче выбора маршрута группы БПЛА
title_sort	интеграционный подход к задаче выбора маршрута группы бпла
author	Козуб, А.Н. Кучеров, Д.П.
author_facet	Козуб, А.Н. Кучеров, Д.П.
topic	Интеллектуальные системы планирования, управления, моделирования и принятия решений
topic_facet	Интеллектуальные системы планирования, управления, моделирования и принятия решений
publishDate	2013
language	Russian
container_title	Искусственный интеллект
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
format	Article
title_alt	Інтеграційний підхід до задачі вибору маршруту групи БПЛА Integrated approach to the problem of planning the route of UAV
description	В статье рассматривается три похода к задаче планирования маршрута беспилотных летательных аппаратов. Проводится сравнительный анализ поисковых методов на графах и мультиагентные алгоритмы: муравьиный алгоритм и алгоритм «запрос-ответ-соглашение». На основе проведенного анализа предлагается интеграция поисковых походов на графах и мультиагентного, работающих на параллельной основе. У статті розглядається три походи до задачі планування маршруту безпілотних літальних апаратів. Проводиться порівняльний аналіз пошукових методів на графах і мультиагентні алгоритми: мурашиний алгоритм та алгоритм «запит-відповідь-угода». На основі проведеного аналізу пропонується інтеграція пошукових походів на графах і мультиагентного, що працюють на паралельній основі. In these paper three approaches to the problem of planning a route of unmanned aerial vehicles is discussed. A comparative analysis of search methods on graphs and multi-agent algorithms: the ant algorithm and the algorithm of the "request-reply-agreement" is given. Based on the analysis the integration of methods running on a parallel basis is proposed.
issn	1561-5359
url	https://nasplib.isofts.kiev.ua/handle/123456789/84968
citation_txt	Интеграционный подход к задаче выбора маршрута группы БПЛА / А.Н. Козуб, Д.П. Кучеров // Искусственный интеллект. — 2013. — № 4. — С. 333–343. — Бібліогр.: 9 назв. — рос.
work_keys_str_mv	AT kozuban integracionnyipodhodkzadačevyboramaršrutagruppybpla AT kučerovdp integracionnyipodhodkzadačevyboramaršrutagruppybpla AT kozuban íntegracíiniipídhíddozadačíviborumaršrutugrupibpla AT kučerovdp íntegracíiniipídhíddozadačíviborumaršrutugrupibpla AT kozuban integratedapproachtotheproblemofplanningtherouteofuav AT kučerovdp integratedapproachtotheproblemofplanningtherouteofuav
first_indexed	2025-11-26T15:10:29Z
last_indexed	2025-11-26T15:10:29Z
_version_	1850625837208961024
fulltext	ISSN 1561-5359 «Штучний інтелект» 2013 № 4 333 4К УДК 519.6:004.93 А.Н. Козуб 1 , Д.П. Кучеров 2 1 Национальная академия обороны Украины (НАОУ) Украина, 03049, г. Киев, пр. Воздухофлотский, 28 2 Национальный авиационный университет (НАУ) Украина, 03680, г. Киев, пр. Космонавта Комарова, 1 Интеграционный подход к задаче выбора маршрута группы БПЛА A.N. Kozub 1 , D.P. Kucherov 2 1 National Defense Academy of Ukraine Ukraine, 03049, Kyiv, Povitroflotskyi Ave, 28 2 National Aviation University Ukraine, 03680, Kyiv, Kosmonavta Komarova Ave, 1 Integrated approach to the problem of planning the route of UAV А.М.Козуб 1 , Д.П.Кучеров 2 1 Національна академія оборони України (НАОУ) Україна, 03049, м. Київ, пр. Повітрофлотський, 28 2 Національний авіаційний університет (НАУ) Україна, 03680, м. Київ, пр. Космонавта Комарова, 1 Інтеграційний підхід до задачі вибору маршруту групи БПЛА В статье рассматривается три похода к задаче планирования маршрута беспилотных летательных аппаратов. Проводится сравнительный анализ поисковых методов на графах и мультиагентные алгоритмы: муравьиный алгоритм и алгоритм «запрос-ответ-соглашение». На основе проведенного анализа предлагается интеграция поисковых походов на графах и мультиагентного, работающих на параллельной основе. Ключевые слова: планирование маршрута, мультиагентная система, поиск на графе. In these paper three approaches to the problem of planning a route of unmanned aerial vehicles is discussed. A comparative analysis of search methods on graphs and multi-agent algorithms: the ant algorithm and the algorithm of the "request-reply-agreement" is given. Based on the analysis the integration of methods running on a parallel basis is proposed. Key words: planning of the route, multi-agent system, search on graph. У статті розглядається три походи до задачі планування маршруту безпілотних літальних апаратів. Проводиться порівняльний аналіз пошукових методів на графах і мультиагентні алгоритми: мурашиний алгоритм та алгоритм «запит-відповідь-угода». На основі проведеного аналізу пропонується інтеграція пошукових походів на графах і мультиагентного, що працюють на паралельній основі. Ключові слова: планування маршруту, мультиагентна система, пошук на графі. Введение В настоящее время накоплен значительный опыт по созданию беспилотных летательных аппаратов (БПЛА), в то же время вопрос их эффективного применения, судя по значительному количеству публикаций в этом направлении в изданиях Козуб А.Н., Кучеров Д.П. «Искусственный интеллект» 2013 № 4 334 4К ближнего и дальнего зарубежья (см., например, [1-3] и ссылки), остается открытым. Одной из наиболее важных задач обеспечения полетов является задача планирова- ния маршрута БПЛА. Эта задача состоит в определении набора точек в про- странстве, которые бы отвечали траектории полета БПЛА и определялись на карте. На выбор маршрута оказывают влияние следующие факторы: ограниченное время полета; безопасность полета; множественность маршрутов. Последний фактор свидетельствует о неоднозначности пути, по которому будут следовать БПЛА. Решение этой задачи требует выдвижения критерия, по которому следует выбрать наиболее подходящий маршрут. В условиях препятствий полету необходимо увеличивать число промежуточных точек, которые обеспечивали бы возможность обхода возможных препятствий. В этом случае возникает совмест- ная задача, как сокращение маршрутного времени, так и уменьшения количества точек, по которым строится траектория. Безопасность полета определяется выбором соответствующих значений дис- танции, интервала и превышения в вертикальной плоскости между элементами группы. Это является самостоятельной задачей, основанной на практике применения БПЛА и корректном выполнении маневров при выполнении конкретных задач. Ограниченность полета по времени предполагает определение такого маршрута, который позволил бы решить поставленную задачу в установленное время. Из прак- тических соображений маршрут БПЛА должен состоять из прямолинейных участков и участков кривизны, соединяющих прямолинейные участки. В работах [1-3] предпринимались попытки решения задачи планирования маршрута с использованием геометрического подхода, базирующегося на работе [4]. Однако, оптимальная траектория при решения задачи по Дубинсу может оказаться физически не реализуемой, в таком случае имеем задачу с ограничением на кри- визну полета или же эти подходы в принципе не являются применимыми в условиях большого количества опорных точек, по которым строится маршрут. Для этого могут оказаться пригодными поисковые методы такие, как, например, поиск на графах [5], [6] и мультиагентные алгоритмы [7-9], интенсивно развиваемые в по- следнее время. Однако эти алгоритмы обладают проблемами сходимости и точности полученного решения. Таким образом, целью статьи является разработка подхода, обеспечивающего построение маршрутов группы БПЛА, которые имели бы минимальное расстояние между начальной и конечной опорными точками в условиях с большим количеством промежуточных точек на основе графов и мультиагентности. Постановка задачи. Задача функционирования группы БПЛА ставится в форме некоторого задания. В наиболее общей форме система, состоит из оператора с пультом управления, наземных средств управления, контроля и связи, группы из n БПЛА, n≥2. Предполагается, что БПЛА являются разноцелевыми и могут много- кратно использоваться (рис. 1). На рис. 1 введены обозначения областей выполнения задания О1-О4 отдельными БПЛА, маршруты М1-М4, БПЛА – Л1-Л5. Полученное задание вводится в вычислительную часть, где оно подвергается формализации и обработке планировщиком. Планировщиком определяется тре- буемое количество БПЛА, им назначаются маршруты, производится выдача заданий самолетам, мониторинг выполнения планов и обнаружение расхождения / несоот- ветствие их выполнения. БПЛА получают и отрабатывают задание, реагируют на определенные события и формируют отчета о выполнении задания. Этот процесс контролируется оператором, а именно производится анализ отчетов, при необходи- мости могут вноситься коррективы. Интеграционный подход к задаче выбора маршрута группы БПЛА «Штучний інтелект» 2013 № 4 335 4К Маршрут задается набором, включающим N опорных точек, определяемых пространственными координатами области выполнения задания. Предполагается, что значения начальной (x0, y0, z0) и конечной переменной (xk, yk, zk) фиксированы. Заданы также координаты препятствий, в виде координат (xj, yj, zj) центра и его радиуса, mj ,0= , m≠N, j≠k. Необходимо построить такое решение, которое по- зволяет выбрать набор n опорных точек, таких, что n<N, обеспечивает наименьшую длину пути каждому самолету: ∑ = < = n i i Nn SS 1 min , (1) где S =f(n, m, t), где t имеет смысл длительности алгоритма, а m – отрезки пути. Рисунок 1 – Структура мультиагентной системы с БПЛА Задача (1) определяет последовательность точек в пространстве возможных решений (граф), который обеспечивает минимальное расстояние между начальной и конечной точками с учетом всех возможных N. В статье представляются возможные подходы к построению оптимального маршрута по критерию минимума длины пути, основанные на различных подходах. Построение дерева решений Естественный путь к решению задачи (1) состоит в построении дерева решений и оптимизации маршрута по возможным направлениям. Дерево решений структурно состоит из внутренних и внешних узлов. Во внутренних узлах принимается решение о следующем посещаемом дочернем узле по расчетным значениям некоторой функции решения. Внешние узлы не содержат дочерних узлов, описывают зна- чение, характеризующее входные данные. Деревья решений могут строиться таким образом. В корневом узле рассчи- тывается функция решений по входным данным. Функция решения представляет длину маршрута с учетом путевых препятствий, фиксируемую на каждом очередном узле. По результатам расчета происходит переход к одному из дочерних узлов. Решением считается линия, соединяющая точку S с точкой F (рис. 2). Козуб А.Н., Кучеров Д.П. «Искусственный интеллект» 2013 № 4 336 4К При значительном количестве точек n такой граф представляет набор решен- ий, структура которого позволяет говорить о дереве (лесе) решений. Деревья реше- ний представляют собой нисходящую систему, основной целью которой является разделение дерева на взаимно непересекающиеся подмножества. Процедура при- нятия решения о принадлежности определённого состояния к тому или иному классу с помощью дерева решений относится к методам классификации состояний. Рисунок 2 – Поиск решения по дереву решений Отличительной особенностью такого графа является замкнутость, т.е. конеч- ная точка совпадает с начальной или достаточно близко к ней расположена, однако, S≠0, а ребра определяются кривыми второго порядка. Для упрощения построения графа будет считать ребра прямыми. В случае использования алгоритма с поиском по замкнутому графу (на- пример, Дейкстры [9]) выбор направления может быть сделан по наибольшему рас- стоянию, образуемым соседними треугольниками и следуемым из неравенства тре- угольника ),(),(),( jvcvicjiс +≤ , (2) где i, j, v – опорные узлы дерева. Такие переходы продолжаются до тех пор, пока не будет посещён конечный узел, описывающий либо метку класса, либо значение, связанное с входным вектором значений признаков. Наличие препятствий позволяет добавлять упрежденную путевую точку, в которой направление дальнейшего маршрута следования должно быть изменено. Алгоритм является одноагентным, детерминированным, однако требует как минимум одноразового посещения каждого узла с целью определения и фиксации в дальнейшем наименьшего расстояния. В отличие от муравьиного алгоритма является сходящимся. Алгоритмы, относящиеся к разряду алгоритмов поиска на графе, позволяют находить маршрут с наименьшей стоимостью пути от одной вершины к другой. К алгоритмам такого сорта можно отнести и алгоритмы поиска по дереву решений, Дейкстры, А* и их модификации. Время работы алгоритмов в общем случае не превышает O(n 2 ), а для разреженного графа О((n +m)logn), где n и m – количество вершин и ребер графа соответственно. Построение многоагентной системы с такими алгоритмами возможно при назначении агентам различных подзадач с централизованным распределением областей выполнения задач. Основными проблемными вопросами этих алгоритмов является требования к ресурсам памяти, требующих хранения экспоненциального числа узлов, и временные затраты на поиск всех возможных решений. Интеграционный подход к задаче выбора маршрута группы БПЛА «Штучний інтелект» 2013 № 4 337 4К Мультиагентные алгоритмы. В последнее время многими авторами, разви- вающими децентрализованное управление, пропагандируется подход мультиагент- ных систем [7-9], заимствованный из общественных биосистем, которым относят муравейник, пчелиный рой и другие. Данные системы привлекательны по некото- рым признакам, к которым относят, прежде всего, автономность действий отдельных агентов, децентрализация управления за счет реализации в системе коллективного интеллекта и обучаемость агентов. В зависимости от типа выбранной мультиагент- ной системы накопленная при поиске информация о пройденном маршруте пере- дается в виде феромона для муравьев или же виляющего танца для пчел. Как и в [7], в качестве агентов здесь будем иметь в виду агентов, подобным муравьям, оставляю- щих феромон как единицу информативности. Муравьиный алгоритм. В этой системе рассматривается набор агентов Am={a1, …, am}, выполняющих единую задачу – определение наилучшего маршрута путем многократного исследования пространства поиска в различных направлениях. Особенностью предполагаемого перемещения является наличие феромона, выделяе- мого агентами на пути в процессе своего перемещения. Считается, что маршрут представляется конечным набором отрезков, определяемых рядом опорных точек. Феромон, оставляемый на отрезке ij маршрута, с течением времени испаряется. Запись ij означает, что осуществляется переход из опорной точки i маршрута в точку j, рис. 3. Рисунок 3 – Действие муравьиного алгоритма при определении маршрута Таким образом, наилучшим маршрутом является тот, на котором остаётся большее количество феромона, так как добавление феромона происходит чаще, чем испарение. Тогда правило обновления феромона записывается в виде [9] ][][)1(]1[ kkpk ijijij τ+τ∆−=+τ , (3) В уравнении (3) τij[k] – текущее значение феромона, оставляемого на участке ij, ∆τij[k] имеет смысл количества отложенного феромона на отрезке ij проделанного маршрута очередным агентом на k-ой итерации с начальным значением τ[0], а p≤1 – коэффициент испарения феромона, определяемый интенсивностью действия агентов и выбираемый из интервала p∈[0, 1]. Вероятность выбора транспортировки агента из опорной точки i в точку j на k-ой итерации оценивается формулой [7] ( ) ( ) ( ) ( )∑ βα βα ητ ητ = l ilil ijij ij k k kP ][ ][ )( , (4) Козуб А.Н., Кучеров Д.П. «Искусственный интеллект» 2013 № 4 338 4К где η – видимость следующей опорной точки, представляет величину обратную расстоянию до нее, а α и β – весовые показатели интенсивности следа феромона и видимости, устанавливаемые на основании проводимых опытов. Достоинством подхода является возможность нахождения квазиоптимального маршрута, что достигается многократным повторением процедуры прохождения агентов по маршруту, соответствующему максимальному значению τ из (1). А длительность процедуры поиска является платой за проведенный поиск, что непосредственно ведет к поиску стратегий усовершенствования метода поиска. Как следует из (2) (см. также [9]), количество феромона является величиной вероятностной, поэтому для получения достоверного результата необходимо большое число повторений эксперимента, что значительно увеличивает время поиска наилуч- шего решения. К тому же алгоритм не является конвергентным, т.е. после обнару- жения ближайшего к лучшему решению генерируются новые решения, что дает положительное свойство – возможность избежать попадания в локальные экстремумы. К недостаткам метода следует также отнести эвристичность подхода, а именно от- сутствие строгого математического анализа приводит к тому, что все решения бази- руются только на результатах проводимых экспериментов. Описанный подход с агентами, участвующих в поиске, имеет смысл в задачах со значительным количеством неупорядоченных в пространстве опорных точек, когда возникают определенные трудности при поиске наилучшего маршрута. Следует предполагать, что ввиду большого числа агентов, задействованных в процедуре поиска, в определенных условиях возможно получать временной выигрыш в использовании муравьиного по сравнению с другими известными подходами. Данный подход может быть также целесообразен при выборе кратчайшего маршрута c использованием БПЛА при наличии значительного количества пре- пятствий на маршруте, воспринимаемых как дополнительные опорные точки. В задачах же с малым количеством опорных точек правильный выбор маршрута в большинстве случаев является очевидным и поэтому подход муравьиной колонии не может быть рекомендован к применению. Алгоритм «запрос-ответ-соглашение». Иным подходом к построению де- централизованных систем, использующим роевые решения и оптимизацию на основе деревьев решений при построении систем с БПЛА, является подход исполь- зования мультиагентных систем. В этом случае система также представляет набор агентов, общающихся между собой путем отправки запросов, получения ответа и далее принятия самостоятельного решения на продолжение поиска, которое следует воспринимать как двустороннее соглашение. Такой подход построения мультиагент- ных систем получил название «запрос-ответ-соглашение». В этом случае каждый агент мультиагентной системы занимается своей автономной задачей, способен производить не только обмен информацией с центром, но и оказывать помощь своим коллегам. В соответствии с указанными свойствами, каждому агенту-БПЛА указывается свой специфический маршрут, который не пере- секается с маршрутом агента-коллеги, но может дополнять его. Исходя из на- значения БПЛА, будем считать все маршруты замкнутыми. Варианты маршрутов БПЛА могут использовать схемы, представленные на рис. 4 – 6, где показано, что они могут координироваться также центром управления, представляемого на рисунках оператором. С целью повышения производительности функционирования системы, может быть назначено и большее количество агентов на один маршрут, как это показано на рис. 5. В системе управления с мультиагентным подходом используется аналогия феромон – информация, феромон испаряется – информация устаревает. Представленные Интеграционный подход к задаче выбора маршрута группы БПЛА «Штучний інтелект» 2013 № 4 339 4К на рис. 4-6 возможные маршруты, показывают типовые варианты движения БПЛА на открытых участках местности по замкнутым маршрутам с широким и узким кольцах, а также зигзагообразный. В зависимости от размера области выполнения задачи предполагается, что большая по величине область соответствует маршруту с широким кольцом, а узкая – малой. Рисунок 4 – Маршруты движения БПЛА в широком кольце Рисунок 5 – Маршрут движения БПЛА в узком кольце Рисунок 6 – Зигзагообразные маршруты движения БПЛА Козуб А.Н., Кучеров Д.П. «Искусственный интеллект» 2013 № 4 340 4К Из анализа рис. 4 – 6 видно, что характерными элементами маршрутов являются участки прямолинейного и кругового движений БПЛА, что вполне реали- зуемо техническими средствами, хотя и может требовать значительных вычисли- тельных затрат и хорошей информативности канала связи. Сравнительная оценка различных подходов к построению мультиагентных систем с БПЛА. В результате рассмотрения различных подходов к задаче планиро- вания маршрутов БПЛА в сложных условиях позволяет сделать вывод о целесо- образности ее построения как мультиагентной системы. Все эти алгоритмы бази- руются на разных системах знаний. Так, муравьиный алгоритм требует информацию об испаряемости феромона, видимости (длины) маршрута, набора агентов и по сути является вероятностным. Алгоритм поиска решений на графах является детерми- нированным, использует информацию только об опорных точках и расстоянии между ними, наилучший маршрут определяется одним агентом. Модель «запрос-ответ-со- глашение» также относится к вероятностным, как и муравьиный алгоритм. Алгоритмы муравьиной колонии и принцип «запрос-ответ-соглашение» обладают определен- ными недостатками. Так муравьиному алгоритму свойственны итерационность и многократность повторения связанная с вероятностной природой алгоритма, что приводит к значительным временным затратам на поиск квазиоптимального решения. В свою очередь подходу «запрос-ответ-соглашение» требуется только предваритель- ное определение задачи (конечной цели) и значительное время на согласование действий с соседями. Алгоритмы поиска решений на графе являются хорошо сходящимися, детер- минированными алгоритмами, однако предназначены для работы с одним агентом. Обобщенные результаты сравнительной оценки алгоритмов поиска представлены в табл. 1. Таблица 1 – Сравнительная оценка алгоритмов поиска маршрута Алгоритм поиска решений на графе муравьиный «запрос-ответ- соглашение» Основа детерминированный вероятностный вероятностный Сходимость экспоненциальная полиномиальная полиномиальная Агентность одноагентный мультиагентный число агентов определяется количеством решаемых задач Ресурсы требует хранения всей карты узлов не требует хранения информации о всех узлах не требует хранения информации о всех узлах Информирование исходные данные феромоном запросное Размерность малая высокая высокая В табл. 1 размерность следует выбирать, руководствуясь выводами [7], где малая размерность определена как n<20. Реализация задачи планирования маршрута группы БПЛА. Определение маршрута каждому элементу в группе из БПЛА в сложных условиях функциониро- вания является важной и в тоже время длительной процедурой, связанной с мно- жественностью выбора из возможных решений. Естественным образом возникает желание применить централизованное управление, когда устанавливается маршрут по жесткой схеме, что может приводить к неоправданной трате ресурсов. Интеграционный подход к задаче выбора маршрута группы БПЛА «Штучний інтелект» 2013 № 4 341 4К Анализ возможных решений данной задачи дает представление о способах построения систем, обеспечивающих разработку плана маршрутов. Рассмотренные способы базируются на одноагентном и мультиагентном подходах. Одноагентный, в отличие от мультиагентного подхода, обладает высокой точностью получающихся решений, хотя и проигрывает мультиагентному в скорости сходимости в задачах с высокой размерностью и требованиях к памяти системы. Поэтому представляет интерес интегрировать эти подходы и ожидать от такой комбинации системного эффекта, обеспечивая работу мультиагентного подхода при высокой размерности системы, по мере прохождения опорных точек и, соответственно, сокращении размерности системы передать дальнейший поиск оптимального решения одноагентному алгоритму. Схематически такую интеграцию можно представить в виде следующей схемы рис. 7. Рисунок 7 – Схема интеграции алгоритмов На рис. 7 алгоритмы мультиагентного поиска и поиска на графе работают параллельно и выдают результаты поиска на блок анализа сложности системы. Блок анализа сложности производит оценку сложности задачи путем обратного отсчета необработанных результатов. Принимается решение о целесообразности выдачи в качестве результатов Sma системы мультиагентного поиска или Sгр поиска на графе, в случае определения лучших результатов в при поиске. Сигнал u, который выда- ваемый в блок поиска на графе, говорит о приоритетности результатов этого блока и выдает в качестве результата наилучший маршрут. Данная интеграция позволяет получить решение значительно точнее и быстрее, чем отдельное использование алгоритма решения на графах или же мультиагент- ного. Особенностью подхода является параллельное использование алгоритмов, что обеспечивает высокую скорость сходимости и достаточную точность результата за счет использования точного метода, которым является поиск на графе. В случае, когда анализатор сложности задачи обнаруживает возможность использования поиска на графе, то выдаваемый сигнал u обеспечивает перезагрузку исходных данных А с мультиагентного алгоритма на графовый. Такой переход с одного алгоритма на другой позволяет реализовать идею адаптации к сложности задачи. Полный маршрут формируется в блоке анализа сложности задачи. Данный подход в целом позволяет эффективно решать сложные практические задачи планирования маршрутов БПЛА. Выводы. В статье рассматривается задача выбора маршрута при коллектив- ном использовании БПЛА, а также приводится сравнительный анализ алгоритмов, основанных на различных системах знаний, а именно алгоритмов, применяемые в Козуб А.Н., Кучеров Д.П. «Искусственный интеллект» 2013 № 4 342 4К мультиагентных системах и алгоритмов поиска на графах. Среди мультиагентных рассмотрены муравьиный алгоритм и алгоритм «запрос-ответ-соглашение». Альтер- нативой мультиагентным системам представлено также решение этой задачи детер- минированным алгоритмом, использующим подход поиска решений на графе, обладаю- щим превосходными свойствами сходимости и точности в определении результата. Наилучшего решения задачи выбора маршрута в системах высокой размер- ности, как показано в статье, следует ожидать в комбинировании рассмотренных алгоритмов, когда недостатки продолжительности поиска и точности мультиагент- ных подходов будут компенсироваться сходимостью и точностью графовых алгоритмов поиска решений, что позволит реализовать триаду «интеллект-адаптация- управление» в достижении свойства эмерджентности разрабатываемых систем. Литература 1. Shanmugavel M. Differential Geometric Path Planning of Multiple UAVs / Shanmugavel M., Tsourdos A., White B.A., Zbikowski R.W. / Transactions of the ASME. Journal of Dynamic Systems, Measurement, and Control. - Vol. 129, 2007, p. 620-632. 2. Степанян К.В. Планирование траектории БПЛА в сложных условиях при наличии угроз / Степанян К.В., Миллер А.Б., Миллер Б.М. // Материалы 33-й конференции молодых учених и специалистов ИППИ РАН «Информационные технологи и системы» (ИТИС”10) 20-24 сентября 2010, Россия, Геленджик, с.263-268. [Electronic resource]. – Access mode: http://www.itas2010.ittp.ru/pdf/1569326822903.pdf. 3. Алдошин Д.В. Планирование пространственных маршрутов для БПЛА с использованием поиска на графах / Алдошин Д.В. // Молодеж. науч.-техн. вестник. - №2. – 2013. [Электронный ресурс] – Режим доступа: http:// sutbud.bmstu.ru / doc / 551948.html 4. Dubins L.E. On curves of minimal lengthwith a constrainton overage curvature, and with prescribed initial and terminal positions and tangents / Dubins L.E. // AM. J. Math. – 1957. - 79. – P. 497-516. 5. Гофман Е. А. Мультиагентный метод построения деревьев решений / Е. А. Гофман, А. А. Олейник, С. А. Субботин // Бионика интеллекта. - № 1 (75). - 2011. - С. 35–40 6. Кормен Т.Х. Алгоритмы: построение и анализ / Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. – М.: ИД «Вильямс», 2005. – 1293 с. 7. Субботін С.О. Неітеративні, еволюційні та мультиагентні методи нечітко логічних і нейромережних моделей / Субботін С.О., Олійник А.О., Олійник О.О. // Запоріжжя: ЗНТУ, 2009. – 375 с. 8. Ходашинский И.А. Алгоритмы муравьиной и пчелиной колонии / И.А. Ходашинский, И.В. Горбунов, П.А. Дудин // Доклады ТУСУРа, № 2 (20), декабрь 2009. – С. 157-161. 9. Штовба С.Д. Мурашині алгоритми оптимізації / Штовба С.Д., Рудий О.М. // Вісник ВПІ. - № 4. – 2004. – С.62-69. Literaturа 1. Shanmugavel M. Differential Geometric Path Planning of Multiple UAVs / Shanmugavel M., Tsourdos A., White B.A., Zbikowski R.W. / Transactions of the ASME. Journal of Dynamic Systems, Measurement, and Control. - Vol. 129, 2007, p. 620-632. 2. Stepanyan K.V. UAV path planning in difficult conditions, with threats / Stepanyan K.V., Miller A.B., Miller B.M. // Proceedings of the 33rd conference of young scientists and specialists IPPI RAN "Information Technologies and Systems" (ITIS '10), 20-24 September 2010, Russia, Gelendzhik, p.263- 268. [Electronic resource]. – Access mode: http://www.itas2010.ittp.ru/pdf/1569326822903.pdf. 3. Aldoshin DV Spatial planning routes for UAVs using search on graphs / DV Aldoshin / / Youth. Scientific-Technical. Bulletin. - № 2. - 2013. [Electronic resource]. – Access mode: http:// sutbud.bmstu.ru / doc / 551948.html 4. Dubins L.E. On curves of minimal lengthwith a constrainton overage curvature, and with prescribed initial and terminal positions and tangents / Dubins L.E. // AM. J. Math. – 1957. - 79. – P. 497-516. Интеграционный подход к задаче выбора маршрута группы БПЛА «Штучний інтелект» 2013 № 4 343 4К 5. Hoffman E.A. Multiagent method of decision trees / E.A. Hoffman, A.A. Oleinik, S.A. Subbotin // Bionics intelligence. - № 1 (75). - 2011. - P. 35-40. 6. Cormen T.H. Algorithms: construction and analysis / Corman T.H., Leiserson Ch.I., Rivest R.L., Stein C. – Moscow: ID "Williams", 2005. - 1293 p. 7. Subbotіn SO Neіterativnі, evolyutsіynі that multiagentnі methodological nechіtko logіchnih i neyromerezhnih models / Subbotіn S.O., Olіynik A.O., Olіynik O.O.// Zaporizhzhya: Zaporozhye National Technical University, 2009. – 375 p. 8. Khodashinsky I.A. Algorithms and ant bee colony / I.A. Khodashinsky, I.V. Gorbunov, P.A. Dudin // Reports TUSUR, № 2 (20), December 2009. - P. 157-161. 9. Shtovba S.D. Murashinі algorithmic optimіzatsії / Shtovba SD, Rudy O. // News VPІ. - № 4. - 2004. - P.62-69. RESUME A.N. Kozub, D.P. Kucherov Integrated approach to the problem of planning the route of UAV In this paper considered the problem of planning a route of unmanned aerial vehicles in complex environment with a lot of control points. To solve this problem are analyzed deterministic and probabilistic approaches. Among deterministic approaches are chosen search methods on graphs are considered as probabilistic multi-agent: an ant algorithm and the algorithm of the "request-reply-agreement". A comparative analysis of the considered algorithms is given. A distinctive feature of deterministic algorithms is the accuracy of the solutions, but in difficult conditions, this accuracy is achieved considerable duration of the work, at the same time multi-agent have a higher convergence, but have low accuracy. Based on the analysis is proposed integration of search approaches on graphs and multi-agent running on a parallel basis, which leads to the acquisition system, the so-called "systemic effect". Статья поступила в редакцию 10.07.2013.

Интеграционный подход к задаче выбора маршрута группы БПЛА

Institution

Ähnliche Einträge