Главная arrow Поиск arrow Введение
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Введение Печать

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

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

Агенты, решающие задачи

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

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

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

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

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

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

Итак, наш агент поставил перед собой цель доехать на автомобиле до Бухареста и определяет, куда отправиться для этого из Арада. Из этого города ведут три дороги: в Сибиу, Тимишоару и Зеринд. Прибытие в какой-либо из этих городов не представляет собой достижение намеченной цели, поэтому агент, не очень знакомый с географией Румынии, не будет знать, по какой дороге он должен следовать. Иными словами, агент не знает, какое из его возможных действий является наилучшим, поскольку не обладает достаточными знаниями о состоянии, возникающем в результате выполнения каждого действия. Если агент не получит дополнительных знаний, то окажется в тупике. Самое лучшее, что он может сделать, — это выбрать одно из указанных действий случайным образом.

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

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

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

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


function Simple-Problem-Solving-Agent(percept) returns действие action
  inputs: percept, результат восприятия
  static: seq, последовательность действий, первоначально пустая
            state, некоторое описание текущего состояния мира
            goal, цель, первоначально неопределенная
            problem, формулировка задачи
            state <— Update-State (state, percept)
  if последовательность seq пуста then do
    goal <— Formulate-Goal(state)
    problem <— Formulate-Problem(state, goal)
    seq <— Search (problem)
  action <— First(seg)
  seg <— Rest (seg)
return action


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

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

Последней и наиболее важной особенностью является следующее: в проекте агента предполагается, что среда является детерминированной. Решения задач представляют собой единственные последовательности действий, поэтому в них не могут учитываться какие-либо неожиданные события; более того, решения выполняются без учета результатов каких-либо актов восприятия! Агент, выполняющий свои планы, образно говоря, с закрытыми глазами, должен быть вполне уверенным в том, что он делает. (В теории управления подобный проект именуется системой с разомкнутой обратной связью, поскольку игнорирование результатов восприятия приводит к нарушению обратной связи между агентом и средой.)