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

Оглавление

Сбросить всё

←

→

Английский оригинал	Перевод на русский
Сожалеем, но текст оригинала доступен только зарегистрированным пользователям.	в предыдущих и последующих состояниях, когда оператор принимается. . Пусть A = {a1, . . . , ak} будет Mark_Krass 05.01.14 в 23:18 0	+1
	начальным состоянием. Формулы, описывающие последующие и предыдущие состояния оператора oi ∈ O Mark_Krass 05.01.14 в 23:18 0	+1
	следующие: Mark_Krass 05.01.14 в 23:19 0
	Пример 4.28 Пусть операторы o1 = hA, (0.5B\|0.5(C B D))i и o2 = hB, (0.5(D B B)\|0.5C)i. Alex_ander 06.01.14 в 10:51 0
	Применение этих операторов описывается следующей формулой Mark_Krass 05.01.14 в 23:19 0
	(пример отсутствует) Alex_ander 06.01.14 в 10:53 0
	Два оператора могут применяться параллельно если не противоречат друг другу, так что необходимо Mark_Krass 05.01.14 в 23:19 0	+1
	¬oi _ ¬oj Mark_Krass 06.01.14 в 21:24 0
	Чтобы для всех операторов i и j выполнялось i ≠ j. Mark_Krass 05.01.14 в 23:20 0
	Вместе все приведенные выше формулы обозначаются как Mark_Krass 05.01.14 в 23:20 0	+1
	R3(A,A0) Mark_Krass 06.01.14 в 21:24 0
	При изменении утверждения в некоторой точке t, также утверждение о для оператора о ∈ О и Mark_Krass 05.01.14 в 23:20 0	+1
	утверждение а ∈ А должны быть переименованы, и для этого мы используем обозначение: Mark_Krass 05.01.14 в 23:20 0
	Rt3(At,At+1). Alex_ander 06.01.14 в 11:14 1
	Отыскание планов методом оценивания QBF. Alex_ander 06.01.14 в 11:13 1
	При детерминированном планировании (Раздел 3.5) методами логики суждений задача состоит в отыскании последовательности Alex_ander 06.01.14 в 10:59 1
	операторов, такой, что цель достигается в случае применения операторов, начиная от исходного Alex_ander 06.01.14 в 11:01 1
	состояния. Если есть неопределённость, то задача состоит в в отыскании такой последовательности операторов, что состояние цели Alex_ander 06.01.14 в 11:03 1
	достигается для всех возможных исполнений этой последовательности операторов. Число исполнений Alex_ander 06.01.14 в 11:04 1
	последовательности операторов может быть больше единицы, поскольку может быть несколько исходных состояний Alex_ander 06.01.14 в 11:06 1
	и поскольку операторы могут быть детерминированными. Выражение количественной оценки всех возможных Alex_ander 06.01.14 в 11:08 1
	исполнений последовательности операторов не может быть дано в сжатой форме методами логики суждений, Alex_ander 06.01.14 в 11:10 1
	вот почему вместо этого приходится использовать дискретные булевы формулы. Alex_ander 06.01.14 в 11:12 1
	Здесь Vexec = A0 [ A0 [ • • • [ At−1 где A - набор дополнительных переменных, содержащихся в Alex_ander 06.01.14 в 11:16 1
	nEPCl(e, _,>) для некоторых hc, ei 2 O and l 2 {a,¬a} для некоторых a 2 A. План выражается Alex_ander 06.01.14 в 11:28 1
	через переменные oi где o 2 O и i 2 {0, . . . , t−1}. Значения истинности остальных Alex_ander 06.01.14 в 11:26 1
	переменных Vrest = A1 [ • • • [ At определяются операторами и исполнением, выбранным Alex_ander 06.01.14 в 11:27 1
	в Vexec Mark_Krass 06.01.14 в 19:19 0
	Существуют алгоритмы для оценки QBF, расширяющие процедуру Davis-Putnam Mark_Krass 06.01.14 в 19:24 0
	и/или процедуру обхода по дереву. And-узлы соответствуют любому количеству состояний, а or-узлы Mark_Krass 06.01.14 в 19:29 0
	соответствуют экзистенциальным состояниям. Эти алгоритмы возвращают оценку Mark_Krass 06.01.14 в 19:32 0
	крайних экзистенциальных состояний, если QBF принимает значение "истина". Mark_Krass 06.01.14 в 19:33 0
	Поиск плана для недетерминированных задач без наблюдения может быть более эффективен, чем Mark_Krass 06.01.14 в 19:37 0
	чем использование стандартных алгоритмов поиска с регрессией и вычислением образов/прообразов с использованием BDDs Mark_Krass 06.01.14 в 19:39 0
	когда планы короткие и много операторов может быть использовано параллельно. Если длинные Mark_Krass 06.01.14 в 19:46 0
	планы необходимы при наличии малого числа параллелий, алгоритмы, которые пересекают пространство высказываний, оказываются Mark_Krass 06.01.14 в 19:49 0
	более эффективными. Mark_Krass 06.01.14 в 19:50 0
	4.4.3 Алгоритмы планирования с частичным наблюдением Mark_Krass 06.01.14 в 19:50 0
	Планирование с частичным наблюдением гораздо сложнее, чем два частных случая с полным наблюдением Mark_Krass 06.01.14 в 19:52 0
	и его отсутствием. При планировании без наблюдения, понятие верных утверждений становится очень Mark_Krass 06.01.14 в 19:57 0
	важным. Для планирования с полной наблюдаемостью формализации планов как последовательностей операторов Mark_Krass 06.01.14 в 20:01 0
	недостаточно. Тем не менее, планы также не могут быть оформлены в виде отображений из состояний в операторы, потому что Mark_Krass 06.01.14 в 20:05 0
	частичная наблюдаемость подразумевает, что текущее состояние не обязательно однозначно известно. Mark_Krass 06.01.14 в 20:06 0
	Поэтому нам понадобится общее определение планов, представленное в разделе 4.2.1. Mark_Krass 06.01.14 в 20:08 0
	При выполнении оператора "о" в состоянии В устанавливается возможное успешное состояние в imgo(B), и Mark_Krass 06.01.14 в 20:12 0
	базируется на том факте, что набор ограничивает B0 = imgo(B) \ C где С Mark_Krass 06.01.14 в 21:01 0
	является классом эквивалентности экспериментально неразличимых состояний соответствующих наблюдений. Mark_Krass 06.01.14 в 21:02 0
	В планировании без наблюдения обратный алгоритм поиска начинается с главного верного состояния Mark_Krass 06.01.14 в 21:10 0
	и используя регрессию или сильные прообразы для нахождения предыдущего верного состояния, до тех пор, пока верное состояние, Mark_Krass 06.01.14 в 21:15 0
	охватывающее начальное состояние, не будет найдено. Mark_Krass 06.01.14 в 21:16 0

← Предыдущая страница

Следующая страница →