Chmyr_I_A_Sistemy_II_4_razdela_2012

11

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

1.2.2. Свойства проблемной среды

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

Полностью наблюдаемая или частично наблюдаемая проблемная среда

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

Детерминированная или стохастическая проблемная среда

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

Эпизодическая или последовательная проблемная среда

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

12

Статическая или динамическая проблемная среда

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

Дискретная или непрерывная проблемная среда

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

Одноагентная или мультиагентная проблемная среда

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

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

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

1.3. Структура интеллектуальных агентов

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

фекторами. Эту систему называют архитектурой интеллектуального агента. Архитек-

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

Очевидно, что программа и архитектура должны соответствовать друг другу. Например, если программа формирует действие Walk (идти), то архитектура должна включать опорно-двигательный аппарат.

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

							13
		Наблю-	Детерми-		Статиче-	Дис-	Одно-
				Эпизоди-	ская, ди-		агентная
		даемая	нирован-			кретная
	Проблемная			ческая или	намиче-		или
		полностью	ная или			или не-
	среда			последова-	ская или		муль-
		или час-	стохасти-			прерыв-
				тельная	полудина-		тиагент-
		тично	ческая			ная
					мическая		ная
	Решение	Полностью	Детерми-	Последова-	Статиче-	Дискрет-	Одно-
		наблюдае-
	кроссворда		нированная	тельная	ская	ная	агентная
		мая
	Игра в шахма-	Полностью	Стохасти-	Последова-	Полудина-	Дискрет-	Мультиа-
	ты с контролем	наблюдае-
			ческая	тельная	мическая	ная	гентная
	времени	мая
		Полностью	Стохасти-	Последова-	Статиче-	Дискрет-	Мультиа-
	Игра в нарды	наблюдае-
			ческая	тельная	ская	ная	гентная
		мая
	Вождение	Частично	Стохасти-	Последова-	Динамиче-	Непре-	Мультиа-
		наблюдае-
	такси		ческая	тельная	ская	рывная	гентная
		мая
	Медицинская	Частично	Стохасти-	Последова-	Динамиче-	Непре-	Одно-
	диагностика и	наблюдае-
			ческая	тельная	ская	рывная	агентная
	лечение	мая
	Анализ	Полностью	Детерми-	Эпизодиче-	Полудина-	Непре-	Одно-
		наблюдае-
	изображений		нированная	ская	мическая	рывная	агентная
		мая
	Робот-	Частично	Стохасти-	Эпизодиче-	Динамиче-	Непре-	Одно-
	сортировщик	наблюдае-
			ческая	ская	ская	рывная	агентная
	деталей	мая
	Контроллер	Частично
	ректификаци-		Стохасти-	Последова-	Динамиче-	Непре-	Одно-
		наблюдае-
	онной установ-		ческая	тельная	ская	рывная	агентная
		мая
	ки
	Интерактивная
	программа,	Частично	Стохасти-	Последова-	Динамиче-	Дискрет-	Одно-
	обучающая	наблюдае-
			ческая	тельная	ская	ная	агентная
	английскому	мая
	языку

Рис. 1.6. Примеры проблемных сред и их классификационные признаки.

1.3.1. Программы интеллектуальных агентов

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

ния, что восприятие представляет собой оцифрованное сенсорное событие. Это предпо-

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

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

Для описания программ агентов будем использовать простой псевдокод. Программа агента, приведенная на рис. 1.7 иллюстрирует этот псевдокод на примере рассмотренного ранее табличного агента (см., например, рис. 1.3).

Как видно на рис. 1.7, программа интеллектуального агента рассматривается нами в виде функции. Функция имеет один входной аргумент в виде ссылки на структуру данных, моделирующую восприятие (perception). Возвращаемым значением функции является ссылка на структуру данных, которая моделирует действие (action). Заголовок функции, приведенный на рис. 1.7, является стандартным, и будет использоваться нами

14

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

function TableDrivenAgent(perception) returns action static: historyOfPerception, очередь истории восприятий,

первоначально пустая

table, таблица действий, индексированная историями восприятий и полностью заполненная

