Figure 2.2.1: Example of good coordination of radars in tracking multiple targets
The logistics challenge problem involved the coordinated scheduling of flight operations and aircraft maintenance. The Marines Air Group 13 (MAG13) in Yuma Arizona provided the context for this challenge problem. They provided the requirements, the data and military personnel committed to evaluate and use incremental releases of the software. The logistics challenge problem is a practical problem that the Marines solve on a daily basis to schedule their flight operations and maintenance.
The users involved in producing the flight and maintenance schedules fall into three groups:
The commanding officers generate yearly and monthly guidance. The operations people must produce weekly schedules to meet the guidance, and refine those schedules every day to produce the schedules that get executed every day. The operations and maintenance people must communicate frequently to coordinate their schedules: in order for operations to produce a schedule they need to know how many aircraft of each type are available. In order to answer that question maintenance needs to know the flight schedule in order to figure out whether they have time to carry out all the usage-based and calendar based maintenance that must be done on the aircraft. The cycle is broken by starting with estimates and refining those estimates though iterative refinement of the schedules.
The users have databases that record all the information relevant for producing the schedules. Operations has databases that record the flight logs of each pilot, their qualifications, etc. Maintenance has databases that record all the maintenance work items that must be performed or are being performed on each aircraft.
These databases have viewers and editors that allow users to see what is going on, and to edit the information. Operations has a sophisticated schedule editor application that enables users to enter and validate flight schedules, but they do not have a scheduling application that computes as schedule. The users determine the schedules manually, typically on a white board, and then enter it in the computer to validate it and to print the official schedules that get signed signed by the commanding officers. The maintenance schedules are kept on white board and paper and never entered in a computer.
The goal of the logistics challenge is to automate the production of the operations and maintenance schedules. The payoff is large because developing the schedules by hand is labor intensive and time consuming (typically 6 hours for a weekly operations schedule), and little time is left to explore alternatives and to deal with often changing requirements. In addition, producing schedules that extend beyond a week is infeasible, resulting in commanders having limited ability to forecast the consequences of taking on new commitments (e.g., can you participate in a week-long exercise at the beginning of next month and still make your deployment commitments 6 months from now?)
We describe the operations side of the logistics challenge in terms of the goals that commanders can specify, in terms of the objective functions that define the score of a schedule, the resources and tasks, and constraints that define the scheduling problem.
The following list of goals is not a complete list of all the goals that commanders would like to state. The list contains the goals that the challenge problem focused on.
The objective function is a linear combination of metrics that specify how well each goal is achieved. Each goal is scored using a piece-wise linear function that specifies how good it is to obtain a certain quantity of something. For example, an objective function for the number of sorties goal could be specified as follows: flying 0 sorties gives a score of 0, flying 90% of the sorties gives a score of 0.5, and flying 100% gives a score of 1.
The score of a schedule is specified as a linear combination of the score for each goal. Note: in the implemented system, the user interface did not allow users to give numeric weights. Instead we offered the values "require", "prefer" and "don't care", which were defined in such a way that all the "prefers" weighed less than a single "require".
One of the lessons learned in the logistics challenge problem is that it is very difficult for users to specify an objective function that captures all the issues they care about. We found that it was only after seeing a solution that users would think about trade-offs that would be impractical to specify in advance (e.g., I'll accept having Jones fly 8 rather than 5 sorties if that is the only way I can get Smith's night systems qualification done).
The following is a list of the resources involved in producing operations flight schedules.
The tasks specify the activities that appear in the schedule. There are 3 types of tasks: on-base activities, simulator training and flights. On-base activities such as serving as operations duty officer involves booking a pilot qualified for that activity for a specific period of time. Simulator training involves booking a simulator, the pilot serving as the trainee and an instructor pilot. Flights are the most complex tasks, because they have rich internal structure and involve all the resources.
The structure of a flight is defined in terms of the number of aircraft that participate in the flight, and in terms of a number of flight segments that specify at what points during the flight the different resources are needed.
Resources participate in flights as follows:
The previous section discussed the constraints that specify the required relationships between the resources that participate in a task. There are additional constraints that define relationships between tasks.
We describe the maintenance side of the logistics challenge problems in terms of the expected outputs of the system, the goals the user - typically a maintenance control officer - can specify, resources and tasks, and the constraints that define the scheduling problems.
The solution to the maintenance planning problem should yield two outputs:
The list below gives a summary of the various goals the user can specify, that will influence the aircraft and maintenance schedules.
The following list shows the resources involved in aircraft and maintenance scheduling.
The following list shows the tasks involved in aircraft and maintenance scheduling.
The following list shows specifies the major constraints that define the aircraft and maintenance scheduling problems.
The operations/maintenance coordination problem is to compute a flight schedule and an aircraft availability forecast such that it supports the flight schedule. This comes about in the following way:
If operations makes any changes to the flight schedule, then the cycle must be repeated until it is verified that maintenance can support the flight schedule. If maintenance needs to change the forecast, the cycle must also be repeated to verify the new forecast supports the flight schedule.
As mentioned in section 2.1.1., in the end the squadron is better off when operations produces more maintainable schedules. This means that the the scheduling of flights is made sensitive to maintenance requirements. This defines a spectrum of possibilities: in one end of the spectrum (full sensitivity), the operations and maintenance problems are solved as a single larger problem; at the other end of the spectrum (no sensitivity), the problems are solved independently and only the results are exchanged between the parties. In the full sensitivity mode steps 1 through 4 wash out into a collection of constraints that tie the requirements together. In the no sensitivity mode the steps 1 through 4 are done with the results of the schedulers and repeated until convergence is reached. In the middile points of the spectrum operations and maintenance echange additional information than just point solutions (e.g., ranges of take-off times) and repeat the cycles incrementally (e.g., for single aircraft rather than for all aircraft at a time).
During this project only the no-sensitivity mode was explored. The operations scheduler produce a fully detailed flight schedule. The maintenance scheduler user the fully detailed flight schedule to produce a single aircraft availability forecast (i.e., with no what-ifs), and steps 1 through 4 were repeated until convergence was reached. Even though this was a very simple solution, the outcome was much better than the pre-existing way of doing business, which involved coordinating the schedules by talking on the phone.
The logistics challenge problem gave rise to a number of difficult technical
challenges.
The operations scheduling problem is a planning and scheduling problem. The goal statements (e.g., achieve night systems qualification for Smith) specify what needs to be done, whereas the tasks specify how it will be done. The challenge problem requires creating the tasks and scheduling them. For example, to achieve the night systems qualification for Smith, he must fly mission codes 280 and 281. This could be done with one task with a refueling stop such that 280 is done before the refueling and 281 done after. It could be done with two tasks without a refueling stop, and in fact, could be done in other kinds of tasks.
One simple approach to solve this problem is to have a "create tasks" phase that creates tasks to meet the goals, followed by a scheduling phase that schedules the tasks. Of course, the difficulty is that the scheduling problem could be made much easier if a different set of tasks had been generated. However, without the information gathered during scheduling it is not possible to determine which tasks make the scheduling problem easier.
Alternative approaches are to interleave task creation and scheduling, or to do both things at the same time. The difficulty here is that the search space becomes much larger because it converts a scheduling problem into a planning and scheduling problem.
The solution to the challenge problem used the first approach even though it sometimes led to unscheduled tasks and obviously sub-optimal solutions. However, the system gave users the ability to overcome the problem by allowing them to edit the tasks to re-structure them to be more amenable to the scheduler. In typical schedules users only had to do this a few times.
The maintenance scheduling part faced a similar problem. Given a flight schedule, the maintenance tool would assign aircraft to flights, making assignments to maximize the number of flights that could be supported. Once aircraft are assigned to flights, the tools can forecast the flight hours for each aircraft and create the tasks to perform maintenance on the aircraft. Again, the aircraft assignments were done without consideration of how it affects scheduling of maintenance on the aircraft. This sometimes resulted in unscheduled tasks or sub-optimal solutions. The solution here was also to let the user edit the aircraft assignments to make the maintenance scheduling easier.
The enablement problem is similar to the "create tasks" problem in that it brings planning aspects into the scheduling problem. The enablement problem concerns qualifications that pilots gain by participating in tasks and qualifications they lose from not participating in certain tasks. We called it the enablement problem because participating in certain tasks enables pilots to participate in others. If participation in task T gives a pilot a qualification to participate in task S, then if the system wants to select that pilot for both S and T, then task S must be scheduled after task T. The difficulty is that the relationship between tasks S and T is dynamic in the sense that it depends on the assignment of pilots to the tasks: if a pilot is already qualified to participate in both S and T, then those two tasks can be scheduled in any order.
The enablement problem is significantly easier than the "create tasks" problem because it does not change the structure of the tasks. The problem was solved in two different ways.
The ISI/Cornell collaboration produced a solution based on a pseudo-Boolean encoding of the problem (XXX LINK TO ALEJANDRO/CARMEL HERE) where the system automatically figures out both pilot assignments and timing of tasks when it is optimizing the number of scheduled tasks.
The ISI team solved the problem in the greedy solver to provide a fast solution to the most common cases. The most common occurrences of the enablement problem are in the tasks generated to satisfy qualification build goal and in the tasks to achieve new core competencies. In those tasks, one of the pilots is always known, i.e., the pilot assignment is constrained to have a single value. This allows the greedy scheduler to sort the tasks in enablement order so that if tasks T enables task S, the scheduler first schedules task T and when it schedules task S, it can select the start time of S to be after the end time of T. This simple approach covers the most common cases although it can lead to sub-optimal solutions. For example, when scheduling task S the greedy scheduler does not consider task T, so it doesn't know not to delay task S (e.g., to optimize another objective such as range preference) in a way that task T is squeezed out of the schedule.
The crew day and crew rest constraints were briefly discussed in section 2.1.1.2.5. These constraints were difficult to solve in both the greedy and pseudo-Boolean solvers for the logistics problem.
In the greedy solver 90% of the time was spent evaluating the crew day and crew rest constraints in order to compute the time intervals when these constraints allowed pilots to fly. The problem is that the solver invokes this computation each time it considers a time point for a pilot because for each proposed time it must figure out if there is a way to arrange the work and rest patterns of the pilot to make them consistent with all other activities the pilot has in the schedule. The ISI team is considering less sophisticated algorithms that would miss some of the more creative solutions, but would be significantly faster.
In the pseudo-Booelan solver the number of variables and constraints devoted to encoding these constraints are 3 times more than the variables and constraints used to encode the rest of the problem.
In both solvers, the parts of the solver that address these constraints were written several times and significant development time was spent just on this aspect of the system. Even though crew day and crew rest are just one of the constraints in the logistics problem, it was important to address them thoroughly because these constraints are critical to safety. A general, fast solution to this type of constraint remains an important unsolved problem.
The logistics challenge required producing schedules at 1 minute resolution. This was challenging for the discrete methods such as pseudo-Boolean, finite domain constraint and SAT solvers, because in these method time must be represented using discrete variables or finite sets. This means that time must be discretized into slots, and using slots of 1 minute duration results in an unreasonable number of variables or very large sets. For example, discretizing time to 4 minutes results in over 100,000 pseudo-Boolean variables to encode a problem with a 3 day planning horizon. The challenge problem called for solving problems with a 1-month planning horizon.
Two approaches were tried.
In the greedy solver approach the solver represents time at a resulting of milliseconds (by using long integers to time), and it computes all the possible time intervals when a task can be scheduled based on the times when all candidate resources are available. It then selects the time that maximizes the objective function.
In order to use a discrete method such as a pseudo-Boolean solver, the ISI team built a 2-phase solver. In the first phase it used a pseudo-Boolean solver working on an encoding of the problem with time discretized to specified amount (typically 1/2 hour). The solution produced by this solver was converted into soft constraints and added to the original problem. The second phase used the greedy solver working on the problem augmented with the soft constraints. The idea here was to advantage of the sophisticated pseudo-Boolean solvers available that could do a more thorough search for solutions, and then use that solution as guidance for the greedy solver. For example, if the pseudo-Boolean would determined that task T should be scheduled between 10:00 and 10:30 using Jones and Smith. The greedy solver would then narrow down the time a specific minute.
The difficulty with this technique is that the 2-phase solver is quite sensitive to the discretization size. If the size is too small, the problem encoding is enormous (over 500,000 variables) and if it is too small (e.g., 2 hours) then the encoding is too imprecise, and the second phase solver cannot refine the times within the soft-constraints. For example, the first phase solver will recommend scheduling a task between 10:00 and 10:30. However, because some resources are available at odd times (e.g., range available from 9:45 to 10:15), it might not be possible to schedule the task in the recommended interval. For example, it might be necessary to schedule the task at 9:50. These errors add up, and may cause violations of other constraints such as lighting, crew day, etc.
There was not enough time in the project to thoroughly evaluate the 2-phase solver. Preliminary results showed that the idea is promising and pointed out some of the difficulties that will need to be overcome.
The logistics challenge called for computing daily, weekly and monthly schedules, all with the same level of detail. The technical challenge was to produce scheduling algorithms that scale linearly with the size of the planning horizon. The greedy scheduler is almost linear with the size of the planning horizon because it schedules one task at a time and does not backtracking. The pseudo-Boolean solver is not linear with the size of the planning horizon because it's complexity is not linear with the number of tasks, and the number of tasks grows linearly with the size of the planning horizon. The greedy solver computed daily schedules in a few seconds, and monthly schedules in about 5 to 10 minutes.
Even though the 2-phase solver offers the opportunity to address long planning horizons by discretizing long planning horizons very coarsely (say to 6 hours), this was not tried because coarse discretizations should be conceptually different from fine-grained discretizations. For example, crew day and crew rest make no sense when discretized more coarsely than the amount of shift allowed between adjacent crew days (typically 2 hours). In that case, crew day and crew rest constraints should be replaced by capacity constraints, that for instance, limit pilots to fly twice a day. There was no time to implement such problem reformulations.
Understandability refers to the users' ability to understand why tasks were scheduled the way they were, and most importantly, why an allocation they had in mind had not been done. In schedules with short planning horizons users would often edit the tasks to add specific constraints such as specifying both pilots. The additional constraints made the problem harder to solve, often resulting in tasks not being scheduled. In those cases, users wanted to know why their tasks had not been scheduled.
In general, such questions are very hard to answer succinctly because there are a large number of constraints that affect the allocation of a task, and the chains or reasoning can be long. The solution to this challenge takes advantage of the simplicity of the greedy solver, and the ability of the greedy solver to essentially hide from the user the sophistication of the pseudo-Boolean solver when using the 2-phase solver.
The why, and why not questions are answered using a feasibility display that shows all the possible times when the resources that can participate in a task are available. The display cleverly arranges the timeline for each resource and each constraint class so it is easy for the user to see which resource or which constraint prevents a task from getting scheduled during all times in the planning horizon. The users learned how to use this display, and were able to solve almost all scheduling questions using it.
The feasibility display relies on the sequential nature of the greedy solver in that the ability to schedule a task depends only on the tasks that have been scheduled so far. This means that the feasibility display does not work for solvers that do backtracking. The 2-phase solver enabled a compromise in that the feasibility display is built from the results of the greedy solver which runs after the more sophisticated pseudo-Boolean solver. The result is that the feasibility display shows only one of the reasons why something didn't happen (based on the reasoning abilities of the greedy solver), but that is enough to let users fix problems. Without the feasibility display users were unable to fix scheduling problems, and thus were unable to use the system to solve practical problems.
The logistics challenge problem produced two tools: SNAP for scheduling flights and MAPLANT for scheduling maintenance and assigning aircraft to flights. The two tools work together to enable users to coordinate flight operations and maintenance to guide operations to produce flight schedules that can be supported by maintenance.
The SNAP and MAPLANT tools were developed with help from users from the MAG-13 squadrons and guidance from commanders and subject matter experts. The resulting tools were fielded at MAG-13 and on board amphibious attack ships engaged in operations in Afghanistan, and Iraq A formal military usability assessment was conducted and the tools were selected for transition to all US Marines aviation and the Joint Strike Fighter.
The contributions of the complexity and dynamics researchers to the logistics challenge problem are captured in two solvers that were integrated in the final demonstration.
A number of teams, including Cornell-Hebrew University, Washington University, CIRL, and ISI, explored the application of SAT solvers to the logistics challenge problem. This work reached its most mature form in CIRL's development of the OPARIS pseudo-Boolean solver, and its application to the operations scheduling problem by CIRL and ISI.
Altarum's work on pheromone learning and deadline-sensitive negotiation led to the development of the RAPSIDY solver, which can start with an existing solution and quickly repair it to meet changed mission constraints.
The main objective of the ANTs program was to develop approaches to distributed resource management that are (1) real-time, (2) scalable, (3) robust, and (4) low-cost. The Electronic Warfare (EW) challenge problem was developed as a room-sized test-bed in which researchers could show how well their approaches performed with respect to each of these characteristics; at the same time, the challenge problem would present many of the problems that arise in practical applications (such as measurement noise and limitations on communication).
The main problem statement for the EW challenge problem is: track a set of moving targets using a network of short-range, radio-equipped radars, each coupled to a computer. Each radar is capable of producing only limited data about a target so several (ideally, three) radars need to collaborate to accurately pin down a target's position and velocity. Moreover, each radar is able to scan only one target at a time, so a radar with several targets within range needs to decide which target to scan - see Figure 2.2.1.
Figure 2.2.1: Example of good coordination of radars in tracking multiple targets
The danger, if coordination is performed badly, is that one target may be tracked by wastefully many radars while other targets are neglecting - see Figure 2.2.2. Coordination of the collaboration and exchange of data to compute the target tracks can be performed using radio communication.
Figure 2.2.2: Example of poor coordination of radars in tracking multiple targets
Thus, the EW projects were to develop a coordination mechanism to ensure that, as far as possible, each target was scanned continually by three radars. In this context, the four characteristics listed above arise as follows:
The following sections described the challenge problem hardware and infrastructure, how target tracking is performed based on radar measurements, and a monitoring and visualization system.
Each node in the sensor network is comprised of a radar unit and a moderate-power computer. While the computer would be of interest in a practical deployment (being a significant cost and consumer of power), the radar units are the main focus for this challenge problem.
Figure 2.2.3: A radar unit
Figure 2.2.3 shows a radar unit. Each radar unit has the following components:
Figure 2.2.4: Coverage of one head of a radar unit
Each head can be independently powered on/off (a head consumes power when on). When a head's power is switched from off to on, there is a stabilization period of about two seconds during which its illumination strength may vary, producing unreliable measurements.
Radio communication is the only feasible technology for many practical applications, but for development, debugging and assessment purposes wired communication is often more convenient. To this end, communication emulators based on UDP and TCP over ethernet were also available. Both emulators used the same API as radio communication. The TCP emulator aimed for reasonable fidelity, mimicking message collision and (adjustable) bandwidth limitations.
The challenge problem infrastructure includes several, interchangeable software modules for target tracking. Each module is designed to be instantiated for each target that is to be tracked, after which the instantiation, or tracker, is continually fed sets of more-or-less simultaneous radar measurements relating to that target. (Preferably, each set of measurements would contain data from at least three radar units and span no more than two seconds.) The tracking API provides functions for estimating a target's position and velocity at any time, based on a straight-line extrapolation of its track.
Details of the algorithms used for tracking are provided in the references. Here, a brief, high-level description is provided of how radar data is interpreted. Each radar measurement may provide an amplitude, representing the strength of the reflected signal, and a frequency, representing the Doppler shift caused by the target's motion towards or away from the radar.
In order to simplify signal processing, the challenge problem used standardized
targets, consisting of a corner reflector made of copper disc of a standardized
size. Because the targets are essentially interchangeable and corner reflectors
provide a more-or-less uniform reflection regardless of the angle of incidence
of the radar beam (at least in theory), the reflected signal strength depends
only on the position of the target relative to the radar unit. Specifically:
reflected(R, phi) = K/R2 e-phi2/A2
where reflected is the strength of the signal received by the radar unit's
detector from a target at a distance R from the unit and at an angle
phi (in the range -180o to 180o)
from the mid-line of the emitter's sector, and where K and A are
constants for a given head describing, respectively, the power and beam width
of the head's emitter.
For a given measured signal strength, this equation determines a contour of possible target positions, approximating an oval with one end located just behind the radar unit. For example, Figure 2.2.5 shows three contours, corresponding to signal strengths of 10, 100 and 1000, for a radar head positioned at the origin and looking along the positive horizontal axis. Note that the strongest signal corresponds to the smallest contour.
Figure 2.2.5: Contours showing the possible positions of targets for various signal strengths
In order to reduce an estimate of a target's position to a single point, in general three such contours must be intersected - see Figure 2.2.6, in which the contours have been approximated using ovals. However, all physical sensors are subject to noise which typically results in the contours may not intersect in a single point, so generally a best-estimate of position must be determined. (For the particular hardware used for the challenge problem, measurement noise can arise from dark current in the detector, fluctuations in the emitter, interference from environmental electro-magnetic sources and deviations of the physical targets from the theoretical model of a corner reflector.)
Figure 2.2.6: Three intersecting contours fix a target's position
Moreover, to reduce the effects of noise, it is generally desirable to combine estimates derived from new measurements with estimates derived by extrapolating the target's track. Also, each frequency measurement gives an estimate of the target's radial speed (i.e., the component of the target's velocity along a vector from the radar unit to the target) which can also be combined into an overall position estimate.
Determining cause-effect relationships in real-time, distributed systems is notoriously difficult due to incomplete or uncorrelated information and due to changes in timing caused by the insertion of monitoring or debugging code. To assist with development, debugging and assessment, a monitoring and visualization system was incorporated into the challenge problem infrastructure in such a way as to minimally perturb the other systems.
The monitoring system had three main parts: monitoring the physical targets; monitoring usage of radar units (including communication); monitoring data being provided to the trackers.
Figure 2.2.7: Radar units places around train tracks, along which targets are moved by model trains
The monitoring code was deployed on each radar unit and data collected fed back in real-time over an ethernet connection to a central visualization terminal, which could display true target positions, target estimates, statistics estimating performance (e.g., number of times a radar scans an empty sector even when a target is nearby, in a different sector), and statistics showing resource usage (power consumption by the radar emitters and amount of communication).
University of South Carolina:
Washington University at St. Louis: