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

Оглавление

Сбросить всё

←

→

Английский оригинал	Перевод на русский
Сожалеем, но текст оригинала доступен только зарегистрированным пользователям.	Мы создаем факторизованное пространство утверждений, базируясь на пространстве состояний, в которых переменные а и b для a 2 A Mark_Krass 08.01.14 в 16:48 0
	и все переменные с а замененные на z являются состояниями. Переменные Z представляют отрицательные литералы. Mark_Krass 08.01.14 в 16:53 0
	Пусть о планирует переход от ai к zi и ai к zi для всех i 2 {1, . . . , k}. Mark_Krass 08.01.14 в 16:55 0
	Мы утверждаем что Т выполнимо тогда и только тогда, когда flat(G) содержит верное состояние В такое что spreimgo(B) Mark_Krass 08.01.14 в 17:02 0
	не состоит в G. Mark_Krass 08.01.14 в 17:02 0
	Предположим, Т выполнимо, т.е. М такое что M \|= T. Определим M0 = {zi\|ai 2 A,M \|= Mark_Krass 08.01.14 в 17:05 0
	ai} [ {bzi\|ai 2 A,M 6\|= ai}. Очевидно, что М0 верное состояние в G. Определим M00 = {ai 2 A\|M \|= Mark_Krass 08.01.14 в 17:06 0
	ai} [ {bai\|ai 2 A,M 6\|= ai}. Очевидно, M00 является прообразом M0 относительно о. Mark_Krass 08.01.14 в 17:06 0
	Мы покажем, что M00 не входит в G. Возьмите любую I 2 {1,. . . , т}. Поскольку М \| = Ei, есть AJ 2 Mark_Krass 08.01.14 в 17:12 0
	такая, что а 2 Е и М \| = а (. Случай ¬ на 2 Ei аналогичен) Сейчас а ^ 2 M00. По определению Mark_Krass 08.01.14 в 17:13 0
	теперь а ^ 62 E0j. Так как это верно для всех г 2 {1,. . . , т}, M00 не является подмножеством любого Ei, и, следовательно, Mark_Krass 08.01.14 в 17:15 0
	не принадлежит G. Mark_Krass 08.01.14 в 17:15 0
	Предположим, есть верное состояние B в G такое, что прообраз B относительно о не состоит в G. Mark_Krass 08.01.14 в 17:16 0
	Очевидно, что B является подмножеством A [{ба \| 2} с не более чем одним а или b для любого г 2 {1,. . . , К}. Определим Mark_Krass 08.01.14 в 17:34 0
	пропозициональную модель М такую что M \|=а тогда и только тогда, когда a 2 B. Покажем, что М \| = Т. Возьмем Mark_Krass 08.01.14 в 17:41 0
	любое условие Е из Т. Т.к. В не входит в G, B 6_ E0 Mark_Krass 08.01.14 в 17:42 0
	Следовательно, существует а или b входящие в B\E0 Mark_Krass 08.01.14 в 17:44 0
	Рассмотрим Mark_Krass 08.01.14 в 17:44 0
	случай с AJ (b аналогично). Mark_Krass 08.01.14 в 17:45 0
	По определению M, M \| = а и, следовательно, Mark_Krass 08.01.14 в 17:46 0
	M \|= Ei. Это верно для всех г 2 {1,. . . , т}, М \| = Т. Это завершает доказательство. Mark_Krass 08.01.14 в 17:48 0
	Пример 4.36 Построение доказательства можно проиллюстрировать на следующем примере. Mark_Krass 08.01.14 в 17:49 0
	Мы используем оператор, который отображает переменную х в переменную х0. Пусть T = {A_B ° C, ¬ A_B, ¬ C}. Mark_Krass 08.01.14 в 17:50 0
	Соответствующее факторизованное пространство утверждений Mark_Krass 08.01.14 в 17:52 0
	h {{ b A, b B, b C}, {A, b B,C, b C}, {A, b A,B, b B,C}}, Mark_Krass 06.01.14 в 22:10 0
	Рисунок 4.12: Алгоритм поиска новых верных состояний Mark_Krass 08.01.14 в 17:53 0
	Далее мы приводим алгоритм для построения условных планов. Основной шаг в алгоритме Mark_Krass 08.01.14 в 17:55 0
	это нахождение верного состояния, для которого план может существовать, базируется на наборе верных состояний в Mark_Krass 08.01.14 в 17:57 0
	планах. Mark_Krass 08.01.14 в 17:57 0
	Процедура на рисунке 4.12 выполняет этот шаг: находим множество S состояний, которые не содержатся Mark_Krass 08.01.14 в 18:00 0
	в H и являются сильным прообразом множества S0 состояний в F относительно оператора о. Mark_Krass 08.01.14 в 18:01 0
	Время, необходимое для процедуры увеличивается по экспоненциальному закону, в зависимости от размера F и поглощает линейное пространство размера F. Mark_Krass 08.01.14 в 18:05 0
	Согласно теореме 4.35 это лучший результат, которого можно ожидать (если это не выполнится, то P = NP). Mark_Krass 08.01.14 в 18:07 0
	Лемма 4.37 Вызов процедуры findnew (о,;, Н, Н0) возвращает множество S0, так что S0 = spreimgo (S) Mark_Krass 08.01.14 в 18:14 0
	для некоторого S 2 flat(H) и S0 _ S00 не для S00 2 flat(H0), и возвращает S00 если нет такого множества состояний. Mark_Krass 08.01.14 в 18:18 0
	Доказательство: Процедура проходит по элементам Hs1,. . . , Sni из F1. • • •. Fn и проверяет, входит ли Mark_Krass 08.01.14 в 18:21 0
	spreimgo (S1 [• • • [Sn) в H. Множества S1 [• • • [Sn являются элементами flat(F). Проход Mark_Krass 08.01.14 в 18:26 0
	через F1. • • •. Fn создает дерево поиска с элементами F1, являющимися дочерними элементами корневого Mark_Krass 08.01.14 в 18:28 0
	узла, элементами F2, являющимися дочерними элементами по отношению к элементам F1 и проверяет наличие сильного прообраза. Mark_Krass 08.01.14 в 18:30 0
	Реализация процедуры может быть улучшена во многих аспектах. Наборы f1,. . . , fм можно Mark_Krass 08.01.14 в 18:36 0
	установить в соответствии с мощностями так, что большие прообразы окажутся первыми в очереди и новое верное Mark_Krass 08.01.14 в 18:38 0
	состояние будет найдено раньше. Также другие виды эвристик могут быть применены здесь, например, те, которые Mark_Krass 08.01.14 в 18:40 0
	будут пытаться найти верные состояния ближе к исходному состоянию, например, в соответствии с эвристиками, Mark_Krass 08.01.14 в 18:42 0
	рассмотренными в разделе 4.4.1. Mark_Krass 08.01.14 в 18:42 0
	Определим altimgo(S) как imgo(wpreimgo(S)). Это множество состояний, которые могут быть достигнуты, Mark_Krass 08.01.14 в 18:44 0
	если будет достигнуто состояние S. Сейчас S _ altimgo(S), и для детерминированных операторов Mark_Krass 08.01.14 в 18:45 0
	S = altimgo(S). Mark_Krass 06.01.14 в 21:25 0
	Методы сокращения, основанные на сильных и слабых прообразах, следующие. Mark_Krass 08.01.14 в 15:09 0
	1. Пусть о детерминизированный оператор. Если spreimgo(fi) spreimgo(fj) и i > j, или spreimgo(fi) spreimgo(fj), тогда мы можем игнорировать fi. Mark_Krass 08.01.14 в 19:00 0
	Если сильный прообраз fi меньше чем fj, сильный прообраз который находится с Mark_Krass 08.01.14 в 19:26 0

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

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