Planificación Clásica y STRIPS
La planificación clásica aborda el problema de encontrar una secuencia de acciones para alcanzar un objetivo en un entorno determinista, completamente observable y estático, utilizando la representación factorizada de acciones al estilo STRIPS mediante precondiciones y efectos.
Definition
La planificación clásica busca una secuencia de acciones deterministas que transforme un estado inicial completamente conocido en un estado que satisfaga el objetivo, donde cada acción se describe por las condiciones que deben cumplirse para que se aplique y los cambios que realiza.
Scope
Este tema cubre el modelo de planificación clásica y sus suposiciones (acciones deterministas, observabilidad completa, un solo agente, tiempo atómico), las representaciones STRIPS y ADL/PDDL de estados y acciones, los métodos básicos de solución de búsqueda en el espacio de estados hacia adelante (progresión) y hacia atrás (regresión) y la planificación de orden parcial, y la complejidad computacional de la planificación proposicional. La guía heurística y los grafos de planificación se tratan en el tema relacionado, y las variantes no deterministas o probabilísticas están fuera del alcance.
Core questions
- ¿Qué suposiciones definen el modelo de planificación clásica y cuándo son apropiadas?
- ¿Cómo factoriza la representación STRIPS un estado en proposiciones y una acción en precondiciones y efectos de adición/eliminación?
- ¿En qué se diferencian la búsqueda de progresión y regresión como estrategias de planificación?
- ¿Qué tan computacionalmente difícil es la planificación clásica en general?
Key concepts
- modelo determinista, completamente observable
- precondiciones y efectos STRIPS
- listas de adición y eliminación
- PDDL y ADL
- búsqueda de progresión (hacia adelante)
- búsqueda de regresión (hacia atrás)
- planificación de orden parcial
- complejidad de la existencia del plan
Key theories
- Representación STRIPS
- STRIPS describe el mundo como un conjunto de proposiciones verdaderas y cada acción mediante una lista de precondiciones más listas de adición y eliminación, de modo que aplicar una acción simplemente añade y elimina proposiciones; este modelo factorizado es la base de casi todos los planificadores clásicos.
- Búsqueda de progresión y regresión
- Los planes clásicos se pueden encontrar buscando hacia adelante desde el estado inicial aplicando acciones aplicables (progresión) o hacia atrás desde el objetivo calculando subobjetivos regresados (regresión), con la planificación de orden parcial relajando el compromiso con un orden total de acciones.
- Complejidad de la planificación
- Decidir si existe un plan STRIPS proposicional es PSPACE-completo en general, lo que explica formalmente por qué la planificación es difícil y motiva métodos heurísticos y estructurales para hacerla práctica.
Clinical relevance
Las representaciones de planificación clásica son la interfaz común para la planificación de tareas de robots, el ensamblaje automatizado y la logística, y cualquier aplicación donde las acciones deterministas deben secuenciarse para alcanzar un objetivo; los planificadores clásicos basados en PDDL son las herramientas principales del campo y de las Competiciones Internacionales de Planificación.
History
STRIPS fue desarrollado en SRI alrededor de 1971 para controlar el robot Shakey, introduciendo el modelo de acción de precondición/efecto que define la planificación clásica. La planificación de orden parcial maduró en las décadas de 1970 y 1980, Bylander estableció la PSPACE-completitud de la planificación proposicional en 1994, y el estándar PDDL unificó posteriormente los puntos de referencia del campo.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Tom Bylander
- Earl D. Sacerdoti
Related topics
Seminal works
- fikes1971
- bylander1994
Frequently asked questions
- ¿Cuáles son las suposiciones de la planificación clásica?
- La planificación clásica asume un solo agente actuando en un entorno determinista, completamente observable y estático, con acciones que toman una unidad de tiempo y un estado inicial completamente conocido. Relajar cualquiera de estas suposiciones, por ejemplo, permitiendo incertidumbre o concurrencia, conduce a problemas de planificación más ricos más allá del modelo clásico.
- ¿Qué significan la lista de adición y la lista de eliminación de STRIPS?
- Cuando se aplica una acción STRIPS, las proposiciones en su lista de adición se vuelven verdaderas y las de su lista de eliminación se vuelven falsas; todas las demás proposiciones permanecen sin cambios. Esta sencilla regla de actualización es lo que hace de STRIPS una representación compacta y computacionalmente conveniente de cómo las acciones cambian el mundo.