Лекция 10. Распределенные интеллектуальные системы на основе агентов
Лекция 10. Распределенные интеллектуальные системы на основе агентов - Лекция, раздел Философия, Распределенные системы и алгоритмы Современные Системы Искусственного Интеллекта Часто Строятся Как Системы Взаи...
Современные системы искусственного интеллекта часто строятся как системы взаимодействующих и сотрудничающих агентов.
Одним из расширений понятия программы стало понятие агента. Оно появилось в связи с использованием программ не только для решения численных задач или иной подобной обработки информации, но и в системах реального времени (real-time systems).
Обычная вычислительная программа, например, программа расчета колебаний струны, запускается на ЭВМ, получает входные данные, выполняется как последовательность заранее написанных команд, выводит результат. До следующего запуска извне (если он вообще состоится) она пребывает в состоянии «комы». В программе расчета колебаний струны, конечно, фигурирует такой параметр как время, но он используется наряду с другими параметрами, такими как амплитуда, и никакого отношения к реальному времени, в котором выполняется программа, не имеет.
Программа реального времени функционирует (запускается, приостанавливается, возобновляется, завершается, запускается вновь) в соответствии с внешними, физическими, а не абстрактными, часами. Это ее главный отличительный признак.
Кроме того, физическое время чаще всего является одним из существенных параметров расчета. Программа реального времени взаимодействует с окружением (получает и передает информацию) посредством интерфейсов, т.е. она влияет на окружающую среду и испытывает, в свою очередь, влияние окружающей среды. Отсюда следует второй важный отличительный признак программы реального времени: потенциально она может оценивать результаты своего выполнения (обратная связь) и менять свои действия в будущем с учетом прошлого.
Таким образом, можно говорить о поведении программы реального времени по отношению к окружению. В связи с этим программа реального времени уже не рассматривается как элемент stand-alone системы, она является частью системы, имеющей признаки распределенной системы.
Эти и другие важные отличия от обычной программы привели к возникновению понятия программного агента и более широкого понятия – автономного агента.
В традиционных системах программы могут правильно функционировать только в условиях полностью предсказуемого окружения. Для того чтобы выполнить с помощью программы некоторое вычисление пользователь должен задать всю входную информацию (аргументы). Если программа берет исходные данные из базы данных, то должна быть полная уверенность в том, что эти данные имеются в базе.
Программные агенты обладают некоторыми знаниями об окружающем мире, которые позволяют им самим решать небольшие проблемы без вмешательства пользователя. Например, Интернет-агенты могут самостоятельно отыскивать нужную информацию в Сети (разумеется, в определенных пределах). Таким образом, агенты – это более гибкая конструкция, чем традиционные программы. Дополнительно, если агент может общаться с другими агентами, то они могут помочь ему решить проблему, действуя совместно.
Как и в случае классических алгоритмов, когда мы обсуждаем интуитивное понятие алгоритма и его формализации, можно обсуждать интуитивное понятие агента и различные его формализации.
Начнем с интуитивного понятия агента. Несмотря на рост числа теоретических исследований и приложений технологий, основанных на применении агентов, так и нет общепринятого определения термина «агент». Существует несколько трактовок, зависящих от целей исследования.
В частности, П.Маес из Media Lab Массачусетского технологического института считает, что «автономные агенты – это вычислительные системы, которые существуют в сложном динамическом окружении, чувствуют и действуют в этом окружении автономно, и так, чтобы реализовать множество целей и задач, для которых они спроектированы».
Б.Хайес-Рот считает, что «мыслящие агенты непрерывно выполняют три функции: восприятие динамически изменяющихся условий окружения; действия по влиянию на окружение; логический вывод для интерпретации получаемой информации, решения проблем, построения заключений и определения действий».
М.Вулдридж и Н.Дженнингс разделяют слабое и сильное понятия агента. Слабый агент рассматривается как система со свойствами автономности, возможности работать в обществе (social ability), реактивности, целенаправленности. Сильное понятие агента предполагает возможность непредписанных действий, предпринимаемых на основе собственных «идей».
Их определение включает следующие свойства: 1) автономия: агенты действуют без непосредственного вмешательства людей или чего-либо еще, определенным образом контролируют свои действия и внутреннее состояние; 2) социальные возможности: агенты взаимодействуют с другими агентами (и, возможно, людьми) с помощью некоторого языка; 3) реактивность: агенты воспринимают свое окружение (которое может быть физическим миром, пользователем – через графический пользовательский интерфейс, набором других агентов, Интернетом, или комбинацией всего этого) и отвечают периодически так, чтобы изменить что-то в своем окружении; 4) целенаправленность: агенты не просто отвечают своему окружению, они способны на целенаправленное поведение и проявление инициативы.
Т.Хесс и др. разделяют свойства на базовые и продвинутые. К базовым относятся целенаправленность, постоянство функционирования и реактивность. Продвинутые свойства включают наличие искусственного интеллекта, мобильность и интерактивность.
С.Франклин и А.Грэссер в 1996 году предложили следующее обобщенное определение агента:
Автономный агент – это система, находящаяся внутри окружения и являющаяся его частью, воспринимающая это окружение (его сигналы) и воздействующая на окружение для выполнения собственной программы действий.
Расшифровка этого определения дается перечнем свойств, которыми должен обладать автономный агент:
1) реактивность;
2) автономность;
3) целенаправленность;
4) непрерывность функционирования;
5) коммуникативность;
6) обучаемость (адаптивность);
7) мобильность;
8) гибкость;
9) индивидуальность.
Разные авторы не совсем одинаково трактуют перечисленные свойства. Попытаемся объяснить их подробнее.
Свойство реактивности означает, что агент временами отвечает на изменения в окружении. Агент имеет сенсоры, с помощью которых получает информацию от окружения. Сенсоры могут быть самыми различными. Это могут быть микрофоны, воспринимающие акустические сигналы и преобразующие их в электрические, видеокарты захвата изображений, клавиатура компьютера или общая область памяти, в которую окружение помещает данные и из которой программный агент берет данные для вычислений.
Не все изменения окружения становятся известными (доступными) сенсорам агента. Это вполне естественно. Ведь и человек не воспринимает звуки частотой свыше 30 кГц, радиоволны и т.д. Таким образом, окружение не является полностью наблюдаемым для агента.
Аналогично, агент воздействует на окружение путем разнообразных исполнительных механизмов, включая общую память. Разумеется, степень воздействия как и степень восприятия является ограниченной. Агент может перевести окружение из некоторого состояния в некоторое другое, но не из любого в любое.
Свойство автономности означает, что агент является самоуправляющимся, сам контролирует свои действия. Программный агент, находящийся на некотором сервере, обладает возможностью «самозапуска». Он не требует от пользователя каких-либо специальных действий по обеспечению его старта (подобно тому, как мы «кликаем» два раза по иконке некоторого файла).
Свойство целенаправленности означает, что у агента имеется определенная цель и его поведение (воздействие на окружение) подчинено этой цели, а не является простым откликом на сигналы из окружения. Иначе говоря, агент является управляющей системой, а не управляемым объектом.
Свойство непрерывности функционирования означает, что агент постоянно находится в состоянии исполнения. Это не значит, что он ежесекундно выдает в окружение какие-то сигналы. Он может прекратить активные действия, «заснуть», до некоторого момента времени или какого-то события. Но в необходимый момент времени он сам возобновляет действия, не требуя какого-то «включения» извне.
Свойство коммуникативности означает, что агент общается с другими агентами (включая людей), используя для этого некоторый язык. Это не обязательно единый язык для всех агентов. Достаточно, чтобы у пары общающихся агентов был общий язык. Язык может быть сложным как, например, естественный язык. Но может быть и примитивным: обмен числами или короткими словами. Если многословные фразы сложного языка несут всю информацию, как правило, в себе, то слова простого языка предполагают «умолчание»: обе стороны диалога «знают», о чем идет речь (как в известном анекдоте о занумерованных анекдотах).
Свойство обучаемости означает, что агент может корректировать свое поведение, основываясь на предыдущем опыте. Это не просто накопление в памяти параметров окружения, т.е. использование исторических данных, но сопоставление истории собственных действий с историей их влияние на окружение, и изменение в связи с этим своей программы действий.
Свойство мобильности означает, что агент может транспортировать себя с одной машины на другую. В общем случае можно сказать, что агент меняет свое положение в окружении (не меняя самого окружения).
Свойство гибкости означает, что действия агента не предписаны. Это, конечно, весьма относительное утверждение. Имеется в виду, что программа, заложенная в агента, предполагает выбор из многочисленных вариантов поведения. Такого рода выбор производится если не на каждом шагу, то достаточно часто, и зависит от выполнения или невыполнения различных условий. Выбор не является ни случайным, ни недетерминированным. Гибкость означает, что действия агента не примитивны, не легко предсказуемы.
Свойство индивидуальности означает наличие персональных свойств, данных, возможно, «эмоционального» состояния.
Систему, состоящую из нескольких взаимодействующих агентов, называют мультиагентной системой (МАС). Если мультиагентная система, в свою очередь, по отношению к ее окружению действует как (единый) агент, то естественно, составляющих ее агентов назвать подагентами (субагентами).
В мультагентной системе необязательно все агенты взаимодействуют (общаются) между собой. В крайнем случае, общения нет вообще. Такие системы назовем дискретными мультиагентными системами. Второй крайний случай – каждый агент общается с каждым. Такую систему назовем полносвязной мультиагентной системой.
Мультиагентная система, действующая как единый агент, должна характеризоваться и некоторой общей для всех субагентов целью и координацией действий по достижению этой цели.
Поскольку встречаются и другие ситуации, когда агенты не связаны столь тесно, то такие системы можно назвать обществами агентов. Отсутствие единой цели, однако, не отрицает возможного группового поведения агентов. Но оно является, скорее, эпизодическим, чем систематическим.
Важным отличием мультиагентной системы от программы или одного агента является то, что входящие в систему программные агенты (по крайней мере, некоторые) не были спроектированы специально для этой системы. Может быть, это – повторно используемые агенты, или агенты, разработанные для решения более универсальных задач. В этих случаях агенты имеют собственные цели, не совпадающие полностью с целями системы (организации), но совместимые с ними. Тем не менее, они могут быть полезны друг другу для решения стоящих перед ними задач и, поэтому, очень важным для них с этой точки зрения является свойство коммуникативности.
С организационной точки зрения существуют общие цели всего сообщества, и эти общие цели выражаются, прежде всего, в ролях (которые играют агенты) и нормах взаимодействия.
Исследования в области систем поддержки принятия решений (DSS) в последние годы все больше переходят от создания систем в виде традиционного «ящика с инструментами» (toolbox) к парадигме сотрудничества и интеграции независимых приложений. Быстро растущая область исследований интеллектуальных агентов и мультиагентных систем предлагает возможности создания более эффективных систем на основе единого подхода. Например, Р.Вахидов и Б.Фазлоллахи предлагают плюралистическую мультиагентную систему поддержки принятия решений. Слово «плюралистический» в названии подхода говорит о множественности, различности источников информации, точек зрения и перспектив, используемых в рамках одной системы. Агенты распределены по ролям в соответствии с различными фазами решения проблем. Они взаимодействуют с пользователем, окружением, друг с другом для улучшения процесса принятия решения.
Сосредоточенные и распределенные системы
Во многих случаях термин «распределенная» является альтернативой термину «сосредоточенная». Так бывает, когда существуют (или могут существовать) системы, решающие одинаковые задачи, системы, функц
Тандемы распределенных систем
Рассмотрим две системы, S1 и S2 . Первая система функционирует для достижения некоторой цели G1 . При этом в любой момент времени имеется некот
Лекция 2. Распределенные задачи и алгоритмы
С системой S связана цель G, ради которой система функционирует. Эта цель ставится самой системой (если система – активная), или поставлена извне. Для достижения цели в системе должна
Лекция 3. Надежность и безопасность распределенных систем
Сравним сосредоточенную и распределенную системы с точки зрения надежности и безопасности.
Под надежностью понимается в соответствии с ГОСТ 27.002-89 свойство системы сохранять во в
Структура информационного пространства
Хотя термин «информационное пространство» является лишь метафорой, обратимся к проблеме анализа структуры этого пространства. Математики привыкли связывать с любым пространством некоторую структуру
Структуры РРИСО
Структуру РРИСО можно рассматривать с нескольких точек зрения. Прежде всего, это наиболее очевидная – географически ориентированная структура. Многие (но не все) элементы информационной системы при
Подсистемы. Взаимоотношения структур
Каждая из структур РРИСО строится по своим законам, поэтому, не стоит ожидать изоморфизма между парами структур. Идеально, если одни структуры являются надстройками над другими, использующими механ
Условная корпоративность
Хотя мы называем РРИСО корпоративной системой в силу того, что имеется определенный административный «каркас» на множестве ее пользователей, и у нее довольно четкая целевая направленность, тем не м
Неоднородность
Неоднородность – одна из важнейших характеристик РРИСО. Если многие корпоративные системы являются однородными, или неоднородность имеет место в одном - двух аспектах построения системы, то неоднор
Интегрируемость
Это одно из ключевых свойств в характеристике РРИСО. Это и «врожденное» и приобретаемое свойство.
Невозможно представить себе, чтобы такая система создавалась «с нуля». Существуют базы дан
Лекция 6. Моделирование распределенных систем. Язык Triad
Исследование распределенных систем – трудная задача. Прежде всего, распределенная система должна быть описана, т.е. должна быть построена модель системы. Для этой цели можно использовать различные
For i:= 1 to n do
routine(System2.Node[i]) := Generator
endf.
При этом создается n экземпляров рутины Generator. Для каждого экземпляра рутины создается свой комплект локальных пер
For i:= 1 to n – 1 do
System := System + (System.Node[i] « System.Node[i + 1])
endf;
System := System + (System.Node[n] « System.Node[1])
В цикле к системе добавляются ребра м
Лекция 7. Распределенное имитационное моделирование
В одной из лекций шла речь о методах исследования распределенных систем. В качестве одного из методов рассматривался метод имитационного моделирования.
Если предположить, что предметом исс
Причины для перехода к распределенному моделированию
Использование распределенного моделирования объясняется:
- возможностью использования вычислительных ресурсов нескольких процессоров (компьютеров) для выполнения имитационного эксперимента
Два направления в развитии распределенных систем моделирования
Развитие распределенного имитационного моделирования идет по двум направлениям. Это монолитные системы моделирования и готовые системы моделирования, объединенные с помощью специального программног
Физическое время
Рассмотрим пример: пусть на нескольких компьютерах (клиентах) располагаются директории с файлами – списки товаров, на сервере – сводная директория, которая периодически обновляется. Приложение, рас
Управление временем в распределенном моделировании
Управление временем в распределённом моделировании должно обеспечивать выполнение событий в правильном хронологическом порядке. Более того, на алгоритмы синхронизации возлагается обязанность коррек
Парадоксы времени
Алгоритм управления временем должен следить за тем, чтобы события выполнялись в хронологическом порядке. Эта задача не является тривиальной. Действительно, логический процесс заранее не может знать
Консервативное управление временем
Первые алгоритмы синхронизации использовали консервативный подход. Принципиальная задача консервативного протокола – определить время, когда обработка очередного события из списка необработанных со
Алгоритм с нулевыми сообщениями
Первыми консервативными алгоритмами считаются алгоритмы, разработанные Bryant, Chandy, Misra.
Алгоритм предполагает:
- Топология процессов, которые посылают сообщения друг другу,
Оптимистическое управление временем
В отличие от консервативных алгоритмов, не допускающих нарушения ограничения локальной каузальности, оптимистические методы не следят за этим ограничением. Однако этот подход гарантирует выявление
Лекция 9. Балансировка нагрузки в распределенных системах
Балансировка нагрузки (Load Balancing) применяется для оптимизации выполнения распределённых (параллельных) вычислений с помощью распределённой (параллельной) ВС. Балансировка
Статическая и динамическая балансировки
Следует различать статическую и динамическую балансировки.
Статическая балансировка выполняется до начала выполнения распределенн
Оценка загрузки
На этом этапе осуществляется приблизительная оценка загрузки каждого процессора. Полученная информация о загрузке используется в качестве базы данных для процесса балансировки, во-первых, для опред
Инициализация балансировки загрузки
Слишком частое выполнение балансировки загрузки может привести к тому, что выполнение имитационной модели только замедлится. Затраты на саму балансировку могут превзойти возможную выгоду от ее пров
Балансировка загрузки распределенной имитационной модели
В одной из предыдущих лекций мы рассматривали вопросы реализации распределенных систем имитации. Балансировку необходимо выполнять и при проведении распределённого моделирования. Первоначальная цел
Динамическая балансировка и перенос нагрузки
Алгоритм динамической балансировки использует характеристики состояния системы и принимает решение о том, с какого компьютера и на какой следует перенести работу во время моделирования. Это подход
RCL – cтратегия переноса нагрузки
Рассмотрим три алгоритма динамического переноса нагрузки, предложенные разработчиками SPEEDES:
- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communica
Действия первого уровня
В начале действий по переносу нагрузки информации все компьютеры прекращают свою работу, и каждый получает информацию о локальной нагрузке в текущий момент времени. Информация о локальной нагрузке
Действия второго уровня
Действия второго уровня охватывают все рабочие станции распределённой системы. Конкретной количество нагрузки посылается с одной рабочей станции на другую. Основные действия связаны с выбором нагру
Реализация
Стратегия динамического переноса нагрузки RCL была разработана для SPEEDES с целью повышения её производительности. Были проведены эксперименты для выявления конкретных параметров, которые влияют н
Распределенные веб-сервисы
В настоящее время веб-сервисы находят все более широкое применение. Они используются в самых разных случаях в Интернет. Быстрое увеличение числа веб-сервисов и пользователей этих сервисов требует в
Использование мобильных агентов
Наряду с традиционными подходами (парадигма обмена сообщениями) рассмотрим другой – мультиагентный подход.
Напомним, что мобильный агент – это программный компонент, который может автомати
Мультиагентный подход к балансировке
Мобильные агенты используются для поддержки балансировки загрузки в параллельных и распределенных вычислениях. Рассмотрим кратко несколько проектов.
Проект Traveller
Проект
Агенты и МАС
Развитие интеллектуальных агентов и МАС очень популярны в среде исследователей ИС.
В области ИС интеллектуальные агенты используются, прежде всего, для интеграции информационных систем, по
Лекция 11. Распределенное хранение информации
Источники информации часто, как говорилось ранее, находятся в различных точках физического пространства. Если информация из этих источников не используется сразу, а потребность в ней возникает лишь
Фрагментация
Реляционные базы данных хранят отношения – таблицы, состоящие из строк и столбцов. Строка отношения называется кортежем и представляет собой запись (record в смысле языка программирования, н
Репликация
Под репликацией понимается создание копий некоторых фрагментов отношений и одновременное хранение нескольких копий на разных сайтах (в разных локальных БД). Репликация используется для того,
Схемы владения данными в распределенной БД
Выше, рассматривая распределенную базу данных, состоящую из локальных сайтов, мы неявно предполагали, что для каждой единицы данных существует вполне определенный единственный сайт, владеющий этими
Лекция 12. Волновые алгоритмы распространения информации
Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей систем
Алгоритм для кольцевой архитектуры
Если сайты распределенной системы соединены однонаправленными каналами связи так, что образуют граф – ориентированный цикл, применим следующий волновой алгоритм.
Суть его в следующем. Один
Алгоритм для структуры – дерева
Предположим, что соединение сайтов распределенной системы каналами образует граф – неориентированное дерево. Из теории графов известны следующие факты для деревьев:
1) дерево – связный аци
Алгоритм голосования
Алгоритм голосования применяется для распределенных систем, имеющих структуры полных графов. В этом случае инициатором может быть любой сайт. Для графа – звезды его тоже можно использовать, но иниц
Фазовый алгоритм
Фазовый алгоритм является децентрализованным алгоритмом для произвольных ориентированных графов. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встреч
Алгоритм Финна
Алгоритм Финна – еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает
Распространение информации с обратной связью
Важным применением волновых алгоритмов является случай, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задач
Синхронизация
Волновые алгоритмы могут использоваться для случаев, когда должна быть достигнута глобальная синхронизация процессов. Задача синхронизации формулируется следующим образом. В каждом процессе q
Вычисление нижней грани
Продемонстрируем применение волновых алгоритмов для вычисления функций, значения которых зависят от входов процесса на каждом сайте. В качестве представителей таких функций будут рассмотрены алгори
Лекция 13. Алгоритмы обхода сайтов
Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.
1) В каждом вычислении один сайт-инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщен
Алгоритм обхода тора
Граф вида «тор» представляет собой решетку с дополнительными ребрами, соединяющими вершины из верхнего ряда («строки») решетки с вершинами из нижнего ряда, а также с ребрами, соединяющими вершины и
Алгоритм обхода гиперкуба
В теории графов известен класс графов Qn , называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K2
Алгоритм Тарри
Алгоритм обхода для произвольных связных графов был дан Тарри. Алгоритм основан на следующих двух правилах.
1. Процесс никогда не передает маркер дважды по одному и тому же каналу.
Лекция 14. Алгоритмы выбора сайтов
Во многих распределенных системах один из сайтов играет роль координатора при выполнении распределенного алгоритма. Иногда координатором является сайт, который инициировал выполнение алгоритма. Но
Алгоритм смещения
Алгоритм предназначен для динамического выбора координатора на основе локальных оценок сайтов. Предполагается, что каналы связи надежны, а сайты иногда могут прерывать (например, из-за отказов) сво
Выбор с помощью алгоритма для деревьев
Если топология распределенной системы – дерево или доступно остовное дерево системы, выбор можно провести с помощью алгоритма, приведенного в лекции 12. В этом алгоритме требуется, чтобы все концев
Алгоритмы выбора для кольцевых архитектур
В алгоритме Лелана для распределенной системы с архитектурой кольца (ориентированного цикла) каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с на
Лекция 15. Поиск в пиринговых системах
Пиринговые системы (peer-to-peer, P2P) – это такие компьютерные сети, в которых не используется классическая схема клиент-сервер, разделяющая множество всех узлов на два подмножества – серверов и к
Лекция 16. Тенденции в области распределенных систем
В одной из своих статей в 2001 году Дж. Бэкус отметил, что компьютерная революция испытала три волны. Первая волна началась с коммерциализацией кремниевых чипов и продолжалась 10-15 лет. Вторая вол
Архитектура Грид
Следуя традиционному построению распределенных систем, можно описать архитектуру Грид, состоящую из четырех слоев:
1. Пользовательские интерфейсы, приложения и среда решения задач (problem
Мобильный компьютинг
Самостоятельным направлением является мобильный компьютинг. В его основе (в дополнение к распределенному компьютингу) лежат:
1) сети, обеспечивающие подключение к ним
Тотальный компьютинг
Английский термин pervasive computing обозначает проникающий, распространяющийся повсюду, всеобъемлющий, глубоко влияющий (компьютинг). Тотальный компьютинг ставит во главу угла конечного пользоват
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов