1 of 31

Airport Ground Operations Scheduling

1/21

Planning & Reasoning 2024-2025

Vincenzo Crisà 2143080

Stefano D’Urso 2143081

Fabrizio Italia 2143104

​

2 of 31

1. PDDL

​

  • Description
  • Constraints
  • Predicates
  • Functions
  • Actions
  • General Problem
  • Instances

3 of 31

Description

1 Domain

The goal is to efficiently manage the movement and allocation of planes, runways, and gates in an airport.

Planes arrive at the airport and require an available runway for

landing.

Once landed, they must taxi to a gate for passenger unloading

and boarding.

After completing operations at the gate, the planes need a

runway to take off.

4 of 31

Constraints

1 Domain

Constraints include:

  • Runways can only be used by one plane at a time.
  • Gates have limited availability and can accommodate only one plane at a time.
  • Taxiing between runways and gates consumes time and fuel level.

​

The system should minimize fuel consumption while ensuring efficient use of runways and gates.

5 of 31

Predicates

1 Domain

(plane-at ?p - plane ?l - object)

Plane p is at a location l (runway or gate)

(gate-available ?g - gate)

Gate g is available for assignment

(runway-available ?r - runway)

Runway r is available for landing or takeoff

(waiting-to-land ?p - plane)

Plane p is waiting to land

(plane-takenoff ?p - plane)

Plane p has taken off

(passengers-loaded ?p - plane)

Plane p has passengers on board

(has-unloaded-passengers ?p - plane)

Plane p disembarked passengers at the gate

(has-loaded-passengers ?p - plane)

Plane p boarded passengers at the gate

(assigned-gate ?p -plane ?g -gate)

Plane p has assigned gate g

(priority ?p - plane)

Plane p is a priority plane

6 of 31

Functions

1 Domain

(taxi-time ?p - plane ?g - gate)

Time needed to taxi from gate to runway and viceversa

(fuel-level ?p - plane)

Amount of fuel remaining in the plane

(fuel-consumption-rate ?p - plane)

Fuel consumption per action

(total-cost)

Cost to minimize

7 of 31

Actions

1 Domain

​

LAND

TAXI TO ASSIGNED GATE

Preconditions

The plane is waiting to land.

The runway is available.

The plane has passengers loaded.

The plane has priority or no higher-priority planes are waiting.

The plane is at a runway.

The assigned gate is available.

The plane has passengers loaded.

The plane has priority or no higher-priority planes are ahead.

Sufficient fuel for taxiing.

Effects

The plane lands and is now at the runway.

The runway becomes unavailable.

The plane is no longer waiting to land.

The plane moves to the assigned gate.

The gate becomes unavailable.

The runway becomes available.

Cost

2 × fuel consumption rate

taxi time × fuel consumption rate

8 of 31

Actions

1 Domain

​

TAXI TO GATE

UNLOAD PASSENGERS

Preconditions

The plane is at a runway.

An available gate exists.

The plane has passengers loaded.

The plane has priority or no higher-priority planes are ahead.

Sufficient fuel for taxiing.

The plane is at a gate.

The plane has passengers loaded.

Effects

The plane moves to an available gate.

The gate becomes unavailable.

The runway becomes available.

Passengers are unloaded.

Cost

taxi time × fuel consumption rate

No additional cost

9 of 31

Actions

1 Domain

​

REFUEL PLANE

LOAD PASSENGERS

Preconditions

The plane is at a gate.

The fuel level is not enougth to go to the runway and take off.

The plane is at a gate.

The plane has already unloaded its previous passengers.

Effects

The plane’s fuel level increases by 50 units.

The plane now has loaded passengers.

Cost

No additional cost

No additional cost

10 of 31

Actions

1 Domain

​

TAXI TO RUNWAY

TAKE OFF

Preconditions

The plane is at a gate.

The plane has passengers loaded.

The runway is available.

The plane has priority or no higher-priority planes are ahead.

Sufficient fuel for taxiing and landing.

The plane is at a runway.

The plane has passengers loaded.

