On the relationship between dynamics and complexity in multi-agent collision avoidance

This work examines how dynamics and complexity are related in multi-agent collision avoidance. Motivated particularly by work in the field of automated driving, this work considers a variant of the reciprocal n-body collision avoidance problem. In this problem, agents must avoid collision while moving according to individual reward functions in a crowded environment. The main contribution of this work is the result that there is a quantifiable relationship between system dynamics and the requirement for agent coordination, and that this requirement can change the complexity class of the problem dramatically: from P to NEXP or even . A constructive proof is provided that demonstrates the relationship, and potential practical applications are discussed.