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

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

Mark_Krass 08.01.14 в 19:27

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

Mark_Krass 08.01.14 в 19:28

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

Mark_Krass 08.01.14 в 19:30

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

Mark_Krass 08.01.14 в 19:30

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

Mark_Krass 08.01.14 в 19:33

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

Mark_Krass 08.01.14 в 19:33

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

Mark_Krass 08.01.14 в 19:36

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

Mark_Krass 08.01.14 в 19:38

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

Mark_Krass 08.01.14 в 19:42

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

Mark_Krass 08.01.14 в 19:43

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

Mark_Krass 08.01.14 в 19:46

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

Mark_Krass 08.01.14 в 19:47

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

Mark_Krass 08.01.14 в 19:51

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

Mark_Krass 08.01.14 в 19:52

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

Mark_Krass 08.01.14 в 19:52

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

Mark_Krass 08.01.14 в 19:54

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

Mark_Krass 08.01.14 в 19:57

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

Mark_Krass 08.01.14 в 19:59

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

Mark_Krass 08.01.14 в 20:01

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

Mark_Krass 08.01.14 в 20:02

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

Mark_Krass 08.01.14 в 20:02

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

Mark_Krass 08.01.14 в 20:07

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

Mark_Krass 08.01.14 в 20:10

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

Mark_Krass 08.01.14 в 20:13

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

Mark_Krass 08.01.14 в 20:28

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

Mark_Krass 08.01.14 в 20:29

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

Mark_Krass 08.01.14 в 20:31

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

Mark_Krass 08.01.14 в 20:35

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

Mark_Krass 08.01.14 в 20:35

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

Mark_Krass 08.01.14 в 20:59

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

Mark_Krass 08.01.14 в 21:03

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

Mark_Krass 08.01.14 в 21:04

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

Mark_Krass 08.01.14 в 21:07

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

Mark_Krass 08.01.14 в 21:10

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

Mark_Krass 08.01.14 в 21:11

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

Mark_Krass 08.01.14 в 21:18

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

Mark_Krass 08.01.14 в 21:19

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

Mark_Krass 08.01.14 в 21:23

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

Mark_Krass 08.01.14 в 21:24

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

Mark_Krass 08.01.14 в 21:27

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

Mark_Krass 08.01.14 в 21:29

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

Mark_Krass 08.01.14 в 21:30

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

Mark_Krass 08.01.14 в 21:32

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

Mark_Krass 08.01.14 в 21:33

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

Mark_Krass 08.01.14 в 21:35

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

Mark_Krass 08.01.14 в 21:36

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

Mark_Krass 08.01.14 в 21:37

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

Mark_Krass 08.01.14 в 21:40

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

Mark_Krass 06.01.14 в 22:12

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

Mark_Krass 08.01.14 в 21:44