Network-Flow-Problem-Based Approach to Multi-Agent Path Finding for Connected Autonomous Vehicles

Vehicle coordination is one of the essential technologies for connected autonomous vehicles (CAVs). It is necessary for the route-level coordination as well as trajectory-level coordination to solve conflicts among vehicles in congested situations. The multi-agent path finding problem (MAPF) has been studied to efficiently find collision-free paths (i.e., routes) on a graph for a large number of agents. However, the paths cannot be applied for CAVs because the vehicle's kinematic constraints are not considered in the standard MAPF. This paper proposes a new variant of MAPF that considers the orientation and dimensions for CAVs by extending the graph structure and collision definition to obtain paths that can generate feasible trajectories in the real world. The proposed MAPF is formulated by a network flow problem approach using 0-1 integer linear programming. A trajectory generation based on the paths by MAPF is also implemented and the feasibility of the paths are confirmed by simulations for CAVs.