Steiner traveler: Relay deployment for remote sensing in heterogeneous multi-robot exploration

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.