Готовый перевод Introduction to Automated Planning / Введение в автоматизированное планирование: Planning without observability by evaluation of QBF

Планирование без наблюдения по оценке QBF

В этом разделе мы расширим методы из раздела 3.5 для ненаблюдаемого планирования. Потому что

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

Получается, что логика высказываний не подходит для представления ненаблюдаемого планирования

а вместо него необходим язык количественных Булевых формул. Интуитивно понятно, что причина

этого в том, что нам приходится количественно оценивать нарастающее в геометрической прогрессии число вариантов выполнения плана: нам нужно выражение типа

"существует план, такой что для всех вариантов его выполнения...", а [выразить это кратко средствами обычной логики суждений не предcтавляется возможным.]

использование данной логики не возможно. Теоретическое обоснование, данное в разделе 4.5.4 показывает, что тестирование

существующих планов проблематично в случае отсутствия наблюдения даже когда выполнено ограничение плана

полиноминальной длины классом сложности ∑2 и он не содержится в NP как

соответствующая задача недетерминированного планирования. Это заставляет предположить,

ввиду общепринятых теоретических гипотез о сложности, что в рамках логики суждений

эффективного способа постановки этой задачи не существует.

В разделе 4.1.2 мы показали, как недетерминированные операторы могут быть переведены в формулы

логики высказываний. Целью этого перевода было использования формул в планировании BDD

алгоритмов для вычисления образов и прообразов множеств состояний. Для QBF

представления недетерминированных операторов мы должны иметь возможность определять количество

всех возможных успешных состояний производящих операторов, и не можем просто выразить это, используя

формулы из раздела 4.1.2, поэтому мы делаем новый перевод использующий для определения количества Булевы

формулы (смотри раздел 2.2.1)

Перевод недетерминированных операторов в логику высказываний

Для обработки недетерминизмов мы должны определить количество всех недетерминированных операторов

потому что в любом случае остальные операторы в плане должны приводить к целевому состоянию. Для достижения результата

при n недетерминированных альтернативах можно применить m = dlog2 ne
единообразно задаваемых

количество вспомогательных переменных. Для оценки каждой переменной должен быть выбран один из альтернативных вариантов.

Поставим в соответствие каждому атомарному событию формулу, которая истинна тогда и только тогда, когда событие выполняется.

Это аналогично расширению понятия функции EPCl(e) в определении 3.3. Проблема расширения

недетерминизма состоит в следующем: если l принимает значение «истина», то вспомогательные переменные должны

иметь значения, соответствующие событиям, делающим l «истиной».

Условием выполнения l является выполнение события e в nEPCl(e, σ, t).

Целочисленная последовательность σ получает уникальные имена для вспомогательных переменных в nEPCl(e, σ, t), и

значение вспомогательной переменной t в формуле определяется когда будет вычислено e. Предполагается, что результат будет представлен

в нормальной форме I

nEPCl(e, _, t) = EPCl(e) ^ t если е детерминизировано

nEPCl(p1e1| • • • |pnen, _, t) = nEPCl(e1, _; 1, cn1(_) ^ t) _ • • • _ nEPCl(en, _; n, cnn(_) ^ t)

nEPCl(e1 ^ • • • ^ en, _, t) = nEPCl(e1, _; 1, t) _ • • • _ nEPCl(en, _; n, t)

Функция Cni (σ) строится по формуле для вычисления i-ого результата из n вариантов. Эта

формула обычно соединяет вспомогательные переменные
Amσ = {aσ,1, . . . , aσ, m}

соответствующих одной оценке Amσ. Здесь m= log2n. Когда n не является степенью двойки, последний

результат en соответствует более чем одной оценке Amσ. Определим:

dmi(_) =V({a_,j 2 Am_ |jth bit of i − 1 is 1}{¬a_,j |a_,j 2 Am_ , jth bit of i − 1 is 0}).

Когда i ∈ {1, . . . , n − 1} (и в этом особом случае i = n = 2m) мы определяем Cni (σ) как dm i(σ). Когда n=i мы определяем Cni (σ) как dm n(σ) ˅ • • • ˅ dm 2m(σ)

Отсюда события с e1 до en−1 соответствуют бинарной кодировке чисел от 0 до n-2 и en охватывает

все остальные оценки Amσ

Следующий фрейм аксиоматически выражает условия, при которых значение переменной а ∈ А может

