Средства для создания программных агентов

Средства для создания программных агентов

Средства для создания программных агентов

Содержание

Глава I. Анализ предметной области.......................................................................................... 3

1.1 Анализ существующих программных агентов........................................................... 3

1.2 Описание инструментария для создания программных агентов............................. 6

1.3 Языки программирования и программные платформы для создания................... 11

программных агентов........................................................................................................ 11

1.4 Средства спецификаций типовых моделей.............................................................. 19

1.5 Архитектура мультиагентных приложений............................................................. 22

Выводы по I главе............................................................................................................. 25

Глава II. Особенности разработки программных агентов...................................................... 27

2.1 Среды разработки для построения программных агентов...................................... 27

2.2 Модель программного агента ресурсов..................................................................... 44

Выводы по II главе............................................................................................................ 47

Глава 3. Развитие программных агентов и средств из разработки........................................ 49

3.1 Описание программного модуля............................................................................... 49

3.2 Построение модели программного агента................................................................ 49

3.3 Влияние программных агентов на развитие экономики........................................ 49

Выводы по III главе.......................................................................................................... 49

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

1.1 Анализ существующих программных агентов

         Согласно классическому определению, программный агент — это программа-посредник.  Эти посредники взаимодействуют с пользователями или другими программами и смыслом этого взаимодействия является выполнение каких-либо действий от имени пользователя или другой программы. [1]

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

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

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

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

         В задачи программного агента входят:

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

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

         Существуют различные классификации программных агентов. Рассмотрим наиболее популярную классификацию, в которой выделяют четыре основных типа программных агентов [3]:

1. Агенты-покупатели или торговые боты;
2. Пользовательские и  персональные агенты;
3. Агенты по мониторингу и наблюдению;
4. Агенты по добыче и анализу данных.

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

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

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

Пользовательские или персональные агенты по данной классификации — это интеллектуальные агенты, которые действуют от имени пользователя. Примером таких действий является отправка данных, получение и автоматическая обработка данных. Есть несколько версий таких агентов, в том числе newshub и CNN.

Персональные агенты могут выполнять ряд следующих действий:

1. осуществлять поиск информации по заданной теме и запросу;

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

3. сканировать веб-страницы для поиска и выделения текста, который представляет собой «важную» часть информации;

4. имеют возможность «обсуждать» темы в диапазоне от подсознательного страха до спорта;

5. содействовать онлайн поиску работы путём сканирования известных досок объявлений о работе и отправки резюме с указанием достоинств, которые соответствуют желаемым критериям;

6. профилировать синхронизацию разнородных социальных сетей.

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

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

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

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

1.2  Описание инструментария для создания программных агентов

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

1. языки и программные средства реализации агентов;

2. языки коммуникации агентов;

3. языки описания поведения агентов и законов среды;

4. языки представления и управления знаниями;

5. языки формализации и спецификации агентов и мультиагентных систем (МАС).

         К средствам взаимодействия агентов относятся языки коммуникации агентов (FIPA ACL, KQML). Язык коммуникации агентов обеспечивает обмен знаниями и информацией между агентами. FIPA ACL в отличии от таких средств как RPC, RMI, CORBA, обеспечивающих обмен информацией между приложениями, имеет более сложную семантику и обладает следующими преимуществами:

·   FIPA ACL управляет суждениями, правилами, действиями, а не семантически не связанными объектами;

·   сообщения FIPA ACL описывает ожидаемое состояние, а не процедуру или метод.

Однако ACL не охватывают полный спектр объектов, которыми могли бы обмениваться агенты, например планы, цели, опыт, стратегии. На техническом уровне, при использовании ACL, агенты транспортируют сообщения по сети, используя протоколы низшего уровня, например SMTP, TCP/IP, POP3, или HTTP.

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

1. Процедурный, включает обмен процедурными директивами/командами. Это может быть реализовано используя такие языки программирования как Java или Tcl.

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

Из-за ограничений на процедурные подходы (например, такие сценарии трудно координировать, объединить), декларативные языки были предпочтены для создания языков взаимодействия агентов. Одни из наиболее популярных декларативных языков - KQML со своими диалектами и FIPA ACL.

         В контексте практического построения агентов и МАС главную роль играют инструментальные средства программирования и коммуникации агентов. Языки коммуникации (ACL, KQML) и координации агентов (AgenTalk) обеспечивают согласованное взаимодействие агентов — циркуляцию информации, передачу запросов услуг, реализуют механизмы переговоров, поддерживают сотрудничество между агентами, направленное на достижение общей цели и, как следствие, формирование коллективов агентов. Эти языки можно рассматривать как многоуровневые структуры, включающие уровень представления знаний, уровень переговоров или координации, уровень стратегий коммуникации, и т. п. Так язык KQML (Knowledge Query and Manipulation Language), служащий для поддержки взаимодействия агентов в распределенных приложениях, опирается на специальный протокол переноса знаний SKTP (Simple Knowledge Transfer Protocol). В свою очередь, язык ACL (Agent Communication Language), претендующий на роль стандарта для коммуникации агентов, состоит из трех частей— словаря, “внутреннего языка” KIF (Knowledge Interchange Format) и “внешнего языка” KQML. Сообщение, передаваемое на языке ACL, может трактоваться как KQML-выражение, “аргументами” которого выступают предложения в формате KIF, построенные из элементов словаря ACL [Genesereth and Ketchpel, 1994].

         Программные средства, применяемые для реализации агентов, делятся на три основных класса:

1. языки программирования;

2. библиотеки разработки агентов;

3. среды разработки агентов.

         При программировании агентов чаще всего применяются языки объектно-ориентированного программирования (Си++, Java), реже используются символьные языки и языки логического программирования (LISP, Oz).

         Среди существующих библиотек агентов можно выделить Intelligent Agent Library — коммерческий продукт фирмы Bits й Pixels, систему Кайса, разработанную фирмой Fujitsu и Agentx — сеть высокоэффективных библиотек распределенных вычислений в программной среде Java, предложенную фирмой International Knowledge Systems. Библиотека интеллектуальных агентов Intelligent Agent Library представляет собой набор средств, предназначенных для обеспечения коммуникации агентов и построения их групп. Она основана на языке KQML и содержит иллюстративные примеры агентов, функционирующих в Web-приложениях. Эта библиотека поддерживает разработку мобильных агентов.

         Одной из самых известных и уже зарекомендовавших себя интегрированныхсред для разработки интеллектуальных программных агентов является AgentBuilder фирмы Reticular Systems, Inc. Это средство состоит из двух основных компонентов: инструментария (Toolkit) и исполнительной системы. Инструментарий вкпючает:

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

