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

Оглавление

Сбросить всё

←

→

Английский оригинал	Перевод на русский
Сожалеем, но текст оригинала доступен только зарегистрированным пользователям.	Покажем, что для всех _ 0, для каждого множества состояний в Hi существует план, который достигает G. Mark_Krass 08.01.14 в 21:45 0
	Индукционная гипотеза: Hi содержит только такие множества S 2 flat(Hi), для которых план достижения G Mark_Krass 08.01.14 в 22:02 0
	существует. Mark_Krass 08.01.14 в 22:02 0
	Базовый сценарий = 0: Изначально Н0 = F (G) и единственный набор в H0 является G. Пустой план достигает G Mark_Krass 08.01.14 в 22:05 0
	от G. Mark_Krass 08.01.14 в 22:06 0
	Шаг индукции i _ 1: Hi+1 получается как Hi_F(spreimgo(S)) где S =findnew(o,;,Hi,Hi). Mark_Krass 08.01.14 в 22:07 0
	По лемме 4.37 S 2 flat(Hi) и spreimgo(S) _ S0 не для S0 2 flat(Hi). Поскольку S находится в Hi Mark_Krass 08.01.14 в 22:09 0
	есть план _ для достижения G из S. План, в котором выполняется О с последующим _ достижением G из spreimgo(S). Mark_Krass 08.01.14 в 22:11 0
	Пусть Z быть любой член из flat(Hi+1). Покажем, что для Z есть план достижения G. Mark_Krass 08.01.14 в 22:12 0
	План Z начинается с ветвления. Покажем, что для каждого возможного наблюдения, соответствующему одному Mark_Krass 08.01.14 в 22:17 0
	классу наблюдаемости, есть план, который достигает G. Пусть Cj быть JTH класс наблюдаемости. Тогда Mark_Krass 08.01.14 в 22:18 0
	при наблюдении Cj текущее состояние находится в Zj = Z \ Cj. Теперь для Zj есть Z0j 2 Hi+1j с Zj _ Z0j где Hi+1 Mark_Krass 08.01.14 в 22:21 0
	J IS-я компонента Hi+1. Далее по индукции существует план для которого Z0jif Z0j 2 Hij, и если Z0j 2 Hi+1j \Hij, тогда для ветви соответствующей Cj мы используем план для spreimgo(S), а Z0 Mark_Krass 08.01.14 в 22:23 0
	должен быть spreimgo(S) \ Cj . Некоторые из ветвей могут быть необязательны, и если пересечение Z с одним классов наблюдаемости непусто, плана может начинаться с оператора узла вместо вырожденного узла ветви. Mark_Krass 08.01.14 в 22:26 0
	4.5 Сложность вычислений Mark_Krass 06.01.14 в 12:46 0
	В этом разделе мы анализируем вычислительную сложность решений, связанную с проблемами Mark_Krass 06.01.14 в 12:46 0
	недетерминированного планирования. Проблема условного планирования является обобщением проблем Mark_Krass 06.01.14 в 12:46 0
	детерминированного планирования из главы 3 и, следовательно, существующие проблемы планирования как минимум в классе сложности Mark_Krass 06.01.14 в 12:46 0
	PSPACE. В этом разделе мы обсудим вычислительную сложность каждой из трех проблем Mark_Krass 06.01.14 в 12:47 0
	планирования, с полным наблюдением, без наблюдения, а так же проблемы с частичным наблюдением, Mark_Krass 06.01.14 в 12:47 0
	покажем их, соответственно полным классам сложности EXP, EXPSPACE Mark_Krass 06.01.14 в 12:48 0
	и 2-EXP. Mark_Krass 06.01.14 в 12:48 0

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