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

128
Гл. 3. Методы интеллектуального планирования
f n
1
, fn
2
∈ mxf , то создать в AL
t+1
узел-действие an → act
и создать ребра — предусловия между an и соответствую- щими узлами fn ∈ F L
t
(b) выявить конфликты mxa на ярусе AL
t+1 4. cоздание следующего яруса фактов F L
t+1
(a) для каждого узла an ∈ AL
t+1
добавить в F L
t+1
узлы-факты,
ассоциированные с фактами из A (act← an) и D (act← an)
и соединить соответствующими ребрами-добавления или ребрами-удаления узлы F L
t+1
и узлы AL
t+1
(b) выявить конфликты mxf на ярусе F L
t+1
ПОИСК ПЛАНА
результат: «цель G разрешима»/«цель G пока не разрешима»
5. если GN ⊆ F L
t
то добавить GN в GS
t i
, где i — номер текущего яруса фактов, t — номер текущей стадии, GN — множество узлов-фактов, ассоциированных с компонентами цели
6. если GS
t i
разрешимо то вернуть «цель G разрешима» иначе
вернуть «цель G пока не разрешима»
РАЗРЕШИМОСТЬ ЦЕЛИ
вход: GS
t i
выход: «GS
t i
разрешимо» / « GS
t i
не разрешимо»
GS
t i
— множество (под)целей на i-ом ярусе фактов
Comb — множество всех комбинаций A
comb действий яруса AL
i−1
таких, что любая пара действий в A
comb не состоит в конфликте mxa ∈ M XA, и при этом A
comb
7. для каждой A
comb
⊆ Comb создать подцель GS
t i−1
, состоящую из предусловий действий в A
comb
8. если
цели
GS
t i−1
разрешимы
то
добавить
тройку hGS
t i−1
, A
comb
, GS
t i
i в Plan и вернуть
«GS
t i
разрешимо»
9. если цели GS
t i
не разрешимы то вернуть «GS
t i
не разрешимо»
Поясним работу алгоритма.
Вначале Graphplan формирует первичный ярус фактов F L
0
На каждой фазе алгритма (переменная t) выполняется:
1) расширение графа планирования P G,
2) поиск плана в графе P G.
На этапе расширения графа P G на основе текущего яруса фак- тов создается новый ярус действий, а затем, на основе нового яруса действий, формируется новый ярус фактов. Во вновь сформированных ярусах выявляются конфликты M XF и M XA (процедура Расширение
Графа Планирования).
Graphplan строит частично-упорядоченный план. Извлечение пла- на осуществляется с помощью техники обратного хода от текущего

3.5. Планирование как задача удовлетворения ограничений
129
яруса к начальному ярусу. Эта техника позволяет более эффективно использовать информацию о конфликтах между действиями и фактами в графе PG.
Опишем эту технику.
Перед поиском плана Graphplan проверяет следующее условие:
«справедливо ли, что GN ⊆ F L
тек
и для каждой пары узлов
gn
1
, gn
2
∈ GN и gn
1
, gn
2
/
∈ mxf , где GN — множество целевых
фактов, ассоциированных с узлами на ярусе
F L
тек
».
Если это так, тогда возможно план существует, и Graphplan приступает к поиску.
Суть поиска плана сводится к тому, чтобы от целевых фактов в текущем ярусе GN ⊆ F L
тек выделить путь, ведущий к ярусу F L
0
В пути не должны содержаться конфликтные действия. На основе выделенного пути формируется план.
Более точно происходит следующее.
Формируется множество GS — хранилище (под)целевых наборов
GS
t i
GS
t i
— множество целей, выбираемые из яруса фактов с номером i,
при поиске плана на стадии t.
Начиная с текущего яруса F L
i
(на первом шаге i = t) в GS
t i
зано- сятся целевые факты GN ⊆ F L
i
. Далее, на ярусе действий с номером
(i − 1) выделяются всевозможные комбинации действий (A
comb
), до- ставляющие GS
t i
(множество Comb). Устанавливается подцель GS
t i−1
,
в которую помещаются предусловия выделенных действий, располо- женные на ярусе фактов F L
i−1
. Для каждой из комбинаций действий
A
comb
⊆ Comb процесс продолжается рекурсивно, до тех пор, пока
GS
t i−1
окажется разрешимой либо не найдется комбинации действий,
доставляющей GS
t i−1
, т. е. Comb = ∅.
Если подцель GS
t i−1
оказывается разрешимой, то при возврате из рекурсии в план Plan помещаются тройки hGS
t i−1
, A
comb
, GS
t i
i, в кото- рой для каждого действия из A
comb известно, какие (под)цели из GS
t i
достигает действие и какие цели из GS
t i−1
необходимо достичь, прежде чем выполнить действие.
Для получения линейного плана необходимо выполнить топологи- ческую сортировку нелинейного плана Plan с учетом целевых ограни- чений GS
t i
Упомянем здесь вкратце еще об одном планировщике, использую- щем для сокращения пространства поиска так называемый механизм абстрагирования [72]. Результатом абстрагирования является «значи- мый контекст рассуждений», т. е. множество конкретизированных дей- ствий, релевантных решаемой задаче.
Для этих целей автором планировщика был разработан специаль- ный язык описания значимого контекста рассуждений. В языке опи-
5 Г. С. Осипов

