Zeitliche Planung und Terminierung

Die zeitliche Planung und Terminierung erweitert die Planung um die Handhabung von Aktionen, die Zeit in Anspruch nehmen, gleichzeitig ablaufen können und begrenzte Ressourcen verbrauchen, wodurch Pläne erstellt werden, die nicht nur festlegen, was zu tun ist, sondern auch, wann es zu tun ist.

Definition

Die zeitliche Planung erstellt einen Plan, in dem Aktionen Dauern haben und sich überlappen können, unter Berücksichtigung zeitlicher und ressourcenbezogener Beschränkungen; die Terminierung weist einer Reihe von Aktivitäten Startzeiten (und Ressourcen) zu, sodass alle Beschränkungen, wie Reihenfolge, Fristen und Kapazitäten, erfüllt werden.

Scope

Dieses Thema behandelt Planung und Terminierung mit expliziter Zeit und Ressourcen: durative Aktionen, Parallelität und zeitliche Beschränkungen, die Darstellung und Lösung von zeitlichen Beschränkungsnetzwerken (wie dem einfachen zeitlichen Problem) und Allens Intervallalgebra sowie die Integration der Planung mit der Terminierung ressourcenbeschränkter Aktivitäten. Es wird untersucht, wie die zeitliche und ressourcenbezogene Machbarkeit neben der Aktionsauswahl berücksichtigt wird. Die reine ressourcenfreie klassische Planung wird in den verwandten Themen behandelt.

Core questions

• Wie werden durative Aktionen und ihre Start- und Endbedingungen dargestellt?
• Wie werden zeitliche Beschränkungen zwischen Ereignissen modelliert und auf Konsistenz geprüft?
• Wie werden begrenzte Ressourcen auf gleichzeitige Aktivitäten verteilt?
• Wie werden Planung (Entscheidung, welche Aktionen) und Terminierung (Entscheidung, wann) kombiniert oder getrennt?

Key concepts

• durative Aktionen
• Parallelität und Überlappung
• zeitliche Beschränkungen
• einfaches zeitliches Problem
• Allens Intervallalgebra
• Ressourcenbeschränkungen
• Terminierung
• Fristen und Durchlaufzeit

Key theories

Zeitliche Beschränkungsnetzwerke

Quantitative zeitliche Beschränkungen zwischen Zeitpunkten können als Netzwerk dargestellt werden, dessen Konsistenz und engste Grenzen für das einfache zeitliche Problem effizient berechnet werden, was das Rückgrat vieler Planer und Terminierer für die zeitliche Argumentation bildet.

Intervallalgebra für qualitative Zeit

Allens Intervallalgebra erfasst die möglichen qualitativen Beziehungen zwischen Zeitintervallen (vor, während, überlappt usw.) und unterstützt die Argumentation über zeitliches Wissen, wenn genaue Zeiten unbekannt sind.

Integration von Planung und Terminierung

Realistische Probleme erfordern die gemeinsame Auswahl von Aktionen und die Zuweisung von Zeiten und Ressourcen; die Theorie der automatisierten Planung behandelt durative Aktionen, Parallelität und Ressourcenbeschränkungen als Erweiterungen, die die Aktionsauswahl mit der beschränkungsbasierten Terminierung koppeln.

Clinical relevance

Zeitliche Planung und Terminierung sind unerlässlich bei Raumfahrt- und Rover-Operationen, in der Fertigungs- und Projektplanung, im Transport- und Personalmanagement sowie in jedem Umfeld, in dem zeitlich festgelegte, gleichzeitige, ressourcenbeschränkte Aktivitäten koordiniert werden müssen; solche Systeme haben Operationen für reale Weltraummissionen geplant.

History

Qualitatives zeitliches Denken wurde durch Allens Intervallalgebra (1983) und quantitative zeitliche Beschränkungsnetzwerke durch Dechter, Meiri und Pearl (1991) formalisiert. Diese Grundlagen ermöglichten zusammen mit den in den frühen 2000er Jahren zu PDDL hinzugefügten Modellen für durative Aktionen zeitliche Planer, die in Anwendungen wie der autonomen Raumfahrzeugsteuerung eingesetzt werden.

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

Was ist der Unterschied zwischen Planung und Terminierung?

Die Planung entscheidet, welche Aktionen zur Erreichung von Zielen durchgeführt werden sollen, während die Terminierung entscheidet, wann diese Aktionen stattfinden und welche Ressourcen sie unter Berücksichtigung von Reihenfolge- und Kapazitätsbeschränkungen nutzen. Viele reale Probleme erfordern beides, und die zeitliche Planung integriert die Aktionsauswahl mit der Zeit- und Ressourcenbetrachtung.

Was ist das einfache zeitliche Problem?

Das einfache zeitliche Problem ist ein zeitliches Beschränkungsnetzwerk, in dem jede Beschränkung die Differenz zwischen zwei Zeitpunkten durch ein Intervall begrenzt. Seine Konsistenz und die engsten implizierten Grenzen können effizient berechnet werden, was es zu einem praktischen Kern für die zeitliche Argumentation in Planern und Terminierern macht.