Scalable Markov chain approximation for a safe intercept navigation in the presence of multiple vehicles

This paper studies a safe intercept navigation which accounts for the uncertainty of other vehicles’ trajectories, avoids collisions and any other positions in which vehicle safety is compromised. Since the number of vehicles can vary with time, it is important that the navigation strategy can quickly adjust to the current number of vehicles, i.e, that it scales well with the number of vehicles. The scalable strategy is based on a stochastic optimal control problem formulation of safe navigation in the presence of a single vehicle, denoted as the one-on-one vehicle problem. It is shown that safe navigation in the presence of multiple vehicles can be solved exactly as an auxiliary Markov decision problem. This allows us to approximate the solution based on the one-on-one vehicle optimal control solution and achieve scalable navigation. Our work is illustrated by a numerical example of safely navigating a vehicle in the presence of four other vehicles and by a robot experiment.