2. средства анализа области функционирования агента;

3. средства проектирования и разработки сетей из взаимодействующих агентов;

4. средства моделирования поведения отдельных агентов;

5. средства отладки и тестирования программных агентов.

         Исполнительная система содержит машину агента (agent engine), формирующую среду для реализации программных агентов. Агенты, разработанные с помощью среды AgentBuilder, взаимодействуют на языке KQM L, в основе которого лежат примитивные действия — перформативы.
         Назначение инструментального средства (ИС) AgentBuilder состоит в том, чтобы предоставить разработчику программного обеспечения, основанного на агентах, интегрированную среду, которая позволяет быстро и легко создавать интеллектуальных агентов и сложные программы на их основе. Агенты, созданные с помощью AgentBuilder, могут быть реализованы на любой виртуальной Java-машине.

         В таблице 1 приведены примеры средств для разработки агентов.

          Таблица 1

Примеры средств разработки агентов

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

Таблица 2

Сравнение параметров инструментальных средств разработки агентов

            Анализ табл. 3 и 4 показал, что средства для разработки агентов можно условно разделить на две группы: средства, построенные на базе языка Java, и средства, построенные на базе других языков. Средства первой группы предназначены для разработки сетевых приложений на базе мобильных агентов, взаимодействующих через протокол TCP/IP.

1.3 Языки программирования и программные платформы для создания

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

         Для программирования агентов могут применяться: универсальные языки (Java, C++ , Visual Basic и др.), языки представления знаний (SL, KIF), языки переговоров и обмена знаниями (KQML, AgentSpeak, April), языки сценариев (Tcl/Tk, Python, Perl 5 и др), специализированные языки (TeleScript, COOL, Agent0, AgentK и др.), символьные языки и языки логического программирова- ния (Oz, ConGolog, IMPACT, Dylog, Concurrent METATEM, Ehhf и др.), а также другие языки и средства разработки агентов. На рисунке 1.1 представлена классификация языков межагентных коммуникаций.

Рис. 1.1 Классификация языков межагентных коммуникаций

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

         Инструментальные средства второй группы, в основном, предназначены для проектирования сложных динамических агентных структур и реализации сред, хотя имеются отдельные экземпляры для создания мобильных приложений (Telescript, Agent Tcl). При этом агенты разрабатываются согласно BDI-модели. Коммуникации осуществляются через протокол TCP/IP. Однако такие средства имеют слабые возможности по согласованию и сотрудничеству между агентами и работают на ограниченном количестве платформ, поскольку язык программирования – не унифицированный.

         Большинство коммуникативных агентных языков (Agent Communication Language – ACL) основаны на речевом взаимодействии (речевые действия выражаются посредством стандартных ключевых слов).

         Известны два подхода к разработке таких языков – процедурный и декларативный. При первом подходе коммуникации происходят при выполнении инструкций. Язык проектируется с помощью Java или TСl (Tool Command Lanuage). При декларативном подходе коммуникации реализуются на основе опи- саний. Декларативный подход получил большое распространение для создания языков общения агентов, наиболее популярным из которых является KQML-структурированный язык взаимодействия агентов. Этот язык используется в качестве языка взаимодействия в различных многоагентных системах и средах для их программирования, таких как Agent-K, LALO, Java(tm) Agent Template (JATLite). Цели, аналогичные KQML, имеети KAoS (Knowledgeable Agent-oriented System).

         При создании межагентного сообщения необходим язык для представления самого содержания. Обычно для этого используют “логические языки”, представляющие знания как логические выражения (используя синтаксис, подобный LISP), и “информационных языков”, устанавливающих правила для описания типов информационных элементов.          Типичный логический язык содержания – это язык KIF (Knowledge Interchange Format), облегчающий обмен знаниями между системами искусственного интеллекта. Он использовался вместе с KQML в американских научно- исследовательских проектах по представлению знания в мультиагентных системах. Его синтаксис основан на Common LISP. Формат KIF является декларативным языком, который позволяет различным системам обмениваться онтологиями (соглашением между различными системами о структурах представления знаний различных предметных областей), используя тем самым в работе вычислительные преимущества этих систем.

         Второй логический язык содержания – SL (Semantics Language), предложенный FIPA. SL-предложения выражаются логикой ментальных отношений и действий. Ментальная модель агента основана на представлении трех примитивов: убеждение, неопределенность, выбор. Основное свойство SL-логики позволяют смоделированным агентам находится в соответствии с их ментальными отноше- ниями.

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

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

         Существует довольно большой набор платформ, подходящих для создания мультиагентных систем, и этот набор постоянно пополняется. Внеговходят NetLogo, StarLogo, Repast Simphony, Eclipse AMP, JADE, Jason. Сами эти платформы реализованы весьма по-разному: от отдельных сред разработки до встраиваемых плагинов и подключаемых библиотек. Они могут использовать как уже существующие языки различных парадигм, так и языки, специально разработанные для построения программных агентов, например, AgentSpeak в системе разработки Jason.

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

         Платформа разработки Java-агентов JADE (Java Agent Development Framework) используется для создания мультиагентных систем и приложений в соответствии со стандартами FIPA [5] для интеллектуальных агентов. Она включает в себя среду выполнения агентов. Агенты регистрируются и работают под управлением этой среды, в ней предусмотрены механизмы создания, уничтожения, взаимодействия, поиска агентов (рис. 1.2).  

