Planification et ordonnancement temporels
La planification et l'ordonnancement temporels étendent la planification pour gérer des actions qui prennent du temps, peuvent s'exécuter concurremment et consomment des ressources limitées, produisant des plans qui spécifient non seulement quoi faire, mais aussi quand le faire.
Definition
La planification temporelle produit un plan dans lequel les actions ont des durées et peuvent se chevaucher, sous réserve de contraintes temporelles et de ressources ; l'ordonnancement attribue des heures de début (et des ressources) à un ensemble d'activités afin que toutes les contraintes, telles que l'ordonnancement, les échéances et les capacités, soient satisfaites.
Scope
Ce sujet couvre la planification et l'ordonnancement avec une gestion explicite du temps et des ressources : les actions duratives, la concurrence et les contraintes temporelles, la représentation et la résolution des réseaux de contraintes temporelles (tels que le problème temporel simple) et l'algèbre d'intervalles d'Allen, ainsi que l'intégration de la planification avec l'ordonnancement d'activités soumises à des contraintes de ressources. Il aborde la manière dont la faisabilité temporelle et des ressources est raisonnée parallèlement à la sélection des actions. La planification classique pure sans ressources est traitée dans les sujets connexes.
Core questions
- Comment les actions duratives et leurs conditions de début et de fin sont-elles représentées ?
- Comment les contraintes temporelles entre les événements sont-elles modélisées et vérifiées pour leur cohérence ?
- Comment les ressources limitées sont-elles allouées entre les activités concurrentes ?
- Comment la planification (décider quelles actions) et l'ordonnancement (décider quand) sont-ils combinés ou séparés ?
Key concepts
- actions duratives
- concurrence et chevauchement
- contraintes temporelles
- problème temporel simple
- algèbre d'intervalles d'Allen
- contraintes de ressources
- ordonnancement
- échéances et durée totale (makespan)
Key theories
- Réseaux de contraintes temporelles
- Les contraintes temporelles quantitatives entre des points temporels peuvent être représentées comme un réseau dont la cohérence et les bornes les plus strictes sont calculées efficacement pour le problème temporel simple, constituant ainsi l'épine dorsale du raisonnement temporel de nombreux planificateurs et ordonnanceurs.
- Algèbre d'intervalles pour le temps qualitatif
- L'algèbre d'intervalles d'Allen saisit les relations qualitatives possibles entre les intervalles de temps (avant, pendant, chevauche, etc.) et soutient le raisonnement sur les connaissances temporelles lorsque les heures exactes sont inconnues.
- Intégration de la planification et de l'ordonnancement
- Les problèmes réalistes nécessitent de choisir des actions et de leur attribuer simultanément des temps et des ressources ; la théorie de la planification automatisée traite les actions duratives, la concurrence et les contraintes de ressources comme des extensions qui couplent la sélection d'actions avec l'ordonnancement basé sur les contraintes.
Clinical relevance
La planification et l'ordonnancement temporels sont essentiels dans les opérations de vaisseaux spatiaux et de rovers, la planification de la fabrication et des projets, la planification des transports et des équipages, et tout contexte où des activités chronométrées, concurrentes et limitées en ressources doivent être coordonnées ; de tels systèmes ont planifié des opérations pour de réelles missions spatiales.
History
Le raisonnement temporel qualitatif a été formalisé par l'algèbre d'intervalles d'Allen (1983), et les réseaux de contraintes temporelles quantitatives par Dechter, Meiri et Pearl (1991). Ces fondations, associées aux modèles d'actions duratives ajoutés au PDDL au début des années 2000, ont permis le développement de planificateurs temporels utilisés dans des applications telles que le contrôle autonome de vaisseaux spatiaux.
Key figures
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
Related topics
Seminal works
- dechter1991
- allen1983
Frequently asked questions
- Quelle est la différence entre la planification et l'ordonnancement ?
- La planification décide quelles actions entreprendre pour atteindre des objectifs, tandis que l'ordonnancement décide quand ces actions se produisent et quelles ressources elles utilisent, compte tenu des contraintes d'ordre et de capacité. De nombreux problèmes réels nécessitent les deux, et la planification temporelle intègre la sélection d'actions avec le raisonnement temporel et de ressources.
- Qu'est-ce que le problème temporel simple ?
- Le problème temporel simple est un réseau de contraintes temporelles dans lequel chaque contrainte borne la différence entre deux points temporels par un intervalle. Sa cohérence et les bornes implicites les plus strictes peuvent être calculées efficacement, ce qui en fait un noyau pratique pour le raisonnement temporel dans les planificateurs et les ordonnanceurs.