Решение проблем Стэнфордского исследовательского института

, Решение проблем Стэнфордского исследовательского института известное под аббревиатурой STRIPS , представляет собой автоматизированный планировщик, разработанный Ричардом Файксом и Нильсом Нильссоном в 1971 году в SRI International . ^[1] Это же имя позже использовалось для обозначения формального языка входных данных этого планировщика. Этот язык является основой для большинства языков для описания примеров задач автоматизированного планирования , используемых сегодня; такие языки широко известны как языки действий . В этой статье описывается только язык, а не планировщик.

Определение [ править ]

Экземпляр STRIPS состоит из:

Исходное состояние;
В спецификации цели указываются ситуации, которых планировщик пытается достичь;
Набор действий. Для каждого действия предусмотрено следующее:
- предпосылки (то, что должно быть установлено до совершения действия);
- постусловия (то, что устанавливается после совершения действия).

Математически экземпляр STRIPS представляет собой четверку $\langle P,O,I,G\rangle$ , в котором каждый компонент имеет следующее значение:

$P$ представляет собой набор условий (т.е. пропозициональных переменных );
$O$ представляет собой набор операторов (т.е. действий); каждый оператор сам по себе является четверкой $\langle \alpha ,\beta ,\gamma ,\delta \rangle$ , каждый элемент представляет собой набор условий. Эти четыре набора по порядку определяют, какие условия должны быть истинными, чтобы действие было исполняемым, какие из них должны быть ложными, какие из них становятся истинными в результате действия, а какие — ложными;
$I$ — начальное состояние, заданное как набор условий, которые изначально истинны (все остальные считаются ложными);
$G$ — спецификация целевого состояния; это дано как пара $\langle N,M\rangle$ , которые определяют, какие условия являются истинными и ложными соответственно, чтобы состояние считалось целевым состоянием.

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

Формально состояние представляет собой набор условий: состояние представлено набором условий, которые в нем истинны. Переходы между состояниями моделируются функцией перехода, которая представляет собой функцию, отображающую состояния в новые состояния, возникающие в результате выполнения действий. Поскольку состояния представлены наборами условий, функция перехода относительно экземпляра STRIPS $\langle P,O,I,G\rangle$ это функция

\operatorname {succ} :2^{P}\times O\rightarrow 2^{P},

где $2^{P}$ представляет собой совокупность всех подмножеств $P$ , и, следовательно, представляет собой набор всех возможных состояний.

Функция перехода $\operatorname {succ}$ для государства $C\subseteq P$ , можно определить следующим образом, используя упрощающее предположение, что действия всегда могут выполняться, но не иметь эффекта, если их предварительные условия не выполнены:

$\operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )$	= $(C\backslash \delta )\cup \gamma$	если $\alpha \subseteq C$ и $\beta \cap C=\varnothing$
	= $C$	в противном случае

Функция $\operatorname {succ}$ можно распространить на последовательности действий с помощью следующих рекурсивных уравнений:

\operatorname {succ} (C,[\ ])=C

\operatorname {succ} (C,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])

План для экземпляра STRIPS — это последовательность действий, при которой состояние, возникающее в результате выполнения действий по порядку из исходного состояния, удовлетворяет целевым условиям. Формально, $[a_{1},a_{2},\ldots ,a_{n}]$ это план для $G=\langle N,M\rangle$ если $F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])$ удовлетворяет следующим двум условиям:

N\subseteq F

M\cap F=\varnothing

Расширения [ править ]

Вышеупомянутый язык на самом деле является пропозициональной версией STRIPS; на практике условия часто связаны с объектами: например, положение робота можно смоделировать с помощью предиката $At$ , и $At(room1)$ означает, что робот находится в Room1. В этом случае действия могут иметь свободные переменные , которые неявно экзистенциально квантифицированы. Другими словами, действие представляет собой все возможные пропозициональные действия, которые можно получить, заменив каждую свободную переменную значением.

Начальное состояние считается полностью известным на описанном выше языке: состояния, которых нет в $I$ все считаются ложными. Часто это ограничивающее предположение, поскольку существуют естественные примеры задач планирования, в которых исходное состояние не полностью известно. Расширения STRIPS были разработаны для работы с частично известными начальными состояниями.

Пример задачи STRIPS [ править ]

Обезьяна находится в точке А в лаборатории. В локации C есть коробка. Обезьянке нужны бананы, свисающие с потолка в локации B, но ей нужно передвинуть коробку и залезть на нее, чтобы добраться до них.

Initial state: At(A), Level(low), BoxAt(C), BananasAt(B)
Goal state:    Have(bananas)

