Reciprocally-rotating velocity obstacles

Andrew Giese; Daniel Latypov; Nancy M. Amato

doi:10.1109/ICRA.2014.6907324

Reciprocally-rotating velocity obstacles

Andrew Giese, Daniel Latypov, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Modern multi-agent systems frequently use highlevel 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 Collision Avoidance (ORCA). Despite being fast and efficient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcoming, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO generalizes ORCA by introducing a notion of rotation for polygonally-shaped agents. This generalization permits more realistic motion than ORCA and does not suffer from as much deadlock. In this paper, we present the theory of RRVO and show empirically that it does not suffer from the deadlock issue ORCA has, permits agents to reach goals faster, and has a comparable collision rate at the cost of performance overhead quadratic in the (typically small) user-defined parameter δ.

Original language	English (US)
Title of host publication	Proceedings - IEEE International Conference on Robotics and Automation
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3234-3241
Number of pages	8
ISBN (Electronic)	9781479936854, 9781479936854
DOIs	https://doi.org/10.1109/ICRA.2014.6907324
State	Published - Sep 22 2014
Externally published	Yes
Event	2014 IEEE International Conference on Robotics and Automation, ICRA 2014 - Hong Kong, China Duration: May 31 2014 → Jun 7 2014

Publication series

Name	Proceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)	1050-4729

Other

Other	2014 IEEE International Conference on Robotics and Automation, ICRA 2014
Country/Territory	China
City	Hong Kong
Period	5/31/14 → 6/7/14

ASJC Scopus subject areas

Software
Artificial Intelligence
Electrical and Electronic Engineering
Control and Systems Engineering

Online availability

10.1109/ICRA.2014.6907324

Library availability

Discover UIUC Full Text

Cite this

Reciprocally-rotating velocity obstacles. / Giese, Andrew; Latypov, Daniel; Amato, Nancy M.
Proceedings - IEEE International Conference on Robotics and Automation. Institute of Electrical and Electronics Engineers Inc., 2014. p. 3234-3241 6907324 (Proceedings - IEEE International Conference on Robotics and Automation).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Giese, A, Latypov, D & Amato, NM 2014, Reciprocally-rotating velocity obstacles. in Proceedings - IEEE International Conference on Robotics and Automation., 6907324, Proceedings - IEEE International Conference on Robotics and Automation, Institute of Electrical and Electronics Engineers Inc., pp. 3234-3241, 2014 IEEE International Conference on Robotics and Automation, ICRA 2014, Hong Kong, China, 5/31/14. https://doi.org/10.1109/ICRA.2014.6907324

@inproceedings{dd3eb716da5947888ccc05267021f587,

title = "Reciprocally-rotating velocity obstacles",

abstract = "Modern multi-agent systems frequently use highlevel 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 Collision Avoidance (ORCA). Despite being fast and efficient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcoming, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO generalizes ORCA by introducing a notion of rotation for polygonally-shaped agents. This generalization permits more realistic motion than ORCA and does not suffer from as much deadlock. In this paper, we present the theory of RRVO and show empirically that it does not suffer from the deadlock issue ORCA has, permits agents to reach goals faster, and has a comparable collision rate at the cost of performance overhead quadratic in the (typically small) user-defined parameter δ.",

author = "Andrew Giese and Daniel Latypov and Amato, {Nancy M.}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 IEEE International Conference on Robotics and Automation, ICRA 2014 ; Conference date: 31-05-2014 Through 07-06-2014",

year = "2014",

month = sep,

day = "22",

doi = "10.1109/ICRA.2014.6907324",

language = "English (US)",

series = "Proceedings - IEEE International Conference on Robotics and Automation",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3234--3241",

booktitle = "Proceedings - IEEE International Conference on Robotics and Automation",

address = "United States",

}

TY - GEN

T1 - Reciprocally-rotating velocity obstacles

AU - Giese, Andrew

AU - Latypov, Daniel

AU - Amato, Nancy M.

PY - 2014/9/22

Y1 - 2014/9/22

N2 - Modern multi-agent systems frequently use highlevel 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 Collision Avoidance (ORCA). Despite being fast and efficient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcoming, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO generalizes ORCA by introducing a notion of rotation for polygonally-shaped agents. This generalization permits more realistic motion than ORCA and does not suffer from as much deadlock. In this paper, we present the theory of RRVO and show empirically that it does not suffer from the deadlock issue ORCA has, permits agents to reach goals faster, and has a comparable collision rate at the cost of performance overhead quadratic in the (typically small) user-defined parameter δ.

AB - Modern multi-agent systems frequently use highlevel 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 Collision Avoidance (ORCA). Despite being fast and efficient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcoming, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO generalizes ORCA by introducing a notion of rotation for polygonally-shaped agents. This generalization permits more realistic motion than ORCA and does not suffer from as much deadlock. In this paper, we present the theory of RRVO and show empirically that it does not suffer from the deadlock issue ORCA has, permits agents to reach goals faster, and has a comparable collision rate at the cost of performance overhead quadratic in the (typically small) user-defined parameter δ.

UR - http://www.scopus.com/inward/record.url?scp=84929208695&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84929208695&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2014.6907324

DO - 10.1109/ICRA.2014.6907324

M3 - Conference contribution

AN - SCOPUS:84929208695

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 3234

EP - 3241

BT - Proceedings - IEEE International Conference on Robotics and Automation

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE International Conference on Robotics and Automation, ICRA 2014

Y2 - 31 May 2014 through 7 June 2014

ER -

Reciprocally-rotating velocity obstacles

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this