Solucionador de problemas del Instituto de Investigación de Stanford

El solucionador de problemas del Stanford Research Institute , conocido por su acrónimo STRIPS , es un planificador automatizado desarrollado por Richard Fikes y Nils Nilsson en 1971 en SRI International . ^[1] El mismo nombre se utilizó más tarde para referirse al lenguaje formal de las entradas a este planificador. Este lenguaje es la base de la mayoría de los lenguajes para expresar instancias de problemas de planificación automatizada en uso hoy en día; dichos lenguajes se conocen comúnmente como lenguajes de acción . Este artículo solo describe el lenguaje, no el planificador.

Definición

Una instancia de STRIPS se compone de:

• Un estado inicial;
• La especificación del objetivo establece situaciones que el planificador está tratando de alcanzar;
• Un conjunto de acciones. Para cada acción se incluye lo siguiente:
  • condiciones previas (lo que debe establecerse antes de que se realice la acción);
  • postcondiciones (lo que se establece después de que se realiza la acción).

Matemáticamente, una instancia de STRIPS es un cuádruple , en el que cada componente tiene el siguiente significado: ${\displaystyle \langle P,O,I,G\rangle }$

1. ${\displaystyle P}$es un conjunto de condiciones (es decir, variables proposicionales );
2. ${\displaystyle O}$es un conjunto de operadores (es decir, acciones); cada operador es en sí mismo un cuádruple , siendo cada elemento un conjunto de condiciones. Estos cuatro conjuntos especifican, en orden, qué condiciones deben ser verdaderas para que la acción sea ejecutable, cuáles deben ser falsas, cuáles se vuelven verdaderas por la acción y cuáles se vuelven falsas; ${\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle }$
3. ${\displaystyle I}$es el estado inicial, dado como el conjunto de condiciones que son inicialmente verdaderas (se supone que todas las demás son falsas);
4. ${\displaystyle G}$es la especificación del estado objetivo; se proporciona como un par , que especifica qué condiciones son verdaderas y falsas, respectivamente, para que un estado se considere un estado objetivo. ${\displaystyle \langle N,M\rangle }$

Un plan para tal instancia de planificación es una secuencia de operadores que pueden ejecutarse desde el estado inicial y que conduce a un estado objetivo.

Formalmente, un estado es un conjunto de condiciones: un estado está representado por el conjunto de condiciones que son verdaderas en él. Las transiciones entre estados se modelan mediante una función de transición, que es una función que asigna estados a nuevos estados que resultan de la ejecución de acciones. Dado que los estados están representados por conjuntos de condiciones, la función de transición relativa a la instancia STRIPS es una función ${\displaystyle \langle P,O,I,G\rangle }$

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

donde es el conjunto de todos los subconjuntos de , y por lo tanto es el conjunto de todos los estados posibles. ${\displaystyle 2^{P}}$ ${\displaystyle P}$

La función de transición de un estado se puede definir de la siguiente manera, utilizando el supuesto simplificador de que las acciones siempre se pueden ejecutar pero no tienen efecto si no se cumplen sus condiciones previas: ${\displaystyle \operatorname {succ} }$ ${\displaystyle C\subseteq P}$

La función se puede extender a secuencias de acciones mediante las siguientes ecuaciones recursivas: ${\displaystyle \operatorname {succ} }$

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

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

Un plan para una instancia de STRIPS es una secuencia de acciones de modo que el estado que resulta de ejecutar las acciones en orden a partir del estado inicial satisfaga las condiciones del objetivo. Formalmente, es un plan para si satisface las dos condiciones siguientes: ${\displaystyle [a_{1},a_{2},\ldots ,a_{n}]}$ ${\displaystyle G=\langle N,M\rangle }$ ${\displaystyle F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])}$

${\displaystyle N\subseteq F}$

${\displaystyle M\cap F=\varnothing }$

Extensiones

El lenguaje anterior es en realidad la versión proposicional de STRIPS; en la práctica, las condiciones suelen referirse a objetos: por ejemplo, que la posición de un robot se puede modelar mediante un predicado , y significa que el robot está en Room1. En este caso, las acciones pueden tener variables libres , que se cuantifican existencialmente de manera implícita. En otras palabras, una acción representa todas las posibles acciones proposicionales que se pueden obtener al reemplazar cada variable libre por un valor. ${\displaystyle At}$ ${\displaystyle At(room1)}$

En el lenguaje descrito anteriormente, el estado inicial se considera completamente conocido: se supone que todas las condiciones que no se cumplen son falsas. Esta suele ser una suposición limitante, ya que existen ejemplos naturales de problemas de planificación en los que el estado inicial no se conoce completamente. Se han desarrollado extensiones de STRIPS para tratar estados iniciales parcialmente conocidos. ${\displaystyle I}$

Un ejemplo de problema de TIRAS

