Solucionador de problemas del Instituto de Investigación de Stanford

El Solucionador de Problemas del Instituto de Investigación de Stanford , conocido por sus siglas STRIPS , es un planificador automatizado desarrollado por Richard Fikes y Nils Nilsson en 1971 en SRI International . ^{[ 1 ]} Posteriormente, este mismo nombre se utilizó para referirse al lenguaje formal de las entradas de este planificador. Este lenguaje es la base de la mayoría de los lenguajes que se utilizan hoy en día para expresar instancias de problemas de planificación automatizada ; dichos lenguajes se conocen comúnmente como lenguajes de acción . Este artículo solo describe el lenguaje, no el planificador.

Una instancia de STRIPS se compone de:

• Un estado inicial;
• La especificación del objetivo establece las situaciones que el planificador intenta alcanzar;
• Un conjunto de acciones. Para cada acción, se incluyen los siguientes elementos:
  • condiciones previas (lo que debe establecerse antes de realizar la acción);
  • postcondiciones (lo que se establece después de que se realiza la acción).

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

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 una cuádrupla.${\displaystyle \langle \alpha,\beta,\gamma,\delta \rangle}$, 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;
3. ${\displaystyle I}$es el estado inicial, dado como el conjunto de condiciones que son inicialmente verdaderas (todas las demás se consideran falsas);
4. ${\displaystyle G}$es la especificación del estado objetivo; esto se da como un par${\displaystyle \langle N,M\rangle }$, que especifican qué condiciones son verdaderas y falsas, respectivamente, para que un estado se considere un estado objetivo.

Un plan para una instancia de planificación de este tipo es una secuencia de operadores que se pueden ejecutar 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 mapea 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${\displaystyle \langle P,O,I,G\rangle }$es una función

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

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

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

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

${\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 tal que el estado que resulta de ejecutar las acciones en orden desde el estado inicial satisface las condiciones objetivo. Formalmente,${\displaystyle [a_{1},a_{2},\ldots ,a_{n}]}$es un plan para${\displaystyle G=\langle N,M\rangle }$si${\displaystyle F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])}$satisface las dos condiciones siguientes:

${\displaystyle N\subsetequ F}$

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

El lenguaje anterior es en realidad la versión proposicional de STRIPS; en la práctica, las condiciones a menudo se refieren a objetos: por ejemplo, que la posición de un robot puede ser modelada por un predicado.${\displaystyle En}$, y${\displaystyle En(habitación1)}$Esto significa que el robot está en la Habitación 1. En este caso, las acciones pueden tener variables libres , las cuales se cuantifican existencialmente de forma implícita. En otras palabras, una acción representa todas las acciones proposicionales posibles que se pueden obtener al reemplazar cada variable libre con un valor.

El estado inicial se considera completamente conocido en el lenguaje descrito anteriormente: condiciones que no están en${\displaystyle I}$Se asume que todas 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 por completo. Se han desarrollado extensiones de STRIPS para abordar estados iniciales parcialmente conocidos.

Un mono se encuentra en el punto A de un laboratorio. En el punto C hay una caja. El mono quiere los plátanos que cuelgan del techo en el punto B, pero necesita mover la caja y subirse 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 At(X), At(Y) // subirse a la caja _Subir(Ubicación)_ Precondiciones: En(Ubicación), CajaEn(Ubicación), Nivel(bajo) Postcondiciones: Nivel(alto), no Nivel(bajo) // bajar de la caja _Descender(Ubicación)_ Precondiciones: En(Ubicación), CajaEn(Ubicación), Nivel(alto) Postcondiciones: Nivel(bajo), no Nivel(alto) // mover el mono y la caja de X a Y _MoverCaja(X, Y)_ Precondiciones: At(X), BoxAt(X), Level(low) Postcondiciones: BoxAt(Y), no BoxAt(X), At(Y), no At(X) // toma los plátanos _TakeBananas(Ubicación)_ Precondiciones: En(Ubicación), PlátanosEn(Ubicación), Nivel(alto) Postcondiciones: Tener(plátanos)

Decidir si existe algún plan para una instancia proposicional de STRIPS es PSPACE-completo . Se pueden imponer diversas restricciones para decidir si existe un plan en tiempo polinomial o, al menos, convertirlo en un problema NP-completo . ^{[ 2 ]}

En el problema del mono y el plátano , el mono robot debe ejecutar una secuencia de acciones para alcanzar el plátano en el techo. Una sola acción produce 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 reglas normal. ^{[ 3 ]} La superacción consta de 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 puede realizarse mediante programación genética . ^{[ 4 ]} La idea no es planificar el dominio en sí, sino que, en la etapa previa, se crea una heurística que permite resolverlo mucho más rápido. En el contexto del aprendizaje por refuerzo , un macrooperador se denomina opción. De forma similar a la definición en la planificación de IA, la idea es proporcionar una abstracción temporal (que abarca un período más largo) y modificar el estado del juego directamente en una capa superior. ^{[ 5 ]}

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

• C. Bäckström y B. Nebel (1995). Resultados de complejidad para la planificación de SAS+. Inteligencia Computacional , 11:625-656.
• T. Bylander (1991). Resultados de complejidad para la planificación. En Actas de la Duodécima Conferencia Internacional Conjunta 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