A Novel Relationship Between Dynamics and Complexity in Multi agent Collision Avoidance
This paper examines the relationship between system 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 realworld applications of the result are discussed.
Robotics: Science and Systems