A visibility-based approach to computing nondeterministic bouncing strategies |
|
Author: | Nilles, Alexandra Q.1; Ren, Yingying1; Becerra, Israel1; |
Organizations: |
1Department of Computer Science University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA 2Faculty of Information Technology and Electrical Engineering University of Oulu, Oulu, Finland |
Format: | article |
Version: | accepted version |
Access: | open |
Online Access: | PDF Full Text (PDF, 1.4 MB) |
Persistent link: | http://urn.fi/urn:nbn:fi-fe2021102051684 |
Language: | English |
Published: |
Springer Nature,
2021
|
Publish Date: | 2021-10-20 |
Description: |
AbstractInspired by motion patterns of some commercially available mobile robots, we investigate the power of robots that move forward in straight lines until colliding with an environment boundary, at which point they can rotate in place and move forward again; we visualize this as the robot “bouncing” off boundaries. Different boundary interaction rules can be defined for such robots, such as one that orients the robot relative to its heading prior to collision, or relative to the normal of the boundary. We introduce a new data structure, the bounce visibility graph, which is generated from a polygonal environment definition. The bounce visibility graph can be queried to determine the feasibility of path-based tasks such as navigation and patrolling, assuming we have unavoidable nondeterminism in our actuation. If the task is feasible, then this approach synthesizes a strategy (a sequence of nondeterministic rotations). We also show how to compute stable cyclic trajectories and use these to limit uncertainty in the robot’s position (Software implementation at https://github.com/alexandroid000/bounce_viz). see all
|
Series: |
Springer proceedings in advanced robotics |
ISSN: | 2511-1256 |
ISSN-E: | 2511-1264 |
ISSN-L: | 2511-1256 |
ISBN: | 978-3-030-44051-0 |
ISBN Print: | 978-3-030-44050-3 |
Pages: | 89 - 105 |
DOI: | 10.1007/978-3-030-44051-0_6 |
OADOI: | https://oadoi.org/10.1007/978-3-030-44051-0_6 |
Host publication: |
Algorithmic Foundations of Robotics XIII. WAFR 2018. Springer Proceedings in Advanced Robotics |
Host publication editor: |
LaValle, Steven M. Lin, Ming Ojala, Timo Shell, Dylan Yu, Jingjin |
Conference: |
International Workshop on the Algorithmic Foundations of Robotics |
Type of Publication: |
A4 Article in conference proceedings |
Field of Science: |
113 Computer and information sciences |
Subjects: | |
Funding: |
This work was supported by NSF grants 1035345 and 1328018, and CONACyT post-doctoral fellowship 277028. |
Copyright information: |
© Springer Nature Switzerland AG 2020. This is a post-peer-review, pre-copyedit version of an article published in Algorithmic Foundations of Robotics XIII. WAFR 2018. Springer Proceedings in Advanced Robotics. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-44051-0_6. |