Анализ методов интеллектуального планирования.

Примечания:

1)Действия имеют не более чем одно предусловие.

) Для некоторых множеств .

Пояснения к таблице 1:

в графе "ограничения языка" описаны ограничения, накладываемые на язык L домена планирования Р;

в графе "как заданы действия" - "априорно" означает, что множество SR в задаче планирования Т фиксировано, а параметрами являются s0 и G;

в графе "существование плана" представлена вычислительная сложность следующей задачи: "Существует ли для задачи планирования Т= <s0, SR, G> план, который достигает цели G?";

в графе "существование плана длиной £ k" представлена вычислительная сложность следующей задачи: "Существует ли для задачи планирования Т= < s0, SR, G> и заданного целого числа к, план длиной меньшей либо равной к, который достигает цели G?"

Заметим, что задача "существование минимального по длине плана", как минимум, равна по сложности "задаче существовании плана длиной £ k".

Рассмотрим, каким образом входные параметры задачи планирования влияют на её сложность.

Если нет никаких ограничений на описание домена планирования Р, тогда любое конкретизированное действие может появиться несколько раз в плане. Количество конкретизированных действий экспоненциально. Размер каждого состояния в худшем случае является экспоненциальным. Таким образом, пространство состояний в котором необходимо осуществить поиск также экспоненциально. Это приводит к тому что, задача "существование плана" EXPSPASE-полна (строка 1).

(2) Если все действия имеют пустой список удалений (строка 2), тогда каждый факт, добавленный в состояние, остаётся истинным при последующих преобразованиях. Следовательно, нет необходимости использовать одно и то же действие дважды в одном плане. А поскольку, число полностью конкретизированных действий экспоненциальной длины. Таким образом, сложность планирования снижается до NEXPTIME-полноты.

Если дополнительно к ограничениям в пункте (2) добавить ограничения на предусловия, так чтобы они не содержали негативных атомов (строка 3), тогда порядок действий в плане не имеет значения. Это снижает сложность задачи "существование плана" до EXPTIME-полноты. Однако, для задачи "существование плана £ k" сложность не снижается и остается NEXPTIME-полной (строка 1), так как из-за константы k приходится перебирать всё множество последовательностей длины £ к.

Если предусловие действия содержит не более одного литерала (строки 4, 8, 12), тогда использование техники обратного поиска позволяет снизить сложность планирования, так как количество подцелей в этом случае не увеличивается. В этом случае сложность варьируется от NLOGSPACE до PSPACE-полноты.

Все соображения, изложенные в пунктах 1-4 также справедливы для случая ограничения языка домена планирования Р нульместными предикатами (строки 9-13). Кроме того, заметим, что для этого случая, мощность |SR|, а также размер любого состояния s, снижается с экспоненциального до полиномиального. Естественно, что планирование в этом случае существенно легче, чем в случае допущения k-местных предикатов. В общем случае, снижение сложности планирования можно добиться за счёт ограничения местности предиката некоторой постоянной j. При этом нульместное ограничение соответствует случаю, когда j=0.

(6) Когда множество действий SR задано априорно, то местность предикатов и количество переменных в каждом действии постоянно. В этом случае сложность планирования снижается и варьируется в пределах от const до PSPACE-полноты (строки 5,6.7,8,13).

Необходимость описания и решения задач в более сложных доменах привело к появлению языка описания действий ADL

(

Action

Description

Language

)

, являющегося расширением STRIPS-языка. ADL позволяет выражать условные эффекты действий (эффекты, которые применяются только тогда, когда дополнительные условия истинны в момент применения действия), квантифицированные эффекты (эффекты применяются к группе объектов вместо одного), в предусловиях стало возможным выражать дизъюнкции, квантифицированные формулы, и прочие логические связки.

Одним из первых планировщиков, который поддерживал расширенный синтаксис языка ADL, являлся UCPOP.

Поиск в пространстве планов

Первым подобным планировщиком являлся NOAH (Nets Of Action Hierarchies) [97]. NOAH строил оптимальный план для аномалии Суссмана.

В 1991 году МакАлистер и Розенблитт [37] доказали полноту SNLP -алгоритма частично-упорядоченного планирования, что во многом предопределило направление дальнейших исследований.