Агенты и МАС

Развитие интеллектуальных агентов и МАС очень популярны в среде исследователей ИС.

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

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

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

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

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

Пусть в системе имеются серверы Serv ₁, Serv ₂, …, Serv_m, соединенные каналами связи, и агенты A ₁, A ₂, …, A_n, пользующиеся услугами этих серверов. Агенты автономно выполняются на серверах. Агент самостоятельно инициализируется на сервере: процедура и данные агента записываются в память сервера объектов, если на этом сервере достаточно ресурсов для работы агента. Говорят, что агент A_k размещается (land – «приземляется») на сервере Serv_i и этот сервер становится для агента текущим.

Для размещения на сервере важны два условия:

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

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

После выполнения работы с объектами на сервере Serv_i агент A_k может переместиться на сервер Serv_j для выполнения работы с находящимися там объектами. Перемещения агента зависят от того, какая перед ним стоит цель и на каких серверах находятся нужные ему объекты.

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

1) создание агента (по некоторому описанию). Создание происходит всегда на некотором сервере. Этот сервер называют «домашним» для созданного агента;

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

3) расслоение агента A. Агент A разделяется на несколько агентов A ₁, A ₂, …, A_l, начинающих самостоятельное существование в системе. Это разделение может коснуться программ и данных агента, а также его целей и задач;

4) слияние агентов A ₁, A ₂, …, A_l. Вместо нескольких агентов, прекращающих самостоятельное существование, возникает один агент, обобщающий процедуры и данные составляющих агентов, а также их цели и задачи;

5) уничтожение агента A. Агент A перестает существовать в системе.

Рис. 19. Расслоение и слияние агентов

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

Транзакция должна удовлетворять четырем условиям (их называют ACID):

1) атомарности (atomicity). Работа, которую должна выполнить транзакция, не может быть сделана «наполовину». Либо работа выполнена полностью, либо она не выполнена совсем. Это не означает, что транзакция не может состоять из субтранзакций. Если из всех транзакций, которые должны были выполниться, не выполнится хотя бы одна, то считается невыполненной вся транзакция. Должен быть произведен откат (roll back) – последовательность действий, возвращающая сервер (или базу данных) в исходное (до начала выполнения транзакции) состояние;

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

3) изолированности (isolation). Транзакции изолированы друг от друга, кроме случая, когда одна транзакция является субтранзакцией другой. Транзакции либо выполняются последовательно, либо (что вполне возможно в распределенных системах) пересекаются по времени, но не пересекаются по данным. Иными словами, никакие данные, которые читает или изменяет транзакция T ₁, не должны быть доступны для изменения или чтения транзакцией T ₂ до тех пор, пока T ₁ не завершилась.

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

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

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

Мобильные пользователи обычно находятся в условиях относительно низкой полосы пропускания каналов связи и не слишком плотной (с точки зрения количества связей между узлами) сети. Это затрудняет, в частности, работу с объемными Web-документами, передавать которые целиком на терминал пользователя неэффективно.

Решением может быть (С.Яу, Х.Леонг, А.Си) «нарезка» документа на части и передача непосредственно пользователю только той части, с которой он работает в данный короткий отрезок времени. Таким образом, будет решена проблема недостаточной пропускной способности канала связи.

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

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

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

Рис. 20. Перемещение мобильного пользователя и мобильного агента

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

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

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

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

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

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

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

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

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

1) декомпозиция агентом A задачи на подзадачи;

2) назначение подзадач агентам A_i;

3) решение подзадач агентами;

4) синтез общего результата из частных результатов.

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

При назначении подзадач должны быть выбраны подходящие (по тем или иным критериям) агенты.

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

Синтез результата производится тем агентом A, который инициировал распределение задачи. Он собирает частные результаты своих «помощников» A_i и формирует общий результат. Процесс формирования зависит от того, как исходная задача была разделена на подзадачи. Если декомпозиция, как отмечено выше, была многоуровневой, то и синтез результата будет многоуровневым.

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

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

При синтезе общего решения R из локальных решений R_i должна быть произведена «сшивка» решений R_i по границам территорий. И вот здесь может быть выявлена несогласованность сделанных ранее агентами A_i локальных предположений о потоках на границах. Дело в том, что в результате локального решения для территории k будут, в частности, получены и описания «выходных» потоков транспорта с территории k. Если территория k смежна с территорией l и поток из k направляется в l, то «вычисленный» выходной поток k может не совпасть с «предполагаемым» входным потоком l.

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

В результате этого решение R не может быть получено простым объединением решений R_i.

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

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

1) изменение предположений о «входных» потоках территорий с учетом вычисленных «выходных» потоков;

2) пересчет локальных решений R_i;

3) сравнение новых выходных потоков предположениями о входных потоках. При совпадении или небольших отклонениях – прекращение процесса. При больших отклонениях – возврат к пункту 1.

Если итерационный процесс завершился в пункте 3 полными совпадениями, то итоговое решение R может быть получено простым объединением решений R_i.

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

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

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

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

Описанные проблемы поиска решения имеют в области искусственного интеллекта наименование «удовлетворение распределенных ограничений» (Distributed Constraint Satisfaction).