ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 517
Скачиваний: 23
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
3.4. Поиск в пространстве планов
121
Определение 3.4.7. Топологическая сортировка нелинейного
плана является решением, если применение последовательности правил из шагов между шагами START и FINISH из начального состояния, которое задается списком добавлений шага START,
приводит в состояние, в котором содержатся все предусловия шага
FINISH.
Теорема 3.4.1. Любая топологическая сортировка нелинейного
плана, обладающего полнотой, является решением задачи планиро-
вания
T .
Определение 3.4.8. Нелинейный план является противоречивым,
если на нем невозможно осуществить топологическую сортировку.
Таким образом, противоречивый нелинейный план не является ре- шением задачи планирования.
Алгоритм называется систематичным тогда, когда в процессе поис- ка, осуществляемого в пространстве частично-упорядоченных планов,
один и тот же план или эквивалентные планы никогда не рассматри- ваются дважды.
Теорема 3.4.2. Алгоритм SNLP систематичен.
Опишем алгоритм SNLP.
3.4.2. Алгоритм SNLP.
вход: ΣR, Plan
выход: Plan
результат: «план построен»/«план не построен»
1. если Plan противоречив то вернуть Plan = ∅, «план не постро- ен»
2. если Plan обладает полнотой то вернуть Plan, «план построен»
3. если в Plan’е имеется шаг-угроза V для причинной связи hS, f , W i и Plan не содержит защитного ограничения V < S или
V > W , то
недетерминированно выполнить:
либо (a) SNLP (Plan + (V < S))
либо (b) SNLP (Plan + (V > W ))
4. если существует некоторый шаг W с предусловием f, для кото- рого не существует причинной связи hS, f, W i, то
недетермированно выполнить:
либо (a) выбрать некоторый шаг S, добавляющий f и вы-
полнить SNLP (Plan + hS, f, W i)
либо (b) выбрать правило R ∈ ΣR, добавляющее f, и со-
здать новый шаг S, ассоциированный с выбранным прави- лом R и выполнить SNLP (Plan + hS, f, W i).
122
Гл. 3. Методы интеллектуального планирования
Таким образом, на вход алгоритма подается множество правил ΣR,
а также нелинейный план Plan, не обладающий полнотой, который содержит шаги START и FINISH. Далее Plan уточняется путем до- бавления причинных связей и защитных ограничений до тех пор, пока не обнаружится такое уточнение, что план либо противоречив, либо обладает полнотой.
Для случая абстрактного планирования приведенная процедура мо- жет быть расширена следующим образом. Необходимо создать иерар- хию утверждений, которая будет отражать трудность достижения тех или иных условий. Для этого каждому утверждению сопоставляется некоторое число, характеризующее его иерархический уровень. Малые числа могут указывать на низкий уровень иерархичности, большие числа — на высокий уровень иерархичности. Для того чтобы про- цедура удовлетворяла предусловия, спускаясь с вершины иерархии утверждений, в процедуре SNLP на шаге 3 и 4 можно осуществлять выполнение пунктов a) и b) не произвольным образом, а с учетом более иерархичного предусловия f, вовлеченного в причинную связь.
3.4.3. Принцип малой связности. Очень часто нелинейные пла- нировщики называют планировщиками, обладающими малой связно-
стью (least commitment).
Частичная подстановка — один из примеров малой связности. Так,
при поиске плана можно начать с анализа последствий более кон- кретного действия, например, MOVE (A, B), а можно выбрать менее связывающее действие, например, MOVE (A, x), где x — некоторая переменная, вместо которой можно подставить любой объект. Нелиней- ность — еще один пример малой связности, например, можно выбрать действие Put (A, x) в качестве первого шага плана, с другой стороны,
мы можем предположить что Put (A, x) появляется где-то в середине плана без точного указания места.
Однако принцип малой связности не гарантирует нелинейным пла- нировщикам значительного превосходства над линейными.
3.5. Планирование как задача удовлетворения
ограничений
3.5.1. Постановка задачи удовлетворения ограничений. Мно- гие задачи в ИИ и в других областях информатики могут быть рас- смотрены как задачи удовлетворения ограничений (CSP-задачи), для которых существует множество высокопроизводительных алгоритмов.
В связи с этим, формулировка задачи планирования, как задачи удо- влетворения ограничений, приобрела определенную популярность [67].
CSP-задача предъявляет требования к значениям переменных в форме ограничений. Множество возможных значений переменных
3.5. Планирование как задача удовлетворения ограничений
123
конечно и называется доменом. Ограничения указывают, какие кор- тежи значений допустимы для определенного множества переменных.
Ограничение может быть задано явно путем перечисления допустимых кортежей или неявно в форме алгебраического выражения. Решением
CSP-задачи является такая подстановка значений переменных, при которой удовлетворяются все ограничения.
Определение 3.6.1. Задача удовлетворения ограничений — это тройка hV , D, Ci, где:
(1) V = {v
1
, ... , v n
} — множество переменных;
(2) D = {D
1
, ... , D
n
} — множество доменов. Каждый домен D
i
—
конечное множество, содержащее возможные значения, соответ- ствующей переменной;
3) C = {C
1
, ... , C
n
} — множество ограничений. Ограничение C —
отношение, определенное на подмножестве значений всех пере- менных, т. е. D
1
× ... × D
n
⊇ C
i
Заданное (частичное или полное) «означивание» переменных удо- влетворяет ограничению C
i
, если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит C
i
Множество всевозможных означиваний всех переменных является про- странством, содержащим решение CSP-задачи.
Решением CSP-задачи является такое означивание всех перемен- ных, при котором все ограничения удовлетворены. Если для некоторой задачи имеется, по крайней мере, одно решение, то задача является
разрешимой, иначе — неразрешимой, или же противоречивой, или же переограниченной.
В некоторых случаях необходимо получить все решения. Ино- гда может быть сформулирована задача ограниченной оптимизации,
а именно: найти такое решение, в котором значения переменных опти- мизировали бы некоторый заданный функционал. Иногда необходимо просто выяснить, разрешима ли задача. В любом случае CSP-задача принадлежит классу NP-полных задач.
3.5.2. Синтез планов на основе техники прямого распростра-
нения ограничений. В этом разделе рассмотрим алгоритм планиро- вания — Graphplan, который использует технику прямого распростра- нения ограничений [71].
В свое время Graphplan продемонстрировал хорошие результа- ты для ряда тестовых задач классического планирования. Создате- ли Graphplan’а Блюм и Фест объясняют этот успех способностью
Graphplan’а анализировать множество альтернативных планов одновре- менно.
Однако, как показал Камбхампати [74], производительность
Graphplan’а объясняется тем, что он обрабатывает компоненты мно-
124
Гл. 3. Методы интеллектуального планирования
жества планов без разделения, используя уточнения дизъюнктивных планов.
Graphplan принимает на вход стандартное STRIPS-описание зада- чи планирования и переводит это описание в компактную структуру,
называемую графом планирования, из которой впоследствии извлекает частично-упорядоченный план. Важно отметить, что граф планирова- ния — это не граф состояний, который получается при работе плани- ровщика в пространстве состояний.
Graphplan сочетает в себе свойства как планировщика в простран- стве состояний, так и планировщика в пространстве планов и не об- ладает свойством малого связывания. Приведем определения основных понятий планировщика.
Определение 3.5.1. Факты F — множество элементарных формул без переменных из домена планирования P .
Перед основной стадией работы Graphplan создает множество дей- ствий, осуществляя для каждого правила R ∈ ΣR всевозможные ва- рианты подстановки индивидов на места всех переменных. Имеется также специальный вид действия «no-op» — «ничего не делать».
Определение 3.5.2. Действия Acts — множество полностью кон- кретизированных правил из ΣR, а также действие «no-op».
Действие «no-op» имеет условие C(«no-op») = f, список добавлений
A(«no-op») = f и пустой список удалений D(«no-op») = ∅, где f —
произвольный факт из F .
Определение 3.5.3. Граф планирования P G — ориентированный ярусный граф с двумя типами узлов и с тремя типами ребер.
Два типа узлов в P G таковы:
1) F N — множество узлов, ассоциированных с фактами F , и
2) AN — множество узлов, ассоциированных с действиями Acts.
Ассоциацию некоторого факта f ∈ F с узлом fn ∈ P G будем обозначать как fn → f.
Ассоциацию некоторого действия act ∈ Acts с узлом an ∈ AN ⊂ P G
будем обозначать как an → act.
Множество узлов P G разбито на непересекающиеся подмноже- ства hF L
0
, AL
0
, F L
1
, AL
1
, ...AL
n−1
, F L
n i, где F L — ярус, содержащий узлы-факты, AL — ярус, содержащий узлы-действия, F L
0
содержит узлы-факты, соответствующие фактам S
0
Любой ярус AL
i
⊂ P G содержит узлы-действия an → act, такие что
Nodes(C(act← an)) ∈ F L
i и не существует fn
1
, fn
2
∈ Nodes(C(act←
← an)) и hf n
1
, fn
2
i ∈ M XF , где Nodes(C(act← an)) — узлы на ярусе
F L
i
, ассоциированные с фактами из предусловия C(act).
3.5. Планирование как задача удовлетворения ограничений
125
Любой ярус фактов F L
i
⊂ P G (i > 0) содержит узлы-факты f n → f такие, что для любого an ∈ AL
i−1
⊂ P G справедливо (f ∈ D(act← an)
ИЛИ f ∈ A(act← an)).
Три типа ребер PG таковы:
1) ребро-предусловие — устанавливается между узлом-фактом fn →
→ f на некотором ярусе F L
i и узлом-действием an →act на ярусе
AL
i
, если факт f ∈ C(act);
2) ребро-добавление — устанавливается между узлом-действием an →act на некотором ярусе AL
i и узлом-фактом fn → f на ярусе
F L
i+1
, если f ∈ A(act);
3) ребро-удаление — устанавливается между узлом-действием an →
→act на некотором ярусе AL
i и узлом-фактом fn → f на ярусе
F L
i+1
, если f ∈ D(act).
Из определения видно, что ярусы P G чередуются так:
(я ф | я д ), (я ф | я д ) и т. д.,
где (я ф | я д ) — (ярус фактов | ярус действий).
Первый ярус графа содержит факты, характеризующие начальное состояние. Ярусы в P G содержат: факты, истинные в момент време- ни 1; действия, возможные в момент времени 1; факты, возможные в момент времени 2; действия, возможные в момент времени 2; факты,
возможные в момент времени 3; действия, возможные в момент време- ни 3; и т. д.
По сути, граф планирования P G позволяет представлять простран- ство альтернативных состояний. Точнее, множество состояний, напри- мер на ярусе F L
j+1
, возникает в результате всевозможных альтер- нативных вариантов применения действий, расположенных в ярусах с AL
i по AL
j
(i < j), к некоторому состоянию s, представленному на ярусе фактов F L
i
. Однако ясно, что альтернативная перестанов- ка k действий может привести к тому, что одно из действий мо- жет удалять эффект, либо условие другого действия. Для обработки подобных ситуаций используются так называемые конфликты между действиями и конфликты между фактами. Это позволяет при необхо- димости, например, на этапе извлечения плана, выделить из графа P G
альтернативные компоненты пространства состояний.
Планировщики, использующие такой способ представления про- странства состояний, получили название дизъюнктивных планиров-
щиков.
Дадим теперь определение понятию конфликт, следуя [70].
Конфликт — это отношение взаимоисключения между двумя уз- лами на одном ярусе. Существуют конфликты между действиями и между фактами.
126
Гл. 3. Методы интеллектуального планирования
1 ... 10 11 12 13 14 15 16 17 ... 33
Определение 3.5.4. Конфликты MXF — отношения взаимоис- ключения между узлами-фактами hfn
1
, fn
2
i, где f n
1
, fn
2
— узлы-фак- ты, находящиеся на одном ярусе, такие, что:
либо
1) все действия на предыдущем ярусе, добавляющие факт fn
1
, уда- ляют факт fn
2
;
либо
2) все действия на предыдущем ярусе, добавляющие факт fn
2
, уда- ляют факт fn
1
Определение 3.5.5. Конфликты MXA — отношения взаимоис- ключения между узлами-действиями han
1
, an
2
i, где an
1
, an
2
— узлы- действия, находящиеся на одном ярусе такие, что:
1) действие an
1
удаляет условие или же эффект действия an
2
, либо
2) предусловие действия an
1
и предусловие действия an
2
состоят в конфликте mxf ∈ M XF .
Заметим, что конфликт между парой узлов n
1
и n
2
может иметь место на некотором ярусе L и не иметь места на некотором последую- щем ярусе L
′
. С другой стороны, если между парой узлов n
1
и n
2
на некотором ярусе L не существует конфликта, то и на последующих ярусах после L пара узлов n
1
и n
2
не будет конфликтовать.
Конфликты превращают граф планирования в граф ограничений в смысле CSP-задачи. Метод, который используется для построения графа планирования, называется методом прямого распространения
ограничений.
Свойство 3.5.1. Пара ярусов фактов F L
i
и
F L
j
идентична,
если
F L
i
и
F L
j
содержат: 1
) одинаковые факты, 2) одинаковые
конфликты.
Свойство 3.5.2. Граф планирования P G является стабилизи-
рованным, если существуют пара смежных ярусов фактов
F L
i
и
F L
i+1
и
F L
i
идентичен
F L
i+1
Пусть граф P G стабилизирован и имеется пара идентичных ярусов- фактов F L
i
, F L
i+1
∈ P G. Тогда
Утверждение 3.5.1. Ярус фактов F L
k
∈ P G идентичен ярусу
фактов
F L
i
∈ P G, где i ∈ N .
Д о к а з а т е л ь с т в о. Действительно, во-первых, из-за существо- вания «no-op»-действий факт f, однажды появившись на некотором ярусе фактов, будет иметь место во всех последующих ярусах фактов.
Во-вторых, множество фактов, которые могут быть созданы STRIPS- правилами, конечно. Следовательно, должен существовать такой ярус фактов Q, содержащий факты, которые будут иметь место во всех последующих ярусах фактов. В-третьих, если два факта p и q, появив- шиеся на одном ярусе, не конфликтуют, то и в последующих ярусах они
3.5. Планирование как задача удовлетворения ограничений
127
также не будут конфликтовать. Таким образом, должен существовать такой ярус фактов P после Q, что все последующие ярусы фактов име- ют множества конфликтов, идентичные тем, что и в P . Утверждение доказано.
Цель G является разрешимой (достижимой) в 2-х случаях:
1) если она удовлетворяется тривиальным образом, т. е. компоненты цели G имеют место в начальном ярусе фактов,
2) если в графе P G существует подграф Plan, который состоит из множества путей, идущих от начального яруса фактов к ярусу фактов, содержащему G, и в этом множестве путей нет ни одной пары конфликтующих узлов.
Имеют место следующие утверждения.
Теорема 3.5.1. Из графа планирования P G, содержащего n яру-
сов-действий, можно извлечь план длиной
n.
Теорема 3.5.2. Алгоритм GraphPlan возвращает «план не су-
ществует», только если цель
G не достижима.
Теорема 3.5.3. Алгоритм GraphPlan обладает полнотой [63].
Опишем теперь собственно алгоритм GraphPlan.
3.5.3. Алгоритм GraphPlan.
GRAPHPLAN
вход: Acts, S
0
, G
выход: Plan t = 0 — номер начальной фазы
GS — множество для хранения разрешимых/неразрешимых целей
PG.F L
0
← S
0 1. пока P G не стабилизирован или пока цель G не разрешима
делать
1.1. РАСШИРЕНИЕ ГРАФА ПЛАНИРОВАНИЯ P G
1.2. ПОИСК ПЛАНА в P G
1.3. t = t + 1 — переход к следующей фазе
2. если «цель G разрешима» то вернуть Plan иначе вернуть Plan
= ∅
РАСШИРЕНИЕ ГРАФА ПЛАНИРОВАНИЯ
вход: F L
t
3. cоздание следующего яруса действий AL
t+1
(a) для каждого действия act ∈ ACTS, применимого в F L
t
, если
для каждой пары фактов f
1
, f
2
∈ C(act) не существуют
узлы fn
1
→ f
1
, fn
2
→ f
2
, такие что fn
1
, fn
2
∈ F L
t
и