31838

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

Дипломная

Информатика, кибернетика и программирование

КЛАССИФИКАЦИЯ АГЕНТОВ. КОЛЛЕКТИВНОЕ ПОВЕДЕНИЕ АГЕНТОВ. АРХИТЕКТУРА ВЗАИМОДЕЙСТВИЯ СИСТЕМЫ АГЕНТОВ Одноуровневая архитектура взаимодействия агентов Иерархическая архитектура взаимодействия агентов. АРХИТЕКТУРА АГЕНТА Общая классификация архитектур Архитектуры агентов основанные на знаниях Архитектура на основе планирования реактивная архитектура Многоуровневость.

Русский

2013-09-01

662.93 KB

158 чел.


ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 3

1 ОПИСАНИЕ И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 5

1.1 АНАЛИЗ ДЕЯТЕЛЬНОСТИ ТАКСОПАРКА 5

1.1.1 ОПИСАНИЕ ДЕЯТЕЛЬНОСТИ СОТРУДНИКОВ 7

1.1.2 ОБЗОР СУЩЕСТВУЮЩЕГО ПРОГРАМНОГО ОБЕСПЕЧЕНИЯ 8

Схема работы 9

Функциональные возможности программы «2Т-ТАКСИ» 13

1.2 МУЛЬТИАГЕНТНЫЕ СИСТЕМЫ 16

1.2.1 ПОНЯТИЕ АГЕНТА 18

1.2.2 КЛАССИФИКАЦИЯ АГЕНТОВ 20

1.2.3 КОЛЛЕКТИВНОЕ ПОВЕДЕНИЕ АГЕНТОВ 24

1.2.4 МОДЕЛИ КОЛЛЕКТИВНОГО ПОВЕДЕНИЯ 25

1.2.5 АРХИТЕКТУРА МНОГОАГЕНТНЫХ СИСТЕМ 29

1.2.6 АРХИТЕКТУРА ВЗАИМОДЕЙСТВИЯ СИСТЕМЫ АГЕНТОВ 30

Одноуровневая архитектура взаимодействия агентов 30

Иерархическая архитектура взаимодействия агентов 31

1.2.7 АРХИТЕКТУРА АГЕНТА 34

Общая классификация архитектур 34

Архитектуры агентов, основанные на знаниях 35

Архитектура на основе планирования (реактивная архитектура) 36

Многоуровневость 36

1.2.8 ЯЗЫКИ ПРОГРАММИРОВАНИЯ АГЕНТОВ 39

Требования к языкам программирования агентов 39

Сравнительная характеристика языков 40

2 ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ ИНФОРМАЦИОННОЙ СИСТЕМЫ 58

2.1 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 58

2.2 РЕАЛИЗАЦИЯ 63

2.3 ФИЗИЧЕСКАЯ СТРУКТУРА БД 65

3 ЗАКЛЮЧЕНИЕ 69

4 СПИСОК ЛИТЕРАТУРЫ 70

Приложение A. Работа с приложением. 71


ВВЕДЕНИЕ

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

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

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

  1.  изучить существующую информационную систему организации;
  2.  выбрать программное обеспечение для разработки;
  3.  разработать структуру программы;
  4.  оценить экономическую эффективность создаваемого программного продукта;

Гипотеза работы. Использование разработанного программного продукта позволит увеличить производительность труда сотрудников транспортной компании, повысить точность выполнения заявок и контроль над всеми этапами трудовой деятельности.

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

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


  1.  ОПИСАНИЕ И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

  1.   АНАЛИЗ ДЕЯТЕЛЬНОСТИ ТАКСОПАРКА

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

Заказы поступают по телефону к диспетчеру, он записывает необходимые данные в базу заказов. Дату и время поступления заказа диспетчер вводит сам или они вводятся автоматически. Клиент может сразу у диспетчера узнать стоимость заказа, и принять решение о заказе машины.

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

После выполнения заказа водитель по рации отчитывается перед диспетчером, тот ставит заказу статус "Выполнен" и у водителя меняется статус на "Свободен".

В случае, когда заказ отменяется, клиент попадает в "Чёрный список", то есть он не имеет право пользоваться услугами данного таксопарка. Диспетчер вносит имя того водителя, который должен был выполнять отмененный заказ в специальный список, который регламентирует по чьей вине заказ сорвался. Например: водитель опоздал на время назначенное клиентом, и вследствие услуги такси стали неактуальными, в таком случае водитель пишет объяснительную записку, но это не спасает его от взысканий. Может быть так, что клиент просто передумал, но не предупредил диспетчера, в таком случае водитель всё равно пишет объяснительную записку, но никаких взысканий к нему не применяется. В этих случаях водитель сам оповещает диспетчера о том, что заказ аннулирован. Еще может быть случай, когда клиент передумал, но предупредил диспетчера, тот связывается с водителем и перенаправляет его на другой заказ. Во всех случаях статус заказа ставится "Отменен".

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

Эти отчеты поступают к администратору, на основании этого всего администратор формирует общий отчет (сводный отчет) за определенную дату.

В конце месяца администратор, пользуясь своими отчетами, формирует отчет по итогам месяца и отправляет его высшему руководству таксопарка.

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

Проблемы, которые могут возникнуть при осуществлении данной деятельности такие:

  1.  Потеря данных диспетчером, или неправильная их трактовка.
  2.  Выбор не оптимального маршрута следования таксистов
  3.  Не корректная форма представления отчетов и т.д.


  1.  ОПИСАНИЕ ДЕЯТЕЛЬНОСТИ СОТРУДНИКОВ

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

  1.  Начальник смены осуществляет контроль и корректную работу транспортной компании в течение смены, которая длится двенадцать часов,  отслеживает правильность выполнения заявок, принимает претензии от населения, решает организационные вопросы. По окончании смены предоставляет необходимую отчетность руководителю предприятия.
  2.  Диспетчеры принимают заявки от населения при помощи телефонной связи, осуществляют координацию движения водителей при помощи радиосвязи  и обеспечивают контроль выполнения заявок. Всю получаемую информацию заносят в журнал регистрации заявок.
  3.  Водители осуществляют перевозки населения и грузов, доставку товаров руководствуясь сообщениями диспетчеров по радиосвязи. Обеспечивают комфортабельность поездки и сохранность грузов.
  4.  Бухгалтер ведет контроль денежных средств предприятия, выполняет налоговую отчетность и производит отчисления во внебюджетные фонды.
  5.  Руководитель ведет управленческую деятельность предприятия, выполняет функции отдела кадров.


  1.  ОБЗОР СУЩЕСТВУЮЩЕГО ПРОГРАМНОГО ОБЕСПЕЧЕНИЯ

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

Для автоматизации транспортных компаний фирмами ООО «Единая служба такси», ООО «ИнтелТелеком», ООО «Танго Телеком» были разработанны соответственно программы: «Такса», «Infinty taxi»,«2Т-Такси». Указанные программные комплексы схожие, поэтому для примера разобрана была только одна из них, а именно «2Т-Такси». Архитектура изображена на рисунке 1:

Рисунок 1 – Архитектура диспетчерской такси

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

Небезынтересно знать, что организация автоматизированной диспетчерской такси на базе программы такси:

  1.  Сведет к нулю ошибки при внесении данных о номерах телефонов клиентов.
  2.  Уменьшит время приема заявки на 40%.
  3.  Уменьшит время на ручной отзвон клиентам и водителям на 95%.
  4.  Уменьшит время на передачу заказов водителя на 98%.
  5.  Автоматическое распределение заказов по стоянкам уменьшает время подачи такси клиенту на 15%.
  6.  Использование GPRS-сервиса позволяет сократить штат такси диспетчерской в 3 раза.
  7.  Для организации работы диспетчера такси достаточно иметь стандартный компьютер и гарнитуру с микрофоном.

Схема работы

В call-центр такси вызов принимается по любому каналу связи:

  1.  С городских телефонных линий.
  2.  С сотовых телефонов.
  3.  С Интернет сайта.
  4.  По SMS.
  5.  По e-mail.
  6.  По ICQ.

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

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

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