Рис.1.2 Основные компоненты среды JADE  

         Среда включает систему управления агентами (Agent Management System), которая предоставляет средства именования и управления жизненным циклом агента, и службу каталогов (Directory Facilitator), включающую регистрационный каталог (каталог Желтых страниц). Используя этот каталог, агент может связаться с другими агентами, необходимыми ему для достижения цели. Кроме того, JADE содержит библиотеку классов, используемых для разработки агентов и агентной системы, и набор графических утилит для администрирования и наблюдения за жизнедеятельностью агентов, функционирующих в системе. Важной особенностью JADE является поддержка исполнения агентов на устройствах с ограниченными возможностями (CLDC, Connected Limited Device Configuration), например мобильных телефо нах, карманных компьютерах (PocketPC, Palm и др.), за счет использования расширения LEAP (Lightweight Extensible Agent Platform).

         Рассмотрим самостоятельную среду разработки NetLogo. Данная система является типичным примером автономной среды разработки мультиагентных систем. К основным плюсам данной платформы относится  большой объём предоставляемых средств взаимодействия с пользователем – различных кнопок и регуляторов для ввода и корректировки информации, а так же свободная распространяемостью системы.

         Кроме всего этого, данная платформа предоставляет со стандартной сборкой NetLogo очень широкий набор примеров моделей и систем. Эти примеры действительно помогают лучше понять устройство данной агентной платформы и её возможности. Однако за богатством предоставляемых средств скрывается бедность непосредственно технических возможностей системы. Во-первых, набор предоставляемых средств визуализации, хотя и широк, но строго фиксирован и регламентирован, кроме того, невозможно добавление каких-то своих приёмов. А во-вторых, система страдает именно как средство разработки программ, фактически принуждая программиста писать всю программу одним файлом, без какой-либо чёткой структуры. Кроме того, язык программирования весьма специфичен, поскольку он основан на учебном языке Logo, и вдобавок содержит многочисленные методы, предназначенные уже специально для моделирования.

         Язык программирования NetLogo является скриптовым языком и написанные на нём программы исполняются ощутимо медленно. В настоящее время ведутся работы по созданию его транслятора в байт-код, что обещает в перспективе существенное улучшение времени исполнения.

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

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

         Ярким представителем такого класса систем является Repast Simphony – подключаемый модуль к системе разработки (IDE) Eclipse. Во-первых, такая реализация позволяет использовать существующие возможности среды, да и новых языков программирования учить не приходится. А во- вторых, предоставляемые методы разработки агентных систем позволяют сконцентрироваться именно на написании агентов, причём использовать при этом весьма наглядные и интересные средства.

         Главным плюсом, безусловно, является непосредственная работа с агентами и системами их взаимодействия. Так, существуют простые методы создания агента, задания его параметров, описание его поведения даже с использованием блок-схемы. Всё это делает работу с системой довольно удобной и понятной.

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

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

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

1.4 Средства спецификаций типовых моделей

         Рассмотрим типовую модель, которая получила название Reticular Agent Mental Model (RAMM) и является развитием модели Шохама (Shoham), где все действия выполняются только как результат определенных обязательств. В рамках RAMM эта идея расширена до уровня общих правил поведения, которые определяют причину действия агента в каждой точке его функционирования. При этом правила поведения фиксируют множество возможных «откликов» агента на текущее состояние среды так, как это предписывается полаганиями.

         Общая схема процесса проектирования и реализации агентно-ориентированных приложений на основе AgentBuilder ToolKit представлена на рисунке 1.3. Этот инструментарий имеет средства для организации и предметной области создаваемой MAC, средства спецификации архитектуры агенства и поведения агентов, а также средства отладки агентных приложений и наблюдения за поведением созданных агентов.

Рис. 1.3 Технологическая схема процесса разработки

агентно-ориентированных приложений на базе AgentBuilder ToolKit

         Для спецификации поведения агентов в системе AgentBuilder используется специальный объектно-ориентированный язык RADL (Reticular Agent Definition Language). Правила поведения в этом языке могут рассматриваться как конструкции вида WHEN-IF-THEN.

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

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

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

         На рисунке 1.4 представлена модель «жизненного цикла» агента в системе AgentBuilder.

Рис. 1.4 Модель «жизненного цикла» агента в системе AgentBuilder

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

Спецификация поведения агентов и их ментальных моделей составляет специальный файл (agent definition file), который используется совместно с классами и методами из библиотеки действий агентов и библиотеки интерфейсов. Этот файл интерпретируется в рамках компонента Reticular's Run-Time Agent Engine, являющегося частью окружения периода исполнения AgentBuilder.

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

Но в целом можно еще раз отметить, что инструментарий AgentBuilder является современным и мощным средством проектирования и реализации MAC.

1.5 Архитектура мультиагентных приложений

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

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

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

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

Различают три базовых типа архитектуры мультиагентных систем (МАС):

1. архитектура, основанная на принципах и методах работы со знаниями;

2. архитектура, основанная на поведенческих моделях;

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

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

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

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

Выводы по I главе

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

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

         Так же в данной главе рассмотрены языки программирования программных агентов, в результате чего можно сделать вывод, что при программировании агентов чаще всего применяются языки объектно-ориентированного программирования (Си++, Java), реже используются символьные языки и языки логического программирования (LISP, Oz).

         Кроме этого проведен анализ существующих программных платформ для создания программных агентов, рассматривались такие платформы как  NetLogo, StarLogo, Repast Simphony, Eclipse AMP, JADE, Jason.

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

         В данной главе рассмотрены средства спецификаций типовых моделей на примере специального объектно-ориентированного языка RADL (Reticular Agent Definition Language).

Далее в данной главе более подробно рассматриваются мультиагентные системы и архитектура мультиагентных приложений. В результате проделанной работы можно сделать вывод, что мультиагентные системы – это одно из новых перспективных направлений искусственного интеллекта. Ключевым элементом этих систем становится программный агент, способный воспринимать ситуацию, принимать решения и взаимодействовать с другими агентами. Эти возможности радикально отличают МАС от существующих «жестко» организованных систем, обеспечивая им такое принципиально важное новое свойство, как способность к самоорганизации.

Глава II. Особенности разработки программных агентов

2.1 Среды разработки для построения программных агентов

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

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

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

1. АВЕ (Agent Building Environment);

2. Bee-gent;

3. JACK;

4. JADE.

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

1. Инструментальная среда AgentBuilder предоставляет для разработчиков средства разработки и среду выполнения агентного приложения. Технология создания интеллектуального агента в среде AgentBuilder представлен на рисунке 2.1.

Рис. 2.1 Процесс создания интеллектуального агента в инструментарии AgentBuilder

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

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

1. определение состава агентства;

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

3. создание протоколов для спецификации взаимодействия агентов данного агентства;

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

Среда выполнения агентного приложения состоит из агентной программы и процессора выполнения агента. Процессор использует эффективные процедуры логического вывода путём сопоставления правил поведения агента с убеждениями агента, определяемыми текущей ментальной моделью, и входящими сообщениями. На основе проводимых рассуждений процессор выполняет определенные действия, связанные с полномочиями агента. Агентная программа представляет собой определение агента в виде файла на языке RADL вместе с укомплектованной библиотекой классов проекта. Агентная программа совместно с процессором образуют выполняемого агента. При запуске среды выполнения, инициализируется процессор агента, который использует RADL-модель и онтологию агента, представленную в виде библиотеки классов проекта (Project Accessories Library). Для этого необходимы определение агента (файл RADL, который обеспечивает агента способностью рассуждения и начальной ментальной моделью) и библиотека классов проекта (вспомогательные классы проекта PACs из библиотеки классов проекта) – эти объекты используются для отображения предметной области задачи.

