Robotics: Science and Systems XII
A Novel Relationship Between Dynamics and Complexity in Multi-agent Collision Avoidance
Jeffrey Kane JohnsonAbstract:
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.
Bibtex:
@INPROCEEDINGS{Johnson-RSS-16, AUTHOR = {Jeffrey Kane Johnson}, TITLE = {A Novel Relationship Between Dynamics and Complexity in Multi-agent Collision Avoidance}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2016}, ADDRESS = {AnnArbor, Michigan}, MONTH = {June}, DOI = {10.15607/RSS.2016.XII.030} }