Integrated Task Assignment and Trajectory Planning for a Massive Number of Agents Based on Bilayer-Coupled Mean Field Games

Aiming at the problem of integrated task assignment and trajectory planning of a massive number of agents in the scenario with different priority task nodes and multiple static obstacles, this paper proposes a general framework based on bilayer-coupled mean field games, which couples the minimum cost of trajectory planning of an agent in the task assignment process to achieve a reasonable, globally optimal, and targeted adjustable assignment result. In the proposed general framework, firstly, the multi-population mean field game is used to plan the optimal trajectory of an agent between each pair of priority adjacent task nodes, and the minimum costs are calculated. Then, based on the discrete time finite state space mean field game, a task assignment model in the discrete task space is constructed, and the minimum costs obtained in the trajectory planning are coupled into the model as a reference, the task assignment strategies are finally obtained. Moreover, we give a specific example of the proposed general framework and prove the existence of equilibrium solutions of two mean field games. The effectiveness of the proposed general framework is demonstrated through simulation experiments and results analysis. Note to Practitioners—In multi-agent decision-making and control, task assignment and trajectory planning are two fundamental problems that coexist in many scenarios. Examples include the collaborative exploration of multiple task areas by UAV swarm, and the lane selection and efficient driving of autonomous vehicles. There are many methods for dealing with the integrated task assignment and trajectory planning. However, they have difficulties in dealing with large-scale agent problems, mainly due to the significant increase in communication and computation costs as the number of agents increases. In response to this problem, based on the characteristic of mean field game that transforms the game between individuals into a game between an individual and the whole, this paper proposes a general framework of bilayer-coupled mean field games for the scenario with different priority task nodes and multiple static obstacles. The multi-population mean field game is used to plan the optimal trajectory of agents, and the discrete time finite state space mean field game is utilized for task assignment, in which the cost of trajectory planning between task nodes is considered. We propose a specific example model and theoretically prove the existence of an equilibrium solution of this model. The effectiveness of the general framework is verified by simulation experiments and results analysis.

I. Introduction

As task scenarios become more and more complex, much attention has been paid to enabling multi-agent algorithms to solve the integrated task assignment and trajectory planning (ITATP) problem [1], [2], [3]. ITATP requires agents to complete both tasks simultaneously: On the one hand, it is necessary for swarms to plan the trajectory reasonably of each agent to achieve goals such as avoiding obstacles, and on the other hand, it is necessary to assign goals reasonably for each agent so that all goals can be completed in a timely and efficient manner. ITATP is required by many unmanned system applications in real world scenarios, such as outdoor firefighting and warehousing & logistics.