Robotics: Science and Systems XII

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

Jeffrey Kane Johnson

Abstract:

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.

Download:

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} 
}