РЕШЕНИЕ ПРОБЛЕМ ПОСРЕДСТВОМ ПОИСКА
В этой главе показано, каким образом агент может найти последовательность действий, позволяющую достичь его целей в тех условиях, когда единственного действия для этого недостаточно.
Простейшими агентами, которые рассматривались в главе 2, были рефлексные агенты, функционирование которых основано на непосредственном отображении состояний в действия. Подобные агенты не могут успешно действовать в тех вариантах среды, где такие отображения были бы слишком большими, чтобы можно было обеспечить их хранение, а изучение отображений потребовало бы слишком много времени. Агенты на основе цели, с другой стороны, способны достичь успеха, рассматривая будущие действия и оценивая желательность их результатов.
Данная глава посвящена описанию одной разновидности агента на основе цели, называемой агентом, решающим задачи. Агенты, решающие задачи, определяют, что делать, находя последовательности действий, которые ведут к желаемым состояниям. Начнем изложение этой темы с точного определения элементов, из которых состоит "задача" и ее "решение", и приведем несколько примеров для иллюстрации этих определений. Затем представим несколько алгоритмов поиска общего назначения, которые могут использоваться для решения подобных задач, и проведем сравнение преимуществ и недостатков каждого алгоритма. Эти алгоритмы являются неинформированными в том смысле, что в них не используется какая-либо информация о рассматриваемой задаче, кроме ее определения. В главе 4 речь идет об информированных алгоритмах поиска, в которых используются определенные сведения о том, где следует искать решения.
В данной главе применяются понятия из области анализа алгоритмов. Читатели, незнакомые с понятиями асимптотической сложности (т.е. с системой обозначений 00) и NP-полноты, должны обратиться к приложению А.
АГЕНТЫ, РЕШАЮЩИЕ ЗАДАЧИ
Предполагается, что интеллектуальные агенты обладают способностью максимизировать свои показатели производительности. Как уже упоминалось в главе 2, peaлизация указанного свойства в определенной степени упрощается, если агент способен принять на себя обязанность достичь цели и стремиться к ее удовлетворению. Вначале рассмотрим, как и почему агент может приобрести такую способность.
Представьте себе, что некоторый агент находится в городе Арад, Румыния, и проводит свой отпуск в качестве туриста. Показатели производительности агента включают много компонентов: он хочет улучшить свой загар, усовершенствовать знание румынского языка, осмотреть достопримечательности, насладиться ночной жизнью (со всеми ее привлекательными сторонами), избежать неприятностей и т.д. Эта задача принятия решения является сложной; для ее выполнения необходимо учитывать множество компромиссов и внимательно читать путеводители. Кроме того, предположим, что у агента имеется не подлежащий возмещению билет для вылета из Бухареста на следующий день. В данном случае для агента имеет смысл стремиться к достижению цели попасть в Бухарест. Способы действий, не позволяющие вовремя попасть в Бухарест, могут быть отвергнуты без дальнейшего рассмотрения и поэтому задача принятия решения агентом значительно упрощается. Цели позволяют организовать поведение, ограничивая выбор промежуточных этапов, которые пытается осуществить агент. Первым шагом в решении задачи является формулировка цели с учетом текущей ситуации и показателей производительности агента.
Мы будем рассматривать цель как множество состояний мира, а именно тех состояний, в которых достигается такая цель. Задача агента состоит в том, чтобы определить, какая последовательность действий приведет его в целевое состояние. Прежде чем это сделать, агент должен определить, какого рода действия и состояния ему необходимо рассмотреть. Но если бы агент пытался рассматривать действия на уровне "перемещения левой ноги вперед на один сантиметр" или "поворота рулевого колеса на один градус влево", то, по-видимому, так и не смог бы выехать с автомобильной стоянки, не говоря уже о своевременном прибытии в Бухарест, поскольку на таком уровне детализации мир обладает слишком большой неопределенностью, а решение должно состоять из слишком многих этапов. Формулировка задачи представляет собой процесс определения того, какие действия и состояния следует рассматривать с учетом некоторой цели. Этот процесс будет описан более подробно немного позднее. А на данный момент предположим, что агент будет рассматривать действия на уровне автомобильной поездки из одного крупного города в другой. Таким образом, состояния, рассматриваемые агентом, соответствуют его пребыванию в конкретном городе1.
Итак, наш агент поставил перед собой цель доехать на автомобиле до Бухареста и определяет, куда отправиться для этого из Арада. Из этого города ведут три дороги: в Сибиу, Тимишоару и Зеринд. Прибытие в какой-либо из этих городов не представляет собой достижение намеченной цели, поэтому агент, не очень знакомый с географией Румынии, не будет знать, по какой дороге он должен следовать2. Иными словами, агент не знает, какое из его возможных действий является наилучшим, поскольку не обладает достаточными знаниями о состоянии, возникающем в результате выполнения каждого действия. Если агент не получит дополнительных знаний, то окажется в тупике. Самое лучшее, что он может сделать, — это выбрать одно из указанных действий случайным образом.
Но предположим, что у агента есть карта Румынии, либо на бумаге, либо в его памяти. Карта способна обеспечить агента информацией о состояниях, в которых он может оказаться, и о действиях, которые он способен предпринять. Агент имеет возможность воспользоваться этой информацией для определения последовательных этапов гипотетического путешествия через каждый из этих трех городов в попытке найти такой путь, который в конечном итоге приведет его в Бухарест. Найдя на карте путь от Арада до Бухареста, агент может достичь своей цели, осуществляя действия по вождению автомобиля, которые соответствуют этапам этого путешествия. Вообще говоря, агент, имеющий несколько непосредственных вариантов выбора с неизвестной стоимостью, может решить, что делать, исследуя вначале различные возможные последовательности действий, которые ведут к состояниям с известной стоимостью, а затем выбирая из них наилучшую последовательность.
Описанный процесс определения такой последовательности называется поиском. Любой алгоритм поиска принимает в качестве входных данных некоторую задачу и возвращает решение в форме последовательности действий. После того как решение найдено, могут быть осуществлены действия, рекомендованные этим алгоритмом. Такое осуществление происходит на стадии выполнения. Итак, для рассматриваемого агента можно применить простой проект, позволяющий применить принцип "сформулировать, найти, выполнить", как показано в листинге 3.1. После формулировки цели и решаемой задачи агент вызывает процедуру поиска для решения этой задачи. Затем он использует полученное решение для руководства своими действиями, выполняя в качестве следующего предпринимаемого мероприятия все, что рекомендовано в решении (как правило, таковым является первое действие последовательности), а затем удаляет этот этап из последовательности. Сразу после выполнения этого решения агент формулирует новую цель.
Листинг 3.1. Простой агент, решающий задачу. Вначале он формулирует цель и задачу, затем ищет последовательность действий, позволяющую решить эту задачу, и, наконец, осуществляет действия одно за другим. Закончив свою работу, агент формулирует другую цель и начинает сначала. Обратите внимание на то, что при выполнении очередной последовательности действий агент игнорирует данные своих актов восприятия, поскольку предполагает, что найденное им решение всегда выполнимо
function Simple-Problem-Solving-Agent(percept) returns действие action inputs: percept, результат восприятия
static: seg, последовательность действий, первоначально пустая 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 дополнительно не рассматривается.
Прежде чем перейти к подробному описанию, сделаем краткую паузу, чтобы определить, в чем агенты, решающие задачи, соответствуют описанию агентов и вариантов среды, приведенному в главе 2. В проекте агента, показанном в листинге 3.1, предполагается, что данная среда является статической, поскольку этапы формулировки и решения задачи осуществляются без учета каких-либо изменений, которые могут произойти в данной среде. Кроме того, в этом проекте агента допускается, что начальное состояние известно; получить такие сведения проще всего, если среда является наблюдаемой. К тому же в самой идее перечисления "альтернативных стратегий" заключается предположение, что среда может рассматриваться как дискретная. Последней и наиболее важной особенностью является следующее: в проекте агента предполагается, что среда является детерминированной. Решения задач представляют собой единственные последовательности действий, поэтому в них не могут учитываться какие-либо неожиданные события; более того, решения выполняются без учета результатов каких-либо актов восприятия! Агент, выполняющий свои планы, образно говоря, с закрытыми глазами, должен быть вполне уверенным в том, что он делает. (В теории управления подобный проект именуется системой с разомкнутой обратной связью, поскольку игнорирование результатов восприятия приводит к нарушению обратной связи между агентом и средой.) Все эти предположения означают, что мы имеем дело с простейшими разновидностями среды, и в этом состоит одна из причин, по которой настоящая глава помещена в самом начале данной книги. В разделе 3.6 дано краткое описание того, что произойдет, если будут исключены допущения о наблюдаемости и детерминированности, а в главах 12 и 17 приведено гораздо более подробное изложение соответствующей темы.