Рисунок 2 - Пример интерфейса диспетчера такси

Диспетчер заполняет поля формы заказа и отправляет заказ на сервер «2Т-Такси» нажатием всего одной клавиши. Программа «2Т-Такси» связывается с водителями в автоматическом режиме, то есть без участия диспетчера, и передает информацию о заказе.

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

Водитель нажимает на клавишу готовности выполнить заказ, если заказ ему интересен, и указывает время подъезда к клиенту. На экране своего мобильного телефона водитель видит информацию представленную на рисунке 3

  

Рисунок 3 – Экран телефона водителя

Клиент: Иванов Иван Иванович 

Адрес подачи: ул. Ленина 100, кв. 10

Служба такси: 935241 

Дополнительное писание заказа: 2-й подъезд

Для современных телефонов и смартфонов разработан интеллектуальный интерфейс, включающий в себя GPS Таксометр, изображенный на рисунке 4:

  

Рисунок 4 – Интерфейс для современных телефонов

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

Индивидуальная настройка

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

  1.  Алгоритм обработки звонков.
  2.  Автоматический или ручной дозвон.
  3.  Способ отсылки уведомления водителям
  4.  Тревожную кнопку.
  5.  Автозаказ без участия диспетчера.
  6.  Навигацию, в том числе GPS.
  7.  Электронные карты.
  8.  Правила распределения заказов.
  9.  Запись переговоров.
  10.  Отсылка уведомление водителю и многие другие параметры.

К примеру, алгоритм обработки звонка в такси диспетчерской может быть организован и автоматизирован так, как показано на рисунке 5:

Рисунок 5 - Пример алгоритма обработки звонка диспетчерской такси

Функциональные возможности программы «2Т-ТАКСИ»

  1.  Гибкая настройка внешнего вида рабочего места диспетчера, карточки заказа и т.д.
  2.  Настраиваемые правила распределения заказов
  3.  Настраиваемые условия распределения машины в очереди и при отказе от заказа.
  4.  Настраиваемые правила и последовательность действий по клиентам (VIP роутинг).
  5.  Распределение заказов с учетом времени.
  6.  Тревожная кнопка.
  7.  Настраиваемый график работы водителей такси и диспетчеров.
  8.  Передача сообщений от водителей такси в виде шаблонной фразы (не могу найти клиента, стою с торца дома, 1 подъезд и т.д.)
  9.  Функция тарификации и расчета:
  10.  Работа с дисконтными картами.
  11.  Работа с системой скидок.
  12.  Начисления суммы с каждой поездки на личный счет клиента.
  13.  Прием платежей через банкомат и системы оплаты.
  14.  Задание тарифа для каждого клиента (организации) отдельно.
  15.  Учет таксистов и информирование таксистов по балансу его счета.
  16.  Настроенные отчетные формы и статистика.
  17.  Навигационная система с использованием GPS/ ГЛОНАСС:
  18.  Спутниковый таксометр GPS производит подсчет пробега и расчет стоимости поездки.
  19.  Отображает электронные карты, в том числе карты Google, Yandex.
  20.  Отражает расстановку машин в районе.
  21.  Отслеживает перемещения машин к месту вызова и вести учет таксистов.
  22.  Записывает подробный трек с остановками.
  23.  Проигрывает треки движения (анимация).
  24.  Осуществляет расчет оптимальных маршрутов передвижения автомашин с учетом загруженности дорог и пробок.
  25.  Управление пользователями (группы пользователей, с возможность индивидуальных настроек):
  26.  Диспетчер (Оператор).
  27.  Водитель такси.
  28.  Администратор.
  29.  Руководитель.
  30.  Кассир.
  31.  Настройка правил работы программы заказа такси (к примеру, на сотовый отправить СМС, а на городской позвонить).
  32.  Функции Администрирования:
  33.  Управление сервером.
  34.  Управление Базой Данных.
  35.  Резервное копирование.
  36.  Обновление версий.
  37.  Интеграция со сторонними приложениями:
  38.  Интерфейс для взаимодействия с Контакт-центром (Call-центром).
  39.  Интерфейс для взаимодействия с 1C.
  40.  Интерфейс для взаимодействия с внешней системой тарификации и расчетов.
  41.  Интерфейс для взаимодействия с внешней системой для приема/передачи заказов
  42.  Обмен заказами с другими службами такси.
  43.  Предоставление услуг Контакт-центра такси другим службам (аутсорсинг).

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

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

  1.  МУЛЬТИАГЕНТНЫЕ СИСТЕМЫ

Разработка технологии искусственных агентов, создание многоагентных систем (МАС) и виртуальных организаций представляет собой одну из наиболее важных и многообещающих областей развития новых информационных и коммуникационных технологий (НИКТ), где сегодня происходит интеграция современных сетевых WWW-технологий, методов и средств искусственного интеллекта (ИИ), включая большие базы данных/ знаний, многокомпонентные решатели, и систем объектно-ориентированного проектирования. У специалистов по НИКТ сформировалось и вошло в широкий научный обиход представление об искусственных агентах как активных, автономных, коммуникабельных, а главное, мотивированных, объектах, «живущих» и «действующих»  в сложных, динамических и, чаще всего виртуальных, средах.

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

Решение задачи одним агентом на основе инженерии знаний представляет собой точку зрения классического ИИ, согласно которой агент (например, интеллектуальная система), обладая глобальным видением проблемы, имеет все необходимые способности, знания и ресурсы для ее решения. Напротив, в распределенном искусственном интеллекте (РИИ) и, вообще, в области МАС предполагается, что отдельный агент может иметь лишь частичное представление об общей задаче и способен решить лишь некоторую ее подзадачу. Поэтому для решения сколько-нибудь сложной проблемы, как правило, требуется взаимодействие агентов, которое неотделимо от организации МАС. Этот социальный аспект решения задач – одна из фундаментальных характеристик концептуальной новизны передовых компьютерных технологий и искусственных (виртуальных) организаций, строящихся как МАС.

Причины использования Мультиагентных систем:

  1.  сложность современных систем и организаций, которая достигает такого уровня, что централизованное управление в них становится неэффективным из-за наличия огромных потоков информации, когда слишком много времени тратится на ее передачу в центр и принятие им решений
  2.  решаемые задачи или разрабатываемые системы подчас неоднородны и распределены: а) в пространстве (например, транспортная сеть или система космической связи); б) в функциональном плане, поскольку ни один человек не может создать современную сложную систему в одиночку.
  3.  понятие открытой системы означает, что у нее имеются развитые возможности и средства адаптации к изменениям среды, в том числе путем модификации своей структуры и параметров.
  4.  Распространение различных сетей порождает распределенный взгляд на мир.

 


  1.  ПОНЯТИЕ АГЕНТА

Наиболее популярное определение понятия «агент» у М.Вулдриджа и Н.Дженнингса. Они считают, что агент – это программно или аппаратно реализованная система, обладающая следующими свойствами:

  1.  автономность – способность функционировать без прямого вмешательства людей или компьютерных средств и при этом осуществлять самоконтроль над своими действиями и внутренними состояниями;
  2.  общественное поведение (social ability), т.е. способность взаимодействия с другими агентами (а возможно,  людьми), обмениваясь сообщениями с помощью языков коммуникации;
  3.  реактивность – способность  воспринимать состояние среды  (физического мира, пользователя – через пользовательский  интерфейс,  совокупности других агентов, сети Internet, или сразу все этих компонентов внешней среды);
  4.  целенаправленная активность (pro-activity) – способность агентов не просто реагировать на стимулы, поступающие из среды, но и осуществлять целенаправленное поведение, проявляя инициативу.

Ключевыми характеристиками любых агентов как «искусственных деятелей» являются автономность и целенаправленность. Речь идет об автономном выполнении некоторых действий на основе целенаправленных проблемно-ориентированных рассуждений. Подчас в качестве главных признаков агента берутся интеллектуальность и автономность, где интеллектуальность связывается с восприятием и рассуждениями, а автономность - с принятием решений  и действием на среду.

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


  1.  КЛАССИФИКАЦИЯ АГЕНТОВ

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

  1.  материальных, физически существующих и работающих в реальном пространстве, например, интегральные роботы)
  2.  виртуальных, существующих лишь в программной среде (виртуальном пространстве); нередко такие «программные роботы» (software robots) называют сокращенно софтботами (softbots)

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

