Multi-agent task allocation and path planning for autonomous ground support equipment

We aim to contribute to the automation of ground handling tasks using autonomous ground support equipment (GSE) at airports. Automation of airside operations has recently become critical for the airports to achieve higher levels of safety and efficiency under growing traffic demand and requires solving a complex scheduling and path planning problem. To address this problem, we present a multi-agent task allocation and path planning model for handling airside operations on the apron. In the problem, the ground handling tasks are to be allocated to the equipment, the trips of vehicles should be scheduled within specific time windows considering the flight schedules, and the collisions of vehicles on the apron and service roads should be avoided. We present a centralized multi-agent task allocation and routing model which aims to optimize the allocation and routing of various types of ground handling tasks over a heterogeneous set of GSE vehicles. We convert the allocation and routing problem into vehicle routing problem with time windows, pick-ups, deliveries and solve the problem using a warm start mixed integer linear programming (MILP) model. We also introduce a nonlinear objective function which converts the MILP model into a mixed integer nonlinear programming (MINLP) model, to minimize the time service locations at the stands are occupied. Then, we solve the corresponding path finding problem to find collision free paths for the GSE, by the multi-agent path finding model. The proposed model outperforms the decentralized approach in previous research regarding the allocation rate of assigning tasks to vehicles and the performance indicators of finding conflict free paths, and in CPU time. The mean deviations from shortest paths were considerably small in path planning which means that the solution quality was high. Furthermore, the CPU time of allocating tasks has been reduced by 48% compared to the CPU time of decentralized allocation.