Visibility maps for any-shape robots

We introduce in this paper visibility maps for robots of any shape, representing the reachability limit of the robot's motion and sensing in a 2D gridmap with obstacles. The brute-force approach to determine the optimal visibility map is computationally expensive, and prohibitive with dynamic obstacles. We contribute the Robot-Dependent Visibility Map (RDVM) as a close approximation to the optimal, and an effective algorithm to compute it. The RDVM is a function of the robot's shape, initial position, and sensor model. We first overview the computation of RDVM for the circular robot case in terms of the partial morphological closing operation and the optimal choice for the critical points position. We then present how the RDVM for any-shape robots is computed. In order to handle any robot shape, we introduce in the first step multiple layers that discretize the robot orientation. In the second step, our algorithm determines the frontiers of actuation, similarly to the case of the the circular robot case. We then derive the concept of critical points to the any-shape robot, as the points that maximize expected visibility inside unreachable regions. We compare our method with the ground-truth in a simulated map compiled to capture a variety of challenges of obstacle distribution and type, and discuss the accuracy of our approximation to the optimal visibility map.

Authors

• Tiago Raul de Sousa Pereira
• Manuela Veloso
• António Paulo Moreira

Keywords

• Robot sensing systems
• Robot kinematics
• Morphological operations
• Shape
• Planning
• Internationalization
• Visual Map
• Portuguese Foundation For Science
• Critical Point
• Reachable
• Shape Model
• Unreachable
• Sensor Model
• Brute-force Approach
• Dynamic Obstacles
• Function Of The Robot
• Computation Time
• Free Space
• General Case
• Precision And Recall
• Simulation Environment
• Path Planning
• Concavity
• Brute Force
• Ray Casting
• Position Of The Robot
• Robot Model
• Dual Operation
• Robot Sensors
• Histogram Bins
• Layer Spacing
• Representation Of The Environment