Файл: Методыискусственногоинтеллекта.pdf

146
Гл. 3. Методы интеллектуального планирования
приведет к сбою, тем выше приоритет. Примером критика может высту- пать процедура, оценивающая, способна ли компания покрыть расходы на приведение плана в действие.
Если критик говорит о том, что план нуждается в модификации,
то выполняется поиск прецедента, где встречалась такая же пробле- ма. С каждым критиком связан индивидуальный набор свойств, по которым выполняется поиск прецедента. Если прецедент найден, то он оценивается на применимость в данной ситуации. Если предусловия рассматриваемого плана удовлетворяются в текущей ситуации, то план добавляется в текущее решение. Иначе он подвергается модификации или ищется другое решение. Если же прецедент не найден, то для модификации приблизительного плана используются правила, ассоци- ированные с критиком.
Система CHEF. Предметная область системы — приготовление блюд [79]. Она хранит информацию как об успешных эпизодах пла- нирования, так и о сбоях. Хранение информации о сбоях позволяет предсказывать и избегать подобных ситуаций в будущем. При хране- нии планы индексируются по целям, достижению которых они служат,
и по проблемам, которых следует избегать в связи с достижением этих целей.
Система учится сразу трем аспектам:
• новым планам,
• свойствам, по которым можно предсказать возникновение про- блем,
• методам коррекции планов, которые должны быть реализованы в случае возникновения проблем в новых обстоятельствах.
Как и другие CBR-системы, CHEF строит новые планы на основе хранящихся в памяти прецедентов. Прежде чем искать подходящий план и модифицировать его, CHEF исследует цели и предсказывает сбои, которые могут возникнуть из-за взаимовлияния планов, которые будут использованы для достижения этих целей. Это предсказание выполняется на основе проблем, которые планировщик встречал в про- шлом. Когда сбой предсказан, CHEF добавляет в начальный список целей цель для избежания этого сбоя в дальнейшем. CHEF умеет не только предсказывать сбои и избегать их, но и корректировать планы в случае, если сбой все-таки возникнет.
CHEF состоит из 6 модулей:
1. Anticipator — предсказывает проблемы, с которыми возможно придется столкнуться при планировании. Предсказание основано на информации о сбоях, возникавших при взаимовлиянии целей,
подобных текущим.

3.6. Планирование на основе прецедентов
147 2. Retriever — ищет в памяти план, который соответствует как мож- но большему количеству текущих целей и содержит минимальное число проблем, предсказанных на предыдущем шаге.
3. Modifier — изменяет найденный план для достижения тех целей,
которые еще не достигаются найденным планом.
4. Repairer — вызывается, если новый план не срабатывает. Он строит причинное объяснение сбоя, корректирует план и передает рабочий план в модуль Storer для индексации и сохранения.
5. Assigner — использует причинное объяснение, построенное мо- дулем Repairer, для выявления характеристик, которые будут в дальнейшем использованы для предсказания сбоев.
6. Storer — сохраняет план в памяти. Выполняет индексацию по целям, которые достигаются планом, и проблемам, которых он избегает.
Вся адаптация выполняется модулями Modifier и Repairer.
Modifier. Чтобы модифицировать план, необходима дополнитель- ная информация. Во-первых, необходима библиотека правил модифи-
кации, специально созданных для различных планов и классов целей.
Такие правила не должны выдавать завершенные планы для достиже- ния какой-либо конкретной цели. Они могут лишь определять моди- фикации, которые необходимы для изменения существующего плана,
чтобы достичь конкретную цель. Правила модификации позволяют модулю добавлять новые шаги в план в зависимости от типа модифи- цируемого плана и конкретной цели, которую следует удовлетворить.
Модуль также нуждается в информации об особенных объектах предметной области, а именно, в информации о том, как Modifier должен использовать специфические свойства этих объектов во время применения обобщенных правил модификации. Эта информация в фор- ме критиков специального назначения позволит системе приспособить обобщенные модификации плана к специфичным требованиям особен- ных объектов предметной области.
И, наконец, Modifier должен знать, что должны делать планы из тех, которые он модифицирует. Это необходимо, чтобы не разрушить достижение глобальных целей плана во время модификаций, целью которых является достижение специфичных целей.
Repairer. Для работы этого модуля требуется специальный словарь
сбоев. Этот словарь индексирует методы ремонта плана. Ключом ин- декса является пара hсбой, причина сбояi. В случае обнаружении сбоя
(после модификации осуществляется имитация выполнения плана для контроля его корректности), исследуется причина сбоя и отыскивается метод коррекции плана, т. е. набор действий, которые модифицируют план таким образом, чтобы устранить этот конкретный сбой.

