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

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

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

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

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

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

${\ displaystyle P}$ набор условий (т. е. пропозициональных переменных );
${\ displaystyle O}$ набор операторов (т. е. действий); каждый оператор сам по себе является четверкой , каждый элемент представляет собой набор условий. Эти четыре набора определяют по порядку, какие условия должны быть истинными для выполнения действия, какие из них должны быть ложными, какие становятся истинными в результате действия, а какие - ложными; ${\ displaystyle \ langle \ alpha, \ beta, \ gamma, \ delta \ rangle}$
${\ displaystyle I}$ - начальное состояние, заданное как набор условий, которые изначально истинны (все остальные считаются ложными);
${\ displaystyle 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 - это последовательность действий, такая, что состояние, являющееся результатом выполнения действий по порядку от начального состояния, удовлетворяет целевым условиям. Формально это план if, удовлетворяющий следующим двум условиям: $[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; на практике условия часто связаны с объектами: например, положение робота может быть смоделировано с помощью предиката и означает, что робот находится в Комнате1. В этом случае действия могут иметь свободные переменные , которые неявно оцениваются количественно. Другими словами, действие представляет все возможные пропозициональные действия, которые могут быть получены путем замены каждой свободной переменной значением. $At$ $At(room1)$

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

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

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

Исходное состояние: At (A), Level (low), BoxAt (C), BananasAt (B)Состояние цели: есть (бананы)

Действия: // переходим от X к Y _Перемещение (X, Y) _ Предпосылки: На (X), Уровень (низкий) Постусловия: не At (X), At (Y)  // залезаем на ящик _ClimbUp (Местоположение) _ Предпосылки: В (Местоположение), BoxAt (Местоположение), Уровень (низкий) Постусловия: Уровень (высокий), а не Уровень (низкий)  // спускаемся из коробки _ClimbDown (Местоположение) _ Предпосылки: В (Местоположение), BoxAt (Местоположение), Уровень (высокий) Постусловия: Уровень (низкий), а не Уровень (высокий)  // перемещаем обезьяну и коробку с X на Y _MoveBox (X, Y) _ Предпосылки: At (X), BoxAt (X), Level (низкий) Постусловия: BoxAt (Y), а не BoxAt (X), At (Y), не At (X)  // берем бананы _TakeBananas (Расположение) _ Предпосылки: В (Местоположение), BananasAt (Местоположение), Уровень (высокий) Постусловия: есть (бананы)

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

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

Оператор макроса [ править ]

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

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

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

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

^ Ричард Э. Файкс, Нильс Дж. Нильссон (зима 1971). «ПОЛОСЫ: новый подход к применению доказательства теорем для решения проблем» (PDF) . Искусственный интеллект . 2 (3–4): 189–208. CiteSeerX 10.1.1.78.8292 . DOI : 10.1016 / 0004-3702 (71) 90010-5 .
^ Тот Bylander (сентябрь 1994). "Вычислительная сложность пропозиционального планирования STRIPS" . Искусственный интеллект . 69 (1-2): 165-204. CiteSeerX 10.1.1.23.199 . DOI : 10.1016 / 0004-3702 (94) 90081-7 .
^ Haslum, Patrik (2007). Снижение случайной сложности при планировании задач . Материалы 20-й Международной совместной конференции по искусственному интеллекту. С. 189–903.
Перейти ↑ Schmid, Ute (1999). Повторение итерационных макрооператоров: применение синтеза программ к обучению при планировании (Технический отчет). Школа компьютерных наук Университета Карнеги-Меллона. DOI : 10.21236 / ada363524 .
^ Саттон, Ричард С. и Прекап, Дойна и Сингх, Сатиндер (1999). «Между MDP и полу-MDP: структура временной абстракции в обучении с подкреплением». Искусственный интеллект . Эльзевир. 112 (1–2): 18–11. DOI : 10.1016 / s0004-3702 (99) 00052-1 .CS1 maint: multiple names: authors list (link)

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

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

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

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

[3] Haslum, Patrik (2007). Снижение случайной сложности при планировании задач . Материалы 20-й Международной совместной конференции по искусственному интеллекту. С. 189–903.

[4] Перейти ↑ Schmid, Ute (1999). Повторение итерационных макрооператоров: применение синтеза программ к обучению при планировании (Технический отчет). Школа компьютерных наук Университета Карнеги-Меллона. DOI : 10.21236 / ada363524 .

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

[1]