Actions:
               // move from X to Y
               _Move(X, Y)_
               Preconditions:  At(X), Level(low)
               Postconditions: not At(X), At(Y)
               
               // climb up on the box
               _ClimbUp(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(low)
               Postconditions: Level(high), not Level(low)
               
               // climb down from the box
               _ClimbDown(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(high)
               Postconditions: Level(low), not Level(high)
               
               // move monkey and box from X to Y
               _MoveBox(X, Y)_
               Preconditions:  At(X), BoxAt(X), Level(low)
               Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
               
               // take the bananas
               _TakeBananas(Location)_
               Preconditions:  At(Location), BananasAt(Location), Level(high)
               Postconditions: Have(bananas)

Сложность [ править ]

Решение о том, существует ли какой-либо план для пропозиционального экземпляра STRIPS, является PSPACE-полным . Могут быть наложены различные ограничения, чтобы решить, существует ли план за полиномиальное время или, по крайней мере, сделать его NP-полной задачей. ^[2]

Макрооператор [ править ]

В задаче об обезьяне и банане робот-обезьяна должна выполнить последовательность действий, чтобы добраться до банана на потолке. Одно действие вносит небольшие изменения в игру. Чтобы упростить процесс планирования, имеет смысл придумать абстрактное действие, которого нет в обычном описании правила. ^[3] Супердействие состоит из действий низкого уровня и может достигать целей высокого уровня. Преимущество состоит в том, что вычислительная сложность ниже, и решатель может планировать более длинные задачи.

Идентификацию новых макрооператоров для домена можно реализовать с помощью генетического программирования . ^[4] Идея состоит в том, чтобы не планировать саму предметную область, а на предварительном этапе создается эвристика, которая позволяет решать предметную область гораздо быстрее. В контексте обучения с подкреплением макрооператор называется опцией. Подобно определению в планировании ИИ, идея состоит в том, чтобы обеспечить временную абстракцию (охватить более длительный период) и изменить состояние игры непосредственно на более высоком уровне. ^[5]

См. также [ править ]

Ссылки [ править ]

^ Ричард Э. Файкс, Нильс Дж. Нильссон (зима 1971 г.). «STRIPS: новый подход к применению доказательства теорем к решению задач» (PDF) . Искусственный интеллект . 2 (3–4): 189–208. CiteSeerX 10.1.1.78.8292 . дои : 10.1016/0004-3702(71)90010-5 . S2CID 8623866 .
^ Том Байландер (сентябрь 1994 г.). «Вычислительная сложность планирования пропозициональных STRIPS» . Искусственный интеллект . 69 (1–2): 165–204. CiteSeerX 10.1.1.23.199 . дои : 10.1016/0004-3702(94)90081-7 .
^ Хаслум, Патрик (2007). Уменьшение случайной сложности в задачах планирования . Материалы 20-й Международной совместной конференции по искусственному интеллекту. стр. 1898–1903.
^ Шмид, Юте (1999). Возвращение к итеративным макрооператорам: применение синтеза программ к обучению при планировании (технический отчет). Школа компьютерных наук Университета Карнеги-Меллон. дои : 10.21236/ada363524 .
^ Саттон, Ричард С. и Прекап, Дойна и Сингх, Сатиндер (1999). «Между MDP и полу-MDP: основа временной абстракции в обучении с подкреплением» . Искусственный интеллект . 112 (1–2). Эльзевир: 181–211. дои : 10.1016/s0004-3702(99)00052-1 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

Дальнейшее чтение [ править ]

К. Бэкстрем и Б. Небель (1995). Результаты по сложности планирования SAS+. Вычислительный интеллект , 11:625-656.
Т. Байландер (1991). Результаты по сложности для планирования. В материалах двенадцатой международной совместной конференции по искусственному интеллекту (IJCAI'91) , страницы 274–279.
Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Аппер-Сэдл-Ривер, Нью-Джерси: Прентис-Холл, ISBN 0-13-790395-2

[1] Ричард Э. Файкс, Нильс Дж. Нильссон (зима 1971 г.). «STRIPS: новый подход к применению доказательства теорем к решению задач» (PDF) . Искусственный интеллект . 2 (3–4): 189–208. CiteSeerX 10.1.1.78.8292 . дои : 10.1016/0004-3702(71)90010-5 . S2CID 8623866 .

[2] Том Байландер (сентябрь 1994 г.). «Вычислительная сложность планирования пропозициональных STRIPS» . Искусственный интеллект . 69 (1–2): 165–204. CiteSeerX 10.1.1.23.199 . дои : 10.1016/0004-3702(94)90081-7 .

[3] Хаслум, Патрик (2007). Уменьшение случайной сложности в задачах планирования . Материалы 20-й Международной совместной конференции по искусственному интеллекту. стр. 1898–1903.

[4] Шмид, Юте (1999). Возвращение к итеративным макрооператорам: применение синтеза программ к обучению при планировании (технический отчет). Школа компьютерных наук Университета Карнеги-Меллон. дои : 10.21236/ada363524 .

[5] Саттон, Ричард С. и Прекап, Дойна и Сингх, Сатиндер (1999). «Между MDP и полу-MDP: основа временной абстракции в обучении с подкреплением» . Искусственный интеллект . 112 (1–2). Эльзевир: 181–211. дои : 10.1016/s0004-3702(99)00052-1 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]