130
Гл. 3. Методы интеллектуального планирования
сан ряд операций, применимых к специальным базовым множествам,
к множествам действий, кортежей объектов и некоторым другим. Опе- рации над множествами идентичны операциям реляционной алгебры.
Новым множествам, возникающим в результате применения операций,
присваиваются уникальные имена. Для управления порядком выполне- ния операций используются условный оператор, позволяющий прове- рить непустоту полученного множества, и оператор перехода, позволя- ющий явно определить точку продолжения выполнения программы.
Результаты экспериментальной проверки планировщика показали,
что, например в сравнении с планировщиком [60], применение такого подхода дает значительный выигрыш в скорости на задачах с большим количеством объектов, а также в доменах планирования с большим количеством различных действий и целей.
В завершение этой главы кратко рассмотрим методы планирования,
основанные на использовании прецедентной информации.
3.6. Планирование на основе прецедентов
3.6.1. Общая схема метода планирования на основе прецеден-
тов. Планирование на основе прецедентов использует предшествую- щий опыт для решения новых задач. Использование опыта несет в себе двойную выгоду. Во-первых, система планирования становится адап- тивной к предметной области. Такая система может на основе удачных и неудачных попыток планирования пополнять свои знания о предмет- ной области или уточнять их. Это делает возможным применение таких систем в динамических средах. Во-вторых, использование опыта может повысить эффективность планирования, так как для составления новых планов используются фрагменты готовых решений.
Метод работает следующим образом (рис. 3.5). После постановки новой задачи планирования система пытается найти в библиотеке пре- цедентов решение похожей задачи. Под похожестью здесь понимается сходство исходного состояния и целей, хотя в качестве существенных могут выступать и другие параметры, например, ресурсы, время, лег- кость адаптации. При этом система может производить поиск несколь- ких решений и рассматривать их все в дальнейшем или отобрать лишь одно, наиболее похожее решение. Дело здесь обстоит точно так же,
как и при выборе подходящих прецедентов в рассуждениях на основе прецедентов (глава 2).
Следующее действие заключается в модификации выбранного пре- цедента таким образом, чтобы он решал новую задачу. Для этого в прецеденте заменяются цели и начальные условия. После выпол- нения модификации план может оказаться некорректным, т. е. не до- стигающим цели. В этом случае необходимо выполнить адаптацию

3.6. Планирование на основе прецедентов
131
Рис. 3.5
плана. Цель адаптации — приведение плана в корректный вид, т. е.
в вид, доставляющий решение поставленной задачи. Далее выпол- няется проверка полученного решения. Проверка может выполняться различными способами: имитация, выполнение плана в реальной среде или какими-то специальными процедурами ревизии. Так как предпо- лагается, что наши знания о среде неточны, может оказаться, что в результате проверки выявится невыполнимость плана. В этом случае можно выполнить анализ причин невозможности выполнения плана и внести коррективы в описание предметной области. Можно попытаться скорректировать план в соответствии с этими изменениями в описании предметной области и вновь повторить проверку полученного решения.
Эти действия можно выполнять произвольное количество раз.
Последняя фаза — сохранение опыта текущей попытки планирова- ния в библиотеке прецедентов.
Такова общая картина метода планирования на основе прецеден- тов. Поскольку методы поиска подходящих прецедентов рассмотрены во второй главе, остановимся подробнее на процессе модификации и адаптации прецедентов.
3.6.2. Методы адаптации прецедентов. Методы адаптации мож- но классифицировать следующим образом (рис. 3.6).
5*

