ABSTRACT
The exploration of unknown environments is an essential application of multi-robot systems, particularly in critical missions, such as hazard detection and search and rescue. These missions share the need to reach full coverage of the explorable space in the shortest time possible. To minimize the completion time, robots in the fleet must be able to reliably exchange information about the environment with one another. One of the main methods to expand coverage is by placing relays. Existing relay-placement algorithms tend to either require prior knowledge of the environment, or they rely on maintaining specific distances between the relays and the rest of the robots. These approaches lack flexibility and adaptability to the environment. This paper introduces the "Connectivity-Aware Relay Algorithm" (CARA), a dynamic context-aware relay-placement algorithm that does not require any prior knowledge of the environment. We compare CARA against a state-of-the-art distance-based relay-placement algorithm. Our results demonstrate that CARA outperformed the state-of-the-art algorithm in terms of the time to completion by a factor of 10 as it placed, on average, half the number of relays.
Subject(s)
AlgorithmsABSTRACT
In 1794, French Engineer Claude Chappe coordinated the deployment of a network of dozens of optical semaphores. These formed "strings" that were hundreds of kilometers long, allowing for nationwide telegraphy. The Chappe telegraph inspired future developments of long-range telecommunications using electrical telegraphs and, later, digital telecommunication. Long-range wireless networks are used today for the Internet of Things (IoT), including industrial, agricultural, and urban applications. The long-range radio technology used today offers approximately 10 km of range. Long-range IoT solutions use "star" topology: all devices need to be within range of a gateway device. This limits the area covered by one such network to roughly a disk of a 10 km radius. In this article, we demonstrate a 103 km low-power wireless multi-hop network by combining long-range IoT radio technology with Claude Chappe's vision. We placed 11 battery-powered devices at the former locations of the Chappe telegraph towers, hanging under helium balloons. We ran a proprietary protocol stack on these devices so they formed a 10-hop multi-hop network: devices forwarded the frames from the "previous" device in the chain. This is, to our knowledge, the longest low power multi-hop wireless network built to date, demonstrating the potential of combining long-range radio technology with multi-hop technology.
