El Stanford Research Institute Problem Solver , conocido por sus siglas STRIPS , es un planificador automatizado desarrollado por Richard Fikes y Nils Nilsson en 1971 en SRI International . [1] El mismo nombre se usó más tarde para referirse al lenguaje formal de los insumos de este planificador. Este lenguaje es la base para la mayoría de los lenguajes para expresar casos de problemas de planificación automatizados que se utilizan hoy en día; estos lenguajes se conocen comúnmente como lenguajes de acción . Este artículo solo describe el idioma, no el planificador.
Definición
Una instancia de STRIPS se compone de:
- Un estado inicial;
- La especificación de los estados objetivo: situaciones a las 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 lleve a cabo 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:
- es un conjunto de condiciones (es decir, variables proposicionales );
- 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 convierten en verdaderas por la acción y cuáles son falsas;
- es el estado inicial, dado como el conjunto de condiciones que inicialmente son verdaderas (todas las demás se suponen falsas);
- es la especificación del estado objetivo; esto se da como un par, 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 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 de STRIPS es una función
dónde es el conjunto de todos los subconjuntos de , y es por tanto el conjunto de todos los estados posibles.
La función de transición para un estado , se puede definir de la siguiente manera, utilizando el supuesto simplificador de que las acciones siempre se pueden ejecutar pero no tienen ningún efecto si no se cumplen sus condiciones previas:
= | Si y | |
= | de lo contrario |
La función puede extenderse a secuencias de acciones mediante las siguientes ecuaciones recursivas:
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 de la meta. Formalmente, es un plan para Si cumple las siguientes dos condiciones:
Extensiones
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. , y significa que el robot está en Room1. En este caso, las acciones pueden tener variables libres , que están cuantificadas existencialmente implícitamente. En otras palabras, una acción representa todas las posibles acciones proposicionales que se pueden obtener reemplazando cada variable libre con un valor.
El estado inicial se considera completamente conocido en el lenguaje descrito anteriormente: condiciones que no están en todos se asumen falsos. Esta es a menudo 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 hacer frente a estados iniciales parcialmente conocidos.
Un problema de muestra de STRIPS
Un mono está en la ubicación A en un laboratorio. Hay una caja en la ubicación C. El mono quiere los plátanos que cuelgan del techo en la ubicación B, pero necesita mover la caja y trepar para alcanzarlos.
Estado inicial: En (A), Nivel (bajo), BoxAt (C), BananasAt (B)Estado objetivo: Tener (plátanos)
Comportamiento: // pasar de X a Y _Move (X, Y) _ Condiciones previas: en (X), nivel (bajo) Postcondiciones: no en (X), en (Y) // sube a la caja _ClimbUp (ubicación) _ Condiciones previas: en (ubicación), BoxAt (ubicación), nivel (bajo) Condiciones posteriores: nivel (alto), no nivel (bajo) // baja de la caja _ClimbDown (ubicación) _ Condiciones previas: en (ubicación), BoxAt (ubicación), nivel (alto) Condiciones posteriores: nivel (bajo), no nivel (alto) // mueve el mono y la caja de X a Y _MoveBox (X, Y) _ Condiciones previas: En (X), BoxAt (X), Nivel (bajo) Postcondiciones: BoxAt (Y), no BoxAt (X), At (Y), no At (X) // toma los plátanos _TakeBananas (ubicación) _ Condiciones previas: en (ubicación), bananas en (ubicación), nivel (alto) Postcondiciones: Tener (plátanos)
Complejidad
Decidir si existe algún plan para una instancia de STRIPS proposicional es PSPACE-completo . Se pueden aplicar varias restricciones para decidir si un plan existe en tiempo polinomial o al menos convertirlo en un problema NP-completo . [2]
Operador de 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 súper acció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 macro operadores 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. Similar a la definición dentro de la planificación de la IA, la idea es proporcionar una abstracción temporal (abarcar un período más largo) y modificar el estado del juego directamente en una capa superior. [5]
Ver también
Referencias
- ^ Richard E. Fikes, Nils J. Nilsson (invierno de 1971). "TIRAS: un nuevo enfoque para la aplicación del teorema que demuestra 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 .
- ^ Tom Bylander (septiembre de 1994). "La complejidad computacional de la planificación proposicional STRIPS" . Inteligencia artificial . 69 (1–2): 165–204. CiteSeerX 10.1.1.23.199 . doi : 10.1016 / 0004-3702 (94) 90081-7 .
- ^ 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.
- ^ Schmid, Ute (1999). Macrooperadores iterativos revisados: Aplicación de la síntesis del programa al aprendizaje en la planificación (Informe técnico). Facultad de Ciencias de la Computación de la Universidad Carnegie Mellon. doi : 10.21236 / ada363524 .
- ^ 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 por refuerzo". Inteligencia artificial . Elsevier. 112 (1-2): 181-211. doi : 10.1016 / s0004-3702 (99) 00052-1 .CS1 maint: varios nombres: lista de autores ( enlace )
Otras lecturas
- C. Bäckström y B. Nebel (1995). Resultados de complejidad para la planificación SAS +. Inteligencia computacional , 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 (2a ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-790395-2