The plane has priority or no higher-priority planes are ahead.

The plane has minimum 10 units of fuel.

Effects

The plane moves to the runway.

The runway becomes unavailable.

The gate becomes available.

The plane takes off.

The runway becomes available again.

Cost

taxi time × fuel consumption rate

Fuel consumption of 10 units.

11 of 31

General problem

1 Domain

In the problem files the different design choices of the initial state are related to

• Planes that are waiting to land.

  • Available runways and gates.
  • Initial fuel level of each plane.
  • Taxi time for each plane to each gate (and runway).
  • Fuel consumption rate of the actions.
  • The eventual assigned gate of each plane.
  • The eventual high-priority planes.

The goal is to take off all the planes, after their landing and gating process.

​

12 of 31

Instances

1 Domain

Planes

Available gates

Available runways

Fuel level

Taxi time

Fuel consumption rate

Assigned gate

High

priority

P1

P2

G1

G2

G3

R1

P1: 10

P2: 20

​

G1

G2

P1: 0.5

P2: 0.2

-

-

P1

1

0.5

P2

0.2

0.3

P1

P2

P3

G1

G2

G3

G4

R1

R2

P1: 10

P2: 20

P3: 30

​

G1

G2

G3

P1: 0.5

P2: 0.2

P3: 0.3

P1: G1

P2: G2

-

P1

1

0.5

0.3

P2

0.2

0.3

0.8

P3

0.4

0.6

1

P1

P2

P3

P4

P5

​

​

G1

G2

G3

G4

G5

R1

R2

R3

​

P1: 10

P2: 20

P3: 30

P4: 80

P5: 20

​

G1

G2

G3

G4

G5

P1: 0.5

P2: 0.2

P3: 0.3

P4: 0.4

P5: 0.6

-

P1

P2

P1

1

0.5

0.3

0.4

0.2

P2

0.2

0.3

0.8

0.4

0.3

P3

0.4

0.6

1

0.3

0.7

P4

0.1

0.2

0.4

0.3

0.7

P5

0.3

0.4

0.7

1

1.2

Instance 1

Instance 2

Instance 3

13 of 31

2. The Planner

​

  • ENHSP-20
  • Algorithms and heuristics
  • Results
  • sat-hadd vs opt-hmax
  • Plans

​

14 of 31

ENHSP-20

2 The Planner

Expressive Numeric Heuristic Search Planner is a PDDL automated planning system that supports classical and numeric Planning.

The planner reads in input a PDDL domain and problem file and it provides a sequence of actions to achieve the goal state starting from an initial state.

ENHSP transforms the PDDL descriptions into a graph-search problem where nodes represent states visited by the planner. The planner builds this graph in an incremental forward fashion and is guided by a heuristic function to explore only those nodes whose associated state is reachable from the initial state and get the planner closer to the goals.

To run the planner use the command ./run_enhsp.sh, where ENHSP-20 is executed with two different configurations for each instance: sat-hadd and opt-hmax.

The chosen metric to be minimized is the sum of the actions costs, which are proportional to the fuel consumption rate and taxi time.

15 of 31

Algorithms and heuristics

2 The Planner

 

16 of 31

Results

2 The Planner

​

sat-hadd

opt-hmax

​

Inst. 1

Inst. 2

Inst. 3

Inst. 1

Inst. 2

Inst. 3

​

24.78

37.36

75.5

11.25

11.5

12.38

Metric

21.98

33.72

55.12

21.98

33.72

55.12

Plan length

13

19

31

13

19

31

Planning time

599 ms

457 ms

3.5 min

974 ms

794 ms

4.2 min

Heuristic time

17 ms

17 ms

3.15 min

46 ms

68 ms

3.6 min

Search time

43 ms

39 ms

3.5 min

156 ms

165 ms

4.2 min

Expanded

81

28

689,916

86

772

1,591,350

Evaluated

101

74

1,423,817

109

962

1,898,302

Duplicates

108

16

3,755,167

104

1852

7,153,641

Dead-Ends

0

4

0

0

60

0

17 of 31

