Planificación automatizada
La planificación automatizada es la rama de la inteligencia artificial que se ocupa de calcular secuencias de acciones que transforman un estado inicial del mundo en un estado objetivo deseado, dada una descripción formal de las acciones disponibles.
Definition
La planificación automatizada es el cálculo de un plan —un conjunto de acciones ordenado (o parcialmente ordenado)— que logra de manera demostrable un objetivo a partir de un estado inicial, dado un modelo de cómo cada acción cambia el estado del mundo.
Scope
Esta área cubre la representación de problemas de planificación (estados, acciones con precondiciones y efectos, objetivos) y los algoritmos que los resuelven: planificación clásica en dominios deterministas y completamente observables, métodos de grafo de planificación y búsqueda heurística, planificación de redes de tareas jerárquicas, y la extensión al tiempo, los recursos y la programación. Trata formalismos estándar como STRIPS y PDDL y la complejidad de la planificación. La planificación bajo incertidumbre probabilística se conecta con el razonamiento bajo incertidumbre, y el aprendizaje de modelos de acción o políticas a partir de datos pertenece al subcampo del aprendizaje automático.
Sub-topics
Core questions
- ¿Cómo se representan las acciones, los estados y los objetivos de forma lo suficientemente compacta como para describir dominios grandes?
- ¿Cómo se busca el problema de planificación de manera eficiente a pesar de un espacio de estados exponencialmente grande?
- ¿Cómo se derivan heurísticas admisibles e informativas automáticamente a partir de la descripción de un dominio?
- ¿Cómo se pueden estructurar los planes jerárquicamente y cómo se incorporan las restricciones de tiempo y recursos?
Key concepts
- estados, acciones, objetivos
- precondiciones y efectos
- STRIPS y PDDL
- búsqueda en el espacio de estados hacia adelante y hacia atrás
- grafos de planificación
- heurísticas independientes del dominio
- redes de tareas jerárquicas
- planificación temporal y programación
Key theories
- Representación de acciones STRIPS
- El formalismo STRIPS describe las acciones mediante precondiciones y efectos de adición/eliminación sobre un conjunto de proposiciones, proporcionando una representación compacta y factorizada que convierte la planificación en una búsqueda a través de estados simbólicos en lugar de una enumeración de estados explícitos del mundo.
- Búsqueda heurística independiente del dominio para la planificación
- Los planificadores modernos conciben la planificación como una búsqueda heurística y derivan heurísticas automáticamente de la descripción del problema, por ejemplo, ignorando los efectos de eliminación o explotando la estructura causal, lo que permite un rendimiento general sólido.
- La planificación como una jerarquía de clases de problemas
- La planificación abarca un espectro desde la planificación clásica determinista hasta variantes jerárquicas, temporales y con restricciones de recursos, cada una con representaciones y complejidad características, organizadas en la teoría estándar de la planificación automatizada.
Clinical relevance
La planificación automatizada se aplica en robótica y sistemas autónomos, operaciones de naves espaciales y misiones, logística y cadenas de suministro, fabricación y generación de juegos y narrativas; los planificadores derivados de estas técnicas han controlado naves espaciales autónomas reales y coordinan flujos de trabajo complejos.
History
La planificación automatizada comenzó con STRIPS para el robot Shakey en SRI alrededor de 1971, enmarcando la planificación como una demostración de teoremas sobre descripciones de acciones. El campo progresó a través de la planificación de orden parcial, el avance de Graphplan (1995) y el surgimiento de planificadores de búsqueda heurística rápidos e independientes del dominio y el estándar PDDL desde finales de la década de 1990 en adelante, seguido a través de las Competiciones Internacionales de Planificación.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- ¿En qué se diferencia la planificación automatizada de la búsqueda general?
- La planificación automatizada es una forma de búsqueda, pero funciona a partir de una descripción declarativa y factorizada de las acciones (precondiciones y efectos) en lugar de una función sucesora opaca. Esta estructura permite a los planificadores derivar heurísticas automáticamente y razonar sobre qué acciones son relevantes, lo que la búsqueda genérica no puede hacer.
- ¿Qué es PDDL?
- PDDL, el Lenguaje de Definición de Dominio de Planificación, es un lenguaje estándar para describir dominios y problemas de planificación: objetos, predicados, acciones, el estado inicial y el objetivo. Permite comparar planificadores independientes del dominio en un punto de referencia común, como en las Competiciones Internacionales de Planificación.