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

112
Гл. 3. Методы интеллектуального планирования
Действия агента будем описывать с помощью правил, при этом для упрощения таких описаний примем некоторые соглашения.
При описании STRIPS-задачи планирования как в множествах до- бавляемых, так и в множествах удаляемых фактов будем использовать лишь атомарные формулы без функциональных символов.
Пример правила.
Имя правила:
Push(x, y, z).
Условие:
C(R) = {ATR(y), AT(x, y)}.
Список добавлений: A(R) = {ATR(z), AT(x, z)}.
Список удалений:
D(R) = {ATR(y), AT(x, y)}.
В приведенном примере STRIPS-правило Push(x, y, z) описывает действие робота по перемещению ящика x из комнаты y в комнату z.
Здесь x, y, z — переменные.
Выполнение агентом действия сводится к применению правила.
Применение правила модифицирует состояние s.
Определение применимости правила было приведено в гл. 1.
Применение правила R преобразует состояние s в s
′
следующим образом:
s
′
= (s\(D(R)θ)) ∪ (A(R)θ)).
Это преобразование обозначается так: s
R,θ
⇒ s
′
, где через θ обозначена подстановка элементов предметной области вместо переменных.
STRIPS-допущение.
При применении некоторого правила
R к состоянию s выпол-
нимость факта
f ∈ s изменяется только в случае, когда факт f
описан либо в списке удалений
D(R), либо в списке добавлений A(R).
Технически, при проверке применимости некоторого правила R
STRIPS выполняет полную подстановку на места всех переменных индивидов предметной области. Возможны различные варианты под- становок. Некоторые варианты подстановки могут давать примеры правил, применимых (или же неприменимых) в состоянии s. Однако в алгоритм STRIPS можно внести незначительные модификации для применения неполностью означенных правил. В этом случае в состоя- нии s появились бы факты с переменными в описании. Как будет видно далее, неполная подстановка активно используется планировщиками в пространстве планов. Соответствующее свойство этих планировщи- ков получило название малого связывания (least commitment).
Приведем постановку задачи STRIPS-планирования.
Определение 3.3.2. Будем называть доменом планирования P =
= hs
0
, ΣRi, где s
0
— начальное состояние, ΣR — конечное множество правил.

3.3. Планирование в пространстве состояний
113
Определение 3.3.3. Пусть G — целевой факт агента, или просто цель. Будем называть задачей планирования T = hP , Gi.
Решение задачи планирования T заключается в нахождении плана,
который достигает цели G.
Определение 3.3.4. План Plan — это последовательность состоя- ний s
0
, ..., s n
, последовательность правил R
1
, ..., R
n и последователь- ность подстановок θ
1
, ..., θ
n
, такая что G выполнима в s n
; длина плана
Plan равна n:
Plan : s
0
R
1
,θ
1
⇒ s
1
R
2
,θ
2
⇒ s
2
R
n
,θ
n
⇒ s n
3.3.2. Алгоритм STRIPS. :
вход: ΣR, s, G
выход: plan
1. s = s
0 2. пока G не выполнимо в s
делать
2.1. выбрать компоненту g из G
2.2. выбрать правило R ∈ ΣR такое, что g ∈ A(R)
2.3. STRIPS (ΣR, s, C(R))
2.4. применить R к s
2.5. добавить R в plan
3. вернуть plan
Таким образом, на вход алгоритма STRIPS подается множество правил ΣR, начальное состояние s
0
, цель G.
Будем полагать, что в множестве ΣR все правила полностью кон- кретизированы.
Вначале в стек целей помещается главная цель G.
Если цель не является простой, т. е. содержит конъюнкцию лите- ралов, то система STRIPS добавляет в стек в некотором порядке каж- дый из литералов составной цели. Когда верхняя цель стека является однолитеральной, система ищет действие, которое содержит в списке добавлений литерал, сопоставимый с этой целью (п. 2.2). Если такое действие не применимо к текущему состоянию, тогда его предусловие помещается в стек целей, иначе действие применяется к текущему состоянию (п. 2.5) и помещается в план (plan). Если верхняя цель в стеке соответствует текущему состоянию, то она удаляется из стека.
Алгоритм STRIPS завершается, когда стек пуст.
3.3.3. Неполнота алгоритма STRIPS. Существуют задачи, для которых STRIPS либо не может построить план, либо находит не минимальный план.
Причина этого кроется в том, что STRIPS удовлетворяет каждую компоненту составной цели по отдельности, без учета их взаимосвязи.

