This chapter documents the DITOPS problem solving architecture and how it was adapted for the medical evacuation domain.
Scheduling in DITOPS is formulated as a reactive process, reflecting the fact that a schedule at any level or stage of the deployment planning process is a dynamic evolving entity, and is continuously influenced by changing mission requirements, conflicting decision-making perspectives/goals and changing executional circumstances. This problem solving perspective in large part motivates the aforementioned representations of changing resource state over time (i.e., available capacity, location). These representations are pre-requisites to the specification of procedures for reflecting the consequences of changed constraints and for incrementally managing schedules in response to such changes.
Schedule generation and revision at a given level of detail is uniformly cast as an opportunistic process that (potentially) selectively employs a number of distinct scheduling methods. Methods defined in the core DITOPS implementation include general-purpose procedures for "resource" and "movement" oriented scheduling. These methods are derived from the original multi-perspective concept of OPIS and are capable, respectively, of generating/revising the scheduling decisions of a given set of resources or a given set of temporally related movements. A set of more specialized schedule revision methods is also available, providing alternative resolution capabilities in situations of constraint conflicts. All methods share a common search infrastructure, which includes both (1) machinery for incrementally propagating the consequences of scheduling decisions and detecting constraint conflicts, and (2) search space elaboration primitives that support dynamic "batching" and "splitting" of move requirements in situations where the resource capacity constraints of alternative transportation assets dictate. The choice of which set of scheduling decisions to focus on next and which method to apply, at any point during the scheduling or rescheduling process, is based on heuristics that relate characteristics of current solution structure to the optimization and resolution strengths of alternative methods.
Several of DITOPS' scheduling methods are implemented by specializing or instantiating an abstract search class. Among the available specializations of this class is a class that implements a beam search algorithm. The beam search class provides a customizable, heuristic search procedure which allows easy configuration of search state expansion and search direction. Search state expansion is done using a set of programmer-defined search operators, whereas the search direction is customizable using a programmer-defined evaluation function.
The DITOPS control architecture is a specialization of an abstract class based on the blackboard control mechanism. This mechanism organizes and coordinates the actions of several heterogeneous problem-solvers or methods (also called knowledge sources). The control mechanism itself is a specialized knowledge-source called Top Level Manager which encapsulates all the functionality to deal with the control of the system's problem-solving behavior. The knowledge sources define the strategic alternatives available to the system to solve some specific problem. For each particular instantiation of the control architecture, domain specific problem solvers will be added and the control cycle behavior will be customized accordingly. For example, in the medical evacuation domain, the architecture presumes the existence of a set of domain specific knowledge sources that can be used to generate, analyze, and revise patient allocations and mission itineraries.
The Top Level Manager operates on events and tasks. Events are internal and external stimuli to the system: any action the user performs through the user interface is considered an external event or external disruption; external events are mapped onto the solution state generating internal events. The events characterize the current state of the schedule identifying the relevant control information. Control heuristics are used to aggregate, sort and process these events. The problem-solving proceeds via the formulation of tasks as responses to specific events. The tasks generated as a result of processing the events are then prioritized and processed by the knowledge sources. These tasks can perform analysis, generation or revision of the schedule. The Top Level Manager keeps a list of pending tasks. This list constitutes the current plan for solving the scheduling problem. Depending on the type of the task, the Top Level Manager selects the most appropriate knowledge source to process. Changes in the state of the schedule resulting from the execution of other knowledge-sources is also communicated to the Top Level Manager via posting of events.
The higher levels of the hierarchy of objects manipulated by the Top Level Manager are defined as:
The instantiation of the DITOPS problem-solving architecture for the medical evacuation domain is composed of five knowledge sources: the Top Level Manager - responsible for the control cycle; the Model Update that translates external disruptions into internal events; the Analyzer that identifies and collects information about the conflicts in order to suggest the most adequate problem solving behavior; the Route Planner which fixes inconsistent mission routes; and the Patient Scheduler which allocates patients to available missions and guarantees that all patients have complete and consistent itineraries.
The knowledge sources are invoked based on the conflicts introduced as a result of disruptive events. The basic control cycle works as follows:
In the next sections we will present the general behavior of the two problem solvers. The rationale for the analysis knowledge source and the details of how each disruption is treated are presented in chapter 5.