Communication coverage for independently moving robots

We consider the task of providing communication coverage to a group of sensing robots (sensors) moving independently to collect data. We provide communication via controlled placement of router vehicles that relay messages from any sensor to any other sensor in the system under the assumptions of 1) no cooperation from the sensors, and 2) only sensor-router or router-router communication over a maximum distance of R is reliable. We provide a formal framework and design provable exact and approximate (faster) algorithms for finding optimal router vehicle locations that are updated according to sensor movement. Using vehicle limitations, such as bounded control effort and maximum velocities of the sensors, our algorithm approximates areas that each router can reach while preserving connectivity and returns an expiration time window over which these positions are guaranteed to maintain communication of the entire system. The expiration time is compared against computation time required to update positions as a decision variable for choosing either the exact or approximate solution for maintaining connectivity with the sensors on-line.

Authors

• Stephanie Gil
• Dan Feldman
• Daniela Rus

Keywords

• Vehicles
• Mobile communication
• Approximation methods
• Sensor systems
• Approximation algorithms
• Algorithm design and analysis
• Computation Time
• Maximum Distance
• Sensory Systems
• Estimation Algorithm
• Maximum Velocity
• Exact Solution
• Exact Algorithm
• Expiratory Time
• Movement Sensor
• Estimation Error
• Sensor Locations
• Control Limits
• Time In Seconds
• Topological Changes
• Central Problem
• Set Of Sensors
• Spanning Tree
• Vehicle Communication
• Mobile Sensors
• Pair Of Sensors
• Set Of Vehicles
• Reachability Analysis