148
Гл. 3. Методы интеллектуального планирования
Система PRODIGY. Система PRODIGY, разработанная в универ- ситете Карнеги Меллона [80], является одной из наиболее известных систем планирования на основе прецедентов.
Прецедент, частично соответствующий текущей проблеме, является кандидатом на повторное применение. Для ранжирования кандидатов используется метрика подобия. Функциональность модуля, отвечающе- го за повторное использование прецедента, заключается в механизме
«переигрывания», который способен реконструировать решения из пре- цедентов, когда прошлая и новая ситуации соответствуют друг другу лишь частично.
Для адаптации прецедента к текущей проблеме в системе реали- зован вывод на основе прецедентов, оформленный в виде отдельного модуля. Способность использовать предыдущие решения выводом на основе прецедентов предполагает, что решатель (например, генератив- ный планировщик) способен исследовать последовательность им же порождаемую, выделяя обоснования (причины принятия именно такого решения) для каждого решения, выполненного во время поиска в базе прецедентов.
Вывод опирается на планировщик PRODIGY/NoLimit. Это плани- ровщик, работающий в пространстве состояний на основе анализа средств и целей в режиме поиска от цели к исходному состоянию.
Извлечение прецедента выполняется на основе метрики сходства.
Сравниваются цели и начальное состояние. Мера сходства, соответ- ственно, состоит из двух слагаемых. Во-первых, находится расстоя- ние между целями прецедента и новой задачи. Оно вычисляется как количество одинаковых обобщенных (т. е. не замкнутых) дизъюнктов в целях
1
). Второй компонент — расстояние между начальными состо- яниями. При этом нужно учитывать:
• подстановки для приведения новой цели к прецедентной (т. е.
если найдено соответствие по некоторому конъюнкту в цели,
то следует установить соответствие между аргументами этого предиката и учитывать это соответствие в дальнейшем);
• что не все предикаты, характеризующие начальное состояние,
участвуют в решении. Нужно рассматривать только те предика- ты, которые «имеют отношение к делу».
Прецедент представляет собой последовательность решений при движении от цели к начальному состоянию. Выделяются два вида решений:
• текущая цель или подцель;
• оператор, выбранный для удовлетворения цели.
1
) В PRODIGY/NoLimit цель задается коньюнкцией предикатов.

3.6. Планирование на основе прецедентов
149
Существуют и другие виды точек, в которых следует принимать решения. К ним относятся:
• выбор подстановок для конкретизации оператора;
• выбор оператора или продолжение исследования целей;
• продолжение исследования ветви или приостановка исследования или прерывание оного;
• при отсутствии продолжения пути — выбор точки возврата или ветви поиска для продолжения исследования.
Модификация прецедента также начинается от цели. Цели, кото- рым не нашлось аналога в выбранном прецеденте, достигаются методом генерации. К целям, для которых есть аналог в прецеденте, приме- няется метод решения из прецедента — примененный оператор. Если этот оператор в данных условиях применить невозможно, то методом генерации достигаются условия его применимости. Разумеется, все операторы и цели переносятся из прецедента в новое решение с уче- том подстановок (замены аргументов предиката в прецеденте новыми аргументами), выполнявшихся на этапе извлечения прецедента. Таким образом, адаптация в этом случае заключается в генерации недостаю- щих участков плана.

