Mobile surveillance and sensing systems need a networking infrastructure that enables the mobile systems to transmit information gathered to a base station. We consider the problem of an efficient use of mobile robots to sense not only the region but also deploy relays to build the networking infrastructure. To develop an efficient solution to the above problem, 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. By modeling in part by PC2TSP, we then solve the problem of minimum time two-robot real-time search with online relay deployment. We call the solution STAtic Relay aided Search (STARS), which identifies visiting positions, assigns the precedence constraint, and finally generates tours by PC2TSP. STARS enables solutions for remote robotic sensing and control. In addition, 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 show that our solution to PC2TSP achieves near-optimal performance with less than 2 percent average difference from optimal.

ABSTRACT Although there has been substantial progress for multi‐robot exploration of an unknown area, little attention has been given to communication, especially bandwidth constraints in time‐sensitive and bandwidth‐consuming tasks such as search and surveillance. In such tasks, video/audio streams of a newly explored area should be sent back to the base station in a timely manner. To address this issue, we propose connectivity and bandwidth‐aware exploration (CBAX), which is an efficient iteration based real‐time exploration. CBAX divides the problem into frontier node placement, relay node placement with routing path selection, and matching of each robot with its target position. Moreover, we model bandwidth‐constrained relay node placement into a new variant of the Steiner minimum tree problem and present our solution. While reducing the exploration time, CBAX maintains the network's connectivity and ensures the aggregated data flows are under the link capacity in transmission. Simulation shows that CBAX outperforms two recent exploration schemes qualitatively by demonstrating major improvement in terms of non‐overflow transmission time and fully connected transmission time. With enhanced communication quality, CBAX still reduces the exploration time, on average, by 40% and 15%, respectively. In moderately dense scenarios, CBAX even decreases time by 50% and 25%. Copyright © 2011 John Wiley & Sons, Ltd.

In the multi-robot exploration task of an unknown environment, human operators often need to control the robots remotely and obtain the sensed information by real-time bandwidth-consuming multimedia streams. The task has military and civilian applications, such as reconnaissance, search and rescue missions in earthquake, radioactive, and other dangerous or hostile regions. Due to the nature of such applications, infrastructure networks or pre-deployed relays are often not available to support the stream transmission. To address this issue, we present a novel exploration scheme called Bandwidth-aware Exploration with a Steiner Traveler (BEST). BEST has a heterogeneous robot team with a fixed number of frontier nodes (FNs) to sense the area iteratively. In addition, a relay-deployment node (RDN) tracks the FNs movement and places relays when necessary to support the video/audio streams aggregation to the base station. Therefore, the main problem is to find a minimum path for the relay-deployment robot to travel and the positions to deploy necessary relays to support the stream aggregation in each movement iteration. This problem inherits characteristics of both the Steiner minimum tree and traveling salesman problems. We model the novel problem as the minimum velocity Flow constrained Steiner Traveler problem (FST). Extensive simulations show BEST improves exploration efficiency by 62% on average compared to the state-of-the-art homogeneous robot exploration strategies. BEST also saves cost by using only half the number of robots compared to the counterpart, while still achieving a 24% exploration time reduction.

The relay placement problem has been studied extensively in wireless networks. Existing work typically focuses on connectivity to prolong the network time or to achieve fault-tolerance. In contrast, we tackle the problem with the goal of achieving bandwidth sufficiency when real-time multimedia streams need to be sent to the sink. We consider the critical condition of heterogeneous link capacity and transmission range. Besides, we consider the relay placement and routing jointly because routing decides the path on which a stream traverses; and the bandwidth sufficiency depends on both supply (the link capacity) and demand (which streams use the link given the routing paths). We formulate the problem as a new variant of the Steiner tree problem called the heterogeneous bandwidth Steiner routing problem. Extensive simulations show that our scheme reduces the number of relays by an average of 44% compared to the widely used minimum spanning tree based approximation algorithm for relay placement. We also found that considering heterogeneous range and rate is beneficial in relay placement. Compared to the uniform range and rate placement algorithm, our scheme reduces the number of relays by 25%-39%. Besides, our scheme notably improves the movement efficiency when applied to a real-time multi-robot exploration strategy.

Multi-robot real-time exploration calls for joint consideration of mobility and communication: It requires video and audio streams of a newly explored area be transmitted to the base station in a timely fashion as robots explore the area. We address a central problem: How to place a minimum number of relay nodes, within connectivity and bandwidth constraints, to support the real-time stream aggregation from frontier nodes as they proceed? Particularly, we tackle this problem considering two critical and real-world conditions: (1) the heterogeneous transmission ranges and link capacities; (2) the impact of interference. The conditions increase the model complexity but significantly influence the actual available bandwidth and the required node size in placement. We found considering heterogeneous range and rate is beneficial. Our scheme markedly outperforms the uniform link and range relay placement by reduced relay number and enhanced exploration efficiency.

While there has been substantial progress for multi-robot exploration of an unknown area, little attention has been given to communication, especially bandwidth constraints in time-sensitive and bandwidth-consuming tasks such as search and surveillance. In such tasks, video/audio streams of a newly explored area should be sent back to the base station in a timely manner. To address this issue, we propose Connectivity and Bandwidth Aware eXploration (CBAX), which is an efficient iteration based real-time exploration. CBAX divides the problem into frontier node placement, relay node placement with routing path selection, and the match of each robot with its target position. Moreover, we model bandwidth-constrained relay node placement into a new variant of the Steiner Minimum Tree problem and present our solution. While reducing the exploration time, CBAX maintains the network's connectivity and ensures the aggregated data flows are under the link capacity in transmission. Simulation shows that CBAX outperforms two recent exploration schemes qualitatively by demonstrating major improvement in terms of non-overflow transmission time and fully-connected transmission time. With enhanced communication quality, CBAX still reduces the exploration time, on average, by 40% and 15% respectively. In moderately dense scenarios, CBAX even decreases time by 50% and 25%.

Hopping sensors are a type of low cost mobile sensors that are small in size, have limited capability and imprecise movement. However, their unique method of movement makes them suitable for rugged terrains. Sensors may fail when deployed in a rugged terrain or in an obstacle-abundant environment. Therefore, redundant sensors may be identified and relocated to the sensor holes. This paper addresses the problem of relocating such capability-constrained sensors in an obstructive environment. We propose an enhanced quorum-grid solution with binary splitting message forwarding (BSMF), which is decentralized and can detect both existing and newly appearing obstructions in the supplier and consumer cells matching process. Furthermore, a grid-based movement model is introduced for the hopping sensors. Simulation shows that our scheme significantly reduces the communication overhead and achieves relatively constant total energy consumption with varying amount of obstructions.