Аналитический обзор существующих методов и подходов к планированию групповых действий

Информация » Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов » Аналитический обзор существующих методов и подходов к планированию групповых действий

Страница 5

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

В случае, если агент использует для принятия решения оценки будущего, необходимо выстроить прогноз об изменении окружения агента после совершения им какого-либо действия. Здесь возможны два варинта:

в детерминистическом мире модель перехода отображает единственным образом пару состояние-действие в новое состояние;

в стохастическом мире модель перехода отображает пару состояние-действие в распределение вероятности состояний.

В качестве примера алгоритма, использующего мультиагентные системы, рассмотрим алгоритм, предложенный в [3]. Данный алгоритм основан на том, все БЛА связаны в единую сеть, внутри которой принимаются решения о распределении объектов наблюдения между ними. Как и во многих других схожих алгоритмах, принятие решения является коллективным и базируется на том, что каждый БЛА выдвигает предложение о том, к какому объекту он считает необходимым двигаться. Остальные БЛА в процессе переговоров могут принять или отвергнуть это решение.

Сам процесс принятия решения состоит в следующем. Каждый агент в течение одного цикла переговоров совершает 4 действия:

отправляет или получает предложение,

обдумывает полученное предложение,

отправляет ответ (согласие или несогласие),

принимает решение.

Каждый агент вычисляет выигрыш, полученный в том случае, если он последует за ней по следующей формуле

bi(Tj) = VTjwr – St,

где VTjwr – «цена» объекта,

St – относительное время преследования объекта

Таким образом, для каждой цели БЛА формирует списки выигрышей, полученных от следования за каждым объектом, и рассылает другим БЛА номер того объекта, за который он получит максимальную выгоду.

На втором и третьем шагах, когда данные от всех БЛА собраны, каждый из них анализирует полученную информацию и принимает решение о согласии или несогласии и этим на основании следующих правил:

если объект выбран только одним БЛА, то данное предложение одобряется;

если объект выбран несколькими БЛА, то согласие посылается только тому БЛА, для которого максимален выигрыш;

один БЛА может отправить только одно согласие для каждой цели;

если все соседи данного БЛА (то есть те БЛА, от которых он находится в непосредственной близости) согласны с его целью, он получает право на принятие решения о целесообразности следования до его текущей цели;

Четвертый шаг заключается в анализе полученных ответов и принятии решения. Если БЛА получил согласия от всех соседей, он выполняет запланированное действие. Если он получил отказ хотя бы от одного из соседей, он участвует в следующем цикле переговоров. Если же БЛА получил отказ от всех своих соседей, он выполняет задачу поиска новых объектов.

Выделим сильные и слабы стороны данного подхода

Сильные стороны:

постоянное взаимодействие между агентами;

коллективное принятие решения всеми агентами.

Слабые стороны:

в случае необходимости использования большой истории действий возрастает ресурсоемкость данного подхода;

агент зачастую действует по аналогии с жадным алгоритмом, а значит его решение в общем случае нельзя считать оптимальным;

необходимость использования стохастических прогнозов в случае использования информации об оценках будущей реакции окружения да действия агентов.

Задача многих коммивояжеров

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

Очевидно, что вместо торговцев в данной задаче также могут быть представлены БЛА, которым нужно облететь некоторое количество наземных объектов.

Страницы: 1 2 3 4 5 6

Похожие статьи:

Структура и функции организации материально-технического обеспечения на предприятии
Для бесперебойного функционирования производства не­обходимо хо­рошо налаженное материально-техническое обес­печение (МТО), кото­рое на предприятиях осуществляется через органы материально-техниче­ского снабже­ния. Главной задачей органов снабжения предприятия являет­ся своевре­мен­ное и оптимально ...

Разработка лотка
В данном механизме применяется лоток скат коробчатого типа. При конструировании лотков-скатов коробчатого типа следует выбрать значения размеров поперечного сечения лотка, угол наклона и высоту бортов. Для решения первой поставленной задачи, т.е. для определения размеров поперечного сечения лотка, ...

Характеристика детали
Корпус буксы предназначен для передачи нагрузки от массы вагона на шейку оси, ограничения перемещений колесной пары вдоль и поперек относительно рамы тележки и размещения подшипников (рис. 2.1). Рисунок 2.1 – Корпус буксы В корпус буксы закладывают смазку. Конструкция корпуса буксы определяется схе ...

Навигация

Copyright © 2018 - All Rights Reserved - www.localtransport.ru