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

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

Mark_Krass 07.01.14 в 18:09

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

Mark_Krass 07.01.14 в 18:14

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

Mark_Krass 07.01.14 в 18:14

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

Alex_ander 07.01.14 в 20:30

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

Alex_ander 07.01.14 в 20:32

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

Alex_ander 07.01.14 в 20:22

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

Alex_ander 07.01.14 в 20:21

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

Mark_Krass 08.01.14 в 12:39

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

Mark_Krass 08.01.14 в 12:45

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

Mark_Krass 08.01.14 в 12:52

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

Mark_Krass 08.01.14 в 12:55

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

Mark_Krass 08.01.14 в 12:56

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

Mark_Krass 08.01.14 в 13:00

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

Mark_Krass 08.01.14 в 13:05

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

Mark_Krass 08.01.14 в 13:06

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

Mark_Krass 08.01.14 в 13:08

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

Mark_Krass 08.01.14 в 13:11

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

Mark_Krass 08.01.14 в 13:12

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

Mark_Krass 08.01.14 в 13:17

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

Mark_Krass 08.01.14 в 13:23

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

Mark_Krass 08.01.14 в 13:25

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

Mark_Krass 08.01.14 в 13:30

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

Mark_Krass 08.01.14 в 13:33

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

Mark_Krass 08.01.14 в 13:35

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

Mark_Krass 08.01.14 в 13:37

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

Mark_Krass 08.01.14 в 13:39

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

Mark_Krass 08.01.14 в 13:41

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

Mark_Krass 08.01.14 в 13:43

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

Mark_Krass 08.01.14 в 13:43

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

Mark_Krass 08.01.14 в 13:50

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

Mark_Krass 08.01.14 в 13:50

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

Mark_Krass 08.01.14 в 13:53

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

Mark_Krass 08.01.14 в 13:59

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

Mark_Krass 08.01.14 в 14:00

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

Mark_Krass 08.01.14 в 14:04

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

Mark_Krass 08.01.14 в 14:06

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

Mark_Krass 08.01.14 в 14:08

диаграммах.

Mark_Krass 08.01.14 в 14:08

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

Mark_Krass 08.01.14 в 14:10

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

Mark_Krass 08.01.14 в 14:10

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

Mark_Krass 08.01.14 в 14:19

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

Mark_Krass 08.01.14 в 14:21

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

Mark_Krass 08.01.14 в 14:24

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

Mark_Krass 08.01.14 в 14:27

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

Mark_Krass 08.01.14 в 14:54

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

Mark_Krass 08.01.14 в 14:57

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

Mark_Krass 08.01.14 в 14:58

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

Mark_Krass 08.01.14 в 15:02

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

Mark_Krass 08.01.14 в 15:05

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

Mark_Krass 08.01.14 в 16:38