Un mono se encuentra en el lugar A de un laboratorio. Hay una caja en el lugar C. El mono quiere los plátanos que cuelgan del techo en el lugar B, pero necesita mover la caja y treparse a ella para alcanzarlos.

Estado inicial: En(A), Nivel(bajo), CajaEn(C), PlátanosEn(B)Estado objetivo: Tener (plátanos)

Comportamiento: // moverse de X a Y _Mover(X, Y)_ Precondiciones: En (X), Nivel (bajo) Postcondiciones: no En(X), En(Y)  // subirse a la caja _Subir Arriba(Ubicación)_ Precondiciones: At(Ubicación), BoxAt(Ubicación), Nivel(bajo) Postcondiciones: Nivel(alto), no Nivel(bajo)  //baja de la caja _ClimbDown(Ubicación)_ Precondiciones: At(Ubicación), BoxAt(Ubicación), Nivel(alto) Postcondiciones: Nivel(bajo), no Nivel(alto)  // mover el mono y la caja de X a Y _MoverCuadro(X, Y)_ Precondiciones: At(X), BoxAt(X), Nivel(bajo) Poscondiciones: BoxAt(Y), no BoxAt(X), At(Y), no At(X)  //toma los plátanos _TakeBananas(Ubicación)_ Precondiciones: En(Ubicación), BananasEn(Ubicación), Nivel(alto) Postcondiciones: Tener (plátanos)

Complejidad

Decidir si existe un plan para una instancia proposicional de STRIPS es PSPACE-completo . Se pueden aplicar varias restricciones para decidir si existe un plan en tiempo polinomial o al menos convertirlo en un problema NP-completo . ^[2]

Operador macro

En el problema del mono y el plátano , el mono robot tiene que ejecutar una secuencia de acciones para alcanzar el plátano en el techo. Una sola acción proporciona un pequeño cambio en el juego. Para simplificar el proceso de planificación, tiene sentido inventar una acción abstracta, que no está disponible en la descripción de la regla normal. ^[3] La superacción consiste en acciones de bajo nivel y puede alcanzar objetivos de alto nivel. La ventaja es que la complejidad computacional es menor y el solucionador puede planificar tareas más largas.

La identificación de nuevos macrooperadores para un dominio se puede realizar con programación genética . ^[4] La idea no es planificar el dominio en sí, sino que en el paso previo se crea una heurística que permite resolver el dominio mucho más rápido. En el contexto del aprendizaje por refuerzo , un macrooperador se denomina opción. De manera similar a la definición dentro de la planificación de IA, la idea es proporcionar una abstracción temporal (que abarque un período más largo) y modificar el estado del juego directamente en una capa superior. ^[5]

Véase también

• Lenguaje de descripción de acciones (ADL)
• Planificación automatizada
• Red de tareas jerárquica
• Lenguaje de definición del dominio de planificación (PDDL)
• Anomalía de Sussman

Referencias

1. Richard E. Fikes, Nils J. Nilsson (invierno de 1971). "STRIPS: un nuevo enfoque para la aplicación de la demostración de teoremas a la resolución de problemas" (PDF) . Inteligencia artificial . 2 (3–4): 189–208. CiteSeerX  10.1.1.78.8292 . doi :10.1016/0004-3702(71)90010-5. S2CID  8623866.
2. Tom Bylander (septiembre de 1994). "La complejidad computacional de la planificación STRIPS proposicional". Inteligencia artificial . 69 (1–2): 165–204. CiteSeerX 10.1.1.23.199 . doi :10.1016/0004-3702(94)90081-7. 
3. Haslum, Patrik (2007). Reducción de la complejidad accidental en problemas de planificación . Actas de la 20.ª Conferencia conjunta internacional sobre inteligencia artificial. págs. 1898-1903.
4. Schmid, Ute (1999). Macrooperadores iterativos revisitados: aplicación de la síntesis de programas al aprendizaje en la planificación (informe técnico). Facultad de Ciencias de la Computación, Universidad Carnegie Mellon. doi : 10.21236/ada363524 .
5. Sutton, Richard S y Precup, Doina y Singh, Satinder (1999). "Entre MDP y semi-MDP: un marco para la abstracción temporal en el aprendizaje de refuerzo". Inteligencia artificial . 112 (1–2). Elsevier: 181–211. doi : 10.1016/s0004-3702(99)00052-1 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

Lectura adicional

• C. Bäckström y B. Nebel (1995). Resultados de complejidad para la planificación SAS+. Computational Intelligence , 11:625-656.
• T. Bylander (1991). Resultados de complejidad para la planificación. En Actas de la Duodécima Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI'91) , páginas 274-279.
• Russell, Stuart J. ; Norvig, Peter (2003), Inteligencia artificial: un enfoque moderno (2.ª ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-790395-2