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

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

Mark_Krass 06.01.14 в 21:32

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

Mark_Krass 06.01.14 в 21:33

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

Mark_Krass 06.01.14 в 21:42

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

Mark_Krass 06.01.14 в 21:44

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

Mark_Krass 06.01.14 в 21:48

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

Mark_Krass 06.01.14 в 21:49

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

Mark_Krass 06.01.14 в 21:56

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

Mark_Krass 06.01.14 в 22:01

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

Mark_Krass 06.01.14 в 22:04

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

Mark_Krass 06.01.14 в 22:06

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

Mark_Krass 06.01.14 в 22:09

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

Mark_Krass 06.01.14 в 22:09

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

Mark_Krass 07.01.14 в 10:31

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

Mark_Krass 07.01.14 в 10:33

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

Mark_Krass 07.01.14 в 10:38

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

Mark_Krass 07.01.14 в 10:38

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

Mark_Krass 07.01.14 в 10:45

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

Mark_Krass 07.01.14 в 10:46

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

Mark_Krass 07.01.14 в 10:53

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

Mark_Krass 07.01.14 в 10:55

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

Mark_Krass 07.01.14 в 10:58

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

Mark_Krass 06.01.14 в 21:19

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

Mark_Krass 07.01.14 в 11:02

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

Mark_Krass 07.01.14 в 11:03

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

Mark_Krass 07.01.14 в 11:05

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

Mark_Krass 07.01.14 в 11:09

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

Mark_Krass 07.01.14 в 11:09

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

Mark_Krass 07.01.14 в 11:31

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

Mark_Krass 07.01.14 в 11:34

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

Mark_Krass 07.01.14 в 11:37

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

Mark_Krass 07.01.14 в 16:36

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

Mark_Krass 07.01.14 в 16:45

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

Mark_Krass 07.01.14 в 17:15

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

Mark_Krass 07.01.14 в 17:16

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

Mark_Krass 07.01.14 в 17:18

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

Mark_Krass 07.01.14 в 17:20

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

Mark_Krass 07.01.14 в 17:22

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

Mark_Krass 07.01.14 в 17:23

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

Mark_Krass 07.01.14 в 17:24

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

Mark_Krass 07.01.14 в 17:33

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

Mark_Krass 07.01.14 в 17:37

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

Mark_Krass 07.01.14 в 17:37

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

Mark_Krass 07.01.14 в 17:53

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

Mark_Krass 07.01.14 в 17:53

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

Mark_Krass 07.01.14 в 17:38

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

Mark_Krass 07.01.14 в 17:39

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

Mark_Krass 07.01.14 в 17:57

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

Mark_Krass 07.01.14 в 18:01

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

Mark_Krass 07.01.14 в 18:02

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

Mark_Krass 07.01.14 в 18:06