sat-hadd vs opt-hmax

2 The Planner

18 of 31

Plans

2 The Planner

sat-hadd

opt-hmax

(land-plane P1 R1)

(taxi-to-gate P1 R1 G2)

(land-plane P2 R1)

(taxi-to-gate P2 R1 G1)

(unload-passengers P1 G2)

(load-passengers P1 G2)

(refuel-plane P1 G2)

(taxi-to-runway P1 G2 R1)

(takeoff P1 R1)

(unload-passengers P2 G1)

(load-passengers P2 G1)

(taxi-to-runway P2 G1 R1)

(takeoff P2 R1)

(land-plane P1 R1)

(taxi-to-gate P1 R1 G2)

(unload-passengers P1 G2)

(load-passengers P1 G2)

(refuel-plane P1 G2)

(taxi-to-runway P1 G2 R1)

(takeoff P1 R1)

(land-plane P2 R1)

(taxi-to-gate P2 R1 G1)

(unload-passengers P2 G1)

(load-passengers P2 G1)

(taxi-to-runway P2 G1 R1)

(takeoff P2 R1)

19 of 31

Plans

2 The Planner

sat-hadd

opt-hmax

(land-plane P1 R1)

(land-plane P3 R2)

(taxi-to-assigned-gate P1 R1 G1)

(land-plane P2 R1)

(taxi-to-gate P3 R2 G3)

(taxi-to-assigned-gate P2 R1 G2)

(unload-passengers P3 G3)

(load-passengers P3 G3)

(taxi-to-runway P3 G3 R1)

(takeoff P3 R1)

(unload-passengers P2 G2)

(load-passengers P2 G2)

(taxi-to-runway P2 G2 R1)

(takeoff P2 R1)

(unload-passengers P1 G1)

(refuel-plane P1 G1)

(load-passengers P1 G1)

(taxi-to-runway P1 G1 R1)

(takeoff P1 R1)

(land-plane P1 R1)

(taxi-to-assigned-gate P1 R1 G1)

(unload-passengers P1 G1)

(refuel-plane P1 G1)

(land-plane P3 R2)

(taxi-to-gate P3 R2 G3)

(unload-passengers P3 G3)

(load-passengers P3 G3)

(load-passengers P1 G1)

(taxi-to-runway P3 G3 R1)

(takeoff P3 R1)

(land-plane P2 R1)

(taxi-to-runway P1 G1 R2)

(takeoff P1 R2)

(taxi-to-assigned-gate P2 R1 G2)

(unload-passengers P2 G2)

(load-passengers P2 G2)

(taxi-to-runway P2 G2 R1)

(takeoff P2 R1)

20 of 31

Plans

2 The Planner

sat-hadd

opt-hmax

(land-plane P1 R3)

(land-plane P2 R2)

(land-plane P5 R1)

(taxi-to-gate P1 R3 G3)

(land-plane P3 R3)

(taxi-to-gate P2 R2 G5)

(taxi-to-gate P3 R3 G4)

(land-plane P4 R3)

(unload-passengers P3 G4)

(load-passengers P3 G4)

(unload-passengers P1 G3)

(taxi-to-gate P5 R1 G1)

(unload-passengers P5 G1)

(load-passengers P1 G3)

(load-passengers P5 G1)

(refuel-plane P1 G3)

(taxi-to-gate P4 R3 G2)

(taxi-to-runway P1 G3 R2)

(takeoff P1 R2)

(unload-passengers P2 G5)

(load-passengers P2 G5)

(taxi-to-runway P2 G5 R1)

(takeoff P2 R1)

(taxi-to-runway P5 G1 R2)

(takeoff P5 R2)

(taxi-to-runway P3 G4 R3)

(takeoff P3 R3)

(unload-passengers P4 G2)

(load-passengers P4 G2)

(taxi-to-runway P4 G2 R1)

(takeoff P4 R1)

(land-plane P1 R3)

(land-plane P2 R2)

(land-plane P5 R1)

(taxi-to-gate P2 R2 G5)

(unload-passengers P2 G5)

