Airport simulation for evaluation of airport gate assignment problem
Introduction
Airport management is a complex problem. It is composed of many smaller problems of which one is the airport gate assignment problem (AGAP). AGAP was heavily researched over the years, with many papers about different methods to solve it. One problem about AGAP is how to evaluate it. We propose agent based simulation of an airport.
Layout generation
To make the simulator flexible it is able to generate airport definition based on .jpg images. Each layout is divided into 4 parts:
- Contour (contour of the airport)
- Objects (usually large objects on the airport, like shops and restaurants)
- Items (small additional objects, like planes)
- Gates
Each element is generated using color contrasts. Contour has no color definition and is generated by performing color conversion to grayscale and selecting area using binary threshold. All elements that are not connected to the main building are not considered a contour.
Objects, Items and Gates are selected in the similar way to contour. Only difference is that we’re performing detection based on user defined colors and size thresholds. Each of them has its own definition which looks like:
R,G,B name fill min_size max_size
- `R` — integer 0–255 (value for red color)
- `G` — integer 0–255 (value for green color)
- `B` — integer 0–255 (value for blue color)
- `name` — string, name of the object e.g. `restaurant`
- `fill` — string, either `fill` or `nofill` (optional, defaults to `fill`)
- `min_size` — integer, min size of the object in pixels (optional)
- `max_size` — integer, max size of the object in pixels (optional)
Layout parser has additional settings to reduce image noise and prevent unwanted objects from appearing on the output layout. First of them is OBJECTS_EPS, this setting allows to set a minimum size for elements from Object to be considered an Object. Each element below that size is rejected. Value of this setting corresponds to proportional size of the layout. That means if a user wants Object to be only above 1% of the total layout, he needs to set that value to 0.01. Items have a similar threshold setting called SMALL_ITEMS_EPS and it works similar to OBJECTS_EPS. When using those values you have to remember that OBJECTS_EPS is a top limit for Items so we could define it like:
SMALL_ITEMS_EPS < Items < OBJECTS_EPS < Objects
Gates are a special type of objects, they are required and defined only by color (R,G,B). Another difference is that every Gate has a unique incremental ID (other elements have hash) which is used by the simulator. Those IDs could be defined prior to the layout generation.
It is important to use images in high resolution without additional compression which could impact processing. Layout processing produces .json file used by the rest of the simulator.
For quickstart, please head to https://github.com/burnpiro/airport-ai/tree/main/layout_parser#layout-parser
If you want to check layout.json specification it is described under in https://github.com/burnpiro/airport-ai/wiki/Layout-structure
Simulation
For purposes of simulation we divided the airport area into a grid. This allows us to discretize positions in the airport.
Agents
To simulate movement of people in the airport we use agents. There are 3 forces acting on each agent. Attraction force Fatt(ai) that guides agent towards a goal. This force is based on preferred velocity of agent. Preferred velocity is computed based on the direction of the shortest path to a goal. Social force Fsoc(ai) prevents agents from colliding with each other. Collision force Fcoll(ai) pushes agents out of the walls on collision.
Let A denote a set of agents in simulation. Force acting on an agent ai is given by:
, where:
Here m denotes mass of an actor, v pref, preffered velocity, v velocity of an actor, α is social scaling constant, β is agent’s personal space drop-off constant, n_ij is normal direction between agent i and j, n_ig is direction torwards grid (0 if agent is in grid), γ is strength of collision force.
Finding shortest paths
We calculate and store paths from every cell in the grid to every possible goal of agents (entrance, exit, gates). For pathfinding modified Dijkstra algorithm is used. Paths generated by the Dijkstra algorithm will often go very close to the walls and corners, which is unnatural for human movement. In order to create paths that lead to the target and avoid going close to the walls we subtract distance from the nearest wall from the distance, when calculating distance between cells. To make sure distances stay positive we add maximum distance to the wall found in the grid to calculated distance. Resulting distance between two neighbouring cells is:
where d(i, j) distance between cells i and j used in Dijkstra algorithm, pi position of cell i in the grid, |pi-pj| euclidean distance between cells i and j, dist(j) distance of cell j from the closest wall.
Flight schedule generation
To create random simulations we have to randomly generate flight schedule. To generate flight schedule we set length of schedule T and number of flights 2n (n arrivals and n departures).
Then we schedule each flight to random time from range (45, T) — from 45 minutes after start of simulation to the end of schedule length.
Airport procedures
Arrivals
When flight arrives it goes to its assigned gate. If the assigned gate is not free it waits for it to free (adding to delay). After that plane waits 5 minutes at the gate, then for 15 minutes passengers leave the plane. After the next 5 minutes flight is removed and the gate is freed.
Departures
Agents are spawned at the entrance of the airport before scheduled departure time. Spawn time is random from range of 20 to 60 minutes before scheduled departure time. Times are sampled from beta distribution with α=β=2 (interpolated to [20 min;60 min] range).
Airplane is taken to the gate 30 minutes before departure. If the assigned gate is not free, delay is increased until the gate is freed. After 30 minutes at the gate if all passengers boarded plane, airplane leaves and the gate is freed. If some passengers didn’t make it in time, plane waits for them which increases the delay.
Web application
Visualization application is created using ReactJS and connected to Simulation Server with websocket. Both applications are Dockerized and independent from each other. As the Simulator’s purpose is evaluation and/or training of AGAP solutions, Web application is used just as a helper tool that comes in the package.
Web application is using the same layout.json definition to construct the airport’s layout. Every type Object and Item is considered to be a separate layer in the application so the user could easily turn it off and on. Communication between Simulator and web application exchanges timestamped data, each data pack has 3 sets of objects:
- Passengers (also called Agents, position of each passenger on the airport)
- Flights (flight schedule)
- Gates (gate/flight status, it defined which gate is taken and by which flight number)
Full definition of that structure is available at https://github.com/burnpiro/airport-ai/wiki/Data-structure
Flight scheduler shows the current status of flights on the airport. Each flight has a preassigned gate which might change based on AGAP solution and current simulation status. It also has its own status, either “On Time” or “Delayed”. Planes and Gates have the same ID and are displaying current FlightID (above) and GateID (below):
Github project
https://github.com/burnpiro/airport-ai
References
Patil, Sachin, et al. “Directing crowd simulations using navigation fields.” IEEE transactions on visualization and computer graphics 17.2 (2010): 244–254.
Bouras, Abdelghani, et al. “The airport gate assignment problem: a survey.” The scientific world journal 2014 (2014).
Daş, Gülesin Sena, Fatma Gzara, and Thomas Stützle. “A review on airport gate assignment problems: Single versus multi objective approaches.” Omega 92 (2020): 102146.
