@Article{Johnson2018,
author="Johnson, Jeffrey Kane",
title="On the relationship between dynamics and complexity in multi-agent collision avoidance",
journal="Autonomous Robots",
year="2018",
month="Oct",
day="01",
volume="42",
number="7",
pages="1389--1404",
abstract="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 NEXP^NP. A constructive proof is provided that demonstrates the relationship, and potential practical applications are discussed.",
issn="1573-7527",
doi="10.1007/s10514-018-9743-4",
url="https://doi.org/10.1007/s10514-018-9743-4"
}