Meeting Minutes
- Will work on code study and hangout reading separately
- Will create a list of questions for the meeting on Thrusday
- Will create a generalized Makefile for the assetplayer
- Which reference listed in the handout should be read first? A: "Planning, Scheduling and Monitoring for Airport Surface Operations" and "Exact and Heuristic Algorithms for Runway Scheduling"
- What is SARDA framework that applied in ASSET for scheduling? A: _We described the framework in class using the slides. _
- What is the STP(Simple Temporal Problem) framework being discussed in the paper with regards to analyzing STN? A: STP is a popular AI-based approach to planning with time. Given a set of events and a set of temporal constraints that describe how these events related to each other (e.g. one event happens before another or has a duration of between 10 and 15 minutes) a shortest path algorithm determines whether the plan is consistent and also allows for a schedule (assignment of start times to events) to be generated. A simple temporal network (STN) is a graphical representation of an STP using nodes for events and links for constraints between events. Note that a STN and a node-link model of an airport are both graphs, but they are different kinds of graph. The nodes of the airport model represent locations at the airport, whereas nodes of an STN represent events. Similarly, links in the airport model represent a path between nodes, whereas links in an STN represent temporal constraints between events.
- What do the timestamps or edge labels in STN Graph(Figure 4) mean? Edge labels of an STN represent constraints between events. For example, it allows you to represent a constraint like "Event A must happen between 10 and 15 minutes before event B, where A and B are represented as nodes.
- Does the existing implementation of the scheduler include the DTMC model described in the "Modeling and Predictive Analysis" section of the paper? A: No. I'm hoping we find ways to incorporate the DTMC model into the scheduler as part of the work for this class.
Motivation:
Congestion at key airports as the area in which the traffic capacity problem is most prominent. Capacity gain requires construction of new runways and expansion of surface area for taxiing. Capacity gain means more complexity in Air Traffic Control (ATC) operations, increasing risk of human error, operator workload, and the potential for inefficiencies in operations. Capacity gain also means potentially harmful effects on the environment, such as more noise and air pollution, and higher fuel costs for taxiing aircraft. The practical difficulties of increasing capacity through airport expansion introduce the desire for enhanced airport ground movement efficiency by the intelligent use of the existing resources.
The problem to be solved is a logistics problem: the coordinated movement of humans and machines to accomplish a complex task: getting arriving aircraft to gates and departing aircraft in the air.
Safety and efficiency in operations are the primary goals. Efficiency means smart planning and scheduling and also being able to use data to make smart predictions.
Some required capabilities of a decision support tool for airport operations:
Surveillance: provide identification and accurate positional information on aircraft, vehicles, and obstacles within the required area.
Guidance: facilities, information, and advice necessary to provide continuous, unambiguous, and reliable information to keep aircraft or vehicles on the surfaces and assigned routes intended for their use.
Control: Application of measures to prevent collisions, runway incursions and to ensure safe, expeditious and efficient movement.
Route planning and scheduling: The planning and assignment of routes to individual aircraft and vehicles to provide safe, expeditious, and efficient movement from its current position to its intended position.
I uploaded a survey paper on surface movement optimization (ICRAT2010.pdf)
- What's the relation between the state (S) and the sequence (s) in paper "Exact and Heuristic Algorithms for Runway Scheduling"?
- What's the objective function that we are optimizing? Average delay, last departure or makespan time?
- In paper "Exact and Heuristic Algorithms for Runway Scheduling", ILS is able to provide solutions with <10% difference from the optimal solution. Shouldn't this be good enough?
- Why the route is randomly picked at first in simulate.py?
- Why does the scheduler write to its input file instead of reading? A: scheduler reads its input from socket, so the txt files are for saving the logs. Both input and output text files should be generated from scheduler while the real input is from socket.
- It seems that there's no test code in this repo. It may be a good idea to have some (or just a high-level one-line assertion) to make sure things still work while we are making changes.
- How to interpret the data text files including
all_routes_pairs.txt,nodes.txt,links.txt,fixes.txt,ramp.txt, andrunways.txt? - What is "group" in route_arr_decision_tree file?
- What is rtas in Vehicle class?
- What is rnwy_solver doing now?
- What is the goal of this project (clear goals)?
- Can this be defined as a machine learning question as below?
We could write a script to format this model so that it could be used by the simulator.
Needed by the simulator: all_routes_pairs.txt, nodes.txt, links.txt, fixes.txt, ramp.txt, and runways.txt
I uploaded a paper JOSH2014.pdf that uses a variation of a shortest path algorithm to plan routes on a graphical model of an airport. Given a runway sequence (of arrivals and departures) the algorithm will generate a set of shortest paths for each aircraft to (arrival) or from (departure) gates.
- Project todo list on github repo: https://github.com/heronyang/airport-simulation/projects
- Will meet on the following Tuesday 4pm
- Topics
- simulation for SFO
- simulation for uncertainties
- scheduler optimization
- Scheduler problem definition (see Scheduler page)
(nodes.txt)
- Unable to find spot positions in the SFO Model. RM: It's true that they are not named. You could probably figure them out by identifying the main taxiways and the places where you exit the ramp area onto the taxiways.
- What unit of the coordinate used in the original KDFW data? RM: Lat-long?
- What is "SOSS Node Num" in
nodes.txt? Is it just an index for all the nodes? RM: Yes. SOSS = Surface Operations Simulator and Scheduler
(runways.txt)
- Why "allowed aircraft weight classes" is used only for departure? (maybe we can ignore this first) RM: I think it's because you have to factor in the speed of the aircraft when you do scheduling. And you are only scheduling departures.
(scen-dfw.scenario)
- Why spot position and runway position is included? Can they be rescheduled by the scheduler? RM: Yes
- Is the start location just relying on gate number (if departure) and runway number (if arrival)? RM: Yes
- What is try_time, active_time and turnaround? RM: Not sure
- Is "model" referring to the aircraft model? (It seems not, should be another name of the aircraft model type) RM: Where?
(other)
- I'm using this file from GitHub, is it okay? https://github.com/whit537/gheat/blob/master/__/lib/python/gmerc.py
- To modify and try: fixed period, scheduling window, frequency
- Uncertainty: on input data, etc
Planning is about generating sequences of actions or events, given some goals you want to achieve. Scheduling is about assigning times and resources (gates, taxiways, runways) to actions in a plan. A plan or schedule is feasible if it does not violate any constraints associated with the (planning or scheduling) problem you're trying to solve. Those constraints collectively make up a planning model. (What are the constraints in the airport planning and scheduling problems?)
Planning for aircraft movement can either result in sequences of locations (routes) for individual flights or sequences (queues) of events (pushback, spot arrival, departure runway). Sometimes sequences are pre-defined; for example, departure or arrival times provide an ordering for pushback sequences (but what happens when two flights have the same departure time?).
Uncertainty with airport surface operations comes from three sources: human decision-making, mechanical problems, and changes to the environment. A passenger on a departing flight might take too long finding an overhead bin for his bag. This might delay the pushback time for his flight. Mechanical problems to the aircraft or towing vehicles might delay or cancel a flight. Changes to weather conditions (an afternoon summer thunderstorm) typically delay all incoming and outgoing flights.
Uncertainty can make feasible plans infeasible. For this reason it is necessary to manage uncertainty in operations. For example, if a pushback is delayed, it may not be possible to execute a planned runway ordering. A change needs to be made to a plan, for example a reordering of the runway sequence, in order to make it feasible again.
How do you manage uncertainty? If you had a perfect predictor (a genie or a crystal ball) you could find feasible plans or schedules 'off line' and then simply run them. Because of perfect prediction every decision you make, from pushback to runway, will work. Your model will manage the uncertainty by anticipating all future states of the world.
At the other extreme of perfect prediction is a purely reactive approach, where you can't anticipate anything about the future. This requires continuously examining the global state of the world (airport surface), comparing it with your plan, and updating the plan on the fly. Specifically, you check at each time frame whether the world conforms to your plan (is the aircraft pushing back from the gate or landing? Is it at the designated spot location?) and if it does not you revise the plan accordingly.
These extremes illustrate that there are two ways of dealing with uncertainty: during planning and during operations. The first can be called model-based or proactive planning; the second can be called sensor-based (model-free) and reactive. Between these extremes there will be hybrid approaches that combine models and sensing. This is the most reasonable approach, because models will always be approximations of the behavior of complex logistic systems (and so you need sensing), but combined in some ways with state information, models will help you produce good plans.
What do we mean here by good plans? There are many reasons why a plan is good. The quality we're looking for when we talk about 'good at managing uncertainty' is "Robustness". A robust plan is one that remains feasible despite unexpected changes to the operating environment. Discussion question: How can we make a plan robust? Imagine planning in your own life. How do you make your plans robust?
Draft
class UC:
# 1. construct with factor
__init__(int factor, int speed_factor, int , TYPE): # ./run.py --factor 1.5
1.5
# 2. construct with weather
// weather -> factos -> construct with factors
self.amount_uc = amount_uc
# variables want to add uncertainty
P(x,y)=
x= original_value
y= factors
def get_uncertain_value(original_value, factor, type=SPEED/PILOT_DECISION):
return <samle from P>
...
...
def get_uncertain_ac_speed(ac_type, original_speed):
def get_delay_flights(original_flight):
def get_chances_of_pilot_is_sleeping():
return _get_uc(
class Simulation:
self.UC = UC(argv.factor)
- A separate module offering several interfaces for simulation to use
- Factor value is set in constructor, which will be the input argument specified by the simulation user
- A constructor using Weather type as input an be developed in the future
- The current analysis.py is expecting a scenario file mismatching the current one
- Will write our own analysis.py on evaluating the performance of a scheduler
- Developed link objects, so the routes are drawn on the screen
- Manually picked the SPOT positions on Google Map, and they are parsed into current code programmatically
- Working on the SFO airport, will read the schedule file (the scenario file) and draw aircrafts on screen
- RTA seems to be "expected time for the pilot to reach next node". Usually, does the tower do this kind of command? Or, it simply tell the pilot start moving.
- Can we look into the pushback route and the spot position of SFO into details. Are the pushback ways for Gate A1~A12 the red lines here: https://drive.google.com/open?id=1votbJbKKRUF5gDumno4GXOxVLAE&usp=sharing
- Should we open source?
Optimization Route Planning and Scheduling
Consider the problem of assigning routes from a gate to a runway (departures) or from a runway to a gate (arrival). A route can be viewed as a sequence of edges of a node-link graph (equivalently, a set of nodes on the graph). In one version of the problem, the routes of all the aircraft are pre-assigned. Given a gate (for departures) or arrival runway (for arrivals), there is a single route the aircraft always takes. (Maybe this single route is the shortest-time route.) If we know, for each flight, the edges (or nodes) that the aircraft will traverse, then the problem becomes a scheduling problem: assign times to each of the nodes or edges. At the other extreme, suppose that there are no constraints on the route than any aircraft may take. Then the solution requires finding both the route and the times for the route. This version of the problem combines path planning with scheduling. In between these extremes there are problems in which there are constraints on what routes are permissible, and the route chosen must satisfy these constraints. (In our toy problem, choosing a route is a simple table look up: each gate had 2 routes you could choose).
Route planning and scheduling is an optimization problem. In an optimization problems you're trying to achieve (maximizing or minimizing) some objective. Total taxi time (including delays during taxiing) is an example of an objective to minimize. So is minimizing something called makespan (the total time it takes to process all the flights). It's possible to combine objectives into a multi-objective problem, where you assign weights to the different objectives you're trying to achieve.
As we've seen, a model of the airport surface planning problem usually starts with a graphical representation of the airport surface, where nodes represent locations and paths represent direct paths between locations. Time is not represented in this spatial model, so to do scheduling, time must be added. The simplest way to imagine the effect of adding time is to imagine making copies of the graph for a set of discrete moments in time, showing the evolution of surface flow. So instead of a route consisting of a sequence of edges, we know have a route consisting of a sequence of pairs <(e, t)> of edges and times.
(Note: An alternative approach does not deal with assigning discrete times directly but rather solves an ordering problem for each aircraft for each edge or node of the network. So for each node or edge, it assigns 'true' or 'false' to statements of the form 'aircraft i arrives at node n before aircraft j'. The advantage of this approach is that time does not need to be viewed as discrete moments, but rather can be viewed as continuous, which makes solving the problem easier. This is discussed in the paper "The Airport Ground Movement Problem: Past and Current Research and Future Directions" that I posted).
There are two general methods for solving optimization path planning and scheduling problems like we're studying. One method defines the problem using Mixed Integer Linear Programming (MILP); the other main method is Heuristic Search. The MILP approach is discussed in the paper "Optimization of Taxiway Routing and Runway Scheduling", that I posted.
This summarizes much of our discussion of the toy problem we discussed in class this week.
Assumptions (for now):
- Routes predetermined through table look-up; each gate G is associated with a small set of possible routes.
- Departures only (arrivals are just departures in reverse)
- A departing flight is a triple (a, G, T) where a is the aircraft id, G is a gate, T is earliest pushback time
- A world state is a tuple (t, S = {(a, P, R)}) where t is a time and S is a set of pairs of aircraft, position and route.
- flights (a,G,T) enter the world state (become active) at time t >= T and departs the world after it reaches a designated terminal node (runway). Therefore, at some time Tt, the world state will eventually be (Tt, {}). All flights will be processed.
- A schedule D is a list of sequences of positions and times: D = {[ a: (G,t1),(p2,t2),...(pn,tn)]}, where a is the aircraft, G is its gate, and pn is a terminal (runway) node. We are looking for conflict-free schedules.
- A conflict occurs at time t if the world state contains a pair (a, P, R1) and (b, P, R2). I.e., two aircraft occupy the same position.
General form of scheduling algorithm:
Input: a set of flight requests
Output: a schedule D
Initialize W to (t, S = {(a1, G1, R1) ... (am,Gm,Rm}) containing flights with the earliest pushback time t.
While S in W is not empty:
Schedule pushback times
Simulate world state forward in time
Re-schedule to remove conflicts
Return D
Each of the three components of this algorithm can be implemented in different ways. How many ways can you think of? For example, we discussed the idea of 'look-ahead' to anticipate future conflicts.
- Flow prototyped on branch
asset2. Check scheduler file for learning the input/output format of a scheduler. The scheduler is able to access the airport state, the scenario, or ask the simulationexpected_state_afterhttps://github.com/heronyang/airport-simulation/blob/asset2/asset2/scheduler.py - Three time parameters are added, users can set the parameters they want or they can use the default ones. Check: https://github.com/heronyang/airport-simulation/blob/asset2/asset2/simulator.py
- Cache is implemented for routing table. The routing expert will calculate the routing table for the first time, the result will be saved under
cache/in a binary format. The routing expert will use the calculated routing table if they found the cached one. - New departure flights will be added to the airport based on its
appear_timelisted in the scenario file. - Updated the README file in order to let every setup the environment successfully, please let me (Heron) know if any problem encountered. https://github.com/heronyang/airport-simulation/tree/asset2/asset2
OpenStreet data is not a perfect link-node model, so
- there's no way to link to a node located on the middle of a link
- some links are not well separated like way/157111111 and way/157111112
The figure below illustrates the state of the system after the schedule has finished its work of updating the schedule for the time window starting at 'now' (the current world state) to the end of the scheduling window. Blue balls indicate events that have happened in the past (aircraft being at a certain location on the airport surface). White balls indicate expected future events (future release times from gates and future positions of aircraft on the surface, as assigned by the scheduler and predicted by the simulator). Blue dotted lines mean that the aircraft has not moved between the past and now (for example, it has remained at the gate). Black dotted lines indicate that the times between the two balls have not been scheduled yet. The black balls indicate terminal locations, which are known at scheduling time (for example, gates or runways).
Note: I updated the slide after our discussion on 11/1 to show one idea of a flexible schedule horizon, in this case to allow the end of the horizon to expand to allow unscheduled links to be scheduled. Recall that the motivation for this is to avoid delays in the world to be caused by the scheduler.
There is much work on solving stochastic shortest path problems (SSPP), which are exactly those with graphs comprised of links that are random variables. The simplest shortest path definition is then a path with the shortest expected cost. But there are other formulations of the problem that arise from the fact that mostly you want to balance risk with confidence.
There are different categories of SSPP. Offline SSPPs do not consider any feedback from the environment while the path is being traversed. On-line SSPPs do consider such feedback. In addition, there is a distinction between static and dynamic link costs; static costs are ones that do not change over time, and dynamic costs are costs that do. For example, a link between to airport surface locations may be dynamic, because the travel costs might change due to time of day.
How does this literature relate to our work? First, we are focusing currently on scheduling pushback and release times rather than paths. But there is an underlying online dynamic stochastic path planning problem we are looking at. Secondly, we're not solving a single path planning problem but a number of path planning problems, one for each aircraft. This leads to the need of generating paths that are optimal with respect to traffic flow as well as shortest paths. Traffic flow is related to delays and also to safety problems. There is work currently being done solving 'multi-agent' shortest path planning (MAPP) or 'path-finding' (MAPF) problems. We have partnered with a group from USC who specializes in MAPF algorithms.
I am not aware of any group looking at Stochastic MAPF problems, aside from us.
ASSET2 implementation had been updated according to last meeting conclusion. See: https://github.com/heronyang/airport-simulation/commit/6995fa8924305e9417000fcd5fba59f0aa2be107
How can we quantitatively measure tightness of schedule? What schedule properties lead to possible conflicts if there are unexpected delays?
By terminal nodes we mean nodes (specifically gate, taxiway enter and runway entrance nodes) at which aircraft enter and leave the surface scheduling system. Things get slightly more complex at these nodes than at internal nodes. Let’s make some distinctions in order to clarify how we talk about these nodes.
What we’ve been referring to as ’scenarios’ are inputs to the surface scheduling system, the flights that are scheduled to take off or land during a time frame. Let (ARR AA360 R1 G2 500) mean that “Flight AA360 is scheduled to arrive on R1 at time 500 and park at gate G2". For us, the time ‘500’ refers to the time that this flight is scheduled to enter the scheduling system. In the real world it represents the earliest time that the flight can exit the runway after landing and onto the taxiway (actually this is unrealistic because it does not factor in the time the aircraft is on the runway before it enters the taxiway, but this does not matter). For the scheduling system, there is a node that represents the transition between runway and taxiway. That is the arrival ’terminal node’.
Similarly, a scenario entry (DEP AA361 R1 G4 700) could mean ‘Flight AA361 is ready to depart from gate G4 at time 700 and leaves from runway R1”. Time 700 is the time the flight enters the scheduling system. It does not represent the actual pushback time for the flight; that is assigned by the scheduler. There is a node representing gate G4; this is also a terminal node because, again it’s a node where something enters the system.
One kind of uncertainty involves when an aircraft ‘actually’ enters the scheduling system. The arrival flight could enter the system at 510 rather than 500, or the departure flight could be ready to depart from the gate at time 704 rather than 700. Note that ‘delay in ready to depart’ is not the same as ‘delay in departure’. Delay in departure is when the scheduler says ‘pushback’ but the aircraft does not, whereas ‘delay in ready to depart’ means that it is not ready to pushback.
Another kind of uncertainty involves when an aircraft ‘actually’ leaves the scheduling system. Here we assume there is an asymmetry here between terminal nodes for gates and terminal nodes for runways. Specifically, for arrivals, once an aircraft is at a gate it instantly leaves the scheduling system (actually this is not realistic because a flight that arrives at a gate need to remain in the system because it may soon depart for somewhere else but we can ignore this for now). On the other hand, let’s assume that a departing flight can be delayed at a terminal runway node. Why? So we can model a runway queue! So a runway terminal node is a special kind of node in the system because multiple aircraft can be at the node at the same time, unlike any other kind of node. Note the runway queue size is completely determined by take off uncertainty. The time an aircraft leaves the scheduling system (enters the runway) is a random variable. But unlike all other nodes, which are not queues, there is no conflict if many departing aircraft enter a runway terminal node.
This week (11/8) we talked about schedule tightness. Tightness measures the overall spacing between aircraft. A tight schedule is one where the aircraft don’t have a lot of space between them. Tightness is related to robustness because if there is unexpected delay for one aircraft, the overall effect is delay everywhere else in the schedule. If we can have a measure of tightness, we might be able to make intelligent decisions about how often we need to reschedule, given the chance of uncertainty.
For example, here’s a schedule for Example 2:
R: 2,2; 4,5; 5,10
G: 1,1; 3,4; 4,9; 5,14
B: 0,0; 3,3; 4,8; 5,13
O: 6,2; 7,10; 3,12; 4,17; 2,20
Y: 6,4; 7,12; 8,16; 9,18; 3,23; 1,26
N: 6,6; 7,14; 8,18; 9,20; 3,25; 0,28
How tight is this schedule? Consider node 4. We have aircraft going through this node at times 5, 8, 9 and 17. So it’s a little tight because there’s only a space of 1 time unit at some point. Similarly, node 6 is occupied at times 2 4 and 6. So in general it’s a little less tight than node 4.
Suppose we define node tightness as the minimal time difference between consecutive visits to the node. So in this example tightness(4) = 1 and tightness(6) = 2. Then suppose we define schedule tightness as the average of the node tightness for all the nodes (alternatively we could define schedule tightness as the minimal node tightness: then a schedule is as tight as its tightest node).
We can control the effects of unexpected delays on tight schedules in two ways: by re-planning more often or by imposing tightness constraints during scheduling. An example of a tightness constraint is: no schedule should have a tightness less than 3. Notice that this amounts to a new definition of ‘conflict’. We’ve been defining conflict as ‘no two aircraft can occupy the same node at the same time’. We could revise this as ‘no two aircraft can occupy the same node within 3 time units’. In this case, the above schedule would violate this constraint and would not be generated.
Probably a better approach is to tie tightness to the the amount of re-planning that is done. If you generate a schedule that is ‘loose’ then you expect unexpected delays to have no effect on the ability to the schedule to be executed without conflict. So you don’t need to reschedule often. Conversely, if you generate a tight schedule then you need to monitor the world for unexpected delays to avoid conflict.
A simple dataset is added into ASSET2 (https://github.com/heronyang/airport-simulation/tree/master/asset2/data/simple).
To use it, simply enter the following command:
$ ./simulator.py -a simple
With GUI:
$ ./simulator.py -a simple -g
The simple data includes a scenario generated by a script. To generate another scenario with different tightness parameters, rerun the generate_scenario.py.
$ cd data/simple
$ ./generate_scenario.py
We will first test deterministic scheduling and how it degrades with an uncertain world. For us, uncertainty takes the form of delays. Specifically, an aircraft is expected to leave a node at a given time, and it does not. Our uncertainty model on the simulation side (i.e. ‘in the world’) allows us to inject delays randomly into the simulation.
Schedules can be compared with respect to the property of tightness. Recall that we can define the tightness of a node of graph in a schedule in terms of the minimum time difference between consecutive visits to the node by aircraft. (We could also define node tightness as the average time distance rather than minimal). Then, we can say that the schedule tightness is just the average (or minimum) node tightness over all nodes in the graph.
In these tests we are interested in observing the ability of a schedule to be robust to conflicts during schedule execution. We know that although a schedule might be conflict-free, there may be conditions in the world that cause conflicts while the schedule is run (let’s call these run-time conflicts). We want to design the scheduler so that run-time conflicts never happen. One way to do this is by predicting possible conflicts during scheduling (i.e. remove determinism from the scheduler). A simple way to do this would be to control the tightness of the schedule. We’re saying, in effect: we expect delays during run time, so we will systematically inject delays into the schedule in anticipation of delays in the world. Unless we’re lucky, this approach will lead to sub-optimal schedules with respect of minimizing delays.
The other thing we can do is re-plan. This can be viewed as a sort of re-calibration: the world takes our schedule and moves it 'off course' through delays. By re-planning we bring the schedule back in line with the world before run-time conflicts happen.
To set up the experiment we need to
-
generate many schedules that differ in tightness. We could generate at least 50 schedules for a range that represents high tightness (1-5) medium tightness (6-10) and low tightness (11-15). Maybe other ranges are more meaningful.
-
have a procedure for detecting run-time conflicts (the simulator should halt at that point)
-
have a control parameter that allows for changing the amount of uncertainty during simulation.
-
have a re-planning capability and a parameter that controls the amount of re-planning performed.
-
have a way to collect statistics counting the number of conflicts that occur, for schedules of varying tightness and for varying degrees of uncertainty.
Test 1 (See figure). In this test the goal is to measure the effects of schedule tightness on the amount of run-time conflicts, for varying degrees of uncertainty. With no uncertainty, there are never any conflicts, no matter how tight or loose the schedule is. When you inject uncertainty, you expect a curve that peaks at the tightest schedules (tightness = 1) and goes down with less tight schedules. With more uncertainty, the curve starts higher and degrades to 0 more slowly with less tightness. Let’s see what those curves look like.
Test 2. In this test, we fix the level of tightness and measure the effect of different levels of re-planning on the amount of run-time conflicts. We expect that at some level of re-planning, say every 5 seconds, there are never any conflict, no matter what reasonable level of uncertainty is imposed. (Of course, we could impose a ‘herding cats’ level of uncertainty that would make it impossible to schedule anything, but this is not reasonable). In general we expect that the more re-planning we do, the more uncertainty the schedule can tolerate without run-time conflict.
- Adds makespan in result. Makespan is a common measure of quality of schedule. Specifically, the makespan of a schedule is the time that the last aircraft is scheduled to "leave the system" (not, of course, the time it actually departs).
- Checks number of flights departed.
Today we saw that too much looseness in a schedule can be a bad thing. What's the loosest feasible schedule you can generate? Theoretically, you can make a schedule arbitrarily loose and still be feasible. Suppose you only let one aircraft on the surface at a time, and hold all the other flights at the gate or in the air until the flight has left the system. That's a very loose schedule but it's also a bad schedule. Imposing looseness on a schedule to guarantee robustness results in generally bad schedules, if good schedules are ones that minimize delay. We saw this today: imposing looseness means you must delay aircraft entering and exiting the system, as well as delaying them on the surface. As we know because we fly, delays at the gate or in the air are bad things.
This shows that it's better to aim for the tightest schedule you can, given the uncertainty in the world. As we know, re-scheduing is a way to ensure robustness because it's a way to monitor and respond to changes in the world. There is a cost for rescheduling in processing time (either human or machine) but in general it's cheaper than the cost for unnecessary delays as a result of imposing delays at scheduling time. Thus we can control the amount of replanning we do as well as the tightness of the schedule, and in general it's better to generate tight schedules and then incur the cost of rescheduling. On the other hand, an interesting question is whether you can give up a little tightness at schedule time for less rescheduling. Suppose for example that by reducing the tightness of a schedule by 5% you can reduce the amount of replanning you do by 50% and still get the same amount of robustness.
Check Independent Study for progress like todos.
- Our approach belongs to MILP or GA?
Currently, our approach belongs to neither. We're using a version of constraint-based solving that is current in AI approaches.
- What are the virtual nodes?
_??? _
- [Clare 2009] Why it's globally optimal?
I think their approach is not guaranteed to be globally optimal. That's the consequence of the divide-and-conquer approach.
- How will we define robustness?
I think we can use the same definition we've used previously.
-
Which part of the airport are we going to pick? And, which runways are we going to model? Map link
-
Recommended material for learning how to write paper? or, acadamic writing in general.
_Learn by doing! :) _
“Rolling Horizon” (RH) Scheduling. This is our approach as well, although we propose some changes.
Motivation: Divide a large problem into a sequence of smaller problems. This makes computation quicker and also addresses the fact that because of uncertainty, a lot of computation of future plans is potentially wasted.
Assumes a graphical (node-link) model of airport surface. Assigns a planning horizon of k future nodes. At each planning episode, each active aircraft (i.e. one in the system) is scheduled for the next k nodes. k is the planning horizon. There is also an execution horizon (in time units) which is the time between replanning.
The input parameters to the problem are:
-
The airport parameters (node-link model, designated gate, spot and runway nodes)
-
Fixed aircraft parameters (arriving/departing, origin time, start/destination nodes, maximum/minimum speed limits)
-
Dynamic aircraft parameters (active/inactive, current position, current origin/designation node
-
Separation rules (temporal separation limits between aircraft on surface)
Decision variables:
Route of aircraft (note that this is pre-determined in our current implementation) R(a,k): the k-th node in aircraft a’s route
Time at which aircraft passes the nth node in its plan T(a,n)
The planning solution operates as follows. The first step is to generate paths for all active aircraft. The second step is to do conflict resolution for the resulting schedule. Conflict resolution is an iterative process. We have a list of constraints. For each constraint, we check whether the schedule violates the constraint. If it does, we add a new constraint to the schedule that prevents the violation from occurring. The process is repeated until the schedule is conflict-free.
Constraints:
Initial conditions: the first node in the plan will be the next node from the aircraft’s current location at the beginning of the planning cycle; the time it reaches that node is a function of its velocity, and whether it’s entering or exiting the system.
Routing constraints: the route must be possible given the airport connectivity; also there can’t be circular movement or backing up movement.
Speed constraints: movement must be consistent with aircraft speed capabilities;
Separation constraints: if two routes involving different aircraft intersect the same node, the time between the aircraft appearing at the node must be greater than some minimum time.
Cost-to-go constraint. A variable tD stores a prediction of the time it will take from the end of the planning horizon to the end of the route (runway or gate). The use of this variable is somewhat vague but it seems to ensure that the route chosen during the planning horizon remains the shortest path available.
Runway scheduling constraint (departures only). This ensures proper separation at the runway, using the variable tD. Note: I don’t think this constraint is required if we assume that the terminal node for departures is a queue.
Cost function: a weighted sum of the longest taxi time of all active aircraft, the total taxi time over all the aircraft, and the total taxi distance.
Implementation: To implement this solution they use Mixed Integer Linear Programming (MILP). Instead of this, we are considering maintaining the graphical model and doing conflict resolution using an algorithm that inserts resolving constraints directly into the schedule. This is similar to approaches in AI planning and scheduling.
In Hanbong Lee's Thesis, he identified the following sources of uncertainty on the airport surface:
- Pushback times from gates (departures): the difference between scheduled pushback and actual pushback
- Taxiway entrance (arrivals): There are sometimes many exits from the runway onto the taxiway; the pilot will make the choice.
- Taxi or ramp area speeds (arrivals and departures): the speed of the aircraft at any point
- Separation times between takeoff (departures): how much time there is between successive takeoffs.
Parameters
- uncertainty (% of the amount, delay time):
- small: 0.2, medium: 0.5, large: 0.9
- reschedule time + resolve_conflicts_time
- (delay added to solve conflicts)
Metric
- number of conflicts
- makaspan
- delay
- queue size
Problem
- execution cost (time)
100 > n > 10