114
Гл. 3. Методы интеллектуального планирования
Особенность предметной области, где цели взаимосвязаны (взаимодей- ствуют), получила название взаимосвязи целей.
П
РИМЕЧАНИЕ
. Впервые некорректность STRIPS’а в этом случае бы- ла вскрыта в 1973 г. Аленом Брауном из Массачусетского Технологи- ческого института. Браун попытался решить задачу, рассматриваемую в этом разделе, на планировщике HACKER. HACKER был создан Дже- ральдом Суссманом на основе планировщика STRIPS, поэтому задача получила название аномалии Суссмана (Sussman Anomaly) [66].
Рассмотрим аномалию Суссмана.
Дано:
Объекты:
3 кубика — A, B, C.
Состояние описывается предикатами:
ontable (x) — кубик x на столе,
clear (x) — над кубиком x пусто,
handempty — рука агента пуста,
holding (x) — рука агента держит кубик x,
on (x, y) — кубик x находится на кубике y.
x, y — переменные.
Правила:
R1: pickup (x) — поднять кубик со стола
C (R1): ontable (x) & clear (x) handempty
A (R1): holding (x)
D (R1): ontable (x), clear (x), handempty
R2: putdown (x) — опустить кубик на стол
C (R2): holding (x)
A (R2): ontable (x), clear (x), handempty
D (R2): holding (x)
R3: stack (x, y) — положить кубик на другой кубик
C(R3): holding (x) & clear (y)
A(R3): handempty, on (x, y), clear (x)
D(R3): holding (x), clear (y)
R4: unstack (x, y) — снять кубик с другого кубика
C(R4): handempty & on (x, y) & clear (x)
A(R4): holding (x), clear (y)
D(R4): handempty, on (x, y), clear (x)
Начальное состояние s
0
и цель G изображены на рис. 3.1.
Таким образом, цель G = {On (A, B)&On (B, C)}.
Поскольку цель G является составной, то STRIPS расщепляет ее на отдельные компоненты — On (A, B) и On (B, C), которые помещаются в стек и удовлетворяются по очереди.

3.3. Планирование в пространстве состояний
115
Рис. 3.1. Аномалия Суссмана
Положим, что On (A, B) — наверху стека, тогда планировщик находит следующую последовательность правил для удовлетво- рения On (A, B): UNSTACK (C, A), PUTDOWN (C), PICKUP (A),
STACK (A, B). Применяет найденную последовательность к состоянию s
0
. Получается ситуация, изображенная на рис. 3.2, в которой On (A, B)
выполнима. Цель On (A, B) удаляется из стека целей.
Далее, из ситуации на рис. 3.2, удовлетворяется следующая цель в стеке — On (B, C). В результате имеем:
UNSTACK (C, A), PUTDOWN (C), PICKUP (A), STACK (A, B),
UNSTACK (A, B), PUTDOWN (A), PICKUP (B), STACK (B, C).
Применяем последовательность подчеркнутых правил. Получаем си- туацию на рис. 3.3. Цель On (B, C) удовлетворена и удаляется из стека. Однако цель On (A, B), удовлетворенная на предыдущем этапе,
перестает быть выполнимой. Поэтому, далее планировщик пытается из ситуации на рис. 3.3 удовлетворить On (A, B). Это приводит к добавле- нию еще двух правил к имеющейся последовательности.
Рис. 3.2. Удовлетворение первой цели
Рис. 3.3. Удовлетворение второй цели
В результате получаем план:
UNSTACK (C, A), PUTDOWN (C), PICKUP (A), STACK (A, B),
UNSTACK (A, B), PUTDOWN (A), PICKUP (B), STACK (B, C),
PICKUP (A), STACK (A, B).

