A Novel Relationship Between Dynamics and Complexity in Multi-agent Collision Avoidance

This paper examines the relationship between sys- tem dynamics and problem complexity of collision avoidance in multi-agent systems. Motivated particularly by results in the field of automated driving, a variant of the reciprocal n-body collision avoidance problem is considered. 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 novel 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 NEXPNP. In addition, a constructive proof is provided that demonstrates the relationship and potential real- world applications of the result are discussed.