может меняться от ложного к истинному и наоборот. Будем считать, что операторы O = {o1, . . . , on}

пронумерованы от 1 до n

(¬a ^ a0)!((o1 ^ nEPCa(e1, 1,>)) _ • • • _ (on ^ nEPCa(en, n,>)))

(a ^ ¬a0)!((o1 ^ nEPC¬a(e1, 1,>)) _ • • • _ (on ^ nEPC¬a(en, n,>)))

Для каждого оператора o = <z, e> ∈ O мы имеем формулы для описания значений переменных состояния

в предыдущих и последующих состояниях, когда оператор принимается. . Пусть A = {a1, . . . , ak} будет

начальным состоянием. Формулы, описывающие последующие и предыдущие состояния оператора oi ∈ O

следующие:

Пример 4.28 Пусть операторы
o1 = hA, (0.5B|0.5(C B D))i
и o2 = hB, (0.5(D B B)|0.5C)i.

Применение этих операторов описывается следующей формулой

(пример отсутствует)

Два оператора могут применяться параллельно если не противоречат друг другу, так что необходимо

¬oi _ ¬oj

Чтобы для всех операторов i и j выполнялось i ≠ j.

Вместе все приведенные выше формулы обозначаются как

R3(A,A0)

При изменении утверждения в некоторой точке t, также утверждение о для оператора о ∈ О и

утверждение а ∈ А должны быть переименованы, и для этого мы используем обозначение:

Rt3(At,At+1).

Отыскание планов методом оценивания QBF.

При детерминированном планировании (Раздел 3.5) методами логики суждений задача состоит в отыскании последовательности

операторов, такой, что цель достигается в случае применения операторов, начиная от исходного

состояния. Если есть неопределённость, то задача состоит в в отыскании такой последовательности операторов, что состояние цели

достигается для всех возможных исполнений этой последовательности операторов. Число исполнений

последовательности операторов может быть больше единицы, поскольку может быть несколько исходных состояний

и поскольку операторы могут быть детерминированными. Выражение количественной оценки всех возможных

исполнений последовательности операторов не может быть дано в сжатой форме методами логики суждений,

вот почему вместо этого приходится использовать дискретные булевы формулы.