(load-passengers P2 G5)

(taxi-to-runway P2 G5 R2)

(takeoff P2 R2)

(taxi-to-gate P1 R3 G3)

(unload-passengers P1 G3)

(refuel-plane P1 G3)

(taxi-to-gate P5 R1 G1)

(unload-passengers P5 G1)

(load-passengers P5 G1)

(land-plane P4 R3)

(taxi-to-gate P4 R3 G2)

(unload-passengers P4 G2)

(load-passengers P1 G3)

(load-passengers P4 G2)

(taxi-to-runway P1 G3 R2)

(takeoff P1 R2)

(taxi-to-runway P4 G2 R1)

(taxi-to-runway P5 G1 R3)

(takeoff P5 R3)

(land-plane P3 R3)

(taxi-to-gate P3 R3 G4)

(unload-passengers P3 G4)

(load-passengers P3 G4)

(taxi-to-runway P3 G4 R3)

(takeoff P3 R3)

(takeoff P4 R1)

21 of 31

Conclusion

2 The Planner

 

22 of 31

3. IndiGolog

​

  • Reasoning tasks
  • Relational fluents
  • Functional fluents
  • Controllers
  • Simple
  • Smart
  • Exogenous

23 of 31

Reasoning tasks

3 IndiGolog

IndiGolog is applied to the management of airport operations, specifically in handling aircraft landings, taxiing, passenger management, and takeoff processes.

It uses different controllers:

  • Simple scheduling for sequential operations.
  • Smart scheduling for efficient gate assignment, based on the planes dimensions.
  • Exogenous scheduling to incorporate dynamic and emergency landings.

​

24 of 31

Relational Fluents

3 IndiGolog

waitingToLand(Plane)

The plane is waiting for landing.

passengersLoaded(Plane)

Indicates passengers are on board.

hasPassengersLoaded(Plane)

Passengers have been successfully loaded.

hasPassengersUnloaded(Plane)

Passengers have disembarked.

planeTakeonOff(Plane)

The plane has taken off.

gateAvailable(G)

Checks if a gate is available.

runwayAvailable(R)

Checks if a runway is available.

emergency(Plane)

Indicates an emergency for the specified plane.

requestToLand(Plane)

The plane has requested permission to land.

new_land

Represents the occurrence of a new landing.

25 of 31

Functional Fluents

3 IndiGolog

gate(Plane)

The assigned gate for the plane.

runway(Plane)

The assigned runway for the plane.

dim(Plane)

The plane’s dimensions, which influence scheduling.

26 of 31

Simple controller

3 IndiGolog

The Simple controller iterates through all waiting planes, handling their departure in a simple manner without considering aircraft dimensions.

The controller combines the following basic procedures:

proc(go_to_gate(P,R,G), [land(P,R),taxiToGate(P,R,G)]).

​

proc(handle_passengers(P,G), [unload(P,G), load(P,G)]).

​

proc(departure(P,G,R), [taxiToRunway(P,G,R), takeoff(P,R)]).

27 of 31

Smart controller

3 IndiGolog

The Smart controller iterates through all waiting planes accounting for plane dimensions and available gates.

It follows these steps:

  • Selects a runway if available.
  • Assigns a gate based on its availability and the aircraft’s dimensions.
  • After unloading and loading passengers, moves the plane to another available runway for departure.

28 of 31

Exogenous controller

3 IndiGolog

The Exogenous controller introduces dynamic and emergency landings mechanism through prioritized interrupts:

  • If an emergency occurs, it immediately schedules an emergency landing.
  • Otherwise, it follows the same scheduling procedure used by the smart controller.
  • It enqueues the new incoming aircraft.

29 of 31

Exogenous controller

3 IndiGolog

30 of 31

Authors

Fabrizio Italia 2143104

italia.2143104@studenti.uniroma1.it

Stefano D’Urso 2143081

durso.2143081@studenti.uniroma1.it

Vincenzo Crisà 2143080

crisa.2143080@studenti.uniroma1.it

31 of 31

Thank you for the attention!