Библиографическое описание:

Абабий В. В., Судачевски В. М., Подубный М. В., Негарэ Е. А. Многоагентная ассоциативная вычислительная система // Молодой ученый. — 2015. — №16. — С. 30-36.

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

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

 

Введение. По определению Многоагентные Системы (МАС) представляют собой взаимодействие множества индивидуальных интеллектуальных агентов (ИА) используемые для решения общей задачи, решение которой невозможно одним агентом или требует большое количество материальных и/или временных ресурсов, что делает решение данной задачи нецелесообразной [1]. К таким задачам можно отнести задачи искусственного интеллекта (ИИ) решение которых базируется на использование: нейронных сетей, нечеткой логики, генетических алгоритмов и множество математических методов и моделей для ввода и обработки больших объемов информации.

Качество индивидуальности и автономности для ИА является характерной чертой для МАС, что делает данный класс систем принятия решения очень эффективными и устойчивыми к архитектуре и воздействиям внешней среды [2,3].

В зависимости от области применения ИА могут выполнять множество функций, из которых можно выделить несколько главных: ввод данных о состоянии окружающей среды, обработка и хранение данных, обмен данными между агентами, принятие решения и воздействие на внешнюю среду через систему актуаторов. Сложность выполняемых функций может идентифицировать техническую и алгоритмическую сложность ИА. В работах [4,5] предложено проектирование МАС на базе технических средств с ограниченными вычислительными ресурсами, что позволяет снизить себестоимость проектирования при сохранении качественных и количественных характеристик.

Важным критерием функциональности МАС является ее динамичность и масштабируемость информационной топологии, которая определяется разметом и направлением передачи потоков информации в сети в зависимости от решаемой задачи или информационного потока [6].

В настоящее время ассоциативные вычислительные системы нашли широкое применение в различных областях науки и техники. Характерным для таких систем является то, что обращение к данным производится по отличительным признакам, содержащимся в самих данных. Такой способ удобен при обработке больших объемов информации, особенно при решении задач искусственного интеллекта. Преимуществом ассоциативных вычислительных систем является способность поиска информации по признакам и параллельная обработка информации при использовании множества сложных ассоциативных процессоров [7,8] или интеллектуальных агентов [1,2].

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

Решение поставленной задачи. Для решения поставленной задачи в работе рассмотрены следующие вопросы: проектирование структурной схемы МАС, формулировка математической модели, синтез логической структуры агентов, проектирование алгоритма распределения вычислительной мощности между агентами, пример функционирования МАС в виде диаграммы последовательностей.

Проектирование структурной схемы.

На Рисунке 1 представлена структура многоагентной ассоциативной вычислительной системы, где:  — множество мобильных агентов, которые формируют ячеечную вычислительную сеть;  — возможные варианты обмена данными между агентами;  — множество стационарных агентов, которые совместно с множеством Wireless Router  формируют сеть с топологией общая магистраль;  — окружающая среда или область активности МАС.

Рис. 1. Структура многоагентной ассоциативной вычислительной системы.

 

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

Формулировка математической модели.

Математическую модель функционирования МАС можно представить в виде выражения:

,                                                                                                    (1)

где:  — множество правил преобразования пространства состояний  при условии, что  и ;  и  — пространство состояний в момент времени ;  — пространство состояний в момент времени . Множество  это состояние окружающей среды и соответственно  это состояние агентов принимающие решения о преобразовании пространства состояний.

Идеальным условием определения МАС можно считать условие . В таком случае выражение (1) можно представить в виде равенства .

Множество правил  преобразования пространства состояний  можно представить в виде множества простых алгоритмов:

,                                                                                      (2)

где:  — множество алгоритмов для преобразования состояния агентов и  — множество алгоритмов для воздействия на окружающую среду.

Каждое правило преобразования пространства состояний  это множество алгоритмов выполняемые агентом .

В результате анализа множества алгоритмов  можно выделить подмножества одинаковых алгоритмов , которые отличаются только обрабатываемыми данными. В таком случае, в равенстве (2), необходимо произвести замену одинаковых алгоритмов на алгоритм . Такое преобразование позволит снизить программную сложность и сэкономить память для хранения программ при реализации правил преобразования пространства состояний .

Синтез логической структуры агентов.

Логическая структура агентов (Рисунок 2) представляет собой взаимодействие функциональных блоков с указанием управляющих и информационных потоков.

Рис. 2. Логическая структура агентов.

 