Важным основанием для классификации служит наличие (отсутствие) у агентов характеристик обучаемости или адаптивности. У обучаемых агентов поведение основано на предыдущем опыте.

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

В целом, данная типология агентов тесно связана с классической проблемой взаимодействия «субъект – объект». Уровень субъектности агента непосредственно зависит от того, наделен ли он символьными представлениями, требующимися для организации рассуждений, или в противоположность этому он работает только на уровне образов (субсимвольном), связанных с сенсомоторной регуляцией. Соответствующую классификацию агентов можно построить по следующим  двум признакам:

  1.  степень развития внутреннего представления внешнего мира;
  2.   способ  поведения.

 

Рисунок 6 – Классификация агентов

Характеристики

Когнитивные агенты

Реактивные агенты

Внутренняя модель внешнего мира

Развитая

Примитивная

Рассуждения

Сложные и рефлексивные

рассуждения

Простые одношаговые

рассуждения

Мотивация

Развитая система мотивации, включающая  убеждения, желания, намерения

Простейшие побуждения,

связанные с выживанием

Память

Есть

Нет

Адаптивность

Малая

Высокая

Модельная архитектура

Есть

Нет

Состав МАС

Небольшое число

автономных агентов

Большое число зависимых друг от друга агентов

Таблица 1 - Сравнительный анализ свойств когнитивных и реактивных агентов

Еще один тип классификации, где дополнительно к биологическому и психологическому уровням агентообразования вводится социальный, и используются аналогии с триадой «растение – животное – человек», описан П.Браспеннингом. По его мнению, реактивных, интенциональных и социальных агентов можно уподобить компонентам этой триады. Агенты, подобные растениям, характеризуются реактивностью, выполнением стереотипных программ и посылкой сообщений другим агентам и в среду. Агенты, подобные животным, интенциональны,  способны выбирать цели, строить планы действий и обеспечивать их выполнение. Они координируют свои действия, обмениваясь информацией об индивидуальных предпочтениях или задачах. Наконец, гуманоидные агенты, обладая внутренними моделями других агентов (и способностью к рефлексии), характеризуются социальным (ролевым)  поведением. Сложность внутренних моделей зависит от уровня знаний и опыта гуманоидного агента.


  1.  КОЛЛЕКТИВНОЕ ПОВЕДЕНИЕ АГЕНТОВ

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

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

 

  1.  МОДЕЛИ КОЛЛЕКТИВНОГО ПОВЕДЕНИЯ

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

Рассмотрим некоторые из ныне используемых подходов к формализации задач, решаемых на уровне кооперации агентов. Совместное поведение различных объектов изучается в рамках многих научных дисциплин. Выделим среди них те, которые представляются наиболее адекватными идее коллектива интеллектуальных агентов.

  1.  Распределенный искусственный интеллект.  Эта область искусственного интеллекта занимается самыми общими аспектами коллективного поведения агентов. Здесь основу составляют результаты, полученные в теории распределенных систем и теории принятия решений.
  2.  Теория игр. Аппарат теории игр часто используется для исследования коллективов интеллектуальных агентов. Многие ситуации, возникающие в многоагентной системе, находят подходящие аналоги в теории игр. Исследуются кооперативные игры, различные стратегии ведения торгов (переговоров), игры в размещения и др., которые являются аналогами ряда моделей коллективного поведения агентов.
  3.  Теория коллективного поведения автоматов. Она исследует поведение больших коллективов автоматов с примитивными функциями. Поведение автомата может рассматриваться как недетерминированное, что позволяет строить различные вероятностные модели. Допускается обучение автомата при помощи штрафов и поощрений. Автомат может быть наделен памятью, в которой он в некоторой форме запоминает предыдущие штрафы и поощрения, и может использовать эту информацию для улучшения своего и коллективного поведения в соответствии с некоторой функцией дохода.
  4.  Биологические, экономические и социальные модели.

 

Рассмотрим кратко различные модели кооперации агентов.

Модель кооперативного решения проблем (CPS). Эта модель рассматривает взаимодействие агентов, построенных согласно BDI-архитектуре. В модели ментальные понятия формализуются с помощью операторов временной логики. Используя формализм временной логики, в этих работах вводятся определения для таких понятий, как потенциал для кооперации, групповые действия, достижимость цели агентом и т. д.  Остановимся на этих понятиях подробнее.

В процессе формирования кооперативного решения в рамках рассматриваемой CPS-модели выделяют четыре этапа:

  1.  Распознавание. Процесс кооперативного решения начинается тогда, когда агент распознает целесообразность кооперативного действия. Например, у агента имеется цель, достичь которую в изоляции (по его убеждению) он не способен, или для ее достижения он предпочитает кооперацию.
  2.  Формирование группы агентов. На этой стадии агент, установивший возможность совместного действия, ищет партнеров. При успешном завершении этой стадии образуется группа агентов, имеющих совместные обязательства для коллективных действий.
  3.  Формирование совместного плана. Это та стадия, на которой агенты переговариваются с целью выработать совместный план, который по их убеждению приведет к желаемой цели.
  4.  Совместные действия. Здесь агенты действуют согласно выработанному плану, поддерживая взаимодействие согласно принятым на себя обязательствам.

Рассмотрим кратко суть перечисленных этапов.

Распознавание основывается на определении потенциала для кооперации  агентов:

По отношению к цели f агента i имеется потенциал для кооперации тогда и только тогда, когда (1) имеется некоторая группа g, такая, что i верит, что g может совместно достичь f, и, либо (2) i не может достичь f в изоляции, либо (3) i верит, что для каждого действия a, которое он мог бы выполнить для достижения цели f, он имеет иную цель, влекущую невыполнение действия a.

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

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

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

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


  1.  АРХИТЕКТУРА МНОГОАГЕНТНЫХ СИСТЕМ

При выборе архитектуры многоагентной системы необходимо иметь в виду два ее аспекта:

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

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


  1.  АРХИТЕКТУРА ВЗАИМОДЕЙСТВИЯ СИСТЕМЫ АГЕНТОВ

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

Одноуровневая архитектура взаимодействия агентов

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

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

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

Иерархическая архитектура взаимодействия агентов

Рассмотрим простейший вариант иерархической организации взаимодействия агентов, который предполагает использование одного агента “мета-уровня”, осуществляющего координацию распределенного решения задач(и) агентами.

Агент, осуществляющий координацию, может быть привязан к конкретному серверу, и тогда он называется “местом встречи агентов”. Место встречи агентов (AMP - Agent Meeting Place) - это агент, играющий роль брокера между агентами, запрашивающими некоторые ресурсы, которыми обладают другие агенты, и теми агентами, которые эти ресурсы могут предоставить. Архитектура AMP есть архитектура обычного агента (см. далее), дополненная некоторыми вспомогательными компонентами, наличие которых обусловлено ролью этого агента как координатора взаимодействия других агентов. Эти вспомогательные компоненты  должны, с одной стороны, содержать унифицированное описание множества доступных через AMP агентов и их возможностей (ресурсов, функций и пр.) и, с другой, организовать унифицированный доступ к ним. Это обеспечивается такими компонентами AMP.

1.Объекты базовых сервисов, в частности, это могут быть удаленный вызов объектов, упорядочение объектов, дублирование объектов и другие базовые возможности, которые  обычно поддерживаются той или иной платформой открытой распределенной обработки, например, OMG/CORBA.

2. Связные порты, ответственные за прием и отправку агентов в AMP с помощью соответствующих протоколов.

3. Компонента установления подлинности агента по имени (опознание агента, “авторизация”).

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

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

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

7. Глубинный маршрутизатор, который ассистирует поверхностному при более специальных и сложных запросах.