<добавить текущее восприятия к концу historyOfPerception>

action Lookup(historyOfPerception, table) return action

Рис. 1.7. Пример программы табличного агента.

После ключевого слова static описываются ссылки на структуры данных, моделирующие память агента. В нашем случае это: (1) ссылка historyOfPerception на структуру данных, которая хранит историю восприятий и (2) ссылка table на таблицу действий.

Работа программы по формированию действия осуществляется путѐм последовательного вызова функций, реализующих концепцию конкретного типа агента. В нашем случае это: (1) вызов функции (еѐ имя на рис. 1.7 не указано) которая добавляет результат текущего восприятия в память, хранящую историю восприятий и (2) вызов функции Lookup. Функция Lookup просматривает таблицу и находит строку, в которой описанная в левой части строки последовательность восприятий совпадает с содержимым historyOfPerception. Функция Lookup возвращает ссылку action на действие, описанное в правой части строки.

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

Рассмотрим такси, управляемое роботом-водителем. Визуальные входные данные от одной видеокамеры поступают со скоростью примерно 27 мегабайт в секунду (30 кадров в секунду, 640 х 480 пикселей с 24 битным кодированием одного пикселя). Согласно этим данным таблица действий, рассчитанная на один час работы робота-водителя, должна превышать количества строк, превышающее число 10250 000 000 000. Таблица действий, для случая игры в шахматы состоит, по меньшей мере, из 10150 строк. Ошеломляющий размер этих таблиц (притом, что количество атомов в наблюдаемой вселенной не превышает 1080) означает, что, (1) ни один физический агент в нашей вселенной не имеет пространства для хранения такой таблицы, (2) проектировщик не располагает временем, достаточным для создания такой таблицы и (3) ни один агент никогда не сможет обучиться тому, что содержится во всех правильных записях этой таблицы, на основании собственного опыта.

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

простые рефлексные агенты;

рефлексные агенты с внутренней моделью мира;

целеориентированные агенты;

агенты, действующие на основе функции полезности.

15

1.3.2. Простые рефлексные агенты

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

Представьте себя на месте робота-водителя такси. Если движущийся впереди автомобиль тормозит и загораются его тормозные огни, то вы, заметив это, тоже начинаете торможение. Иными словами над воспринятым визуальным образом выполняется обработка для выявления состояния, которое можно записать в виде строки символов: car- in-front-is-breaking (движущийся впереди автомобиль тормозит). Затем это состояние активизирует связь с действием: initiate-braking (начать торможение). В искусственном интеллекте знания о том, каким образом состояния проблемной среды свя-

заны с действием, часто, описываются продукционными правилами или правилом типа условие-действие. В простейшем случае продукционное правило имеет вид:

if car-in-front-is-breaking then initiate-braking.

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

АГЕНТ

Сенсоры

Как сейчас выглядит мир

СРЕДА

Продукционные		Какое сейчас вы-
правила		полнить действие
			Эффекторы

Рис. 1.8. Структура простого рефлексного агента.

Программа простого рефлексного агента приведена на рис. 1.9

function SimpleReflexAgent(perception) returns action static: rules, множество продукционных правил

state InterpretInput(perception) rule RuleMatch(state, rules)

action RuleAction(rule) return action

Рис. 1.9. Программа простого рефлексного агента.

Функция InterpretInput трансформирует восприятие в закодированное состояние (левая часть продукционного правила). Функция RuleMatch возвращает первое найденное продукционное правило, у которого левая часть совпадает со значением state.

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

16

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

1.3.3.Рефлексные агенты с внутренней моделью мира

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

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

пример, что при повороте агентом рулевого колеса по часовой стрелке автомобиль поворачивает вправо).

На рис. 1.10 приведена структура рефлексного агента с внутренней моделью мира. Знания о текущее состояние комбинируется со знаниями, полученными при помощи внутренней модели мира для выработки обновлѐнного описания текущего состояния.

Модель мира	Сенсоры

Законы развития среды
						Как сейчас
	Влияние действий					выглядит мир
	агента на среду
									СРЕДА
	Продукционные				Какое сейчас вы-
	правила				полнить действие
						Эффекторы
	АГЕНТ

