Создание алгоритма для мультиагентной системы
Интеллектуальный агент — это элемент в системе, выполняющий задачи, стоящие перед ним. Агент обладает следующими свойствами: активность, автономность, целенаправленность.
Существует 2 вида структуры агента: гетерогенное и гомогенное. Гомогенные агенты сконструированы идентично, то есть особо не отличаются друг от друга. А гетерогенный вид означает, что агенты отличаются друг от друга.
Также существует 2 вида среды: детермированная и недетермированная. В детермированной среде нет никакой случайности, то есть всегда выполнение действий будет приводить к одному и тому же результату. А недетермированная среда характеризуется непредсказумостью.
Существует 2 основных подхода управления роботами: централизованная и децентрализированная. Централизованная система означает, что есть один какой-то агент, который руководит всем. А децентрализованная противоположна централизованной, то есть каждый агент действует независимо.
Мультиагентная система (МАС) — это система, состоящая из нескольких интеллектуальных агентов. Например, муравейник, он состоит из множества агентов, муравьев.
Актуальность: Мультиагентная система, в отличие от других методов, характеризуется высокой производительностью, быстротой решения поставленных задач и гибкостью.
Цель работы — Создание математической модели и алгоритма для роботизированной системы. Задачи:
Изучить аналоги и существующие решения;
Изучить МАС;
Сделать постановку решаемой задачи и сформировать начальные ограничения;
Выбрать вид МАС;
Создать математическую модель;
Разработать алгоритм.
Анализ предметной области
Группа роботов — совокупность взаимодействующих между собой агентов, стремящихся к общей цели. Примеры группового взаимодействия в живой природе — это стая волков, птиц, рыб, также команда по футболу и хоккею. Группа роботов может состоять из однотипных, то есть из одинаковых агентов, а может состоять из разнотипных, то есть из разных агентов, выполняющих разные функции.
Задача группового управления — задача управления группой роботов, действия которых направлены на достижение общей групповой цели. Смысл задачи группового управления заключается в нахождении и реализации таких действий каждого робота группы, которые приводили бы к оптимальному достижению цели.
Виды стратегий группового управления
Как было сказано ранее, существует 2 главных стратегии группового управления: централизованная и децентрализованная. Централизованное управление в свою же очередь делится на единоначальное управление и иерархическое управление. А децентрализованное управление делится на коллективное и стайное управление.
Единоначальное управление
Единоначальное управление означает, что есть одна группа агентов, которые подчиняются одному центральному агенту.
Иерархическое управление
Иерархическое управление значит, что есть несколько групп агентов, которые подчиняются своему центральному управлению 2 уровня, а эти центральные управления, в свою очередь, подчиняется центральному управлению 1 уровня.
Коллективное управление
Коллективное управление означает, что все агенты могут обмениваться друг с другом информацией и принимать самостоятельно решения.
Стайное управление
Стайное управление означает, что агенты сами анализируют и принимают решения. Стайное управление представлено на картинке.
Существует несколько методов роевого интеллекта, таких как метод частиц в стае, метод муравьиных колоний и метод пчелиных колоний.
Основная идея метода частиц заключается в поведении стаи животных при поиске чего-либо. Каждый член стаи имеет свое положение и скорость. Члены стаи сообщают информацию о позициях друг другу и используют ее для корректировки своего положения. Поиск заканчивается при достижении максимального числа итераций.
Метод муравьиных колоний моделирует колонии муравьев. Муравей при прохождении оставляет за собой след, феромон. Чем больше феромона на тропе, тем больше она привлекательней для колонии. Муравьи также используют информацию об окружающей среде при поиске.
Метод пчелиного роя основан на моделировании поведения пчел при поиске нектара. Для описания поведения пчел в природе используются три следующих основных понятия: источник нектара, занятые фуражиры и незанятые фуражиры. Источник нектара означает полезность, которая характеризуется удаленностью от улья, концентрацией нектара. Занятые фуражиры — это пчелы, которые имеют связь с одним из источников нектара и обладают информацией о полезности источника. Незанятые фуражиры — это пчелы, которые выполняют функцию разведки и наблюдения.
Постановка задач
Пусть будет централизованное иерархическое управление. Агенты имеют гетерогенный вид. Пусть среда будет недетермированной. Также мы будем использовать метод пчелиного роя.
Пусть G — множество грузовиков 
, P — множество погрузчиков 
— общее количество роботов.
Территория разбита на множество секторов 
. На территории находится неподвижные цели 
где w — ценность сектора. wi рассчитывается по формуле
, где dist — функция расстояния между двумя секторами, rk– сектор, в котором находится робот, ri — сектор, чью ценность мы рассчитываем.
Секторы, в которые может перемещаться агент
Роботы могут перемещаться только в тот сектор, находящийся рядом с сектором, в котором находится робот. 
— секторы, в которые может переместиться робот pi. Секторы, в которые робот может переместиться показаны на изображении.
Пусть 
— это множество вместимостей для грузовиков 
соответственно. Под вместимостью грузовика подразумевается его способность переносить некоторое количество груза, где
Пусть 
— это множество заряда батареи робота.
Алгоритм
Робот pi анализирует сектора R и обнаруживает цели T, если ничего не обнаруживает, то не выполняет никакие команды. Затем определяет ценности секторов.
Если целей несколько, то выбирается ближайшая цель. Робот pi перебирает все возможные пути к сектору rk, в котором находится ближайшая цель 
и выбирает кратчайший путь. Если несколько одинаковых путей, то робот выбирает любой. Затем роботы p, g начинают двигаться к этому сектору. При передвижении сектора изменяют свою ценность по формуле.
В момент, когда роботы достигают сектора 
, они начинают процесс отчистки сектора до того, как tm = 0. Если вместимость 
грузовика 
%, то грузовик приостанавливает процесс и едет к сектору 
, где он будет сваливать свой груз и возвращаться обратно.
Если есть несколько грузовиков, то вместо 
приезжает другой грузовик 
в сектор 
, и продолжит работу. Также, если заряд робота 
заканчивается, то он едет на начальную точку, заряжается и едет обратно. После того, как сектор был отчищен, робот pi будет проделывать такой же алгоритм до того, как 
.
Пример
Пусть есть территория, которая состоит из 16 секторов. Есть 1 робот 
и 2 робота 
и 
. Роботы 
, 
, 
находятся в секторе r1.
Робот 
обнаруживает цели 
в секторах r13 и r16 соответственно, а затем определяет ценность секторов.
Секторы, в которых находятся цели отмечены голубым цветом на изображении, также представлена ценность секторов 
.
Затем робот 
выбирает кратчайший путь к ближайшему сектору, в этом случае это r13. И начинает движение к нему. В это же время роботы 
и 
следуют за роботом погрузчиком. Это представлено на изображении.
При передвижении, роботы меняет ценность секторов. Это представлено в и.
Это продолжается до того, как роботы не окажутся в секторе r13. Когда роботы добрались, они начинают устранять.
В течение устранения вместимость 
грузовика 
заполнилась, значит он начинает движение к сектору 
для разгрузки. В это же время 
берется за работу вместо 
. Также, при работе роботы проверяют свой заряд v, при необходимости робот едет в сектор 
, заряжается и едет обратно. Это продолжается до того, как, затем роботы возвращаются в изначальный сектор.
Заключение
В результате проделанной работы, были изучены мультиагентные системы, их виды, подходы к управлению системами, методы роевого интеллекта, а также изучен математический язык для создания математической модели и создания алгоритма.
В дальнейшем планируется внедрение этого проекта в другой проект, суть которого заключается в создании группы роботов, которая состоит из 2 видов робота, один из которых будет погрузчиком, а другой — грузовиком. Эта группа роботов будет убирать мусор, завалы и т. д.