2. В среде Bee-gent разработка агентно-ориентированных приложений выполняется по методологии спецификации поведения агентов распределенной системы с использованием МАС - библиотеки, реализованной на языке Java. На основе предлагаемых системой Bee-gent графических средств, возможна чёткая структуризация поведения каждого агента в виде графа состояний и определение протоколов взаимодействий агентов. Графы состояний агентов строятся на основании жизнеспособности ролей, определенных в виде регулярных выражений на этапе агентно-ориентированного анализа (например, по методологии Gaia). Пример фрагмента графа поведения агента Студент обучающей системы показан на рисунке 2.2.

Рис. 2.2 Граф состояний поведения агента Студент

         Граф состояний регистрирует все имена состояний, в которых агент может находиться. На следующем шаге разработки определяются классы для каждого состояния. Каждое состояние в графе является экземпляром класса AwrIPState из агентной библиотеки фирмы Toshiba, реализованной на языке Java. В конструкторе класса определяются пред и пост условия, т.е. условия, которые должны быть выполнены агентом в текущем состоянии для того, чтобы выполнить действия, определенные классом состояния, и определить переход в следующее состояние. Затем специфицируются действия, которые должны быть выполнены в каждом состоянии (включая собственные процессы агента и взаимодействия с другими агентами). Для начального и конечного состояний также создаются классы "INIT" и "END". Если агент взаимодействует с другими агентами, то при спецификации отдельных состояний система Bee-gent предусматривает определение протокола взаимодействия. Протокол должен отражать все линии поведения агента в данном состоянии. В каждом состоянии деятельность агента направлена на выполнение протоколов взаимодействия с целью реализации планируемой линии поведения. Деятельность каждого агента в МАС определяется, например, моделью услуг, разработанной на этапе агентно- ориентированного анализа по методологии Gaia.

         Каждая линия поведения документируется диаграммой взаимодействия агентов с указанием содержимого сообщений и их очередности. На рисунке 2.3 приведен пример диаграммы взаимодействия для состояния “Изучение дисциплины” агента Студент. Формат сообщений определяется языком XML/ACL, который является развитием языка коммуникации KQML.

Рис. 2.3 Диаграмма взаимодействия агента Студент в состоянии “Изучение дисциплины”

         Таким образом, на основе разработанных логических моделей, система Bee-gent автоматически генерирует на языке Java скелет программного кода многоагентной системы, который дополнятся необходимым программным кодом, обеспечивающим заданный “жизненный цикл” агентов. В системе Bee-gent, в отличие от AgentBuilder, при описании поведения агентов не используются правила, определяющие реакцию агента на внешние события и его внутреннее состояние.

3. JACK TM Intelligent Agents (JACK) представляет собой агентно-ориентированную среду разработки, которая построена на основе языка программирования Java. JACK является надстройкой Java в виде расширения синтаксиса Java конструкциями для программной реализации свойств, связанных с понятием интеллектуального агента. Язык программирования агентов JACK предлагает следующие возможности:

1. определяет новые основные классы, интерфейсы и методы;

2. расширяет синтаксис Java для поддержки новых агентно-ориентированных классов, определений и операторов;

3. предоставляет расширения семантики (особенности при выполнении) для поддержки модели выполнения, требуемой агентно-ориентированной программной системой.

Все расширения языка реализованы как plug-in, что делает язык максимально расширяемым и гибким в агентно-ориентированном программировании.

На уровне классов введены 5 главных конструкций:

1. агент, который в JACK моделирует интеллектуальные сущности;

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

3. событие, для моделирования ситуаций и сообщений, на которые агент должен быть способен ответить;

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

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

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

Для установления отношений между упомянутыми выше классами предоставлен набор деклараций. Ниже приведен фрагмент кода для реализации конструкции плана, написанного на JACK (элементы синтаксиса, которые принадлежат JACK, выделены жирным шрифтом):

plan MovementResponse extends Plan {

#handles event RobotMoveEvent moveresponse;

#uses agent implementing RobotInterface robot;

static boolean relevant (RobotMoveEvent ev)

{ … }

context() { … }

#reasoning method

body(){ … }}.

В этом примере определяемый план действий программного агента наследует свои основные выполняемые функции от класса JACKPlan. Кроме того, с помощью нескольких деклараций для планов языка JACK указывается, каким образом план будет использоваться. Каждая декларации предваряется символом «#» для того, чтобы отличить их от элементов синтаксиса Java. Декларация #handles event определяет цель или событие, на которое этот план отвечает. Декларация #uses agent implementing закрепляет агента(ов), которые могут использовать этот план. План в примере могут выполнять только те агенты, которые реализуют указанный интерфейс (RobotInterface). В фигурных скобках содержится обычный код Java.

Помимо деклараций язык JACK для описания рассуждений и поведения, предпринимаемых агентом при выполнении плана, предоставляет свои операторы методов рассуждения, которые выделяются предшествующим символом «@».

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

1. Многопоточность встроена в ядро и выведена из-под контроля программиста.

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

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

4. Возможность выполнение запросов к множеству убеждений агента, используя для этого логические элементы, посредством их объединения для получения желаемого результата. Если запрос имеет успех, то логический элемент содержит желаемое значение.

Компонент среды разработки JACK (JACK Development Environment) дает возможность рисования обзорных диаграмм, по которым среда генерирует скелет программного кода и следит за тем, чтобы изменения, произведенные в коде, отображались и на диаграммах.

Агенты, создаваемые в JACK, имеют архитектуру, присущую интеллектуальным агентам. Таким образом, возможно моделирование разумного поведения, в соответствии с теоретической моделью BDI- архитектуры агента [8], основанной на убеждениях, желаниях и намерениях.

Согласно BDI-архитектуре, интеллектуальные агенты JACK – это автономные программные компоненты, которые могут проявлять разумное поведение на основе проактивности (целенаправленность) и реактивности (направляемое событиями) на входные сигналы. Каждый такой агент имеет:

·   убеждения (это его набор данных о мире);

·   желания (набор событий на которые он будет реагировать и набор целей, достижения которых он может желать);

·   намерения (набор планов, которые описывают как он может управлять возникающими целями и планами).

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

·   устойчивую целенаправленность – агенты сосредоточены на целях, а не на выбранных методах для их достижения;

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

