A Visibility-Based Approach to Computing Nondeterministic Bouncing Strategies

Alexandra Q. Nilles, Yingying Ren, Israel Becerra, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceedingChapter


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 https://github.com/alexandroid000/bounce_viz).

Original languageEnglish (US)
Title of host publicationSpringer Proceedings in Advanced Robotics
Number of pages17
StatePublished - 2020

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Mechanical Engineering
  • Engineering (miscellaneous)
  • Artificial Intelligence
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'A Visibility-Based Approach to Computing Nondeterministic Bouncing Strategies'. Together they form a unique fingerprint.

Cite this