Г л а в а 4
ИНТЕЛЛЕКТУАЛЬНЫЕ ДИНАМИЧЕСКИЕ
СИСТЕМЫ
Введение
Существенная роль при описании поведения многих систем при- надлежит экспертным суждениям и знаниям человека. В частности,
к такому классу принадлежат системы, в которых зависимости на- столько сложны, что не допускают аналитического представления,
а состояния описываются как количественными, так и качественными параметрами. Это заставляет в дополнение к количественным мето- дам или вместо них применять такие подходы, в которых в качестве значений переменных допускаются не только числа, но и слова или предложения искусственного или естественного языка [81], законы же поведения тогда могут быть представлены средствами, которые используются в искуственном интеллекте, например, эмпирическими или экспертными знаниями. Такого рода задачи возникают при иссле- довании поведения ряда сложных систем, в частности, экологических,
социальных, политических, а также некоторых технических систем.
Другой класс систем такого рода — двухуровневые системы управ- ления, потребность в которых назрела в связи с развитием, например,
беспилотных средств транспортного и иного назначения. В частности,
в беспилотных автономных транспортных средствах одним из уровней управления должен являться стратегический (или, как иногда говорят,
делиберативный) уровень управления, решающий задачи, например,
глобального планирования полета или выбора траектории или выбора цели. Следующий уровень управления — назовем его активным —
реализует требуемые действия. Например, на делиберативном уровне управления беспилотным вертолетом принимается решение о зависа- нии над целью, тогда на активном уровне начинает работать математи- ческая модель зависания, вырабатывающая требуемые управления для исполнительных механизмов.
Еще одно применение интеллектуальных динамических систем —
планирование поведения интеллектуальных агентов при некласси- ческих допущениях, в частности, при непрогнозируемом изменении среды.

Введение
151
Рис. 4.1
Рассмотрим простой пример. Пусть решается задача управления движением автомобилей на нерегулируемом перекрестке. Будем по- лагать, что каждый автомобиль снабжен интеллектуальной системой.
Если на пути автомобиля встречается другой автомобиль, движущийся с ним в попутном направлении, то система управления автомобиля должна принять решение либо об обгоне встретившегося автомобиля,
либо о движении вслед за ним. При подъезде к перекрестку система должна убедиться либо в отсутствии помех, либо, при наличии тако- вых, принять решение о действии в соответствии с правилами дорож- ного движения (рис. 4.1). Эти решения принимаются на делибератив- ном уровне с помощью применения систем правил, затем включается в работу активный уровень, где применяются соответствующие модели обгона или поворота. Более подробно пример рассмотрен в приложе- нии 1 в конце главы.

152
Гл. 4. Интеллектуальные динамические системы
В приложении 2 приведен другой пример двухуровневой системы управления, в котором в качестве делиберативного уровня выступает выбор цели, реализуемый с помощью соответствующей системы пра- вил; активный уровень, в свою очередь, расщепляется на два подуров- ня, реализуемых с помощью правил управления и правил переходов.
Из сказанного следует, что динамическая система приведенного вида должна включать множество правил, образующих базу знаний си- стемы, и некоторые функции, заданные подходящим способом. Кроме того, для хранения текущих значений переменных состояния потребу- ется рабочая память, а для управления работой правил — стратегии применения правил.
4.1. Уточнение постановки задачи. Правила
Правила рассмотрены нами в первой главе. Напомним, что прави- лом называется упорядоченная тройка множеств r = hC, A, Di, где C —
условие правила; A — множество добавляемых фактов; D — множество удаляемых фактов.
Каждое из множеств C, A и D будем считать множеством атомар- ных формул языка исчисления предикатов первого порядка. Наиболее существенное отличие от материала первой главы состоит теперь в том,
что в формулах из указанных множеств будет выделяться сорт пере- менной, соответствующей дискретному времени t, т. е. определенной на дискретном упорядоченном множестве, которое мы обозначим через T .
Определение выполнимости условия правила при этом будет несколько модифицировано, а именно, будем говорить, что условие правила выполнено, если в n-м состоянии рабочей памяти истинна каждая из атомарных формул условия, в которой t = n, где n ∈ T [82].
Среди правил будем выделять правила, не соответствующие ника- ким действиям, а лишь пополняющие множество фактов состояния —
их будем называть правилами замыкания, и правила, являющиеся, по существу, некоторыми действиями и поэтому изменяющие состояние системы — их будем называть правилами переходов. В связи с этим за- метим, что в правилах замыкания значения переменной t одни и те же
как в формулах условия, так и в формулах из множеств добавляемых и удаляемых фактов. Что касается правил переходов, то в формулах из множеств удаляемых и добавляемых фактов этих правил значения переменной t, по крайней мере, на единицу больше, чем в формулах условия. Для простоты наше рассмотрение будет ограничено случаем,
когда это различие в точности равно единице.
Таким образом, если П — множество правил, то оно содержит два подмножества [83]:
П
CL
и П
T R
,

4.2. Стратегии применения правил. Состояния и траектория системы 153
где П
CL
— множество правил замыкания состояний, а П
T R
— множе- ство правил переходов; будем обозначать это следующим образом:
П
CL
= hC(t), A(t), D(t)i,
П
T R
= hC(t), A(t + 1), D(t + 1)i.