ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 456
Скачиваний: 22
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Система DerSNLP. Авторы — Laurie H. Ihrig, Subbarao Kambham- pati из университета Аризоны [74].
DerSNLP — это еще один пример системы, основанной на алгорит- ме SNLP и реализующей генеративную адаптацию. В отличие от SPA,
здесь в качестве прецедентов хранятся не конечные планы, а трассы
1
) Имеются в виду узлы, которые будут рассмотрены на следующем шаге обхода вширь.
3.6. Планирование на основе прецедентов
135
вывода решений. Предварительное решение получается при помощи механизма «переигрывания» (replay). Затем это решение адаптируется при помощи стандартного алгоритма SNLP. Фактически, процесс пе- реигрывания (так же, как и в случае SPA) помещает нас в некоторый узел дерева планов, который при благоприятном исходе должен ока- заться ближе к цели, чем корень дерева.
Переигрывание вывода (derivational replay) подразумевает хранение трасс предыдущих решений проблем и повторное применение их для решения подобных проблем. Трасса решения проблемы состоит из по- следовательности инструкций, которые описывают выборы (choices),
сделанные в исходном эпизоде планирования. Например, планировщик,
работающий в пространстве состояний (по алгоритму «анализ средств и целей»), принимает следующие решения: какую подцель удовлетво- рить следующей, какой шаг использовать для достижения подцели и когда добавить подходящий шаг в план.
SNLP принимает два вида решений: достижение подцелей
(establishment) и разрешение угроз причинным связям (threats resolution). Здесь трасса решения аннотируется выборами, которые были сделаны по пути из корня дерева поиска к конечному плану в листовом узле. Каждое решение становится инструкцией для по- следующих процессов поиска. Инструкции содержат высокоуровневые описания принятых решений и условий их применения в будущих контекстах.
Механизм переигрывания функционирует следующим образом. По описанию новой проблемы отыскивается прецедент, содержащий в цели открытое условие, такое же, какое содержится в новой цели (преды- дущая трасса может соответствовать более чем одному открытому условию). В DerSNLP стратегия переигрывания является интенсивной
(eager), т. е. трасса всегда проигрывается до конца. Это позволяет избежать вопросов о том, как чередовать переигрывание множества прецедентов и как чередовать переигрывание с генеративным плани- рованием. Таким образом, последовательно рассматриваются все ин- струкции в трассе.
Процесс переигрывания должен проверить каждую инструкцию,
содержащуюся в трассе, прежде чем переиграть ее в новых условиях.
В зависимости от типа инструкции (достижение или разрешение угро- зы) формируется уточнение плана.
Например, для случая достижения процесс проверки сначала со- поставляет открытое условие инструкции открытому условию в цели.
Условия сопоставляются на основе отображения объектов (mapping),
формируемого во время поиска прецедента. Объекты в старой цели отображаются на соответствующие объекты в новой схожей цели.
Затем выполняется уточнение текущего плана тем же способом, что
136
Гл. 3. Методы интеллектуального планирования
и в инструкции. Для достижения — это порождение нового действия и связи, либо установление связи с существующим действием. Таких действий может быть несколько. Система пытается найти среди них такое, которое соответствует действию, описанному в инструкции.
В интенсивной стратегии переигрывания рассмотрение инструк- ций выполняется последовательно в соответствии с трассой преце- дента. Именно эта последовательность определяет порядок, в котором предусловия (цели) удовлетворяются, а угрозы разрешаются. Решения в трассе, которые невозможно принять в новой ситуации, пропус- каются. В итоге механизм переигрывания порождает план, который включает все предписанные (трассой) уточнения, которые корректны в новом контексте.
План, порожденный переигрыванием, может все еще содержать открытые условия. Это происходит либо потому, что решения (в преце- денте), которые были выбраны для разрешения подцели, не корректны в новом контексте, либо потому, что в новой задаче есть цели, которые покрываются трассой прецедента. Поэтому требуется дальнейшее пла- нирование для достижения этих целей. Начиная с узла, достигнутого процессом переигрывания, выполняется поиск решения по алгоритму
SNLP — адаптация плана.
В противоположность планировщикам, работающим в пространстве состояний, планировщики, работающие в пространстве планов более гибкие. Если дополнительные цели требуют шагов, которые должны быть включены между шагами плана, порожденного переигрыванием эпизода, эти шаги могут быть добавлены после того, как вся трасса будет переиграна. DerSNLP может в дальнейшем уточнить план, кото- рый получился в результате переигрывания трассы.
Это невозможно, если переигрывание выполняется для планиров- щика, работающего в пространстве состояний.
Ниже приведены схематические представления процедур переигры- вания.
PROCEDURE PlanRefinement(GCs, Act): Plans
IF there is an unsafe link in Act THEN
choose t from Act’s unsafe links, and
RETURN HandleUnsafe(t, Act)
ELSE
pick a subgoal o from the list of open conditions
IF GetCase(o, GCs, Act) returns a candidate c, THEN
IF Replay(c, Act) returns a plan, THEN
RETURN plan
ELSE
RETURN HandleOpen(o, Act)
ELSE
3.6. Планирование на основе прецедентов
137
RETURN HandleOpen(o, Act)
PROCEDURE Replay(Instr, Act): Plan
IF null Instr THEN
RETURN Act
ELSE
SelectedRefinement := ValidateInstr(Instr, Act)
IF SelectedRefinement THEN
RETURN Replay(Next(Instr), SelectedRefinement)
ELSE
RETURN Replay(Next(Instr), Act)
PROCEDURE ValidateInstr(Instr, Act): Plan
IF Instr is of type Establishment THEN
IF OpenCondOf(Instr) in OpenCondsOf(Act) THEN
ActRefinements := HandleOpen(OpenCond, Act)
ELSE IF Instr is of type ThreatResolution THEN
IF UnsafeLinkOf(Instr) in UnsafeLinksOf(Act) THEN
ActRefinements := HandleUnsafe(UnsafeLink, Act)
SelectedRefinement
:=
FindMatch(DescisionOf(Instr),
ActRefinements)
IF SelectedRefinement THEN
puhs it siblings onto SearchQueue, and
RETURN SelectedRefinement
ELSE
RETURN FALSE;
Система DIAL. Разработчики системы David B. Leake, A. Kinley и D. C. Wilson из университета Индианы вместо написания соответ- ствующих эвристических функций решили прибегнуть к обучению
[75]. В качестве способа приобретения знаний был выбран CBR-метод моделирования рассуждений, основанных на прецедентах.
Адаптация в этой системе выполняется следующим образом. После того, как план-прецедент
1
) выбран, производится оценка его приме- нимости в новых условиях. Это осуществляется специальным оцени-
вающим компонентом. Цель этой оценки — обнаружение проблем
в плане (прецедент не является готовым решением новой задачи), кото- рые требуют выполнения некоторых преобразований над планом (т. е.
адаптации). Далее включается в работу модуль адаптации. Этот мо- дуль изначально содержит общие домено-независимые адаптационные знания. К ним относятся небольшое количество абстрактных транс-
1
) В данном случае прецедентом является готовый план.
138
Гл. 3. Методы интеллектуального планирования
формационных правил (называемых также правилами адаптации)
1
)
и библиотека простейших методов поиска в памяти (необходимость последних будет объяснена ниже). Правила адаптации индексируются по элементам словаря описания проблем, т. е. по типам проблем.
Например, тип проблемы FILLER-PROBLEM:UNAVAILABLE-FILLER
является индексом для правила трансформации, выполняющего подста- новку объекта в некоторую ролевую позицию (присвоение значения пе- ременной). Столкнувшись с новой проблемой, DIAL сначала извлекает правило трансформации, связанное с типом новой проблемы. Каждая ассоциация между типом проблемы и правилом трансформации имеет связь с информацией о том, как определить (по типу проблемы) части плана, которые должны быть трансформированы. Ассоциация также связана с информацией о том, как найти информацию, необходимую для применения трансформации. Например, для подстановки объекта в ролевую позицию система извлекает из схемы (действия) ограниче- ния на роль, для которой ищется подстановка. Эти ограничения опреде- ляют информацию, которую необходимо найти (свойства объекта, при- годного для подстановки). После определения информации, которую нужно найти, выполняется поиск объекта в памяти с использованием одного из методов, хранимых в библиотеке методов поиска.
Обучение адаптации в этой системе сводится к обучению стра- тегиям поиска в памяти для различных типов проблем. Изначально система не имеет прецедентов поиска в памяти и должна опираться на какой-либо простой метод (например, локальный поиск). Поиск в памяти выполняется до тех пор, пока не будет получен приемлемый результат или пока не будет достигнут барьер, ограничивающий поиск.
Когда DIAL неспособен получить приемлемое адаптационное решение,
то путь к решению указывает пользователь.
Получив успешное адаптационное решение (самостоятельно или при помощи пользователя), система сохраняет трассу шагов, исполь- зованных в процессе поиска в памяти. Вместе с трансформационным правилом эта трасса образует прецедент адаптации, который можно в дальнейшем использовать.
Прецедент адаптации, а точнее, поисковая стратегия, при повторном использовании может и не найти приемлемое решение. В этом случае можно было бы выполнять адаптацию адаптационного примера, но
DIAL не делает этого. Стратегия поиска не изменяется в процессе работы системы. Для улучшения поисковой стратегии она дополняется стратегией локального поиска, суть которой заключается в следующем.
Если стратегия не находит решения, то применяется локальный поиск
1
) Примерами таких правил могут служить: подстановка, добавление шага или удаление.
3.6. Планирование на основе прецедентов
139
в точке, где закончила работу поисковая стратегия. Если и тут ее постигает неудача, то система производит возврат к предыдущей точке,
найденной поисковой стратегией, и снова выполняет локальный поиск.
И так далее, вдоль всего пути, найденного поисковой стратегией.
Система PARIS (Plan Abstraction and Refinement in an Integrated
System) — независимая от предметной области система планирования,
основанная на прецедентах [76]. Повторное использование осуществ- ляется за счет техники абстрагирования и уточнения прецедентов.
В библиотеке прецедентов хранится несколько уровней абстракции плана. Когда решается новая проблема, из библиотеки извлекается прецедент (некоторого уровня абстракции), описание проблемы кото- рого точно совпадает с описанием новой проблемы некоторого уровня абстракции. На последующей фазе найденное абстрактное решение уточняется, т. е. детали, которые не содержатся в абстрактном примере,
добавляются для получения полного решения.
Абстрагирование здесь рассматривается как уменьшение уровня детализации в описании проблемы и в решении. Абстрактный пре- цедент содержит меньше операторов и меньше состояний. Кроме то- го, абстрактные примеры описываются более абстрактными терма- ми. Вообще, на различных уровнях абстракции могут потребоваться различные языки представления. Это означает, что должны иметься дополнительные уровни абстрактных описаний предметной области
(наряду с детальным описанием). Абстрактные описания предметной области, в свою очередь, содержат абстрактные операторы и правила абстрагирования состояний.
Когда решается новая проблема, извлекается наименее абстракт- ный прецедент, который точно соответствует текущей проблеме на уровне абстракции. На следующей фазе абстрактный прецедент дол- жен быть уточнен. Операторы абстрактного прецедента используются для управления планировщиком (в пространстве состояний), который ищет точное решение проблемы. Каждое абстрактное состояние ис- пользуется как подцель. Планировщик берет конкретное начальное состояние из описания новой проблемы и ищет последовательность конкретных операторов, ведущих к конкретному состоянию, которое может быть абстрагировано к первому абстрактному состоянию аб- страктного прецедента. Получившаяся последовательность операторов является уточнением первого абстрактного оператора. Подобным об- разом уточняются остальные абстрактные операторы, т. е. адаптация сводится к уточнению абстрактного плана.
Система PLEXUS. Система основана на описании предметной об- ласти. Основные соображения, лежащие в основе системы таковы [77]:
а) приоритетными считаются наиболее детализированные планы;
140
Гл. 3. Методы интеллектуального планирования
б) всякий шаг в плане рассматривается как пример некоторой кате- гории действий;
в) адаптация опирается на знания о предметной области и состоит в замене шагов на шаги той же категории. Шаг (план) — это действие (или последовательность подшагов и действий).
Идея адаптивного подхода заключается в следующем: содержание и структура знаний, связанных со старым планом, должны быть явными и доступными, чтобы с легкостью использовать их в новом контексте.
Знания о предметной области описываются в виде семантической сети. Сеть отражает 4 вида знаний: таксономические, родовые, кау- зальные и ролевые.
Таксономические (категоризационные) знания отражаются при по- мощи ISA-связей. Эти связи используются для описание иерархических связей между двумя концептами, в частности, для отражения связей класс–элемент и класс–подкласс связей. Движение вверх по ISA-связи удаляет свойства концепта (абстрагирование), а вниз — добавляет свойства (детализация). Таким образом, ISA-иерархия используется не только для наследования свойств, но и для выполнения двух важных функций: абстрагирования и детализации. Некоторые связи помечают- ся либо для обозначения плана по умолчанию, либо для подчеркива- ния, что данный план часто используется в данном контексте.
Знания включают также родовую иерархию.
Каждый план представляется последовательностью пронумерован- ных шагов. В свою очередь, каждый шаг может являться планом, кото- рый, в принципе, может быть разложен на последовательность шагов.
PLEXUS использует родовую структуру для установления фрагмента сети, требующего уточнения в данной ситуации.
Каузальные знания представлены пятью видами связей: назначение,
причина, цель, предусловие и результат. Связь назначения использует- ся для отражения связи между планом (шагом или действием) и наи- более абстрактной версией плана, которая удовлетворяет данному на- значению. Например, назначением действия «покупка билета на поезд»
является «получение доступа к сервису». Связь причины соединяет шаг плана с некоторым последующим шагом этого плана. Связь при- чины показывает, что существует некоторая причинная цепочка между шагами. Например, причиной «покупки билета» является «выход на посадочную платформу». Когда шаг плана проваливается и ищется альтернатива, PLEXUS использует причинную связь для определения последующих шагов, которые будут затронуты новой подстановкой. Та- ким образом, причинные связи отражают зависимости между шагами и используются для определения эффектов (результатов) изменений.
Целевая связь соединяет шаг с целью, достижению которой он слу- жит. Например, целью, ассоциированной с «перемещением», является
DerSNLP — это еще один пример системы, основанной на алгорит- ме SNLP и реализующей генеративную адаптацию. В отличие от SPA,
здесь в качестве прецедентов хранятся не конечные планы, а трассы
1
) Имеются в виду узлы, которые будут рассмотрены на следующем шаге обхода вширь.
3.6. Планирование на основе прецедентов
135
вывода решений. Предварительное решение получается при помощи механизма «переигрывания» (replay). Затем это решение адаптируется при помощи стандартного алгоритма SNLP. Фактически, процесс пе- реигрывания (так же, как и в случае SPA) помещает нас в некоторый узел дерева планов, который при благоприятном исходе должен ока- заться ближе к цели, чем корень дерева.
Переигрывание вывода (derivational replay) подразумевает хранение трасс предыдущих решений проблем и повторное применение их для решения подобных проблем. Трасса решения проблемы состоит из по- следовательности инструкций, которые описывают выборы (choices),
сделанные в исходном эпизоде планирования. Например, планировщик,
работающий в пространстве состояний (по алгоритму «анализ средств и целей»), принимает следующие решения: какую подцель удовлетво- рить следующей, какой шаг использовать для достижения подцели и когда добавить подходящий шаг в план.
SNLP принимает два вида решений: достижение подцелей
(establishment) и разрешение угроз причинным связям (threats resolution). Здесь трасса решения аннотируется выборами, которые были сделаны по пути из корня дерева поиска к конечному плану в листовом узле. Каждое решение становится инструкцией для по- следующих процессов поиска. Инструкции содержат высокоуровневые описания принятых решений и условий их применения в будущих контекстах.
Механизм переигрывания функционирует следующим образом. По описанию новой проблемы отыскивается прецедент, содержащий в цели открытое условие, такое же, какое содержится в новой цели (преды- дущая трасса может соответствовать более чем одному открытому условию). В DerSNLP стратегия переигрывания является интенсивной
(eager), т. е. трасса всегда проигрывается до конца. Это позволяет избежать вопросов о том, как чередовать переигрывание множества прецедентов и как чередовать переигрывание с генеративным плани- рованием. Таким образом, последовательно рассматриваются все ин- струкции в трассе.
Процесс переигрывания должен проверить каждую инструкцию,
содержащуюся в трассе, прежде чем переиграть ее в новых условиях.
В зависимости от типа инструкции (достижение или разрешение угро- зы) формируется уточнение плана.
Например, для случая достижения процесс проверки сначала со- поставляет открытое условие инструкции открытому условию в цели.
Условия сопоставляются на основе отображения объектов (mapping),
формируемого во время поиска прецедента. Объекты в старой цели отображаются на соответствующие объекты в новой схожей цели.
Затем выполняется уточнение текущего плана тем же способом, что
136
Гл. 3. Методы интеллектуального планирования
и в инструкции. Для достижения — это порождение нового действия и связи, либо установление связи с существующим действием. Таких действий может быть несколько. Система пытается найти среди них такое, которое соответствует действию, описанному в инструкции.
В интенсивной стратегии переигрывания рассмотрение инструк- ций выполняется последовательно в соответствии с трассой преце- дента. Именно эта последовательность определяет порядок, в котором предусловия (цели) удовлетворяются, а угрозы разрешаются. Решения в трассе, которые невозможно принять в новой ситуации, пропус- каются. В итоге механизм переигрывания порождает план, который включает все предписанные (трассой) уточнения, которые корректны в новом контексте.
План, порожденный переигрыванием, может все еще содержать открытые условия. Это происходит либо потому, что решения (в преце- денте), которые были выбраны для разрешения подцели, не корректны в новом контексте, либо потому, что в новой задаче есть цели, которые покрываются трассой прецедента. Поэтому требуется дальнейшее пла- нирование для достижения этих целей. Начиная с узла, достигнутого процессом переигрывания, выполняется поиск решения по алгоритму
SNLP — адаптация плана.
В противоположность планировщикам, работающим в пространстве состояний, планировщики, работающие в пространстве планов более гибкие. Если дополнительные цели требуют шагов, которые должны быть включены между шагами плана, порожденного переигрыванием эпизода, эти шаги могут быть добавлены после того, как вся трасса будет переиграна. DerSNLP может в дальнейшем уточнить план, кото- рый получился в результате переигрывания трассы.
Это невозможно, если переигрывание выполняется для планиров- щика, работающего в пространстве состояний.
Ниже приведены схематические представления процедур переигры- вания.
PROCEDURE PlanRefinement(GCs, Act): Plans
IF there is an unsafe link in Act THEN
choose t from Act’s unsafe links, and
RETURN HandleUnsafe(t, Act)
ELSE
pick a subgoal o from the list of open conditions
IF GetCase(o, GCs, Act) returns a candidate c, THEN
IF Replay(c, Act) returns a plan, THEN
RETURN plan
ELSE
RETURN HandleOpen(o, Act)
ELSE
3.6. Планирование на основе прецедентов
137
RETURN HandleOpen(o, Act)
PROCEDURE Replay(Instr, Act): Plan
IF null Instr THEN
RETURN Act
ELSE
SelectedRefinement := ValidateInstr(Instr, Act)
IF SelectedRefinement THEN
RETURN Replay(Next(Instr), SelectedRefinement)
ELSE
RETURN Replay(Next(Instr), Act)
PROCEDURE ValidateInstr(Instr, Act): Plan
IF Instr is of type Establishment THEN
IF OpenCondOf(Instr) in OpenCondsOf(Act) THEN
ActRefinements := HandleOpen(OpenCond, Act)
ELSE IF Instr is of type ThreatResolution THEN
IF UnsafeLinkOf(Instr) in UnsafeLinksOf(Act) THEN
ActRefinements := HandleUnsafe(UnsafeLink, Act)
SelectedRefinement
:=
FindMatch(DescisionOf(Instr),
ActRefinements)
IF SelectedRefinement THEN
puhs it siblings onto SearchQueue, and
RETURN SelectedRefinement
ELSE
RETURN FALSE;
Система DIAL. Разработчики системы David B. Leake, A. Kinley и D. C. Wilson из университета Индианы вместо написания соответ- ствующих эвристических функций решили прибегнуть к обучению
[75]. В качестве способа приобретения знаний был выбран CBR-метод моделирования рассуждений, основанных на прецедентах.
Адаптация в этой системе выполняется следующим образом. После того, как план-прецедент
1
) выбран, производится оценка его приме- нимости в новых условиях. Это осуществляется специальным оцени-
вающим компонентом. Цель этой оценки — обнаружение проблем
в плане (прецедент не является готовым решением новой задачи), кото- рые требуют выполнения некоторых преобразований над планом (т. е.
адаптации). Далее включается в работу модуль адаптации. Этот мо- дуль изначально содержит общие домено-независимые адаптационные знания. К ним относятся небольшое количество абстрактных транс-
1
) В данном случае прецедентом является готовый план.
138
Гл. 3. Методы интеллектуального планирования
формационных правил (называемых также правилами адаптации)
1
)
и библиотека простейших методов поиска в памяти (необходимость последних будет объяснена ниже). Правила адаптации индексируются по элементам словаря описания проблем, т. е. по типам проблем.
Например, тип проблемы FILLER-PROBLEM:UNAVAILABLE-FILLER
является индексом для правила трансформации, выполняющего подста- новку объекта в некоторую ролевую позицию (присвоение значения пе- ременной). Столкнувшись с новой проблемой, DIAL сначала извлекает правило трансформации, связанное с типом новой проблемы. Каждая ассоциация между типом проблемы и правилом трансформации имеет связь с информацией о том, как определить (по типу проблемы) части плана, которые должны быть трансформированы. Ассоциация также связана с информацией о том, как найти информацию, необходимую для применения трансформации. Например, для подстановки объекта в ролевую позицию система извлекает из схемы (действия) ограниче- ния на роль, для которой ищется подстановка. Эти ограничения опреде- ляют информацию, которую необходимо найти (свойства объекта, при- годного для подстановки). После определения информации, которую нужно найти, выполняется поиск объекта в памяти с использованием одного из методов, хранимых в библиотеке методов поиска.
Обучение адаптации в этой системе сводится к обучению стра- тегиям поиска в памяти для различных типов проблем. Изначально система не имеет прецедентов поиска в памяти и должна опираться на какой-либо простой метод (например, локальный поиск). Поиск в памяти выполняется до тех пор, пока не будет получен приемлемый результат или пока не будет достигнут барьер, ограничивающий поиск.
Когда DIAL неспособен получить приемлемое адаптационное решение,
то путь к решению указывает пользователь.
Получив успешное адаптационное решение (самостоятельно или при помощи пользователя), система сохраняет трассу шагов, исполь- зованных в процессе поиска в памяти. Вместе с трансформационным правилом эта трасса образует прецедент адаптации, который можно в дальнейшем использовать.
Прецедент адаптации, а точнее, поисковая стратегия, при повторном использовании может и не найти приемлемое решение. В этом случае можно было бы выполнять адаптацию адаптационного примера, но
DIAL не делает этого. Стратегия поиска не изменяется в процессе работы системы. Для улучшения поисковой стратегии она дополняется стратегией локального поиска, суть которой заключается в следующем.
Если стратегия не находит решения, то применяется локальный поиск
1
) Примерами таких правил могут служить: подстановка, добавление шага или удаление.
3.6. Планирование на основе прецедентов
139
в точке, где закончила работу поисковая стратегия. Если и тут ее постигает неудача, то система производит возврат к предыдущей точке,
найденной поисковой стратегией, и снова выполняет локальный поиск.
И так далее, вдоль всего пути, найденного поисковой стратегией.
Система PARIS (Plan Abstraction and Refinement in an Integrated
System) — независимая от предметной области система планирования,
основанная на прецедентах [76]. Повторное использование осуществ- ляется за счет техники абстрагирования и уточнения прецедентов.
В библиотеке прецедентов хранится несколько уровней абстракции плана. Когда решается новая проблема, из библиотеки извлекается прецедент (некоторого уровня абстракции), описание проблемы кото- рого точно совпадает с описанием новой проблемы некоторого уровня абстракции. На последующей фазе найденное абстрактное решение уточняется, т. е. детали, которые не содержатся в абстрактном примере,
добавляются для получения полного решения.
Абстрагирование здесь рассматривается как уменьшение уровня детализации в описании проблемы и в решении. Абстрактный пре- цедент содержит меньше операторов и меньше состояний. Кроме то- го, абстрактные примеры описываются более абстрактными терма- ми. Вообще, на различных уровнях абстракции могут потребоваться различные языки представления. Это означает, что должны иметься дополнительные уровни абстрактных описаний предметной области
(наряду с детальным описанием). Абстрактные описания предметной области, в свою очередь, содержат абстрактные операторы и правила абстрагирования состояний.
Когда решается новая проблема, извлекается наименее абстракт- ный прецедент, который точно соответствует текущей проблеме на уровне абстракции. На следующей фазе абстрактный прецедент дол- жен быть уточнен. Операторы абстрактного прецедента используются для управления планировщиком (в пространстве состояний), который ищет точное решение проблемы. Каждое абстрактное состояние ис- пользуется как подцель. Планировщик берет конкретное начальное состояние из описания новой проблемы и ищет последовательность конкретных операторов, ведущих к конкретному состоянию, которое может быть абстрагировано к первому абстрактному состоянию аб- страктного прецедента. Получившаяся последовательность операторов является уточнением первого абстрактного оператора. Подобным об- разом уточняются остальные абстрактные операторы, т. е. адаптация сводится к уточнению абстрактного плана.
Система PLEXUS. Система основана на описании предметной об- ласти. Основные соображения, лежащие в основе системы таковы [77]:
а) приоритетными считаются наиболее детализированные планы;
140
Гл. 3. Методы интеллектуального планирования
б) всякий шаг в плане рассматривается как пример некоторой кате- гории действий;
в) адаптация опирается на знания о предметной области и состоит в замене шагов на шаги той же категории. Шаг (план) — это действие (или последовательность подшагов и действий).
Идея адаптивного подхода заключается в следующем: содержание и структура знаний, связанных со старым планом, должны быть явными и доступными, чтобы с легкостью использовать их в новом контексте.
Знания о предметной области описываются в виде семантической сети. Сеть отражает 4 вида знаний: таксономические, родовые, кау- зальные и ролевые.
Таксономические (категоризационные) знания отражаются при по- мощи ISA-связей. Эти связи используются для описание иерархических связей между двумя концептами, в частности, для отражения связей класс–элемент и класс–подкласс связей. Движение вверх по ISA-связи удаляет свойства концепта (абстрагирование), а вниз — добавляет свойства (детализация). Таким образом, ISA-иерархия используется не только для наследования свойств, но и для выполнения двух важных функций: абстрагирования и детализации. Некоторые связи помечают- ся либо для обозначения плана по умолчанию, либо для подчеркива- ния, что данный план часто используется в данном контексте.
Знания включают также родовую иерархию.
Каждый план представляется последовательностью пронумерован- ных шагов. В свою очередь, каждый шаг может являться планом, кото- рый, в принципе, может быть разложен на последовательность шагов.
PLEXUS использует родовую структуру для установления фрагмента сети, требующего уточнения в данной ситуации.
Каузальные знания представлены пятью видами связей: назначение,
причина, цель, предусловие и результат. Связь назначения использует- ся для отражения связи между планом (шагом или действием) и наи- более абстрактной версией плана, которая удовлетворяет данному на- значению. Например, назначением действия «покупка билета на поезд»
является «получение доступа к сервису». Связь причины соединяет шаг плана с некоторым последующим шагом этого плана. Связь при- чины показывает, что существует некоторая причинная цепочка между шагами. Например, причиной «покупки билета» является «выход на посадочную платформу». Когда шаг плана проваливается и ищется альтернатива, PLEXUS использует причинную связь для определения последующих шагов, которые будут затронуты новой подстановкой. Та- ким образом, причинные связи отражают зависимости между шагами и используются для определения эффектов (результатов) изменений.
Целевая связь соединяет шаг с целью, достижению которой он слу- жит. Например, целью, ассоциированной с «перемещением», является