8. Менеджер ресурсов; он регистрирует агентов на AMP и ассоциированные с ними ресурсы, а также управляет ресурсами AMP.

9. Среда исполнения агента, которая регистрируется в AMP и управляет доступом к компонентам агента; она интерпретирует сценарии, обеспечивает доступ к базовым возможностям и др.

10. Система доставки событий; источниками событий могут быть локальные средства, резидентные агенты AMP и др.; система регистрирует события и выполняет поиск агентов для соответствующего типа событий, сообщений.

В остальном архитектура координирующего агента аналогична архитектуре обычного агента.


  1.  АРХИТЕКТУРА АГЕНТА

Общая классификация архитектур

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

-архитектура, которая базируется на принципах и методах искусственного интеллекта, т.е. систем основанных на знаниях (deliberative agent architecture”, “архитектура разумного агента”),

и как альтернатива, так называемая

-архитектура, основанная на поведении (reactive architecture) или “реактивная архитектура” (основанная на реакции системы на события внешнего мира).

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

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

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

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

 Архитектуры агентов, основанные на знаниях

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

Сначала идея агента, основанного на знаниях, строилась на чисто логической основе и представлялась весьма перспективной. Однако позднее было обнаружено, что лежащее в основе такого подхода исчисление предикатов первого порядка неразрешимо. Более того, такие ментальные свойства агента, как убеждения, желания, намерения, обязательства по отношению к другим агентам и т.д, невыразимы в терминах исчисления предикатов первого порядка. Были разработаны некоторые специальные варианты расширений модальных логик и подобных модальным, которые оказались с точки зрения реализуемости более удачными. Такие архитектуры были названы Belief-Desire-Intention (BDI) - архитектурами.

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

 Архитектура на основе планирования (реактивная архитектура) 

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

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

Многоуровневость 

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

  1.  восприятие и исполнение действий,
  2.  реактивное поведение,
  3.  локальное планирование,
  4.  кооперативное поведение,
  5.  моделирование,
  6.  формирование намерений, и
  7.  обучение агента.

Существует два основных класса многоуровневых архитектур в зависимости от того, как организуется взаимодействие уровней:

  1.  горизонтально организованная архитектура и
  2.  вертикально организованная архитектура.

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

Основные проблемы реализации горизонтально организованной архитектуры обусловлены сложностью организации согласованной работы всех уровней.

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

Недостатком вертикально организованной архитектуры считается то ее свойство, что оказывается перегруженным уровень исполнения (действий).


  1.  ЯЗЫКИ ПРОГРАММИРОВАНИЯ АГЕНТОВ

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

Требования к языкам программирования агентов

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

  1.  Доступность на многих платформах.
  2.  Поддержка сетевого взаимодействия.
  3.  Многопоточная обработка (“Multithreading”).
  4.  Поддержка символьных вычислений.
  5.  Безопасность, в частности, наличие системы защиты от несанкционированного доступа и “плохих кодов
  6.   Истинная объектная ориентированность.
  7.  Языковая поддержка свойств агента. Эффективность, достаточная для потребностей прикладных программ.

Классификация

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

  1.  Универсальные языки программирования (Java)
  2.  Языки, "ориентированные на знания":
  3.  языки представления знаний (KIF)
  4.  языки переговоров и обмена знаниями (KQML, AgentSpeak, April)
  5.  языки спецификаций агентов.

3. Специализированные языки программирования агентов (TeleScript)

4 Языки сценариев и scripting languages (Tcl/Tk)

5. Символьные языки и языки логического программирования (Oz)

Сравнительная характеристика языков

Java - вероятно, один из наиболее популярных языков используемых в последнее время для программирования агентов. Java представляет из себя язык программирования, подобный C++ по синтаксису, но более схожий со Smalltalk и Objective C по идеологии. Система программирования на Java включает в себя виртуальную машину Java и транслятор с Java в bytecode.

Язык Java предусматривает создание приложений, переносимых на различные платформы. Программа, написанная на Java, компилируется в специальный машинно-независимый байт-код. Затем этот код может быть исполнен с помощью интерпретатора Java на любом компьютере, где реализована Java Virtual Machine. Тем самым обеспечивается платформо-независимость Java - приложений на уровне байт-кода, который может приходить откуда угодно, включая Web-страницу, в которой содержится ссылка на него. Java Virtual Machine работает в среде вытесняющей мультизадачности и поддерживает облегченные процессы (threads). Средства создания и синхронизации таких процессов включены в Java на уровне языковых конструкций и классов. Средства многозадачности также призваны обеспечить реакцию системы в реальном времени для мультимедийных приложений, критичных ко времени.

Java представляет собой истинно объектно-ориентированный язык программирования с сильной типизацией. Схожесть с C++ делает его простым для изучения программистами. В нем отсутствует предельно ясное распределение памяти и для повышения надежности программ из языка исключена арифметика указателей. Каждый тип данных понимается как класс объектов, любая функция является методом класса. Ее вызов рассматривается с объектно-ориентированных позиций как посылка сообщения объекту. Имеется встроенная расширяемая библиотека классов, включающая Abstract Window Toolkit (AWT) для создания пользовательских интерфейсов, классы поддержки основных типов данных, threads, сетевых возможностей, графики, мультимедиа, и т. д. К средствам повышения надежности следует отнести встроенную в язык обработку исключительных ситуаций (exceptions) и run-time контроль за выполнением программы, такой, как проверка выхода за границы массивов и т.д.

Язык Java может быть использован для создания двух типов программного обеспечения: автономных приложений, которые могут включать «родной» (т.е. машинно-зависимый) код и апплетов - платформо-независимых приложений, которые могут приходить из сети и запускаться с помощью поддерживающих Java Web - браузеров. Апплеты могут встраиваться в Web страницы после специальной метки языка HTML, указывающей ссылку на их код, и запускаться автоматически, когда страница открывается в браузере.

Язык Java был спроектирован с учетом возможности создания приложений работающих в распределенной среде. Кроме поддержки возможностей TCP/IP, таких как чтение URLs, работу с сокетами и обмен сообщениями на уровне датаграмм, в Java предусмотрен механизм удаленного вызова объектов, определенный в спецификации RMI (Remote Method Invocation). Этот механизм позволяет вызывать методы удаленных объектов, объявленные в специальном интерфейсе, причем синтаксически такой вызов выглядит идентично вызову простого метода. Эта схема предоставляет более гибкие возможности по сравнению с традиционным протоколом RPC (Remote Procedure Call). Механизм сериализации (Serialization) позволяет сохранять объекты и графы объектов в потоках данных (файлах, сетевых каналах) и восстанавливать их при необходимости. При этом обеспечивается достаточный уровень секретности передаваемой информации. С выходом спецификации Java IDL и нового продукта Black Widow компании PostModern Computing Technologies открылась возможность к сближению Java приложений и коммуникационного стандарта CORBA 2.0 консорциума OMG (Object Management Group). Специальный компилятор позволяет, исходя из описаний интерфейсов на языке IDL CORBA, генерировать код Java объектов. Это позволит использовать вызовы объектов, находящихся в корпоративных сетях, из Java приложений и сделать Java - объекты доступными для этих вызовов.

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

Приложение, рассчитанное на неподготовленного пользователя (End User Application);

Систему, основанную на знаниях (Knowledge Based System);

Хранилище специальных знаний (Knowledge Base Repository) - хранилище знаний о содержимом базы знаний - используется для отслеживания истории доступа, целостности и других аспектов функционирования баз знаний;

Система управления базами данных (Database System);

Активные сенсоры (Active Sensors) - отвечают за обмен данными (знаниями) с “внешним миром”

Возможны различные способы взаимодействия перечисленных компонент.

Разработчики KQML выделяют 3 направления, особенно важных с их точки зрения для коммуникаций интеллектуальных агентов:

Связность (Connectivity) - фокусируется на способе связывания агентов между собой;

Архитектура (Architecture) - акцентирует внимание на способе построения будущей системы (будет ли система статической, когда все компоненты известны уже на этапе проектирования/реализации или динамической);