·   утверждение правильности подхода в реальном времени – агент будет гарантировать, что он следует выбранному курсу действий до тех пор, пока определенные условия продолжают быть истинными;

·   одновременность – агентная система является многопоточной. Если возникают новые цели и события, то агент способен определить приоритеты по требованию многозадачности.

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

4. Программная среда JADE (Java Agent Development Framework) получила широкое применение для разработки многоагентных систем. Она полностью реализованная на языке Java и поддерживает FIPA – стандарты для создания интеллектуальных агентов. Цель создания среды JADE – упростить процесс разработки посредством стандартизации способов взаимодействия агентов во всеоохватывающей среде системных сервисов.

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

1. агентную платформу FIPA-compliant Agent Platform, основанную на FIPA и включающую обязательные типы системных агентов для управления, во-первых, агентной платформой (AMS), во- вторых, каналом коммуникации (ACC) и службы каталогов (DF) (эти типы агентов автоматически активируются при запуске платформы);

2. распределенную агентную платформу Distributed Agent Platform, которая может использовать несколько хостов, при чем на каждом узле запускается только одна Java Virtual Machine. Агенты выполняются как Java- потоки. В зависимости от местонахождения агента, посылающего сообщение, и того, кто его получает, для доставки сообщений используется соответствующий транспортный механизм.

3. Multiple Domains support – ряд основанных на FIPA DF-агентов могут объединится в федерацию, таким образом реализуя мультидоменную агентную среду.

4. Multithreaded execution environment with twolevel scheduling. Каждый JADE-агент имеет собственный поток управления, но он также способен работать в многопотоковом режиме. Java Virtual Machinе проводит планирование задач, исполняемых агентами или одним из них.

5. Object-оriented programming environment. Большинство концепций, свойственных FIPA- спецификации, представляются Java-классами, формирующими интерфейс пользователя.

6. Library of interaction protocols. Используются стандартные интерактивные протоколы fipa request и fipa-contract-net. Для того, чтобы создать агента, который мог бы действовать согласно таким протоколам, разработчикам прикладных программ нужно только имплементировать специфические доменные действия, в то время как вся независимая от прикладной программы протокольная логика будет осуществляться системой JADE.

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

JADE базируется на технологиях Java RMI, Java CORBA IDL, Java Serialization и Java Reflection API. Разработка МАС в этой среде упрощается благодаря использованию FIPA-спецификаций и ряда инструментов поддержки фазы отладки и развертывания системы. Эта агентная платформа может устанавливаться на компьютерах с разными операционными системами, и ее можно конфигурировать через удаленный GUI-интерфейс. Процесс конфигурирования этой платформы достаточно гибкий: ее можно изменить даже во время исполнения программ, посредством перемещения агентов с одной машины на другую. Единственным требованием для работы системы является установка на машине Java Run Time 1.2.

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

Рис. 2.4 Среда «существования» агентов JADE

JADE агенты должны иметь уникальные имена, знать имена друг друга и, благодаря этому, они могут общаться напрямую, независимо от их фактического местонахождения, т.е. внутри одного контейнера (например, агенты A2 и A3), в различных контейнерах внутри одной платформы (например, A1 и A2) или в различных платформах (например, A4 и A5). Основной контейнер отличается от обычных тем, что содержит систему управления агентами и маршрутизатор, которые автоматически запускаются при запуске основного контейнера. Система управления агентами AMS (Agent Management System), представляет собой «власть» в платформе (создание / удаление агентов в удаленных контейнерах, запрашиваемых через AMS) и обеспечивает службу именования агентов. Маршрутизатор каталогов DF (Directory facilitator), который обеспечивает сервис «Жёлтых страниц», помогает найти агенту других агентов, для получения от них необходимых услуг, необходимых ему для достижения своих целей.

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

В последних версиях системы используется Java RMI, event-notification и IIOP. Однако, можно легко добавить и другие протоколы. Также предусмотрена возможность интеграции SMTP, HTTP и WAP. Большинство коммуникационных протоколов, которые уже определены международным сообществом разработчиков агентных сред, доступны и могут иллюстрироваться на конкретных примерах после определения поведения системы и ее основных состояний. Вместе с поддержкой определенных пользователем контентных языков, реализованы онтологии управления агентами, а также онтологии, которые могут быть реализованы и зарегистрированы агентами и использованы системой. С целью существенного расширения работоспособности JADE, предусмотрена возможность интеграции с JESS и Java-оболочкой CLIPS.

Сравнительный анализ возможностей рассматриваемых инструментальных сред для разработки программных агентов приводится в таблице 4. А на рисунке 2.5 приведены результаты данного анализа.

Таблица 4

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

Рис. 2.5 Оценка возможностей инструментальных сред в %

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

Необходимо обратить внимание на то, что для платформы JADE существует дополнительное BDI расширение - среда Jadex. Эта среда предусматривает гибридную реактивно-делиберативную архитектуру, в которой агент рассматривается как «черный ящик», принимающий и отправляющий сообщения. Основываясь на результатах обработки сообщений, внутренних и внешних событий, делиберативный механизм принимает решения о переходе к новому плану действий или продолжению старого. Действующий план может посылать сообщения другим агентам, изменять базу убеждений, формировать новые цели и вызывать внутренние события. Система использует библиотеку планов, которые обрабатываются как Java-классы.

Одним из главных преимуществ разработки интеллектуальных агентов на платформе Jadex является то, что не требуется изучения новых языков программирования. Вместо этого агенты кодируются на базе объектно-ориентированного программирования в интегрированной среде разработки (IDEs), типа Eclipse и Intellij IDEA.

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

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

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

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

2.2 Модель программного агента ресурсов

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

Одной из самых интересных и широко распространяемых архитектур агента является архитектура Цели-Факты-Планы (BDI). Эта архитектура состоит из понятий знаний, фактов и целей как мысленные отношения, которые генерируют человеческое действие.

Jadex объединяет эту модель в агентов Jade, вводя цели, факты и планы для манипуляции внутри агента. В Jadex, агенты имеют знания, которые могут быть каким-нибудь видом объектов Java, и запомнены в базу знаний. Цели изображают конкретные побуждения (состояния, которые достигнуты).

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

Цели в Jadex представляют собой объекты с некоторыми атрибутами. Целевое состояние, достигаемой цели, может быть явно представлено выражением, которое проверяет, достигнута ли цель.

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

Jadex поддерживает 4 вида целей:

1. цель выполнения – утверждает, что должно быть выполнено, но не обязательно приведет к определенному результату;