116
Гл. 3. Методы интеллектуального планирования
Подчеркнутые правила применяются. Цель On (A, B) & On (B, C) до- стигается. План построен.
Однако существует другой план, содержащий меньше действий:
UNSTACK (C, A), PUTDOWN (C), PICKUP (B),
STACK (B, C), PICKUP (A), STACK (A, B).
3.3.4. Вычислительная сложность задачи STRIPS-планирова-
ния.
Описание задачи классического планирования в терминах
STRIPS допускается любым планировщиком. Приведем без доказа- тельств два утверждения, характеризующие вычислительную слож- ность задачи STRIPS-планирования для условий, являющихся конъ- юнкцией атомарных формул.
Теорема 3.3.1. Задача планирования T не разрешима, если в язы-
ке описания домена планирования
P допустимы функциональные
символы [46].
Теорема 3.3.2. Задача планирования T разрешима, если в языке
описания домена планирования
P недопустимы функциональные
символы [54, 67].
Далее будем рассматривать случай разрешимой задачи планиро- вания, вычислительная сложность которой (табл. 3.2) варьируется от постоянного времени до EXPSPACE-полноты в зависимости от ограни- чений, накладываемых на язык домена планирования P .
Заметим, что задача «существование минимального по длине пла- на», как минимум, равна по сложности «задаче существования плана длиной 6 k».
Рассмотрим, каким образом входные параметры задачи планирова- ния влияют на ее сложность.
(1) Если нет никаких ограничений на описание домена планиро- вания P , тогда любое конкретизированное действие может появиться несколько раз в плане. Количество конкретизированных действий экс- поненциально. Размер каждого состояния в худшем случае является экспоненциальным. Таким образом, пространство состояний, в котором необходимо осуществить поиск, также экспоненциально. Это приводит к тому, что задача «существование плана» EXPSPASE-полна (стро- ка 1).
(2) Если все действия имеют пустой список удалений (строка 2),
тогда каждый факт, добавленный в состояние, остается истинным при последующих преобразованиях. Следовательно, нет необходимости ис- пользовать одно и то же действие дважды в одном плане. А поскольку число полностью конкретизированных действий экспоненциально, то

3.3. Планирование в пространстве состояний
117
план будет также экспоненциальной длины. Таким образом, сложность планирования снижается до NEXPTIME-полноты.
(3) Если дополнительно к ограничениям в пункте (2) добавить огра- ничения на предусловия, не содержащие негативных атомов (строка 3),
Т а б л и ц а 3.2. Вычислительная сложность задачи планирования
Ограничения языка
Как заданы действия
Список удалений
Отрица- ние в предусло- вии
№
Задача
Существо- вание плана
Существова- ние плана длиной 6 k
Предикаты не содержат функцио- нальные символы
Не априорно
Есть
Есть/нет
1 ExpSpace- полна
NExpTime- полна
Нет
Есть
2 NExpTime- полна
NExpTime- полна
Нет
3 ExpTime- полна
NExpTime- полна
Нет
4 PSpace- полна
PSpace- полна
Априорно
Есть
Есть/нет
5 PSpace
PSpace
Нет
Есть
6 NP
NP
Нет
7 P
NP
Нет
8 NLogSpace
NP
Все предикаты
0-местные
Не априорно
Есть
Есть/нет
9 PSpace- полна
PSpace- полна
Нет
Есть
10 NP-полна
NP-полна
Нет
11 P
NP-полна
Нет
12 NLogSpace- полна
NP-полна
Априорно Есть/нет Есть/нет 13 Постоянное время
Постоянное время

118
Гл. 3. Методы интеллектуального планирования
тогда порядок действий в плане не имеет значения. Это снижает слож- ность задачи «существование плана» до EXPTIME-полноты. Однако для задачи «существование плана 6 k» сложность не снижается и остается NEXPTIME-полной (строка 1), так как из-за константы k приходится перебирать все множество последовательностей длины 6 k.
(4) Если предусловие действия содержит не более одного литерала
(строки 4, 8, 12), тогда использование техники обратного поиска поз- воляет снизить сложность планирования, так как количество подцелей в этом случае не увеличивается. В этом случае сложность варьируется от NLOGSPACE до PSPACE-полноты.
(5) Все соображения, изложенные в пунктах 1–4, также справед- ливы для случая ограничения языка домена планирования P нуль- местными предикатами (строки 9–13). Кроме того, заметим, что для этого случая мощность |ΣR|, а также размер любого состояния s,
снижается с экспоненциального до полиномиального. Естественно, что планирование в этом случае существенно легче, чем в случае допу- щения k-местных предикатов. В общем случае снижения сложности планирования можно добиться за счет ограничения местности преди- ката некоторой постоянной j.
(6) Когда множество действий ΣR задано априорно, то местность предикатов и количество переменных в каждом действии постоянно.
В этом случае сложность планирования снижается и варьируется в пре- делах от const до PSPACE-полноты (строки 5, 6, 7, 8, 13).
3.3.5. Языковые средства описания доменов планирования.
Необходимость описания и решения задач в более сложных доменах привела к появлению языка описания действий ADL [68], являюще- гося расширением STRIPS-языка. ADL позволяет выражать условные эффекты действий (эффекты, которые применяются только тогда, когда дополнительные условия истинны в момент применения действия),
квантифицированные эффекты (эффекты применяются к группе объек- тов вместо одного), в условиях допускаются дизъюнкции, квантифици- рованные формулы и иные логические связки.
Одним из первых планировщиков, который поддерживает расши- ренный синтаксис языка ADL, является UCPOP.
3.4. Поиск в пространстве планов
3.4.1. Основная идея. Первым планировщиком, строящим план на основе поиска в пространстве планов, являлся NOAH (Nets Of
Action Hierarchies). В 1991 г. МакАлистер и Розенблитт доказали полноту SNLP — алгоритма частично-упорядоченного планирования,
что во многом предопределило направление дальнейших исследова- ний [50].