Логическая структура агента содержит:

 — процессор, предназначенный для выполнения арифметических и логических команд и управления составными частями вычислительной системы агента;

 — память программ и данных, которая содержит:  — ядро и данные операционной системы (ОС);  — собственные процедуры агента , которые включают методы преобразования пространства состояния и запросы на обслуживание другими агентами сети;  — общие процедуры агента , предназначенные для обслуживания запросов генерируемые агентами подключенные к сети;  — данные предназначенные для обработки, это собственные данные и данные, полученные от агентов из сети, предназначенные для обработки на базе общих процедур ;

 — интерфейс для обмена данными в сети (Ethernet or WiFi);

 — порты ввода — вывода данных, это: порты ввода данных от набора датчиков и команд пользователя, и порты вывода для воздействия на окружающую среду и информирования пользователя;

- окружающая среда определяющее состояние системы;

1 — операции ОС для управления вводом — выводом;

2 — управление вводом — выводом собственными процедурами;

3 — управление вводом — выводом общими процедурами, это обеспечивает доступ любого агента к портам для ввода данных о состоянии окружающей среды и вывод данных для воздействия на окружающую среду через данный агент;

4 — поток входных и выходных данных;

5 — операции ОС для управления обменом данными в сети;

6 — управление обменом данными в сети собственными процедурами агента;

7 — управление обменом данными в сети, инициируемые общими процедурами, это обеспечивает формирование последовательности запросов к другим агентам;

8 — данные принимаемые из сети и передаваемые в сеть;

9 — выходные сигналы для воздействия на окружающую среду;

10 — входные сигналы от датчиков о состоянии окружающей среды.

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

Проектирование алгоритма распределения вычислительной мощности между агентами.

Пусть в пространстве  определена задача  сложности . Задача  решается МАС состоящая из  устройств с ограниченными вычислительными ресурсами, где  и  — множество процедур  выполняемые агентом , то есть это множество   и  , где .

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

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

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

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

1)        Постановка задачи ;

2)        Определение топологии сети, множество мобильных  и множество стационарных  агентов;

3)        Определение множества   и   для каждого агента;

4)        Проверка выполнения условия , если условие выполнимо переход на п.5, если невыполнимо переход на п.3 для перераспределения  между другими агентами;

5)        Утверждение   для каждого агента и формирование таблицы имен процедур и  адрес агента решающий соответствующую процедуру;

6)        Конец алгоритма.

Пример функционирования МАС.

Для разъяснения принципа функционирования многоагентной ассоциативной вычислительной системы предлагается пример на базе диаграммы последовательностей (Рисунок 3).

Рис. 3. Пример функционирования МАС на базе диаграммы последовательностей.

 

На диаграмме последовательностей представлено МАС, которая состоит из  агентов, где:

 — все агенты параллельно выполняют собственные процедуры ;

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

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

 

Литература:

 

1.                  Wooldridge, Michael. An Introduction to MultiAgent Systems, John Wiley & Sons Ltd, 366 p., 2002, ISBN 0–471–49691-X.

2.                  Weiss, Gerhard. Multiagent Systems. A Modern Approach to Distributed Artificial Intelligence, MIT Press, 1999, ISBN 0–262–23203–0.

3.                  Емельянов, В. В.: Курейчик, В. В.; Курейчик, В. М. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003. — 432 с. — ISBN 5–9221–0337–7.

4.                  Абабий, Виктор; Судачевски, Виорика; Подубный, Марин; Морошан, Ион. Ассоциативная вычислительная сеть для решения сложных задач на базе устройств с ограниченными вычислительными ресурсами. Proceeding of the 3rd International Conference «Computational Intelligence (Results, Problems and Perspectives) — 2015", ComInt-2015, May 12–15, 2015, Cherkasy, Ukraine, pp. 48–49.

5.                  Абабий, В.; Судачевски, В.; Подубный, М.; Сафонов, Г. Ассоциативная распределенная вычислительная система. Proceedings of the Ninth International Scientific-Practical Conference INTERNET — EDUCATION — SCIENCE, IES-2014, 14–17 October, 2014, Vinnytsia, Ukraine, pp. 187–189, ISBN 978–966–641–491–8.

6.                  Олифер, В. Г.; Олифер, Н. А. Компьютерные сети. Принципы, технологии, протоколы. Учебное пособие. — Санкт-Петербург: Питер, 2010, 943 с. ISBN: 978–5-49807–389–7.

7.                  Цилькер, Б. Я. Организация ЭВМ и систем: Учебник для вузов. / С. А. Орлов, Б. Я. Цилькер. — 2-е изд. — СПб.: Питер, 2011. — 688 с. — ISBN 978–5-49807–862–5.

8.                  Михайлов, Б.М.; Халабия, Р. Ф. Классификация и организация вычислительных систем: Учебное пособие. — М.: МГУПИ, 2010. -144с.

Обсуждение

Социальные комментарии Cackle