132
Гл. 3. Методы интеллектуального планирования
Рис. 3.6
Методы удовлетворения ограничений сводятся к связыванию переменных с конкретными объектами новой задачи без изменения структуры плана. В этом случае прецедент должен иметь обобщенный вид, т. е. содержать не конкретные объекты, а переменные. Если же прецедент является конкретизированным (не обобщенным) решением,
то выполняется не связывание, а замена старых объектов на новые.
Новые объекты должны удовлетворять множеству ограничений, на- лагаемых прецедентом. В качестве такого ограничения может, напри- мер, выступать тип объекта.
Если для адаптации применять только этот метод, то невозможна структурная трансформация прецедентов. Следовательно, прецедент должен содержать решение аналогичной задачи, но оперирующей дру- гими объектами, что, в свою очередь, может потребовать наличия большой базы прецедентов. Поэтому может оказаться целесообразным использовать этот метод совместно с каким-либо другим методом,
который будет выполнять трансформации структуры плана.
Генеративная адаптация предполагает удовлетворение еще недо- стигнутых целей методом, аналогичным порождению плана. Каждая из неудовлетворенных целей достигается путем поиска либо в простран- стве планов, либо в пространстве состояний.
Этот метод удобно использовать совместно с другими видами адап- тации. Когда другой метод не может справиться с порождением необхо- димой части плана, то для этой цели применяется какой-либо алгоритм классического планирования.
Разделение и слияние для каждой неудовлетворенной цели выпол- няет поиск решения независимо. Затем полученные решения объеди- няются в единое решение задачи. Такая декомпозиция может повысить эффективность, если есть легкий способ выполнения слияния. Для

3.6. Планирование на основе прецедентов
133
поиска окончательного решения (слияния) может применяться любой метод (генерация, CBR).
Рекурсивная адаптация основывается на применении планиро- вания по прецедентам для каждой из неудовлетворенных подцелей.
Найденное решение некоторой подцели может породить множество от- крытых подцелей, которые достигаются тем же методом. В общем виде метод достаточно сложен, так как приходится выполнять объединение решений: текущего решения задачи и способа разрешения очередной подцели.
Адаптация по прецедентам заключается в применении методоло- гии CBR к случаям адаптации. Иначе говоря, система пополняет биб- лиотеку адаптаций и затем пользуется этим опытом для выполнения новых адаптаций.
Эвристические методы адаптации используют применение мно- жества эвристических правил преобразования плана. По своей сути эти преобразования сводятся к набору правил, определяющих изменения плана в зависимости от контекста.
Ниже приводится обзор нескольких наиболее известных систем планирования, основанного на прецедентах. В каждой из рассматрива- емых систем особое внимание уделено используемым методам адапта- ции.
3.6.3. Некоторые системы планирования, основанного на пре-
цедентах.
Система SPA. Авторы системы Steve Hanks и Daniel S. Weld из университета Джорджа Вашингтона [73].
Система является примером планировщика с генеративной адапта- цией. Здесь процесс адаптации плана, по сути, является расширением процесса генерации.
Для генерации частичных планов используется методология плани- ровщика SNLP [50], суть которой заключается в следующем. Берется пустой план (есть только шаги Start и Finish, представляющие собой постановку задачи) и строится дерево всех возможных уточнений этого плана. Каждое уточнение преследует цель удовлетворения очередной подцели каким-либо способом. Образуемое таким образом дерево со- держит нулевой план в своем корне и частичные (возможно, финаль- ные) планы в прочих узлах (рис. 3.7). Построение дерева выполняется обходом «сначала вширь». Обход продолжается до тех пор, пока не будет найдено решение задачи.
В системе SPA прецедент представляет собой окончательное (не аб- страктное) решение некоторой проблемы, которое является узлом дере- ва всех возможных планов. Таким образом, использование прецедента

134
Гл. 3. Методы интеллектуального планирования
Рис. 3.7
позволяет начать поиск решения не с корня дерева (нулевого плана),
а некоторого его узла, который может находиться ближе к решению,
чем нулевой план. При этом модуль адаптации может переходить по узлам не только вниз, но и вверх (в сторону более короткого плана).
Обход также выполняется в ширину. Начальная стратегия
1
) обхода определяется множеством связей с узлом, соответствующим прецеден- ту. Графически схему поиска можно представить следующим образом
(рис. 3.8).
Рис. 3.8
Система обладает корректностью и полнотой, так как выполняется полный обход. Но так как обход начинается не с нулевого плана,
а с некоторого узла, который предположительно близок к решению, то эффективность поиска выше, чем у SNLP планировщика.