Efficient trajectory planning for a fleet of vehicles

Abstract

A method of planning trajectories for vehicles operating in a common environment, wherein movements of each vehicle are controllable by a control signal is provided the method includes for each vehicle, obtaining a predefined vehicle path to be traversed; performing a first computation to obtain a vehicle crossing orderat each mutually exclusive—MUTEX—zone between two vehicle paths, wherein the first computation is subject to safety constraints; and performing trajectory planning subject to the obtained vehicle crossing order at the MUTEX zones, to obtain a control signal for each of the vehicles. The method further includes assigning a dependency metric to each pair of vehicles, and partitioning the vehicles into a number Nof vehicle subsets such that the dependency metric exceeds a threshold within each, wherein the trajectory planning is performed as multiple independent subproblems, each relating to one of the vehicle subsets.