Bouncing Robots in Rectilinear Polygons

Abstract

In this paper, we describe a bouncing strategy (smart strategy) for a mobile robot that uses one bit of memory for feedback, and guarantees that the robot will traverse all the rooms (and doorways) of a 2D environment. The environment is modeled as a rectilinear polygon (also called orthogonal polygon), and the rooms and the doorways are defined by the decomposition algorithm we describe. Such a decomposition helps the robot to not go back to a room after leaving. We also define the notion of “virtual doors” that have the ability to let the robot through, or make the robot bounce from them. We compared three different types of bouncing rules: smart, random, billiard. The smart strategy grantees to reach to target. Although the random strategy on average behaves the same as the smart strategy, there are rectilinear polygons in which the robot cannot reach the target in the expected time steps. On the other hand, the billiard bouncing strategy can cause the robot to become trapped.