Multi-Agent Task Allocation and Path Planning for Autonomous Ground Support Equipment

Master of Science Thesis

Master thesis (2023)

Authors

M. van der Zwan Aerospace Engineering

Contributors

Alexei Sharpanskykh Air Transport & Operations - Aerospace Engineering (supervisor 1)
G. Ermis Air Transport & Operations - Aerospace Engineering (supervisor 2)
Faculty
Aerospace Engineering
Copyright: © 2023 Manouk van der Zwan
More Info
expand_more

Published Date

19-12-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Aerospace Engineering

Abstract

Many large airports aim to have complete autonomous airside operations in the future. Amsterdam Airport Schiphol (AAS) for example, launched the Autonomous Airside Operations program to achieve this goal. Our main contribution is to present a Multi-agent Pickup-and-Delivery (MAPD) model that uses a centralized task allocation mechanism to improve the performance of integrated task allocation and path planning for autonomous ground handling operations compared to previous research. This study models a global multi-vehicle Pickup and Delivery Problem with Time Windows (PDPTW) for the scheduling of autonomous ground handling tasks. A warm start multi-objective mixed integer linear programming model is proposed to solve the scheduling problem where the initial feasible solution is obtained by an insertion heuristic. This multi-agent task allocation model, when combined with multi-agent path planning, forms a MAPD model for modeling autonomous ground handling operations. Multi-agent path planning is solved using prioritized Safe Interval Path Planning (SIPP). A replanning model is developed to assess the resilience of our model to disruptions of operations. Also, a mixed integer nonlinear programming model, which includes an additional non-linear objective, is proposed to generate more realistic task assignments by minimizing the waiting time of vehicles on the aircraft stands. In this study, a four-hour planning window with three aircraft stands at AAS is used for the experiments. The results show that the proposed approach improves the computational time of the task allocation model with 48% for the normal traffic scenario, compared to the previously published results. The conflict-free routes of all ground support equipment (GSE) vehicles are all successful and close to the shortest path results, with an average increase of 0.04% and 10% for the path length and the duration of the path, respectively. Our model is therefore able to generate complete, high quality solutions in less than three minutes.