Здесь Vexec = A0 [ A0 [ • • • [ At−1 где A - набор дополнительных переменных, содержащихся в

nEPCl(e, _,>) для некоторых hc, ei 2 O and l 2 {a,¬a} для некоторых a 2 A. План выражается

через переменные oi где o 2 O и i 2 {0, . . . , t−1}. Значения истинности остальных

переменных Vrest = A1 [ • • • [ At определяются операторами и исполнением, выбранным

в Vexec

Существуют алгоритмы для оценки QBF, расширяющие процедуру Davis-Putnam

и/или процедуру обхода по дереву. And-узлы соответствуют любому количеству состояний, а or-узлы

соответствуют экзистенциальным состояниям. Эти алгоритмы возвращают оценку

крайних экзистенциальных состояний, если QBF принимает значение "истина".

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

чем использование стандартных алгоритмов поиска с регрессией и вычислением образов/прообразов с использованием BDDs

когда планы короткие и много операторов может быть использовано параллельно. Если длинные

планы необходимы при наличии малого числа параллелий, алгоритмы, которые пересекают пространство высказываний, оказываются

более эффективными.

4.4.3 Алгоритмы планирования с частичным наблюдением

Планирование с частичным наблюдением гораздо сложнее, чем два частных случая с полным наблюдением

и его отсутствием. При планировании без наблюдения, понятие верных утверждений становится очень

важным. Для планирования с полной наблюдаемостью формализации планов как последовательностей операторов

недостаточно. Тем не менее, планы также не могут быть оформлены в виде отображений из состояний в операторы, потому что

частичная наблюдаемость подразумевает, что текущее состояние не обязательно однозначно известно.

Поэтому нам понадобится общее определение планов, представленное в разделе 4.2.1.

При выполнении оператора "о" в состоянии В устанавливается возможное успешное состояние в imgo(B), и

базируется на том факте, что набор ограничивает B0 = imgo(B) \ C где С

является классом эквивалентности экспериментально неразличимых состояний соответствующих наблюдений.

В планировании без наблюдения обратный алгоритм поиска начинается с главного верного состояния

и используя регрессию или сильные прообразы для нахождения предыдущего верного состояния, до тех пор, пока верное состояние,

охватывающее начальное состояние, не будет найдено.

При частичном наблюдении планы не только содержат операторы, но так же могут расширяться. С расширением

последовательность операторов может зависеть от наблюдений, и это дает возможность для достижения

целей и тогда, когда не фиксированная последовательность операторов не достигнет поставленных целей. Т.к. сильные прообразы в поиске

в обратном направлении соответствуют образам, возникает вопрос, чему соответствуют ветвления в поиске в обратном направлении?

Предположим, что мы имеем для верных состояний В1 и В2 соответственно планы _1 и _2, которые достигают

целей и что эти верные состояния экспериментально различимы т.е. они включены в

различные классы наблюдаемости. Теперь мы можем построить план _12, который начинается с узла ветвления,

сделав наблюдение и продолжив с _1 или с _2 в зависимости от того, какое наблюдение было

сделано. Если мы изначально находимся в любом состоянии в В1 В2, план _12 всегда ведет нас к целевому состоянию. Мы

можем продолжить расширение _12 с операторами. Например, если B = wpreimgo(B1 [ B2), то

план сначала выполняет оператор "о" и продолжает с _ приведет к целевому состоянию начиная

с любого состояния в В.

Далее мы формализуем эти идеи и выведем алгоритм, который строит планы ветвления в

обратном направлении, начиная с целевого состояния.

Пусть _ = hC1, . . . ,Cni разбивает пространство состояний на классы наблюдаемости, каждый из которых состоит

из внешне неотличимых состояний.

Наборы верных состояний, порожденные при обратном обходе пространства начиная с целевого

состояния, содержат много закономерностей, вызванных наблюдаемостью. Например, если у нас есть планы достижения

целей из трех различных состояний В1, В2 и В3, и они имеют непустые пересечения с

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

состояний. Эти 3*n множеств имеют краткое представление в факторизованной форме, такое как

h{B1 \C1,B2 \C1,B3 \C1}, {B1 \C2,B2 \C2,B3 \C2}, . . . , {B1 \Cn,B2 \Cn,B3 \Cn}i

из которого наборы могут быть получены путем вычисления Декартового произведения и последующего объединения n

компонентов каждого из 3*n кортежей. Это порождает следующие определения.

Определение 4.29 (факторизованное пространство состояний) Пусть _ = НС1,. . . , Cni разбиение множества всех

состояний. Тогда факторизованно пространство hG1, . . . ,Gni где s _ s0 не для каждого {s, s0} _ Gi и

Gi _ 2Ci для каждого i 2 {1, . . . , n}.

Интуитивно понятно, что факторизованное пространство представляет собой совокупность верных состояний, разбитое на подмножество соответствующих

классом наблюдаемости. Это просто техническое определение, которое упрощает разговор о

состояниях соответствующих одному классу наблюдаемости. Обратим внимание на условие минимальности:

ни одно из верных состояний в факторизованном пространстве не может быть подмножеством другого. Нам необходимо

условие минимальности потому что мы используем факторизованные пространства в качестве представления множеств

состояний, для которых существует план. Если существует план для некоторого верного состояния В, то этот план также

справедлив для любого верного состояния В0 такого что B0 _ B.

Представим один элемент множества состояний S как F(S) = h{C1\S}, . . . , {Cn\ S}i.

Когда это будет следовать из контекста будем писать S вместо F(S).

Когда мы имеем два множества состояний в факторизованной форме, мы можем объединить их и представить

результат в факторизованной форме.

Определение 4.30 (Объединение факторизованных пространств) Пусть G = hG1, . . . ,Gni andH = hH1, . . . ,Hni

факторизованные пространства. Определим G_H как hG1 dH1, . . . ,Gn dHni, где оператор d является

объединением двух наборов множеств и устраняет множества которые не включены в основное. Формально

определим это как G d H = {R 2 G [ H|R _ K for no K 2 G [ H}.

Важным в этом объединении операторов является то, что условие минимальности сохраняется: любое

состояние, которое является подмножеством другого состояния, исключается.

Объединенный оператор обладает следующими свойствами.

Лемма 4.31 (Пространство с коммутативными моноидами) Оператор _ обладает свойствами ассоциативности,

коммутативности и идентичен элементу h;, . . . , ;i.

Факторизованное пространство G = hG1, . . . ,Gni можно рассматривать как набор множеств состояний

flat(G) = {s1[• • •[sn|si 2 Gi для всех i 2 {1, . . . , n}}, и его мощность |G1| • |G2| • . . . • |Gn|.

Мощность может быт представлена в виде экспоненты, в зависимости от степени факторизации. Если предположить, что у нас

есть план для всех состояний в G, у нас так же есть план для любых состояний в flat(G). Этот план начинается с

ветви соответствующей сделанному наблюдению С и следующий план соответствует

состоянию В\С.

Определение 4.32 (Отношение включения для пространств убеждений). Разложенное пространство убеждений G включено в

разложенное пространство убеждений H, если для всех S 2 flat(G) есть такое S0 2 flat(H), что S _ S0. Мы

записываем это в форме
G v H.

Эти определения обладают свойством:
S 2 flat(G) тогда и только тогда, если F(S) v G.

Обсудим сложность некоторых операций на пространстве утверждений. Базовые операции, необходимые

в алгоритмах планирования для проверки наличия множества состояний в факторизованном пространстве убеждений

и нахождения набора состояний, прообраз относительного оператора которых, не содержится в пространстве утверждений.

Эта последняя операция необходима на резервном шаге алгоритма планирования: найти план

который охватывает состояния, для которых ранее не было плана.

Теорема 4.33 Тестирование G V H для факторизации пространства утверждений G и H временным многочленом.

Доказательство: Тестирование hG1, . . . ,Gni v hH1, . . . ,Hni просто путем проверки всех i 2 {1, . . . , n}

и всех s 2 Gi где t 2 Hi такие что s _ t. _

Пример 4.34 Рассмотрим мир блоков с тремя блоками с главным состоянием, в котором все

блоки лежат на столе. Есть три оператора, каждый из которых поднимает один блок (если

на столе ничего нет) и помещает его на стол. Мы можем только наблюдать, как одни блоки оказываются ниже

других. Это разбивает пространство состояний на 7 классов наблюдаемости, соответствующих

оценкам переменных состояния А-верно, В-верно и С-верно, когда по крайней мере один блок находится в состоянии "верно".

Шаги по созданию плана приведены на рисунке 4.10. Начиная с верхнего левого, первая диаграмма

отображает состояние целевого утверждения. Вторая диаграмма изображает состояния, полученные путем вычисления

прообраза целевого состояния по отношению к перемещению состояния А в таблице действий и

разделению наборов состояний на соответствующие классы наблюдаемости. Следующие две

диаграммы аналогичны для прообразов перемещения В и С в таблице.

Пятая схема изображает вычисление сильного прообраза от объединения двух существующих

верных состояний, в которых блок А находится на столе и С находится на В или В на С. В результате

состояния А верхний блок попадает в стек содержащий все три блока. Следующие две диаграммы аналогично

строят состояния в которых соответственно В и С верхние блоки.

Последние три диаграммы изображают наиболее интересные случаи конструирования состояний относительно

двух существующих состояний в одном классе наблюдаемости. Первая диаграмма изображает создание

верного состояния состоящего из двух состояний в которых А и В верны и С находится под А или В.

Эти верные состояния получаются из объединения сильных прообразов двух существующих верных состояний,

того, в котором все блоки на столе и того, в котором А на столе и В на С.

Действие, которое перемещает блок А на стол делает состояние верным потому что если А на С, все блоки

будут на столе и если А уже на столе, то ничего не произойдет. Создание верных

состояний в которых В и С являются ясными и А и С являются ясными аналогично и изображено на двух последних

диаграммах.

В результате план достигает целевого состояния из любого состояния в мире блоков. План в виде

программы представлен на рисунке 4.11 (порядок строительства от конца к началу.)

Мы представляем алгоритм для расширения факторизованного пространства утверждений путем вычисления прообразов

комбинации некоторых из своих верных состояний, основываясь на переборе и работе в худшем случае

по экспоненциальному закону. Алгоритм обоснован следующей теоремой, которая показывает, что нахождение новых

верных состояний обладает NP сложностью. Доказательство является сокращением от SAT: представим каждое предложение как множество

букв, которых в нем нет, а затем назначим такой набор букв, который не включает в себя ни один другой набор.

Теорема 4.35 При тестировании G = HG1,. . . , Gni множество S содержит такие состояния, что spreimgo (S)

не входит в G в законченном NP состоянии. Это справедливо и для детерминированных операторов о.

Доказательство: Количество членов в NP ограничено: недетерминированно выберем Si 2 Gi для каждого I 2 {1,. . . , П},

вычислим прообраз р от s1 [• • • [Sn в детерминированное полиномиальное время, и убедимся, что в многочлене пересечение г \ Ci прообраза с одним из классов наблюдаемости Ci не попадает в Gi.

Пусть T = {e1,. . . , Эм} множество условий для набора пропозициональных переменных A = {a1, . . . , ak}.

Мы создаем факторизованное пространство утверждений, базируясь на пространстве состояний, в которых переменные а и b для a 2 A

и все переменные с а замененные на z являются состояниями. Переменные Z представляют отрицательные литералы.

Пусть о планирует переход от ai к zi и ai к zi для всех i 2 {1, . . . , k}.

Мы утверждаем что Т выполнимо тогда и только тогда, когда flat(G) содержит верное состояние В такое что spreimgo(B)

не состоит в G.

Предположим, Т выполнимо, т.е. М такое что M |= T. Определим M0 = {zi|ai 2 A,M |=

ai} [ {bzi|ai 2 A,M 6|= ai}. Очевидно, что М0 верное состояние в G. Определим M00 = {ai 2 A|M |=

ai} [ {bai|ai 2 A,M 6|= ai}. Очевидно, M00 является прообразом M0 относительно о.

Мы покажем, что M00 не входит в G. Возьмите любую I 2 {1,. . . , т}. Поскольку М | = Ei, есть AJ 2

такая, что а 2 Е и М | = а (. Случай ¬ на 2 Ei аналогичен) Сейчас а ^ 2 M00. По определению

теперь а ^ 62 E0j. Так как это верно для всех г 2 {1,. . . , т}, M00 не является подмножеством любого Ei, и, следовательно,

не принадлежит G.

Предположим, есть верное состояние B в G такое, что прообраз B относительно о не состоит в G.

Очевидно, что B является подмножеством A [{ба | 2} с не более чем одним а или b для любого г 2 {1,. . . , К}. Определим

пропозициональную модель М такую что M |=а тогда и только тогда, когда a 2 B. Покажем, что М | = Т. Возьмем

любое условие Е из Т. Т.к. В не входит в G, B 6_ E0

Следовательно, существует а или b входящие в B\E0

Рассмотрим

случай с AJ (b аналогично).

По определению M, M | = а и, следовательно,

M |= Ei. Это верно для всех г 2 {1,. . . , т}, М | = Т. Это завершает доказательство.

Пример 4.36 Построение доказательства можно проиллюстрировать на следующем примере.

Мы используем оператор, который отображает переменную х в переменную х0. Пусть T = {A_B ° C, ¬ A_B, ¬ C}.

Соответствующее факторизованное пространство утверждений

h {{ b A, b B, b C}, {A, b B,C, b C}, {A, b A,B, b B,C}},

Рисунок 4.12: Алгоритм поиска новых верных состояний

Далее мы приводим алгоритм для построения условных планов. Основной шаг в алгоритме

это нахождение верного состояния, для которого план может существовать, базируется на наборе верных состояний в

планах.

Процедура на рисунке 4.12 выполняет этот шаг: находим множество S состояний, которые не содержатся

в H и являются сильным прообразом множества S0 состояний в F относительно оператора о.

Время, необходимое для процедуры увеличивается по экспоненциальному закону, в зависимости от размера F и поглощает линейное пространство размера F.

Согласно теореме 4.35 это лучший результат, которого можно ожидать (если это не выполнится, то P = NP).

Лемма 4.37 Вызов процедуры findnew (о,;, Н, Н0) возвращает множество S0, так что S0 = spreimgo (S)

для некоторого S 2 flat(H) и S0 _ S00 не для S00 2 flat(H0), и возвращает S00 если нет такого множества состояний.

Доказательство: Процедура проходит по элементам Hs1,. . . , Sni из F1. • • •. Fn и проверяет, входит ли

spreimgo (S1 [• • • [Sn) в H. Множества S1 [• • • [Sn являются элементами flat(F). Проход

через F1. • • •. Fn создает дерево поиска с элементами F1, являющимися дочерними элементами корневого

узла, элементами F2, являющимися дочерними элементами по отношению к элементам F1 и проверяет наличие сильного прообраза.

Реализация процедуры может быть улучшена во многих аспектах. Наборы f1,. . . , fм можно

установить в соответствии с мощностями так, что большие прообразы окажутся первыми в очереди и новое верное

состояние будет найдено раньше. Также другие виды эвристик могут быть применены здесь, например, те, которые

будут пытаться найти верные состояния ближе к исходному состоянию, например, в соответствии с эвристиками,

рассмотренными в разделе 4.4.1.

Определим altimgo(S) как imgo(wpreimgo(S)). Это множество состояний, которые могут быть достигнуты,

если будет достигнуто состояние S. Сейчас S _ altimgo(S), и для детерминированных операторов

S = altimgo(S).

Методы сокращения, основанные на сильных и слабых прообразах, следующие.

1. Пусть о детерминизированный оператор. Если spreimgo(fi)  spreimgo(fj) и i > j, или spreimgo(fi) spreimgo(fj), тогда мы можем игнорировать fi.

Если сильный прообраз fi меньше чем fj, сильный прообраз который находится с

fi не может быть больше, чем fj, и следовательно, использование Fi не является необходимым.

2. Методы сокращения для недетерминированных операторов являются более сложными.

Если wpreimgo(fi) _ wpreimgo(fj) и altimgo(fi) \ fi _ altimgo(fj) и i > j, или

wpreimgo(fi) _ wpreimgo(fj) и altimgo(fi) \ fi _ altimgo(fj) то fi может быть проигнорировано.

Рисунок 4.13: Обратный алгоритм поиска для планирования с частичным наблюдением.

Более продвинутая версия этого метода может быть использована во время поиска. Если наборы включенные

в С1,. . . , Ск уже были выбраны, а их объединением является B, состояния s 2 fi такое что

altimgo({s}) \ ((Si{1,...,k} Ci)\B) 6= ; не поможет в поиске нового (большего) верного состояния.

Рисунок 4.13 показывает проблемы алгоритма нахождения плана с частичным наблюдением. Алгоритм

использует подпроцедуру findnew для расширения пространства утверждений (это подзадача NP сложности

из теоремы 4.35). Алгоритм нахождения плана не гарантирует оптимальности, потому что

он не находит все возможные планы в первую очередь.

Здесь мы не найдем описания, необходимого для получения плана, и алгоритм

просто возвращает истину или ложь в зависимости от того, существует план или нет. Улучшить алгоритм для получения

необходимого описания просто.

Лемма 4.38 Предположим, S 2 flat(H). Тогда есть S0 2 flat(H _ G) такой что S _ S0.

Лемма 4.39 Пусть S1,. . . , Sn множество состояний таких что для каждого i 2 {1, . . . , n} есть S0

i 2 flat(H) такое что Si _ S0i, класса наблюдаемости С, такого что некоторые {i, j} _ {1, . . . , n}

оба i 6= j и Si\C 6= ; и Sj\C 6= ;. Тогда есть S0 2 flat(H) такое что S1[• • •[Sn _ S0.

Теорема 4.40 Всякий раз, когда существует конечный ациклический план для некоторой задачи, алгоритм

на рис 4.13 возвращает "иситну".

Доказательство: предположим что есть план для некоторой задачи hA, I,O, G,Bi. Пометим все узлы

плана следующим образом. Корневой узел N пометим как I, то есть, л (N) = I. По возможности

пометив родительские узлы для узла n мы можем вычислить метку для n. Пусть ho1, ni, . . . , hom, ni

аннотации всех узлов оператора n1, . . . , nm в плане с n в качестве дочернего узла и пусть

{h_1, ni, . . .}, . . . , {h_k, ni, . . .} соответствующие аннотации всех ветвей узлов n01, . . . , n0k с n

в качестве одного из дочерних узлов. Когда метка n является imgo1(l(n1)) [ • • • [ imgom(l(nm)) [ (l(n01) \_1) [ • • • [ (l(n0

k) \ _k). Эта отметка просто говорит о возможном текущем состоянии для каждого

узла плана когда план выполняется, начиная с некоторого начального состояния.

Покажем, что при условии того, что алгоритм не прекращает работу после получения расширенного набора

I алгоритм определяет, что для каждого помеченного узла план достижения G существует если план

существует для его дочерних узлов.

Индукционная гипотеза: Для каждого плана узла n, такого что, все пути к цели узла имеют длину i

или менее, его метка S = l(n) является подмножеством некоторого S0 2 flat(H), где H является значением переменной

H после окончания программы, когда цикл Н не может быть продолжен.

Базовое состояние i = 0: Конечные узлы плана помечены с последовательностями G. По лемме 4.38

G0 2 flat(H) для некоторого множества G0 такого, что G _ G0 потому что G находится в H изначально.

Шаг индукции i _ 1: Пусть n буде узлом плана. По предположению индукции для всех дочерних узлов от n0

до n, l(n0) _ S для некоторых S 2 flat(H).

Если n является ветвью узла с дочерними узлами n1, . . . , nk и соответствуют условиям _1, . . . , _k, то

l(n) \ _1, . . ., l(n) \ _k все занимают не пересекающиеся классы наблюдаемости и расширенный набор l(n) \ _i для

каждого i 2 {1, . . . , k}, входящего в flat(H). Следовательно, по лемме 4.39 l(n) _ S для некоторого S 2 flat(H).

Если n является оператором узла с оператором о и дочерний узел n0, то imgo(l(n)) _ l(n0), и по

определению индукции l(n0) _ S0 для некоторого S 2 flat(H). Мы должны показать, что l(n) _ S00 для

некоторого S00 2 flat(H). Предположим, что нет таких S00. Но по лемме 4.37 найдем новый (o,;,H,H)

который вернет S000, такой что spreimgo(S000) _ S не для S 2 flat(H), и тогда цикл не

завершится с H, вопреки нашим предположениям об Н.

Теорема 4.41 Пусть _ = hA, I,O, G,Bi будет примером задачи. Если процедура plan(I,O,G) на

Рисунке 4.13 возвращает "истину" когда _ имеет план решения.

Доказательство: Пусть H0, H1,. . . -последовательность факторизованных пространств утверждений Н произведенная алгоритмом.

Покажем, что для всех _ 0, для каждого множества состояний в Hi существует план, который достигает G.

Индукционная гипотеза: Hi содержит только такие множества S 2 flat(Hi), для которых план достижения G

существует.

Базовый сценарий = 0: Изначально Н0 = F (G) и единственный набор в H0 является G. Пустой план достигает G

от G.

Шаг индукции i _ 1: Hi+1 получается как Hi_F(spreimgo(S)) где S =findnew(o,;,Hi,Hi).

По лемме 4.37 S 2 flat(Hi) и spreimgo(S) _ S0 не для S0 2 flat(Hi). Поскольку S находится в Hi

есть план _ для достижения G из S. План, в котором выполняется О с последующим _ достижением G из spreimgo(S).

Пусть Z быть любой член из flat(Hi+1). Покажем, что для Z есть план достижения G.

План Z начинается с ветвления. Покажем, что для каждого возможного наблюдения, соответствующему одному

классу наблюдаемости, есть план, который достигает G. Пусть Cj быть JTH класс наблюдаемости. Тогда

при наблюдении Cj текущее состояние находится в Zj = Z \ Cj. Теперь для Zj есть Z0j 2 Hi+1j с Zj _ Z0j где Hi+1

J IS-я компонента Hi+1. Далее по индукции существует план для которого Z0jif Z0j 2 Hij, и если Z0j 2 Hi+1j \Hij, тогда для ветви соответствующей Cj мы используем план для spreimgo(S), а Z0

должен быть spreimgo(S) \ Cj . Некоторые из ветвей могут быть необязательны, и если пересечение Z с одним классов наблюдаемости непусто, плана может начинаться с оператора узла вместо вырожденного узла ветви.

4.5 Сложность вычислений

В этом разделе мы анализируем вычислительную сложность решений, связанную с проблемами

недетерминированного планирования. Проблема условного планирования является обобщением проблем

детерминированного планирования из главы 3 и, следовательно, существующие проблемы планирования как минимум в классе сложности

PSPACE. В этом разделе мы обсудим вычислительную сложность каждой из трех проблем

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

покажем их, соответственно полным классам сложности EXP, EXPSPACE

и 2-EXP.

Внимание! Этот перевод, возможно, ещё не готов.
Его статус: идёт перевод

Переведено на Нотабеноиде
http://notabenoid.org/book/47116/190814

Переводчики: Mark_Krass, Alex_ander