Коммуникации (Communication) - данное направление рассматривает синхронность/асинхронность обмена сообщениями между агентами.

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

Архитектура. Агенты - это отдельные процессы, работающие в одном адресном пространстве или на различных машинах, соединенные посредством Internet.

Коммуникации. Язык поддерживает следующие стратегии передачи информации: point to point, multicast, broadcast.

Синтаксис. Сообщения между уровнями содержимого, сообщений и коммуникаций представлены в виде s-выражений языка Lisp. Между процессами выражения передаются как потоки ASCII -символов.

Протокол. Для транспортной поддержки KQML был создан специальный протокол - SKTP (Simple Knowledge Transfer Protocol).

Рассмотрим уровни языка KQML. Язык KQML состоит из трех уровней: содержимого, сообщений и коммуникаций. KQML-выражение можно рассматривать как выражение-содержимое, помещенное в сообщение-обертку, которое, в свою очередь, помещено в коммуникационную обертку. На уровне содержимого находится представление знаний на некотором языке. Уровень сообщений добавляет дополнительные атрибуты, такие как описание языка, на котором выражено содержимое, его онтологию и тип используемого метода переговоров. Коммуникационный уровень добавляет информацию об отправителе и получателе сообщения, а также указывает, является сообщение синхронным или асинхронным.

Основу синтаксиса языка KQML составляют имена примитивных действий- сообщений, которые в английской транскрипции называются “performatives” Тип сообщений определяет, что можно сделать с предложениями, содержащимися в сообщении, с этим связано само название KQML-сообщений на английском языке.

Все действия-сообщения можно разделить на следующие категории:

-языка содержимого KQML, который предполагает модель баз в форме множества предложений некоторого языка, который может быть объектным;

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

-определения, которые имеют целью  активизировать и отменять определения;

-ответы на вопросы, которые позволяют задавать вопросы относительно истинности предложений;

-отклики, которые определяют набор сообщений для получения ответов на заданные вопросы.    

SKTP - Simple Knowledge Transfer Protocol. Первые две реализации SKTP были написаны на языках Common Lisp и Пролог соответственно. В настоящее время разрабатываются интерфейсы на других языках. SKTP - это реализация стека протокола KQML. Как и KQML, SKTP состоит из нескольких уровней: содержимого, сообщений и коммуникации. Коммуникации между приложениями происходят на языке приложений, поддержку данного процесса обеспечивает уровень содержимого (content layer). Выражения, помеченные для передачи, “обертываются” в сообщения - это т.н. уровень сообщений (message layer) , реализуемый с помощью интерфейса библиотеки посредника (Facilitator Interface Library - FIL).  Уровень, отвечающий за  стратегию передачи сообщений (multicast, broadcast и т.д.) называется коммуникационным и реализован в виде отдельного агента, называемого посредником (facilitator). На самом нижнем уровне, реально несущем структурированные данные между посредниками, находится протокол TCP/IP.

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

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

Перечислим основные свойства языка KIF.

1. Язык является декларативным, чем отличается от языков типа Prolog и Emycin.

2. Язык является логически полным.

3. Язык является транслируемым (translatability) - он предполагает значения для трансляции декларативных баз знаний в/из типичных языков представления знаний.

4. Язык является хорошо читаемым, что упрощает его использование разработчиком баз знаний.

5. Язык может быть использован как язык представления знаний.

Существуют две разновидности языка KIF: линейный и структурированный. В линейном варианте все его выражения - это строки ASCII-символов, что удобно для хранения на устройствах с последовательным доступом. В структурированном варианте языка правильные выражения - это структурированные объекты. Структурированный язык удобен для использования при коммуникациях программ, работающих в одном адресном пространстве. Между линейным и структурированным представлениями одной и той же сущности существует взаимно-однозначное соответствие.

Соответствие между линейным и структурированным представлениями определяется следующим образом: строка ASCII-символов будет правильным выражением линейного варианта языка KIF тогда и только тогда, когда она допускается интерпретатором языка Common Lisp, и  структура, порожденная интерпретатором Common Lisp  будет правильным выражением структурированного KIF.

В структурированном KIF определены следующие синтаксические конструкции: word, expression, operator, constant, term, sentence, definition, rule и т.д.

Применимость KIF в рамках разработки агентов видится следующим образом. Ядро агента, а именно: подсистемы управления памятью, планирования, база знаний и т.д. пишутся на С++ или на одном из языков Java, Telescript (если нас интересует способность агента к мигрированию по сетям), а KIF используется как язык для обмена знаниями/данными с другими агентами (для этого агент должен иметь подсистему перетрансляции с языка внутреннего представления знаний на KIF). Язык KIF можно также использовать и как язык представления собственных знаний агента, в этом случае отпадает надобность в упомянутом выше трансляторе.

 April: Agent Process Interaction Language. Это язык высокого уровня, который предлагает простой интерфейс к другим языкам программирования типа C. April ориентирован на реализацию многоагентных систем. Однако, April не является языком программирования агентов в том смысле, что он не предлагает таких высокоуровневых возможностей, как планировщики, механизмы вывода на основе правил и системы представления знаний. April скорее является объектно-ориентированным языком со средствами поддержки параллельного выполнения задач и рассматривающим объекты как процессы. Он является подходящей основой расширений для задач распределенного искусственного интеллекта и для прикладного программирования многоагентных систем.

AgentSpeak. Аналогом класса в данном языке выступает семейство, представителем (экземпляром) семейства является агент. Каждый агент обладает базой данных отношений с публичной и приватной частями, множеством сервисов и множества планов - процедур, о которых известно лишь то, выполнены они или нет. Язык обеспечивает распределенность хранения информации в пространстве функционирования агентов.

Каждый агентский сервис может быть одного из следующих трех типов: achieve, query, told. Каждый агентский план определяется при помощи имени и описания абстрактной ситуации, в которой он может быть применен. Во время работы агента, если план применим в текущей ситуации, выполняются действия, связанные с данным планом.

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

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

Каждый агент может находиться в одном из трех состояний: активный, ожидающий, неработающий (idle).

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

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

Agent0 и Placa трактуют агентно-ориентированное программирование как вид объектно ориентированного программирования, создатели же AgentSpeak считают, что первое является расширением (продолжением) второго.

TeleScript. Первая коммерческая реализация концепции мобильного агента была сделана в среде TeleScript-технологии фирмы General Magic. Данная технология основана на метафоре электронного рынка - общедоступной сети (public network), которая позволяет продавцам и потребителям товаров и услуг находить друг друга и заниматься совместным бизнесом.

TeleScript-технология оперирует следующими понятиями: места (places), агенты (agents), перемещения (travels), встречи (meetings), соединения (connections), полномочия (authority) и разрешения (permits). Далее кратко разъясняются перечисленные понятия:

  1.  Места. TeleScript-технология рассматривает компьютерную сеть как множество мест. Место - стационарный процесс на сервере, предлагающий услуги входящему агенту.
  2.  Агенты. Коммуникационное приложение трактуется как набор агентов. Каждый агент занимает конкретное место. Однако, агент может перемещаться от места к месту, и поэтому он может занимать несколько различных мест в одно и то же время. Агентские процедуры выполняются параллельно. В модели электронного рынка на типичном месте постоянно присутствует один, выделенный агент.
  3.  Перемещение. Агенту предоставляется возможность путешествовать с места на место. Перемещение - отличительный признак системы удаленного программирования, оно позволяет агенту получить удаленную услугу и затем вернуться на место его старта. TeleScript позволяет коммуникационному пакету (computer package) - агенту (его процедурам и состоянию) перемещаться между компьютерами. Для перемещения между компьютерами агент выполняет инструкцию go. Инструкция включает ticket - данные о желаемом месте доставки, и других параметрах перемещения. В случае, если перемещение прошло успешно, агент получает уведомление об этом (его следующая инструкция выполняется уже на новом месте). В модели электронного рынка инструкция go позволяет агентам покупателей и продавцов располагать друг друга для более эффективного взаимодействия.
  4.  Встречи. Встреча позволяет агентам вызывать процедуры друг друга. Встречи - это то, что “заставляет” агента перемещаться. Для встречи с расположенным рядом (co-located) агентом, агент выполняет инструкцию meet. Данная инструкция содержит требование (petition) - данные, определяющие агента, который “хочет” встретится и другие параметры встречи. Meet-инструкция позволяет покупателям и продавцам осуществлять транзакции.
  5.  Соединения (пока не реализованы на 1995 год). Они позволяют агентам обмениваться информацией с разных мест. Для соединения агент выполняет connect-инструкцию. Данная инструкция содержит несколько параметров, таких как цель (target) соединения. Connect-инструкция позволяет агентам обмениваться информацией на расстоянии.
  6.  Полномочия. Технология позволяет агенту или месту распознавать полномочия другого агента/места, причем агент или место не могут ни скрывать, ни фальсифицировать свои полномочия. Анонимность исключена. Технологией предусмотрена проверка полномочий при перемещении агента между регионами (network regions) сети - набором мест, расположенных на компьютерах, обладающих одинаковыми полномочиями. Для проверки полномочий агент или место выполняет инструкцию name. Результатом выполнения инструкции является telename - данные, позволяющие распознавать полномочия в рамках региона сети. Данная возможность позволяет защитить агентов и места от проникновения вирусов.
  7.  Разрешения. Технология позволяет управлять назначением полномочий.

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