2. цель достижения – описывает абстрактное целевое состояние, которое необходимо достигнуть, без определения как это сделать. Таким образом, агент может опробовать разные альтернативы, для достижения цели;

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

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

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

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

Рассмотрим схему работы программного агента ресурсов (рис. 2.6). Работа агента начинается с того, что агент координатор (1 блок модели) посылает агенту ресурса запрос на поиск информации. Далее запускается агент ресурсов (2 блок модели), после подачи запроса на поиск информации, которую ищет пользователь с помощью других агентов. После этого управление передается в следующей блок модели для поиска необходимой информации по метаданным. Агент координатор управляет взаимодействием между всеми агентами. В  данной схеме возможно два варианта событий, при которых искомая информация либо найдена, либо нет. Если информация не найдена, агенту координатору отправляется сообщение о том, что данный ресурс отсутствует (блок 4). Если же информация найдена (блок 5), тогда агенту координатору перенаправляется материал, который был найден. При выполнении блока 4 или 5 функция агента считается выполненной. После чего агент переходит в спящий режим (блок 6), до того времени пока не появится новая необходимость в работе агента.

Рисунок 2.6 Схематическая модель работы программного агента ресурса

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

Выводы по II главе

Широта исследований в области мультиагентных систем, сложность архитектуры и многообразие компонент агентов, различные методологии представления МАС породили множество программных средств для их разработки.

В данной главе были подробна рассмотрены наиболее известные и популярные среды разработки агентов, а так же проведен сравнительный анализ возможностей таких инструментальных сред для разработки программных агентов, как АВЕ (Agent Building Environment), Bee-gent, JACK и  JADE.

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

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

Глава III. Развитие программных агентов и средств их разработки

3.1 Описание программного модуля

Jadex - это агент, ориентированный на собственный механизм принятия решений, взаимодействуя с XML и Java файлами, поддержки этих решений.

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

Чтобы создать агента необходимо определить в системе свойства агента.

Действия агента описываются с помощью представлений, целями и планами. Помещая их, в так называемую библиотеку XML файла, этот файл называется ADF (agent definition file) файл определения агента. В ADF файле определяются агент как объект, описанный в классах java-файлов.

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

Функционирование в агента в системе происходит за счет получения от системы и отправка измененных сообщений в систему. Система подает на вход агенту какое-то сообщение, после чего агент заносит его так в так называемый модуль событий. Передавая его в блок обработки сообщений, и далее передавая его по цепочке в блок планов, анализирует его. Где событие анализируется к принадлежности агента. Если сообщение не принадлежит агенту, то оно передаётся обратно в систему не изменённым. Блок планов, обрабатывая событие, сравнивает их с собственной базой планов и при положительном сравнении с планами начинает обработка сообщения в базе знаний, откуда поступает для сравнения с целями агента для передачи в модуль событий. Пройдя весь цикл сравнения и преобразования данных, в установленные задачи, поступает в систему для дальнейшего функционирования.

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

Рассмотрим базовый алгоритм построения агента на платформе Jadex. Разрабатывая приложение с использованием Jadex, программист обязан создавать два типа файлов: XML-файлы обозначая агента и Java-файлы для выполнения планов. Файл определения агента используется как спецификация для классов выполнения плана, базирующийся на объявлениях действий этого плана и основных фактах взаимосвязи между ними. Файлы с форматом XML и Java, определяют функциональные возможности агента.

В главном файле агента XML определяются все функциональные возможности, которыми будет наделен агент такие как: imports, capabilities, beliefs, goals, plans, events, expressions, properties, initial states. Когда ADF и java загружены, объекты созданные для xml в ADF, позволяют системе взаимодействовать, используя Jadex платформу для принятия решений по определенным действиям и взаимодействия внутри программного модуля.

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

Самая интересная и широко распространенная архитектура агента - это введенная архитектура Цели-Факты-Планы (BDI). Данная архитектура состоит из понятий знаний, фактов и целей как мысленные отношения, которые генерируют человеческое действие. Приняли эту модель, и преобразовали в формальную теорию и модель выполнения для агентов программного обеспечения, основанных на мнении фактов, целей, и планов. Jadex объединяет эту модель в агентов Jade, вводя цели, факты и планы для манипуляции внутри агента. В Jadex, агенты имеют знания, которые могут быть каким-нибудь видом объектов Java, и запомнены в базу знаний. Цели изображают конкретные побуждения (состояния, которые достигнуты)

3.2 Построение модели программного агента

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

Разрабатываемый модуль агента BazaZnanii: содержит модули по формированию терминов BazaZnaniiDictionary.xml к нему прилагается документ BazaZnaniiDictionary.dtd определяющий тип документа, определяет законные блоки документа XML, структуру документа со списком законных элементов (атрибутов). Также содержит модуль логического ответа пользователю BazaZnaniiAgent.xml.

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

<?xml version="1.0"?> данный тег обозначает версию документа. <!DOCTYPE bazaznanii SYSTEM "GlossaryDictionary.dtd"> данная строка показывает, что мы определяем структуру нашего документа XML в DTD формате. В начале XML файл описывается заглавным тегом, определяющим его назначение <bazaznanii>…</bazaznanii>. Описываем название с помощью атрибута title ="…" и дату создания orderDate="…?...?..." Уже в нем мы определяем наши термины <terms>…</terms>. Свойства термина описываем, используя, теги: <term>…</term> - тег, которым мы объявляем термин. value="term…" – значения термина при поиске в перечне материла. Далее объявляем его имя с помощью тега <name>…</name>. <image ref="...> данный тег описывает рисунки к тому термину, который ему соответствует. <count>…</count> отвечает за количество определений термина. А в свою очередь определения обозначаются как <definition>…</definition>, и уже в нем мы описываем count="…" какое это определение по счету. Также существуют вложенные гиперссылки - <giperlink>…</giperlink>, которые отвечают за то, что бы при просмотре термина, когда человек переходит на вложенную ссылку агент мог отреагировать на этот запрос.

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

Рисунок 3.1Общееописаниеагентабазы знаний

Рисунок 3.2Импортируемые библиотеки

Рисунок 3.3Цели работы агента

Рисунок 3.4Используемые знания агентом, которые описывают исполняемые факты

Рисунок 3.5Исполняемые планы агента

Рисунок 3.7События, выводимые сообщения для передачи иным агентам или конечному пользователю

