| Summary: | Modern multi-agent systems frequently use high-level planners to extract basic paths for agents, and then rely on local collision avoidance to ensure that the agents reach their destinations without colliding with one another or dynamic obstacles. One state-of-the-art local collision avoidance technique is Optimal Reciprocal Colli-sion Avoidance (ORCA). Despite being fast and ecient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcom-ing, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO extends ORCA by introducing a notion of rotation. This extension permits more realistic motion than ORCA for polygonally-shaped agents and does not suer from as much deadlock. In this thesis, we present the theory of RRVO and show empirically that it does not suer from the deadlock issue ORCA has, that it permits agents to reach goals faster, and that it has a comparable collision rate at the cost of some performance overhead. ii DEDICATION To my parents, for everything. iii ACKNOWLEDGEMENTS I would like to thank my advisor Nancy M. Amato for mentoring me through my research here at Texas A&M. During my time under her, I've learned an incredible amount and grown signicantly as a technical person. I'm humbled by the patience she displayed as I searched far and wide for a thesis topic, and beholden to her reassuring words when things didn't work as well as I'd hoped. I am grateful to the GAMMA group at UNC Chapel Hill for helping me un-derstand and use their open-source RVO2 library, which RRVO was built o of.
|
|---|