3.4. Поиск в пространстве планов
119
Начнем с примера, демонстрирующего особенности частично-упо- рядоченного планирования.
Пусть агенту необходимо выполнить несколько задач в комнате A
и несколько задач в комнате B (рис. 3.4).
Рис. 3.4. Иллюстрация к частично-упорядоченным планам
Агент способен выполнять:
1) действия A
1
, ..., A
n
, B
1
, ..., B
m
, которые доставляют, соответ- ственно, факты P
i
(i∈1, ... , n) и Q
j
(j ∈1, ... , m). Условие С(A
i
) =
= IN(A), условие C(B
i
) = IN (B);
2) действие GO (A), которое не имеет условий, но имеет в списке добавлений IN (A), а в списке удалений IN (B);
3) действие GO (B), которое не имеет условий, но имеет в списке добавлений IN (B), а в списке удалений IN (A).
Необходимо достичь цели G = {P
1
, ..., P
n
, Q
1
, ..., Q
m
}.
Очевидно, что цель G может быть достигнута после исполнения плана Plan = {GO (A); A
1
; ...; A
n
; GO (B); B
1
; ...; B
m
}. Заметим, что по- рядок выполнения действий A
1
, ..., A
n
, как и порядок выполнения действий B
1
, ..., B
m
, не имеет значения, поскольку все действия A
i выполняются в одной комнате (в комнате A); то же самое касает- ся и действий B
i
(которые выполняются в комнате B), а в усло- вия действий входит только это обстоятельство. Следовательно, план
{GO (A), A
n
; ...; A
1
, GO (B), B
m
, ...; B
1
} будет эквивалентен вышепри- веденному плану.
Для рассматриваемой задачи множество всех линейных планов может быть обобщено одним нелинейным (частично-упорядоченным)
планом. Особенность его состоит в том, что на действиях задается частичный порядок. При этом два линейных плана являются экви- валентными, если они являются представлениями одного и того же нелинейного плана.
Введем несколько определений.
Определение 3.4.1. Шаг плана — это пара h№, Ri, где № — уни- кальный номер шага, R — некоторое правило.

120
Гл. 3. Методы интеллектуального планирования
Два разных шага могут включать одно и то же правило. Таким образом, допустимы планы, содержащие более одного вхождения неко- торого правила.
В SNLP нелинейный план всегда содержит хотя бы два шага:
1) стартовый — START, соответствующий правилу, которое имеет список добавлений, задающих множество начальных фактов (на- чальное состояние среды), но не имеет предусловий и списка удалений, и
2) конечный — FINISH, соответствующий действию, которое в ка- честве предусловий имеет целевые формулы, но не имеет списка добавлений и списка удалений.
Определение 3.4.2. Каузальная связь — это тройка hS, f, W i, где f — некоторый факт, S — шаг, имеющий факт f в списке добавлений,
W — шаг, имеющий в предусловии атом f .
Определение 3.4.3. Угроза V для каузальной связи hS, f, W i —
это шаг, который либо добавляет, либо удаляет факт f, и при этом не является ни шагом S, ни шагом W .
Определение 3.4.4. Защитное ограничение — это отношение по- рядка «<», заданное на шагах плана, при этом S < W означает, что шаг S должен быть выполнен до шага W , и напротив, S > W означает,
что шаг S должен быть выполнен после шага W .
Определение 3.4.5. Нелинейный план Plan = hST , CL, SCi, где
ST — множество шагов, CL — множество каузальных связей, SC —
множество защитных ограничений.
Заметим, что нелинейный план Plan обладает полнотой, если:
1) каждый шаг плана участвует либо в каузальной связи, либо в защитном ограничении;
2) любой шаг W с предусловием f состоит в некоторой каузальной связи hS, f, W i;
3) имеется шаг-угроза V для каузальной связи hS, f, W i и нели- нейный план содержит либо защитное ограничение V < S, либо защитное ограничение V > W .
Определение 3.4.6. Топологическая сортировка нелинейного
плана Plan — это линейная последовательность всех шагов, которая удовлетворяет следующим условиям:
1) первый шаг в последовательности — START;
2) последний шаг в последовательности — FINISH;
3) для каждой каузальной связи hS, f, W i шаг S в последовательно- сти предшествует шагу W ;
4) для каждого защитного ограничения U < V шаг U в последова- тельности предшествует шагу V .