The AMC BARREL ALLOCATOR: Technical Overview

1. Background

DITOPS is an advanced system for complex transportation and logistics planning and scheduling applications, developed by Carnegie Mellon University (CMU) under sponsorship of the DOD Advanced Research Projects Agency (DARPA). It utilizes novel constraint-based representation and search techniques to provide capabilities

These planning and scheduling capabilities are coupled with a sophisticated, graphical user interface that enables visualization of plans and schedules from resource-oriented, mission-oriented and geographical (map-based) perspectives, flexible editing of problem constraints and parameters as well as planning and scheduling decisions, and selective control over the automated scheduling process.

2. Architecture

DITOPS is built using an underlying scheduling framework called OZONE (or O3 which stands for Object-Oriented OPIS, an earlier scheduling system architecture developed at CMU; DITOPS actually stands for Distributed Transportation Scheduling in OPIS). The OZONE "application building framework" is designed to promote rapid configuration of planning and scheduling systems that incorporate the specific constraints, rules, and characteristics of a given application environment. At its core is a customizable, constraint-based modeling framework and search architecture, based around three principal components:

The Ozone framework is implemented in Commonlisp (scheduler component) and Java (user interface component) using object-oriented representation and programming techniques. It includes an extensive class library for modeling different types of domain activities, resources, demands and constraints, as well as other scheduling system and UI components. Protocols are provided for extending and customizing basic concepts into more specialized ones that match the characteristics of a given application, and for combining concepts from the library. The OZONE class library and architectural template provide a powerful basis for constructing customized, high performance planning and scheduling systems.

3. Application Status

The DITOPS scheduler was originally developed and demonstrated in the context of strategic deployment planning. In this domain, on full-scale "TPFDD" scheduling problems, DITOPS was shown to produce better schedules than current USTranscom transportation scheduling tools in a fraction of the time taken by these tools while also enforcing additional types of transportation constraints. DITOPS was subsequently adapted and applied to the problem of reactive aero-medical evacuation re-planning, where capabilities for interleaving itinerary planning and resource assignment in the movement of patients to required medical facilities were demonstrated. Starting in 1997, with joint funding from DARPA and AMC, work was initiated toward extending and customizing the DITOPS/OZONE technology for transition into CAMPS (Consolidated Air Mobility Planning System), the future operational system for the TACC at AMC. This has led to development of BARREL ALLOCATOR, a tool for integrated planning and tasking of airlift and tanker missions. This scheduler is was delivered to AMC in October, 1998 for initial user evaluation within the TACC, and current plans call for insertion into actual operations in 4th Quarter, 1999. The current technical capabilities of BARREL ALLOCATOR are summarized below.

4. Current Capabilities

The BARREL ALLOCATOR provides a range of mission planning and scheduling capabilities:

4.1 Generation of airlift mission schedules

In basic operation, the scheduler accepts a set of planned airlift missions as input, and establishes time windows and wing assignments for each. An input airlift mission (minimally) specifies:

The scheduler produces an assignment of (notional) aircraft from specific wings to each mission (creating and inserting positioning/de-positioning flights as necessary) and an assignment of flight times to each mission leg.

Currently, the following constraints are taken into account and enforced in constructing a schedule for all current missions:

The mission scheduling procedure is quite efficient —a 2 week interval of missions recently extracted from the current ADANs data base at AMC (approximately 1000 missions, 5000 flights) is scheduled from scratch in 45 seconds on a Sun Ultra-Sparc (roughly equivalent to a 300Mhz PC). In a more typical mode of operation, however, the problem is one of integrating sets of newly planned missions into an existing current global schedule (which is typically much faster). In this mode, the scheduler will attempt to assign aircraft and schedule new missions without disrupting the current set of assignments. Any mission that cannot be integrated into the schedule in this way (which implies that there is not enough lift capacity to accomplish the mission without changing existing resource assignments) is flagged as "unschedulable" (requiring subsequent user attention — see below). Alternatively, the scheduler can be directed to integrate new missions into the current schedule in "priority order", in which case the scheduler may reassign or pre-empt lower priority missions if necessary to get newly received missions into the schedule. This range of scheduling modes provides a continuum of scheduling actions that are progressively more disruptive in the changes that can be made to the current schedule.

4.2 Generation/Assignment of tanker missions

In addition to generating wing/aircraft assignments and mission schedules, capabilities are also provided for generating and assigning tanker missions to airlift missions that require arial refueling support. A set of refueling events is accepted as input, and tanker assignments can be generated either interactively or automatically. In automatic mode, the scheduler first attempts to link tanker missions that are already included in the schedule (e.g., training missions); tanker wing assignments are determined and tanker missions are created for any remaining unsupported airlift missions.

In interactive mode, a map-based display (similar to the display in Figure 3 below) is used to indicate candidate refueling tracks that are already covered by tanker missions in the temporal interval required by a given airlift mission. The user can select one of these highlighted refueling tracks (potentially changing the originally planned refueling location) or select the current track (which will result in creation of a new tanker mission if one is not already in the schedule). In the case of the selection of a pre-existing tanker mission, the system will also present opportunities to support multiple arial refueling events with the same tanker mission (provided that fuel requirements and tanker fuel capacity constraints are satisfied).

4.3 Visualization and Analysis of Schedules

The automated, semi-automated and interactive scheduling capabilities described above are embedded in a Java-based, graphical user interface that provides powerful capabilities for visualizing and analyzing schedules. Three basic perspectives are defined for viewing the current schedule:

These three visual perspectives are highly integrated and managed in a coordinated fashion. Selections in the mission window can be used to create specific resource or map-based displays, and changes made to the schedule from any display are immediately reflected in all displays.

4.4 What-If Analysis of Options and Interactive Revision of Schedules

As mentioned earlier during discussion of airlift mission schedule generation, the scheduler, in default mode, will classify as "unschedulable", any mission that cannot be integrated into the current schedule without some change to previous assignments. In such cases, it is not possible to satisfy mission time constraints with existing available lift capacity. To support resolution of such situations, BARREL ALLOCATOR gives the user the ability to analyze and compare various constraint relaxation options. Specifically, for any given "unschedulable" mission (or set of unschedulable missions), the user can choose to:

Any of these options can be invoked by the user in "what-if" mode; a general "undo" capability allows the retraction of any sequence of scheduling actions that have been issued by the user, and thus provide a basis for exploring alternatives. Alternatively, the user can ask the system to generate and and compare all options.

4.5 Interactive Mission Merging

A final interactive capability provided to the user to support more efficient usage of available aircraft is mission merging. Whereas missions are, by default, planned as round trips from a particular home base, mission merging attempts to exploit non-cargo-carrying positioning/de-positioning flights to support missions (such as retro-grade missions) that are flowing cargo in opposite directions. Using the map-based interface, a mission (perhaps currently unschedulable) for which merge candidates are sought is displayed, and a find merge candidates query is formulated by specifying 3 parameters:

The interactive mission merging function is illustrated here.