Planificación y Programación Temporal
La planificación y programación temporal extienden la planificación para manejar acciones que toman tiempo, pueden ejecutarse concurrentemente y consumen recursos limitados, produciendo planes que especifican no solo qué hacer, sino también cuándo hacerlo.
Definition
La planificación temporal produce un plan en el que las acciones tienen duraciones y pueden superponerse, sujetas a restricciones temporales y de recursos; la programación asigna tiempos de inicio (y recursos) a un conjunto de actividades para que se satisfagan todas las restricciones, como el orden, los plazos y las capacidades.
Scope
Este tema abarca la planificación y programación con tiempo y recursos explícitos: acciones durativas, concurrencia y restricciones temporales, la representación y solución de redes de restricciones temporales (como el problema temporal simple) y el álgebra de intervalos de Allen, y la integración de la planificación con la programación de actividades con recursos restringidos. Aborda cómo se razona sobre la viabilidad temporal y de recursos junto con la selección de acciones. La planificación clásica pura sin recursos se trata en los temas relacionados.
Core questions
- ¿Cómo se representan las acciones durativas y sus condiciones de inicio y fin?
- ¿Cómo se modelan las restricciones temporales entre eventos y se verifica su consistencia?
- ¿Cómo se asignan los recursos limitados entre actividades concurrentes?
- ¿Cómo se combinan o separan la planificación (decidir qué acciones) y la programación (decidir cuándo)?
Key concepts
- acciones durativas
- concurrencia y superposición
- restricciones temporales
- problema temporal simple
- álgebra de intervalos de Allen
- restricciones de recursos
- programación
- plazos y makespan
Key theories
- Redes de restricciones temporales
- Las restricciones temporales cuantitativas entre puntos de tiempo pueden representarse como una red cuya consistencia y límites más ajustados se calculan eficientemente para el problema temporal simple, proporcionando la columna vertebral del razonamiento temporal de muchos planificadores y programadores.
- Álgebra de intervalos para el tiempo cualitativo
- El álgebra de intervalos de Allen captura las posibles relaciones cualitativas entre intervalos de tiempo (antes, durante, se superpone, etc.) y apoya el razonamiento sobre el conocimiento temporal cuando se desconocen los tiempos exactos.
- Integración de la planificación con la programación
- Los problemas realistas requieren elegir acciones y asignarles tiempos y recursos conjuntamente; la teoría de la planificación automatizada trata las acciones durativas, la concurrencia y las restricciones de recursos como extensiones que acoplan la selección de acciones con la programación basada en restricciones.
Clinical relevance
La planificación y programación temporal son esenciales en operaciones de naves espaciales y rovers, programación de fabricación y proyectos, transporte y programación de tripulaciones, y en cualquier entorno donde se deban coordinar actividades temporizadas, concurrentes y con recursos limitados; dichos sistemas han planificado operaciones para misiones espaciales reales.
History
El razonamiento temporal cualitativo fue formalizado por el álgebra de intervalos de Allen (1983), y las redes de restricciones temporales cuantitativas por Dechter, Meiri y Pearl (1991). Estos fundamentos, junto con los modelos de acciones durativas añadidos a PDDL a principios de la década de 2000, permitieron el desarrollo de planificadores temporales utilizados en aplicaciones como el control autónomo de naves espaciales.
Key figures
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
Related topics
Seminal works
- dechter1991
- allen1983
Frequently asked questions
- ¿Cuál es la diferencia entre planificación y programación?
- La planificación decide qué acciones tomar para lograr los objetivos, mientras que la programación decide cuándo ocurren esas acciones y qué recursos utilizan, dadas las restricciones de orden y capacidad. Muchos problemas reales requieren ambos, y la planificación temporal integra la selección de acciones con el razonamiento de tiempo y recursos.
- ¿Qué es el problema temporal simple?
- El problema temporal simple es una red de restricciones temporales en la que cada restricción limita la diferencia entre dos puntos de tiempo mediante un intervalo. Su consistencia y los límites implícitos más ajustados se pueden calcular de manera eficiente, lo que lo convierte en un núcleo práctico para el razonamiento temporal en planificadores y programadores.