Рис. 1.10. Структура рефлексного агента с внутренней моделью мира.

На рис. 1.11 приведена программа рефлексного агента с внутренней моделью мира.

function ReflexAgentWithModel(perception) returns action static: state, описание текущего состояния мира

rules, множество продукционных правил

state CurrentState(perception, InternalModel()) rule RuleMatch(state, rules)

action RuleAction(rule) return action

Рис. 1.11. Программа рефлексного агента c внутренней моделью мира.

В программе, приведенной на рис. 1.11, интерес представляет функция CurrentState, которая формирует описание состояния проблемного пространства. Эта функция использует, в качестве аргументов, как текущее восприятие (perception), так и данные, полученные от внутренней модели мира (возвращаемое значение функции InternalModel()).

17

1.3.4. Целеориентированные агенты

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

Процедура принятия решения целеориентированным агентом имеет фундаментальные отличия от процедуры принятия решения рефлексным агентом, поскольку агенту приходится размышлять о будущем (прогнозировать), отвечая на вопросы: «Что произойдѐт с проблемной средой, если я выполню данное действие?» и «Позволит ли данное действие приблизиться к целевому состоянию?». Рефлексные агенты не способны на подобные размышления. Рефлексный агент-водитель такси тормозит, увидев сигналы торможения движущегося впереди автомобиля, даже если он находится далеко впереди. Целеориентированный агент-водитель такси принимает решение о торможении на основании рассуждений. Он может рассудить, что если на движущемся впереди автомобиле появились тормозные огни, то этот автомобиль замедляет движение и, следовательно, расстояние до движущегося впереди автомобиля сокращается. Если целью агентаводителя такси является предотвращение столкновения, то единственным действием, позволяющим еѐ достичь является торможение.

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

1.3.5. Агенты, действующие на основе функции полезности

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

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

Упражнения

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

a. робот-футболист;

18

b.агент, покупающий книги в Internet;

c.автономный марсианский вездеход;

d.ассистент математика, занимающийся доказательством теорем.

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

1.3.Обоснуйте каждый классификационный признак проблемных сред, приведенных на рис. 1.6.

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

1.5.Предложите программу целеориентированного агента.

1.6.Предложите программу агента, действующего на основе функции полезности.

19

2.РЕШЕНИЕ ПРОБЛЕМ ПОСРЕДСТВОМ ПОИСКА

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

2.1. Агенты, решающие проблемы

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

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

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

ляется «перемещение из данного города в один из ближайших городов».

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

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

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

20

полнение действий эффекторами агента осуществляется на заключительном этапе – вы-

полнения решения.

Обобщая сказанное можно написать программу агента, решающего проблему, основанную на принципе «сформулируй проблему, найди решение, выполни решение». Эта программа приведена на рис. 2.1.

function SimpleProblemSolvingAgent(perception) returns action inputs: perception, результат восприятия

static: seq, последовательность действий, первоначально пустая state, описание текущего состояния среды

goal, цель, первоначально не определѐнная problem, формулировка проблемы

state UpdateState(state, perception) if последовательность seq пустая then do

goal FomulateGoal(state)

problem FomulateProblem(state, goal)

seq Search(problem)

repeat

action First(seq)

seq Rest(seq) return action

until

Рис. 2.1. Программа агента, решающего проблему.

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

2.1.1. Хорошо структурированные проблемы

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

Хорошо структурированные проблемы решаются в полностью наблюдаемой и детерми-

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

Начальное состояние, в котором находится среда, когда агент приступает к работе. Например, для нашего агента в Румынии, начальное состояние может быть описа-

но, как In(Arad).

Перечень действий, доступных агенту, или задание функции последующих состояний – SuccessorFn. Если задано конкретное состояние x, то функция SuccessorFn(x) возвращает множество упорядоченных пар <action,successor>, где action представляет собой одно из доступных действий в состоянии x, а successor представляет собой состояние, которое может быть достигнуто из x путѐм применения этого действия. Например, для состояния In(Arad) функция