STARS: Static relays for multi-robot real-time search and monitoring

Abstract

We first present a problem called precedence constrained two traveling salesman (PC2TSP). We propose a near-optimal heuristic to PC2TSP to generate tours by clustering points, generating optimal single-traveler tours, and tour pruning and balance. Second, we show an application of PC2TSP and how our solution to PC2TSP can be applied to the application. By modeling in part by PC2TSP, we solve the problem of minimum time two-robot real-time search with relay deployment. We call the solution STAtic Relay aided Search (STARS), which identifies visiting positions by set cover and Steiner connected dominating set; assigns the precedence constraint by breadth-first search; and finally generates tours by PC2TSP. STARS substantially reduces cost compared to a homogeneous mobile robot system and enables constant monitoring of suspicious areas. STARS and our solution to PC2TSP are extensible to deal with more than two travelers. Extensive simulations with both narrow and wide regions show that our solution to PC2TSP achieves near-optimal performance with less than 2% average difference from optimal.