Рисунок 3.8Описывает начальное состояние агента и завершение его описания

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

         Рассмотримпостроениепрограммного агента с использованием платформы Jadex. Для начала агент описывается в HTML в соответствии с заданными планами, целями и фактами, как это представлено выше.

Рассмотрим характеристики агента. Агент имеет такие характеристики как:

·   наличие запроса и поиска дополнительной информации;

·   открытие найденой искомой информации;

·   просмотр необходимой информации.

          Входная информация:

·   запрос на поиск необходимого материала.

Выходная информация:

• найденная по ссылке информация.

В разрабатываемом агенте выделяется две цели. Это цели вида запроса (query) и главная цель (main goal). Цель запроса изображает необходимость в информации, выполняет поиск условий. Представляет необходимость в информации. Главная цель – это предоставить студенту дополнительную информацию. Эта цель специфицирует состояние, которое должно быть достигнуто.

В знаниях описываются происходящие факты в ходе работы агента. В нашем случае описывается семь знаний, в которых определяются факты. При запуске агента вызывается факт Restart agent. Следующим фактом есть зарос на поиск QuerySearch, показывает присутствие запроса на дополнительную информацию и выполняет поиск терминов от списка материалов. Открытие искомой информации со словаря выполняется с помощью факта ContentOpen. TermNotFound – говорит о том, что будет отправлено сообщение об ошибке агенту координатору. А агенту чата отправляется сообщение с помощью факта NoTerm о том, что необходимо, чтоб преподаватель выложил необходимый материал, которого нет в наличии. Отсылается сообщение студенту о неправильной ссылке. SleepMode – показывает переход агента в спящий режим.

В разрабатываемом агенте выделяются планы restart, reference, search, content_open, coordinator, chat, student, sleep:

·   Restart - выполняет запуск агента при вызове его агентом координаторе;

·   Reference - присутствие ссылок по тексту;

·   Search – поиск необходимого термина;

·   Content_open - отображение содержимого словаря;

·   Coordinator - описание взаимодействия с агентом координатором. Отсылает сообщение об ошибке, термин не найден. Является внешним планом;

·   Chat - внешний план. Описание взаимодействия с агентом чата. Отсылает сообщение о том, что материала нет в наличии;

·   Student – вывод сообщения студенту. Отсылает сообщение о том, что ссылка неправильная и материала нет в наличии;

·   Sleep – агент переходит в спящий режим.

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

3.3 Влияние программных агентов на развитие экономики

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

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

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

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

По словам нобелевского лауреата К. Эрроу, за агент-ориентированным моделированием будущее экономической науки. Публикационная активность в данной области растет экспоненциально.

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

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

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

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

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

Прорывной особенностью модели экономики является комплексность в моделировании большой экономики и внимание к фактору пространства, что особенно актуально в контексте современных вызовов экономике РФ, таких как:

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

Выводы по III главе.

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

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

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

Приложение 1

Содержание базы знаний в XML

BazaZnaniiTerm.xml

<?xml version="1.0"?>

<!DOCTYPE bazaznanii SYSTEM "BazaZnaniiTerm.dtd">

<bazaznanii title ="The XML- Helpbook" orderDate="2016?10?10">

<terms>

<term value="term1">

<name>dictionary</name>

<count>1</count>

<definition count="1">An abstract data type storing items, or values. A value is accessed by an associated key. Basic operations are new, insert, find and delete. </definition>

<giperlink>abstract data type</giperlink>

<giperlink>key</giperlink>

</term>

<term value="term2">

<name>heap</name>

<count>1</count>

<definition count="1">A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap. </definition>

<giperlink>complete tree</giperlink>

<giperlink>key</giperlink>

<giperlink>node</giperlink>

<giperlink>parent</giperlink>

<giperlink>binary heap</giperlink>

</term>

<term value="term3">

<name>linked list</name>

<count>1</count>

<definition count="1">A list implemented by each item having a link to the next item. </definition>

<giperlink>list</giperlink>

<giperlink>link</giperlink>

</term>

<term value="term4">

<name>queue</name>

<count>1</count>

<definition count="1">A collection of items in which only the earliest added item may be accessed. Basic operations are add (to the tail) or enqueue and delete (from the head) or dequeue. Delete returns the item removed. Also known as "first-in, first-out" or FIFO. </definition>

<giperlink>head</giperlink>

<giperlink>tail</giperlink>

</term>

<term value="term5">

<name>stack</name>

<count>1</count>

<definition count="1">A collection of items in which only the most recently added item may be removed. The latest added item is at the top. Basic operations are push and pop. Often top and isEmpty are available, too. Also known as "last-in, first-out" or LIFO. </definition>

</term>

<term value="term6">

<name>tree</name>

<count>2</count>

<image ref="./tree.bmp"/>

<definition count="1">A data structure accessed beginning at the root node. Each node is either a leaf or an internal node. An internal node has one or more child nodes and is called the parent of its child nodes. All children of the same node are siblings. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom. </definition>

<definition count="2">A connected, undirected, acyclic graph. It is rooted and ordered unless otherwise specified. </definition>

<giperlink>node</giperlink>

<giperlink>tree</giperlink>

<giperlink>parent</giperlink>

<giperlink>root</giperlink>

<giperlink>leaf</giperlink>

<giperlink>internal node</giperlink>

<giperlink>child</giperlink>

<giperlink>siblings</giperlink>

<giperlink>connected</giperlink>

<giperlink>undirected</giperlink>

<giperlink>acyclic graph</giperlink>

<giperlink>rooted</giperlink>

<giperlink>ordered</giperlink>

</term>

<term value="term7">

<name>array</name>

<count>1</count>

<definition count="1">A set of items which are randomly accessible by numeric index. </definition>

</term>

<term value="term8">

<name>array index</name>

<count>1</count>

<definition count="1">The location of an item in an array. </definition>

<giperlink>array</giperlink>

</term>

<term value="term9">

<name>child</name>

<count>1</count>

<definition count="1">A node of a tree referred to by a parent node. See the figure at tree. Every node, except the root, is the child of some parent. </definition>

<giperlink>node</giperlink>

<giperlink>tree</giperlink>

<giperlink>parent</giperlink>

<giperlink>root</giperlink>

</term>

<term value="term10">

<name>circular list</name>

<count>1</count>

<definition count="1">A variant of a linked list in which the nominal tail is linked to the head. The entire list may be accessed starting at any item and following links until one comes to the starting item again. </definition>

<giperlink>linked list</giperlink>

<giperlink>link</giperlink>

<giperlink>tail</giperlink>

</term>

<term value="term11">

<name>complete tree</name>