Telescript обладает следующими характеристиками:

  1.  Полнотой.
  2.  Объектно-ориентированностью.
  3.  Динамичностью (dynamic). Агент может переносить информацию с места на место. Даже если при пересылке объект не известен на месте назначения, его класс следует вместе с ним по сети (код, определение класса).
  4.  Сохранением (persistency). На каждом шаге выполнения агент и переносимая им информация безопасно сохраняется в не-volatile - памяти (постоянной - видимо, служебной памяти интерпретатора). Эта операция позволяет предотвратить крах компьютерной системы.
  5.  Переносимостью и безопасностью. Компьютер выполняет инструкции, составляющие агента не напрямую, а посредством engine-интерпретатора. Агент может выполняться на любом компьютере, на котором инсталлирован интерпретатор.
  6.  Ориентированностью на коммуникации (communication-centric). В язык встроены инструкции, позволяющие агенту просто выполнять сложные сетевые задачи.

Agent-Tcl. Agent-Tcl - это система мобильных агентов, в которой агенты написаны на Tcl 7.4 и Tk 4.0. Agent-Tcl активно используется в задачах информационного поиска и прикладных программах информационного управления. Agent-Tcl в целом аналогичен языку TeleScript, за исключением того, что Agent-Tcl более облегчен и в настоящее время обеспечивает ограниченную защиту. Альфа - версия доступна на Unix платформах.

Oz - параллельный, объектно-ориентированный язык программирования, который был разработан в DFKI (Германия). Имеются несколько проектов в DFKI, использующих Oz совместно с архитектурой InteRRaP (см. предыдущий раздел). InteRRaP представляет из себя многоуровневую архитектуру, которая построена для модели взаимодействующих автономных агентов. DFKI предлагает параллельный язык программирования, приспособленный для прикладных программ, которые требуют сложных символьных вычислений, организации кооперации агентов и некоторых возможностей управления в реальном масштабе времени. Реализация Oz является законченной средой программирования, включающей объектно-ориентированный интерфейс к Tcl/Tk. Прикладные программы на Oz уже использовались для моделирования многоагентных систем, обработки естественного языка, виртуальной реальности, графических пользовательских интерфейсов, планирования и создания расписаний.

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

Facile - язык программирования высокого уровня для систем, которые требуют комбинации сложного манипулирования данными с параллельными распределенными вычислениями.

Таблица 2 - Сравнение языков.

Язык

Переносимость кода

Доступность

Сетевые возможности

Параллельность

Java

байт-код, виртуальная машина Java

Windows,

Solaris SPARC /Intel, HP-UX, OS/2, Macintosh, Linux

APIs (библиотеки классов), Remote Method Invocation, сетевая сериализация

Threads синхронизованные с помощью мониторов

TeleScript

интерпретация скриптов

Solaris SPARC, HP-UX, OS IRIX

TCP/IP, UDP, сетевая сериализация

множественные процессы работающие в вытесняющей многозадачности

Tcl/Tk

интерпретация скриптов

Macintosh, Windows 3.1, Windows 95/NT, Solaris

Oz

Solaris SPARC, Sun OS, SGI IRIX, HP-UX, DEC Ultrix, IBM RS6000, Linux


Продолжение таблицы 2

Obliq

гетерогенные распределенные сетевые вычисления

множественные threads внутри одного адресного пространства, множественные адресные пространства в пределах машины, распределенные вычисления в гетерогенных сетях

April

UDP

AKL

Scheme 48

Penguin

Python

интерпретиру-емый язык

Windows, DOS, Macintosh, UNIX

интерфейс к TCP/IP

Facile

AgentSpeak

интерпретиру-емый

пока не реализован

аналог потоков - намерения

Таблица 2 - Сравнение языков.

AKL (Agent Kernel Language) - параллельный язык программирования, разработанный в Шведском Институте Информатики (SICS). В AKL вычисления выполняются агентами, взаимодействующими через хранилища ограничений и условий (stores of constraints). Этот подход объединяет сразу несколько парадигм программирования. В соответствующих контекстах об AKL - агентах можно думать как о процессах, объектах, функциях, отношениях, или ограничениях. AGENTS - система для программирования в AKL. PENNY - это параллельная реализация AKL, для которой были получены очень перспективные результаты, и которая будет развиваться далее.

Scheme 48. Scheme - один из диалектов языка LISP. Широкое разнообразие парадигм программирования, включая императивный и функциональный стили, а также передачу сообщений, находят удобное выражение в данном языке. Реализация Scheme, основана на архитектуре виртуальной машины.

Продолжение таблицы 2

Язык

Символьные вычисления

Обеспечение безопасности

Объектная ориентация

Встроенные агентские свойства

Java

не поддерживаются

есть

есть, без множественного наследования

нет


TeleScript

не поддерживаются

встроенные в язык и библиотеку классов средства

да

агенты, места, маршруты, встречи, соединения, авторизация, полномочия, инструкции: go, meet, connect, permit, name

Tcl/Tk

не поддерживаются

Oz

поддерживаются


Продолжение таблицы 2

Obliq

не поддерживаются

распределенные объектно-ориентированные вычисления легко встраиваемые в приложения на  Modula-3

нет

April

намерения

AKL

Scheme 48


Penguin

кодирование (и цифровая подпись) Perl кода передаваемого удаленной машине

Python

да

Facile

AgentSpeak

агентно-ориентированный язык

BDI (beliefs-desires-intentions) архитектура

 Python - переносимый, интерпретируемый, объектно-ориентированный язык программирования, разработанный пять лет назад в CWI (Амстердаме). Язык имеет изящный (но не переупрощенный) синтаксис; в него встроено небольшое число мощных типов данных. Python может быть расширен, путем добавления новых модулей, выполненных на компилируемом языке типа C или C++. Такие модули расширения могут определять новые функции и переменные, а также новые объектные типы.

Phantom - это интерпретируемый язык, разработанный для крупномасштабных интерактивных распределенных программ типа систем конференцсвязи, игр со многими игроками, и совместных инструментальных средств работы. Ядро языка основано на безопасном, расширенном подмножестве языка программирования Modula-3 и поддерживает ряд возможностей современного программирования, включая статическую типизацию, неявные объявления, объекты, облегченные процессы, и высокоуровневые функции.

Penguin - модуль языка Perl 5, который обеспечивает, набор функций для: (1) посылки шифрованного Perl-кода с цифровой подписью к удаленной машине, на которой он будет затем выполнен; (2) получения кода и, в зависимости от того, кем он подписан, его выполнения с соблюдением соответствующих прав. Комбинация этих функций дает возможность для непосредственного кодирования на языке Perl алгоритмов обработки безопасных финансовых сделок по Internet, мобильных агентов, собирающих информацию, “оживленных” Web-брoузеров, распределенных вычислений, удаленного обновления программного обеспечения, удаленного администрирования, распространения информации, конструкторов сетевых программ, и так далее.

