University of Oulu

Nilles A.Q., Ren Y., Becerra I., LaValle S.M. (2020) A Visibility-Based Approach to Computing Nondeterministic Bouncing Strategies. In: Morales M., Tapia L., Sánchez-Ante G., Hutchinson S. (eds) Algorithmic Foundations of Robotics XIII. WAFR 2018. Springer Proceedings in Advanced Robotics, vol 14. Springer, Cham.

A visibility-based approach to computing nondeterministic bouncing strategies

Saved in:
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:
Language: English
Published: Springer Nature, 2021
Publish Date: 2021-10-20


Inspired 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

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