<count>1</count>

<definition count="1">A tree in which all leaf nodes are at some depth n or n-1, and all leaves at depth n are toward the left. </definition>

<giperlink>tree</giperlink>

<giperlink>depth </giperlink>

<giperlink>leaf</giperlink>

</term>

<term value="term12">

<name>connected graph</name>

<count>1</count>

<definition count="1">An undirected graph that has a path between every pair of vertices. </definition>

</term>

<term value="term13">

<name>depth</name>

<count>1</count>

<definition count="1">Of a node, the distance from the node to the root of the tree. </definition>

<giperlink>node</giperlink>

<giperlink>tree</giperlink>

<giperlink>root</giperlink>

</term>

<term value="term14">

<name>doubly linked list</name>

<count>1</count>

<definition count="1">A variant of a linked list in which each item has a link to the previous item as well as the next. This allows easily accessing list items backward as well as forward and deleting any item in constant time. </definition>

<giperlink>linked list</giperlink>

<giperlink>link </giperlink>

</term>

<term value="term15">

<name>dynamic array</name>

<count>1</count>

<definition count="1">An array whose size may change over time. Items are not only added or removed, but memory used changes, too.

</definition>

<giperlink>array</giperlink>

</term>

<term value="term16">

<name>height</name>

<count>1</count>

<definition count="1">The maximum distance of any leaf from the root of a tree. If a tree has only one node (the root), the height is zero.

</definition>

<giperlink>leaf</giperlink>

<giperlink>tree</giperlink>

<giperlink>root</giperlink>

</term>

<term value="term17">

<name>internal node</name>

<count>1</count>

<definition count="1">A node of a tree that has one or more child nodes, equivalently, one that is not a leaf. </definition>

<giperlink>leaf</giperlink>

<giperlink>tree</giperlink>

<giperlink>node</giperlink>

<giperlink>child</giperlink>

</term>

<term value="term18">

<name>leaf</name>

<count>1</count>

<definition count="1">A node in a tree without any children. See the figure at tree. </definition>

<giperlink>leaf</giperlink>

<giperlink>tree</giperlink>

<giperlink>node</giperlink>

<giperlink>children</giperlink>

</term>

<term value="term19">

<name>linear search</name>

<count>1</count>

<definition count="1">Search an array or list by checking items one at a time. </definition>

<giperlink>list</giperlink>

<giperlink>array</giperlink>

</term>

<term value="term20">

<name>link</name>

<count>1</count>

<definition count="1">A reference, pointer, or access handle to another part of the data structure. Often, a memory address. </definition>

<giperlink>list</giperlink>

<giperlink>array</giperlink>

</term>

<term value="term21">

<name>list</name>

<count>1</count>

<definition count="1"> A collection of items accessible one after another beginning at the head and ending at the tail. </definition>

<giperlink>head</giperlink>

<giperlink>tail</giperlink>

</term>

<term value="term22">

<name>matrix</name>

<count>1</count>

<definition count="1">A two-dimensional array. By convention, the first index is the row, and the second index is the column. </definition>

</term>

<term value="term23">

<name>node</name>

<count>2</count>

<definition count="1">A unit of reference in a data structure. Also called a vertex in graphs and trees. </definition>

<definition count="2">A collection of information which must be kept at a single memory location.

</definition>

<giperlink>graphs</giperlink>

<giperlink>trees</giperlink>

<giperlink>vertex</giperlink>

</term>

<term value="term24">

<name>order</name>

<count>4</count>

<definition count="1">The height of a tree. </definition>

<definition count="2">The number of children of the root of a binomial tree. </definition>

<definition count="3">The maximum number of children of nodes in a B-tree. </definition>

<definition count="4">The number of data streams, usually denoted, in a multiway merge. </definition>

<giperlink>height</giperlink>

<giperlink>tree</giperlink>

<giperlink>children</giperlink>

<giperlink>root</giperlink>

<giperlink>node</giperlink>

</term>

<term value="term25">

<name>ordered linked list</name>

<count>1</count>

<definition count="1">A linked list whose items are kept in some order. </definition>

<giperlink>linked list</giperlink>

</term>

<term value="term26">

<name>ordered tree</name>

<count>1</count>

<definition count="1">A tree where the children of every node are ordered, that is, there is a first child, second child, third child, etc.

</definition>

<giperlink>tree</giperlink>

<giperlink>children</giperlink>

<giperlink>node</giperlink>

</term>

<term value="term27">

<name>parent</name>

<count>1</count>

<definition count="1">Of a node: the tree node conceptually above or closer to the root than the node and which has a link to the node. See the figure at tree. </definition>

<giperlink>tree</giperlink>

<giperlink>link</giperlink>

<giperlink>root</giperlink>

<giperlink>node</giperlink>

</term>

<term value="term28">

<name>root</name>

<count>1</count>

<definition count="1">The distinguished initial or fundamental item of a tree. The only item which has no parent. See the figure at tree.

</definition>

<giperlink>tree</giperlink>

<giperlink>parent</giperlink>

</term>

<term value="term29">

<name>search</name>

<count>1</count>

<definition count="1">To look for a value or item in a data structure. There are dozens of algorithms, data structures, and approaches. </definition>

</term>

<term value="term30">

<name>self-organizing list</name>

<count>1</count>

<definition count="1">A list that reorders the elements based on some self-organizing heuristic to improve average access time. </definition>

<giperlink>list</giperlink>

</term>

<term value="term31">

<name>sibling</name>

<count>1</count>

<definition count="1">A node in a tree that has the same parent as another node is its sibling. </definition>

<giperlink>tree</giperlink>

<giperlink>parent</giperlink>

<giperlink>node</giperlink>

</term>

<term value="term32">

<name>sorted array</name>

<count>1</count>

<definition count="1">An array whose items are kept sorted, often so searching is faster. </definition>

<giperlink>array</giperlink>

</term>

<term value="term33">

<name>sorted list</name>

<count>1</count>

<definition count="1">A list whose items are kept sorted. </definition>

<giperlink>list</giperlink>

</term>

<term value="term34">

<name>square matrix</name>

<count>1</count>

<definition count="1">A n*n matrix, i.e., one whose size is the same in both dimensions. </definition>

<giperlink>matrix</giperlink>

</term>

<term value="term35">

<name>tail</name>

<count>2</count>

<definition count="1">The last item of a list. </definition>

<definition count="2">All but the first item of a list; the list following the head. </definition>

<giperlink>list</giperlink>

</term>

</terms>

</bazaznanii>