Сводные характеристики языков и их сравнительные характеристики  приведены соответственно в таблицах 1 и 2.


  1.  ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ ИНФОРМАЦИОННОЙ СИСТЕМЫ

  1.   МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

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

Опр. Агент-водитель – это агент, отвечающий за представление в системе водителя

Опр. Управляющий агент – это агент, оценивающий эффективность решения.

Весь город разбивается на N районов, в каждом находится по нескольку водителей и клиентов. На рисунке 7  изображен пример такого разбиения. 

 

Рисунок 7

Водители и клиенты имеют свои параметры.

Параметры агента водителя:

  1.  Район в котором находится (обозначается числом от 1 до N);
  2.  Баллы (У каждого водителя в начале рабочего дня A баллов, после каждых 70 рублей(минимальная цена за поездку) их количество уменьшается на 1);
  3.  Предпочитаемые районы для работы;
  4.  Статус(имеет 4 варианта: устал, готов к работе, делает заказ, перерыв);

Параметры клиента:

  1.  Район в котором находится;
  2.  Район в который хочет уехать;
  3.  Приоритет;

Сервер отправляет управляющему агенту список клиентов с их параметрами каждые 30 секунд, если появился новый клиент, или по мере появления клиента. Управляющий агент отправляет всем агентам водителям этот список.

У управляющего агента хранится массив NxN, в котором Nij = коэффициент, отображающий время, за которое из i-го района можно попасть в j-й.  Коэффициенты Nij динамически меняются, т. к. после каждой поездки агент водитель отправляет время, за которое он справился с задачей.  Этот массив отсылается всем водителям по мере изменения коэффициентов Nij.

Так же на управляющем агенте выполняется Алгоритм совместных действий.

Алгоритм выбора клиента водителем.

  1.  Присваиваем переменной T значение 99999
  2.  Берется  число Nij, где i – район водителя, j – район 1го клиента в списке.
  3.  Берется число Nik , где i – район водителя, k – район 2го клиента в списке.
  4.  Выбираем наименьшее из Nij, Nik и Т.
  5.  Сохраняем в переменную T число полученное в шаге четыре и номер клиента у которого было получено это число. Если Nik и Nij равны  и меньше Т сохраняем номера обоих клиентов в отдельный массив.
  6.  Повторяем шаги 2-5 для всех пар клиентов.
  7.  Если номеров сохранилось несколько, выбираем максимальное число из  P1,P2,…Pk, где 1,..,k  - номера клиентов, Pn – приоритет n-ного клиента.
  8.  Если таких несколько, то клиент выбирается случайно из оставшихся.
  9.  Для выбранного клиента находим разность Q = M – Nij,  где М – количество баллов при выборе клиента.
  10.  Включается Алгоритм Совместных Действий(АСД)
  11.  Если в результате работы АСД агент не был выбран водителем, то алгоритм повторяется сначала уже для нового списка клиентов иначе 12
  12.  Выводится на экран подтверждение выбора водителем клиента.
  13.  Если водитель отказывается от заказа параметр «отказы» увеличивается на 1, когда он достигает числа F, которое вводится руководством, водителю не выдаются заказы в течении K минут.

Алгоритм совместных действий

  1.   Q и номер выбранного клиента отправляется каждым агентом водителем управляющему агенту.
  2.  Для всех водителей, у котрых номер выбранного пассажира совпадает сравнивается число Q.
  3.  Если число Q совпадает у нескольких агентов, то смотрим статус у каждого водителя.
  4.  Если статус устал, то заказ водителю выдается только тогда, когда нет других водителей, желающих получить данного клиента.
  5.  Если число М совпадает, то клиент отдается случайно, с равными шансами для каждого агента-водителя
  6.  Полученные результаты отправляются нужным агентам водителям(Тем кому достался клиент отправляется его точный адрес и запрос на согласие, тем кому он не достался отправляется обновленный список клиентов,  в котором выбранный клиент удален).

Рассмотрим ситуацию, в которой весь город разбит на 2 района. С соответствующей матрицей А:

Так же есть 3 водителя: Иванов, Петров и Сидоров. Иванов находится в 1м районе, имеет на счету 100 баллов и статус «свободен».  Петров находится в 3м районе, имеет на счету 100 баллов и статус «свободен». Сидоров находится в 1м районе, имеет на счету 70 баллов и статус «свободен».

Появляется 3 клиента в первом втором и третьем соответственно. Тогда для первого клиента система выбирает первого водителя, для второго клиента 3го водителя, для третьего клиента второго водителя.

Если Иванов поставит статус «устал» заказы распределятся следующим образом:

Первый клиент – третий водитель;

Третий клиент – второй водитель.

Если у нас есть 2 водителя Иванов и Сидоров. Иванов находится в 1м районе, имеет на счету 100 баллов и статус «устал». Петров находится в 3м районе, имеет на счету 100 баллов и статус «свободен».

Появляется 2 клиента в первом и втором районах. Система распределит их следующим образом:

Первый клиент – первый водитель;

Второй клиент – второй водитель.

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

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


  1.  РЕАЛИЗАЦИЯ

В качестве архитектуры системы была выбрана трехзвенная архитектура ClientServer, представленная на рисунке 8.

На первом уровне данной архитектуры расположены клиентские приложения, не имеющие прямого доступа к базе данных. В основном, на уровне клиента выполняется простейшая бизнес-логика. Большая часть бизнес-логики системы вынесена на второй уровень – сервер приложений, имеющий прямой доступ к базе данных. Взаимодействие между клиентом и сервером организовано при помощи API RMI (Remote Method Invocation) – программного интерфейса вызова удаленных методов в языке Java. Другими словами, на стороне клиента есть интерфейс, реализация которого расположена на сервере. Когда клиенту необходимо использовать какой-либо метод из этого интерфейса, сервер передает так называемую удаленную заглушку (stub), отвечающую за доведение вызова до метода.

Рисунок 8 –  Архитектура системы

На третьем уровне расположен сервер базы данных, отвечающий за хранение данных. В качестве сервера базы данных была выбрана  СУБД Apache Derby – кроссплатформенная реляционная СУБД с открытым исходным кодом, написанная на Java. Взаимодействие базы данных с сервером приложений организовано при помощи прослойки JPA в связке с Hibernate, предоставляющей средства для реляционной привязки объектов (объектно-реляционного отображения).

К основным достоинствам выбранной архитектуры можно отнести:

– гибкую конфигурируемость;

– масштабируемость системы;

– высокую безопасность и надежность системы;


  1.  ФИЗИЧЕСКАЯ СТРУКТУРА БД

Для работы с БД понадобятся следующие сущности: Водители,  водители смены, автомобили, диспетчеры, клиенты и заказы.

На рисунке 9 представлены отношения между сущностями.

Автомобили

Водители

Диспетчеры

Клиенты

Водители смены

Заказы

Рисунок 9.

На основе отношений между сущностями составим  таблицы-сущности: «Водители» (таблица 2.1), «Автомобили» (таблица 2.2), «Водители смены» (таблица 2.3),  «Клиенты» (таблица 2.4), «Диспетчеры» (таблица 2.5), «Заказы» (таблица 2.6).


Имя

Тип

Назначение

Код водителя

Целый

Идентификатор водителя

Фамилия

Строковый

Фамилия водителя

Имя

Строковый

Имя водителя

Отчество

строковый

Отчество водителя

Дата рождения

Дата

Дата рождения водителя

Номер паспорта

Целый

Номер паспорта водителя

Серия паспорта

Целый

Серия паспорта водителя

Дата выдачи

Дата

Дата выдачи паспорта водителя

Кем выдан

Строковый

Место выдачи паспорта водителя

Адрес

строковый

Адрес прописки водителя

Таблица 2.1 Сущность «Водители»

Имя

Тип

Назначение

Код автомобиля

Целый

Идентификатор автомобиля

Код водителя

Целый

Идентификатор водителя

