ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 449
Скачиваний: 22
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
2.4. Рассуждения на основе прецедентов
105
Перейдем к более детальному рассмотрению механизмов адаптации.
Ввиду того, что подстановочная адаптация достаточно проста, основное внимание сосредоточим на трансформационной адаптации, имея ввиду,
что подстановочная адаптация может рассматриваться как ее частный случай.
Рассмотрим вначале так называемые операторы адаптации.
Выделяются два класса операторов адаптации: первый — для про- стых атрибутов и второй — для сложных. Здесь будет рассмотрен случай для простых атрибутов.
Определение 2.4.4. Оператор адаптации для простых атрибу-
тов SAO есть следующая пятерка слотов:
SAO = hАТРИБУТ, СТАРОЕ ЗНАЧЕНИЕ, ДЕЙСТВИЯ,
ИСПОЛЬЗОВАННЫЕ ЗНАЧЕНИЯ, ЗАВИСИМОСТИi,
где
АТРИБУТ — атрибут, к которому применим оператор SAO;
СТАРОЕ ЗНАЧЕНИЕ — значение атрибута АТРИБУТ, которое опе- ратор выбрал из описания области значений атрибута. Это зна- чение запоминается оператором, если был применен бэктрекинг
(возврат к точке ветвления);
ДЕЙСТВИЯ — множество действий, которые были использованы для изменения значений атрибута АТРИБУТ. Если выполняется бэктрекинг, оператор использует это множество для определения действий, которые еще не были применены;
ИСПОЛЬЗОВАННЫЕ ЗНАЧЕНИЯ — множество значений, которые уже испытывались;
ЗАВИСИМОСТИ — множество иных операторов, которые могут быть применены, после того, как SAO изменит значение атрибута
АТРИБУТ.
Если выполняется бэктрекинг некоторого оператора, старое значе- ние атрибута запоминается в слоте СТАРОЕ ЗНАЧЕНИЕ. Далее по- средством исключения использованных действий, сохраненных в слоте
ДЕЙСТВИЯ, определяется следующее возможное действие, которое выполняется. Повторное использование значений атрибутов исключает- ся, благодаря их запоминанию в слоте ИСПОЛЬЗОВАННЫЕ ЗНАЧЕ-
НИЯ. Предполагается также, что в хорошо определенных предметных областях множество допустимых значений атрибутов не очень велико.
Это может достигаться, в частности, определением ограничений или использованием зависимостей на множествах атрибутов.
Применение оператора адаптации для простых атрибутов приводит к выполнению так называемых простых адаптационных действий для получения нового значения атрибута.
106
Гл. 2. Методы автоматизации рассуждений
Определение 2.4.5. Простое адаптационное действие SAA есть функция, которая возвращает новое значение атрибута, текущее ре- шение, запрос, найденный прецедент и, опционально, список значений атрибутов, которые нельзя рассматривать как результаты.
К простым адаптационным действиям относятся:
1. ВЫЧИСЛЕНИЕ. Это действие соответствует случаю, когда име- ется функциональная зависимость на множестве атрибутов, поз- воляющая по значению данного атрибута единственным образом вычислить значение другого атрибута.
2. МОДИФИКАЦИЯ. Если существует функциональная зависи- мость между изменениями (приращениями значений атрибутов)
атрибутов прецедентов и текущим атрибутом, то значения атри- бутов подходящих прецедентов используются для построения ап- проксимирующей функции, которая используется для вычисления значений искомых атрибутов запроса.
3. КОПИРОВАНИЕ. Это действие состоит в копировании наиболее подходящих значений из атрибутов найденных прецедентов. Для правильного выбора атрибутов система должна обладать соответ- ствующими знаниями о предметной области.
4. УМОЛЧАНИЕ. Это действие состоит в вычислении значений,
удовлетворяющих имеющимся ограничениям.
5. ВОПРОС. Обращение к пользователю с вопросом о значениях атрибутов, которые удовлетворяют ограничениям. Заметим, что этот оператор не является необходимым, если имеется полное описание предметной области.
В самом общем виде алгоритм адаптации выглядит следующим образом:
Шаг 1. Запомнить текущее значение атрибута в слоте старых значе- ний.
Шаг 2. Выбрать подходящее действие. Запомнить его в слоте ДЕЙ-
СТВИЯ.
Шаг 3. Выполнить действие; если оно возвращает значение атрибута,
не удовлетворяющее ограничениям, то добавить действие в слот
ДЕЙСТВИЯ, а возвращенное значение атрибута — в слот ИС-
ПОЛЬЗОВАННЫЕ ЗНАЧЕНИЯ; выбрать новое значение атри- бута. Если значение атрибута удовлетворяет ограничениям, то —
завершение алгоритма; возвращается найденное значение.
Шаг 4. Если не существует значения атрибута, удовлетворяющего ограничениям, выполнить бэктрекинг и выбрать другое действие.
Перейти к шагу 3.
Г л а в а 3
МЕТОДЫ ИНТЕЛЛЕКТУАЛЬНОГО
ПЛАНИРОВАНИЯ
Введение
Методы интеллектуального планирования с каждым днем привле- кают все большее внимание в связи с возрастающим числом примене- ний во многих областях. В большинстве случаев приложения методов интеллектуального планирования требуют интеграции не только соб- ственно методов планирования, но и методов удовлетворения ограниче- ний, темпоральных рассуждений, представления знаний, формальных языков и моделей и решения сложных технологических задач. Сегодня известно о многих успешных приложениях методов интеллектуального планирования — от промышленного производства до электронного пла- нирования туров и решения проблем окружающей среды, от дистанци- онного обучения до космических исследований. В настоящей главе мы предполагаем рассмотреть основные методы интеллектуального плани- рования (или AI — планирования, как принято иногда говорить), среди которых — планирование в пространстве состояний, планирование в пространстве планов, применение в планировании техники прямого распространения ограничений и планирование на основе прецедентов.
В задаче планирования выделяются две основные составляющие —
среда и агент:
1) Среда. Для построения плана и управления его выполнением необходимо построить формальное описание среды. Основные способы,
используемые для описания среды, базируются на таких методах пред- ставления знаний, как продукционные системы, логические методы,
семантические сети, фреймовые структуры.
2) Агент — аппаратная или программная система, обладающая следующими свойствами:
• автономность — способность работать без внешнего управляюще- го воздействия;
• реактивность — возможность воспринимать среду, реагировать на ее изменения;
108
Гл. 3. Методы интеллектуального планирования
• активность — способность ставить цели и инициативно действо- вать для достижения поставленной цели;
• коммуникативность — способность взаимодействовать с другими агентами (или людьми).
План — последовательность действий, формируемая агентом на ос- нове общих целей, информации о текущем состоянии среды и динамике ее изменения.
Сложность задачи синтеза плана зависит от множества свойств среды и агента, в том числе:
(1) от причин изменений среды — только лишь в результате действий агента или вне зависимости от них;
(2) от наличия информации о состоянии среды — известно оно пол- ностью или частично;
(3) достаточно ли имеющихся у агента датчиков для того, чтобы получить информацию о состоянии среды;
(4) оказывают ли действия агента детерминированное или же стоха- стическое воздействие на состояние среды.
Планировщик имеет дело с первым случаем планирования, когда изменения в среде возникают лишь в результате действий агента,
каждое состояние среды полностью известно, а агент производит де- терминированное воздействие на состояние среды. Синтез плана для этих условий называется задачей планирования при классических до- пущениях. При неклассических допущениях, т. е. в случаях, когда изменения среды непрогнозируемы, говорят о динамическом планиро- вании, если же состояние среды известно не полностью или воздей- ствия агента носят стохастический характер, говорят о стохастическом планировании.
Трудность разработки эффективного алгоритма планирования объ- ясняется вычислительной сложностью задачи планирования, которая относится к классу PSPAСE-полных задач [38, 39]. Задачи планиро- вания при неклассических допущениях более адекватны задачам ре- ального уровня сложности [40], однако следует понимать, что рабо- ты в области планирования при классических допущениях не только способствуют пониманию проблем планирования с неклассическими допущениями, но и лежат в основе последних. В настоящей главе будут рассмотрены методы планирования при классических допущениях. Ос- новы планирования при неклассических допущениях рассматриваются в следующей главе.
Рассмотрим вначале хронологию методов интеллектуального плани- рования. При описании хронологии методов интеллектуального плани- рования, методов планирования в пространстве состояний и простран- стве планов использованы материалы из работы [68].
3.1. Хронология методов интеллектуального планирования
109
1 ... 8 9 10 11 12 13 14 15 ... 33
3.1. Хронология методов интеллектуального
планирования
Начало исследованиям в области интеллектуального планирования положено работами, в которых планирование рассматривалось как до- казательство теорем [42].
Системам на основе доказательства теорем был присущ ряд недо- статков. Наиболее существенными из них являлись: 1) крайне низкая производительность, 2) существование так называемой проблемы фрей- ма [45].
Эти недостатки привели к созданию подходов, основанных на поис- ке в пространстве состояний [44, 45].
Алгоритмы, основанные на поиске в пространстве состояний,
в некоторых случаях оказались негибкими и в новом поколении ме- тодов задача планирования была сформулирована как задача поиска в пространстве частично упорядоченных планов [46–48].
Одновременно с развитием идеи частичных планов развивалась идея иерархического планирования [49, 50], которое подразумевает со- здание планировщиком иерархии абстракций (подцелей). Этот подход упрощает процедуру планирования: в начале создается план в общих чертах, затем выполняется детализация — спуск по иерархии. Таким образом, появляется возможность сосредоточить вычислительные мощ- ности на решении первостепенных задач. Иерархическое планирование также интересно тем, что лишь на основе этого подхода создано большинство реально работающих систем [51, 52].
В начале 90-х годов в связи с появлением высокопроизводительных алгоритмов решения задачи удовлетворения ограничений (CSP-задача)
и задачи проверки истинности в пропозициональной логике (SAT-зада- ча), стали популярными постановки задачи планирования как CSP- задачи и как SAT-задачи [39, 54]. Это позволило значительно повысить скорость синтеза планов. Одновременно с этим появились работы,
в которых задача планирования рассматривалась как задача целочис- ленного линейного программирования (ILP-задача) [55] или как задача построения бинарных диаграмм решений (BDD-задача) [56].
Начиная с 1998 г. стали появляться первые планировщики, исполь- зующие эвристики для поиска плана. Конечно же, использование эври- стик для решения задач не является свежей идеей. Однако их привле- чение к решению задач планирования было инициировано появлением механизмов автоматизированного извлечения эвристик из описания домена планирования. В значительной степени этому способствовало выделение некоторых свойств структур, используемых алгоритмами
Graphplan и Satplan [57–60].
110
Гл. 3. Методы интеллектуального планирования
В таблице 3.1 представлена хронология подходов к решению задачи интеллектуального планирования при классических допущениях.
Т а б л и ц а 3.1. Хронология методов классического планирования
1960 Планирование как доказательство теорем (GPS 1963, QA3 1969)
1970 Планирование как поиск в пространстве состояний (STRIPS 1971,
PRODIGY 1987, Warplan 1975)
1980 Планирование как поиск в пространстве планов (InterPlan 1975,
Tweak 1987, SNLP 1991, UCPOP 1992)
1990 Иерархическое планирование (NOAH 1975, NONLIN 1977, SOPE
1985, O-Plan 1986)
Планирование как задача удовлетворения ограничений: выполни- мости пропозициональных формул (Graphplan 1995, SATPlan 1996)
2000 Эвристическое планирование (HSP 1998, FF 2000, LPG 3002)
Далее подробнее рассмотрим некоторые подходы к решению задачи планирования при классических допущениях.
3.2. Планирование как поиск доказательства теорем
Одним из примеров применения методов доказательства теорем для решения задачи планирования является система QA3 [63].
В системе QA3 одно множество утверждений используется для описания начального состояния, а другое — для описания эффектов действий. Чтобы следить за тем, какие факты являются истинными в текущем состоянии, в каждый предикат включаются выделенные переменные состояния. Целевое условие описывается формулой с пе- ременной, связанной квантором существования.
Задача системы состоит в том, чтобы доказать существование со- стояния, в котором истинно целевое условие. В основе доказательства лежит метод резолюций. К сожалению, система QA3 продемонстриро- вала низкую вычислительную эффективность.
Выше упоминалось о так называемой проблеме фрейма. Суть ее состоит в том, что действие может иметь нелокальный эффект; ина- че говоря, неясно, какие формулы, описывающие состояние системы,
изменяются при применении действия. Это приводит к тому, что в опи- сание действия включаются утверждения об изменении (не изменении)
каждого факта, представленного в состоянии. Очевидно, что в слож- ных предметных областях описание эффектов действий значительно усложняется. Оказалось, что при подходе, основанном на доказатель- стве теорем как методе планирования, не существовует сколько-нибудь приемлемого решения проблемы фрейма.
3.3. Планирование в пространстве состояний
111
3.3. Планирование в пространстве состояний
Первым планировщиком, осуществляющим планирование в про- странстве состояний, являлся STRIPS (STanford Research Institute
Problem Solver) [42, 64], который предполагалось применить для ре- шения задачи формирования плана поведения робота, перемещающего предметы через множество помещений.
Собственно, идея алгоритма STRIPS заимствована из системы
GPS [65]. Метод, использованный в GPS, назывался анализ средств и целей (means-ends analysis). Он подразумевает рассмотрение в теку- щем состоянии только тех действий, которые имеют отношение к цели.
Однако при таком подходе возникает следующая проблема: применять ли действия, связанные с целью, немедленно, как только они найдены,
или же приостановить применение действия до тех пор, пока не будут найдены все действия, имеющие отношение к цели? STRIPS применяет действия не откладывая, достигая каждой цели по отдельности.
Мак-Дермотт [46] показал, что эффективность планирования с ис- пользованием метода анализа средств и целей может быть намного повышена задержкой применения действия до тех пор, пока не будут найдены все релевантные (относящиеся к цели действия) и повторе- нием поиска релевантных действий заново, после каждого применения действия.
Для решения проблемы фрейма STRIPS предлагает в состоянии,
к которому применяется правило (действие), изменять выполнимость лишь тех формул, которые описаны в эффекте действия, а выполни- мость всех остальных оставлять неизменной.
Рассмотрим постановку задачи планирования при классических до- пущениях в терминах STRIPS.
3.3.1. Постановка задачи STRIPS-планирования. Как и выше,
фактом будем называть замкнутую атомарную формулу языка исчис- ления предикатов 1-го порядка (ИПП), а состоянием — некоторое мно- жество фактов. Говоря неформально, состояние представляет модель среды, в которой действует интеллектуальный агент.
Приведем пример описания состояния s среды в терминах STRIPS:
s = {ATR(a), AT(B, b), AT(C, c), ∀u∀x ∀y((AT(u, x) ∧ (x 6= y)) →
→ ¬AT(u, y))}.
Здесь ATR(a) означает, что «робот находится в комнате a», AT(B, b) —
«ящик B находится в комнате b», AT(C, c) — «ящик C находится в комнате c». Имена конкретных объектов из этого множества: a, b,
c — соответственно комната a, комната b, комната c; A, B, C —
соответственно, ящик A, ящик B, ящик C.