Line Coverage with Multiple Robots

The line coverage problem is the coverage of linear environment features (e. g. , road networks, power lines), modeled as 1D segments, by one or more robots while respecting resource constraints (e. g. , battery capacity, flight time) for each of the robots. The robots incur direction dependent costs and resource demands as they traverse the edges. We treat the line coverage problem as an optimization problem, with the total cost of the tours as the objective, by formulating it as a mixed integer linear program (MILP). The line coverage problem is NP-hard and hence we develop a heuristic algorithm, Merge-Embed-Merge (MEM). We compare it against the optimal MILP approach and a baseline heuristic algorithm, Extended Path Scanning. We show the MEM algorithm is fast and suitable for real-time applications. To tackle large-scale problems, our approach performs graph simplification and graph partitioning, followed by robot tour generation for each of the partitioned subgraphs. We demonstrate our approach on a large graph with 4, 658 edges and 4, 504 vertices that represents an urban region of about 16 sq. km. We compare the performance of the algorithms on several small road networks and experimentally demonstrate the approach using UAVs on the UNC Charlotte campus road network.

Authors

• Saurav Agarwal
• Srinivas Akella

Keywords

• Roads
• Task analysis
• Robot sensing systems
• Routing
• Heuristic algorithms
• Partitioning algorithms
• Multiple Robots
• Line Coverage
• Optimization Problem
• Resource Constraints
• Road Network
• Unmanned Aerial Vehicles
• Heuristic Algorithm
• Power Line
• Linear Features
• Mixed Integer Linear Programming
• Battery Capacity
• Simple Graph
• Graph Partitioning
• Large Graphs
• Savings
• Travel Time
• Shortest Path
• Coverage Area
• Cost Of Services
• Directed Graph
• Linear Programming Formulation
• Routing Problem
• Polyline
• Ground Robots
• Direction Of Travel
• Depth-first
• Integer Linear Programming Formulation
• Robotic Applications