Номер

Строковый

Номер автомобиля

Цвет

Строковый

Цвет автомобиля

Марка

Строковый

Марка автомобиля

Таблица 2.2 Сущность «Автомобили»

Имя

Тип

Назначение

Номер смены

Целый

Идентификатор смены

Код водителя

Целый

Идентификатор водителя

Фамилия

Строковый

Фамилия водителя

Имя

строковый

Имя водителя

Таблица 2.3 Сущность «Водители смены»


Имя

Тип

Назначение

Код клиента

Целый

Идентификатор клиента

Фамилия

Строковый

Фамилия клиента

Имя

Строковый

Имя клиента

Адрес отправления

Строковый

Адрес отправления

Адрес прибытия

Строковый

Адрес прибытия

Район отправления

Целый

Район отправления

Район прибытия

Целый

Район прибытия

Телефон

Строковый

Телефон клиента

Таблица 2.4 Сущность «Клиенты»

Имя

Тип

Назначение

Код диспетчера

Целый

Идентификатор диспетчера

Фамилия

Строковый

Фамилия диспетчера

Имя

Строковый

Имя диспетчера

Отчество

Строковый

Отчество диспетчера

Дата рождения

Дата

Дата рождения диспетчера

Серия паспорта

Целый

Серия паспорта диспетчера

Кем выдан

Строковый

Место выдачи паспорта диспетчера

Дата выдачи

Дата

Дата выдачи паспорта диспетчера

Таблица 2.5 Сущность «Диспетчеры»


Имя

Тип

Назначение

Номер заказа

Целый

Идентификатор заказа

Код водителя

Целый

Идентификатор водителя

Код диспетчера

Целый

Идентификатор диспетчера

Код клиента

Целый

Идентификатор клиента

Время поступления

Дата

Время поступления заказа

Статус

Строковый

Статус заказа

Таблица 2.6 Сущность «Заказы»


  1.  ЗАКЛЮЧЕНИЕ

Изучены бизнес процессы работы таксомоторных компаний.

Проведен анализ существующего программного обеспечения.

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

Спроектирована и создана база данных для хранения информации о таксомоторной компании. Создан пользовательский интерфейс для базы данных

Создано приложение, автоматически выбирающее водителя на каждый заказ.


  1.  СПИСОК ЛИТЕРАТУРЫ

  1.  Городецкий В.И. Многоагентные системы (обзор) / В.И. Городецкий, М.С. Грушинский, А.В. Хабалов // Новости искусственного интеллекта. – М.: ЦНИЭИуголь, 1998. – №2. –  196 с.
  2.  Тарасов В.Б.  От искусственного интеллекта к искусственной жизни: новые направления в науках об искусственном// Новости искусственного интеллекта. – 1995. – №4.
  3.  Рассел С., Норвиг П. Искусственный интеллект. Современный подход. Вильямс. 2006 (2007) Издание 2, 1410 стр.
  4.  Wooldridge M.J. An Introduction to Multiagent Systems. Wiley. 1996 (2002)
  5.  Glaschenko, A., Ivaschenko, A., Rzevski, G., Skobelev, P. “Multi-Agent Real Time Scheduling System for Taxi Companies”. Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2009), Decker, Sichman, Sierra, and Castelfranchi (eds.), May, 10–15, 2009, Budapest, Hungary.
  6. Мартин Дж. Организация баз данных в вычислительных системах. – М.: Мир, 1980.
  7.  http://habrahabr.ru/post/29694/ 


Приложение A. Работа с приложением.

При запуске приложения пользователь видит окно для ввода имени пользователя  и пароля, представленное на рисунке 10.

    

Рисунок 10 – окно авторизации

Пройдя авторизацию, пользователь в зависимости от роли увидит свой интерфейс. Всего имеется 3 роли:

  1.  Администратор
  2.  Оператор
  3.  Отладчик

Администратор наделен правами на добавление и удаление пользователей.

Оператор наделен правами на изменение данных в таблицах «Заказы» и «Клиенты».

Отладчик наделен всеми правами.

Пользовательский интерфейс представлен на рисунке 11.

Рисунок 11 – рабочий режим


 

А также другие работы, которые могут Вас заинтересовать

48373. Подготовка конструкторской документации с использованием трехмерных моделей деталей 12.58 KB
  После построения 3Dмодели детали или сборки либо непосредственно в ходе построения конструктор может получить ее чертеж избежав таким образом рутинного создания видов средствами плоского черчения. Плоский чертеж будет создан автоматически и с абсолютной точностью независимо от сложности модели. В Компас3D объемные модели и плоские чертежи ассоциативны между собой. Компас3D располагает мощными средствами редактирования модели которые позволяют задавать параметрические связи и ассоциации как между отдельными элементами деталей так и...
48374. Подготовка конструкторской документации с использованием трехмерных моделей сборок 12.6 KB
  После построения 3Dмодели детали или сборки либо непосредственно в ходе построения конструктор может получить ее чертеж избежав таким образом рутинного создания видов средствами плоского черчения. Плоский чертеж будет создан автоматически и с абсолютной точностью независимо от сложности модели. В Компас3DV объемные модели и плоские чертежи ассоциативны между собой. Компас3D располагает мощными средствами редактирования модели которые позволяют задавать параметрические связи и ассоциации как между отдельными элементами деталей так...
48375. Требования к системам автоматизированной подготовки конструкторской документации 11.32 KB
  Требования к системам автоматизированной подготовки конструкторской документации Требования: наличие средств импорта экспорта графических документов позволяющих поддерживать обмен данными с другими системами: 1 чтение и запись графических файлов плоских dxf. 2 чтение и запись фалов трехмерных моделей iges. 3 чтение и запись текстовых документов scci. 4 запись данных спецификаций dbf.
48376. Модули библиотек как средства автоматизации конструкторского проектирования. Работа с библиотеками 29 KB
  Основная задача информационного обеспечения САПР - удовлетворение информационных потребностей проектировщика и отдельных компонентов САПР. Вопросы повышения достоверности результатов проектирования и скорости их получения напрямую связаны с организацией данных информационного фонда САПР.
48377. Конституционные основы государства 16.14 KB
  Основы конституционного строя закрепляют форму государственной власти в стране. Российская Федерация отмечается в статье 1 Конституции есть демократическое федеративное правовое государство с республиканской формой правления Россия демократическое государство Носителем суверенитета и единственным источником власти в ней является многонациональный народ. Он осуществляет свою власть непосредственно путем референдумов и свободных выборова также через органы государственной власти и местного самоуправления. Эти исходные положения...
48378. Драгоценные камни: свойства и обработка. Учебное пособие 1.86 MB
  В учебном пособии рассматриваются свойства ювелирных и ювелирно-поделочных камней и способы их обработки. Пособие предназначено в помощь студентам специальностей 261001 Технология художественной обработки материалов и 071504 Художественное проектирование ювелирных изделий бакалаврам и магистрам по направлениям подготовки Технология художественной обработки материалов Декоративноприкладное искусство и народные промыслы художественный металл Искусство костюма и текстиля проектирование ювелирных изделий...
48379. Конспект воспитательного мероприятия в форме праздника «Масленица» 3.04 MB
  Ребята а что такое масленица Масленица народный праздничный цикл сохранившийся на Руси с языческих времён. Масленица получила свое название оттого что в этот период времени последнюю неделю перед Великим постом разрешается употребление в пищу сливочного масла молочных продуктов и рыбы.
48380. Основы бухгалтерского учета 252.67 KB
  Цель нашего курса - познакомить Вас с основами системы ведения бухгалтерского учета которая ежедневно используется на предприятии. Вы овладеете основами бухгалтерского учета и научитесь практически применять полученные знания. Материалы курса выходят за рамки только бухгалтерского учета.
48381. Кримінальне право. Курс лекцій 546.71 KB
  Курс лекцій містить зміст лекційного курсу, завдання до самостійного вивчення теоретичного матеріалу курсу, що вивчається в позааудиторний час, список рекомендованої літератури і ресурсів Інтернет, ілюстративний матеріал до лекцій