By K.N. McGuire, C. De Wagter, K. Tuyls, H.J. Kappen, G.C.H.E. de Croon
Greenhouses, search-and-rescue teams and warehouses are all looking for new methods to enable surveillance in a manner that is quick and safe for the objects and people surrounding them. Many of them already found their way into robotics, but wheeled ground-bound systems have limited maneuverability. Ideally it would be great if flying robots, a.k.a. micro aerial vehicles (MAV) can take advantage of their 3rd dimension to perform surveillance. A group or a swarm of them should be ideal to cover as much ground as possible. The price of fully autonomous MAVs usually comes with the cost of weight and size. This is problematic in green- and warehouses in particular, as many of us would not be comfortable working with 3 kilo MAVs flying over our heads.
There have been many advances already in artificial intelligence and navigation techniques to make MAVs fully autonomous navigators through these unknown areas. However, these techniques are computationally expensive and therefore need substantial on-board calculating power. A smaller MAV could rely on the aid of an external computer, but this will become a problem as soon as their numbers and the environment increase in size. Communication speeds through the inner structure of a building will degrade quickly, which makes any search-and-rescue scenario ill-fated. Ideally, a group of tiny MAVs would need to be independent and only use their onboard sensing and computing capabilities. Imagine making such tiny drones navigate in a GPS-deprived environment without the help of an external positioning system.
At the MAVLab of the TU Delft, we have tried to tackle this difficult problem by thinking of creative ways to solve the difficult issues surrounding autonomous indoor navigation. We try to look at nature for inspiration and have implemented that successfully in the past with the Delfly or optical flow-based control. So, if a swarm of bees can do it, why not a group of tiny MAVs? That did not turn out as easy as it initially seemed, as we needed to solve the intermediate issues out from the ground up. An individual bee is very talented as it can already avoid trees, bushes and his peers as soon as it has a chance to spread its wings. These capabilities do not come naturally to an MAV, and this has to be implemented in a very robust manner, because a crashed MAV usually cannot recover by itself. A bee can already go out and explore a field of flowers, and return to its home hive once it’s done. This is something that an MAV weighing less then 50 grams has never done autonomously before, let alone a swarm.
Since many navigation strategies are out of the question because of their complexity, we had to turn to other inspiration from the insect kingdom, namely a path planning technique called ‘Bug Algorithms’. Although the name suggests otherwise, bug algorithms are not really inspired by biology. These algorithms originated for mathematical path planning techniques, of which the core principles are that they require very little memory and are very simple in computation. The idea revolves around the fact that an agent has to go from A to B, and will deal with the intermediate obstacles on-the-fly by following their border (a.k.a. wall-following). Once the path towards the goal is clear, the agent will resume its way towards to goal again. By remembering some places along the way, it can make different decisions on locations it has encountered again to make sure it does not get stuck in an endless loop. By a set of very simple rules and memory blocks which only take a fraction of the computing power and memory, an agent can in most cases find its way to its goal. However, the main problem of most existing bug algorithms is that they rely on a known global location (as with GPS) or rely on perfect odometry. Hence, most existing bug algorithms are actually not so well suited for application to tiny robots that navigate in the real world.
We developed our own bug algorithm and extended it to make it suitable for a swarm of MAVs navigating in the real world. The swarm is leveraged by having the MAVs travel in different directions. The MAVs first fly away from the base station, exploring their environment. They are able to come back with the help of a wireless beacon located at the base station. Based on the signal strength of their connection with the beacon, they can evaluate the right direction to go back to. The MAVs are also communicating with each other for sharing their exploration preference and to avoid each other. We called this technique the Swarm Gradient Bug Algorithm (SGBA).
On the Faculty of Aerospace engineering of the Delft University of Technology, on the 11th floor of the highrise building, we used an empty office space for an ultimate system test of SGBA. We acquired 6 off-the-shelf MAVs, namely the Crazyflie 2.0’s of Bitcraze AB, equipped with the Flowdeck and Multirangerdeck. Six of these are sent in different directions to cover as much ground as possible in the beginning, while they were coordinating and avoiding each other at the same time. Once their battery is at 60%, they navigate back to the home beacon. With this, the crazyflies explored 80 % of the open rooms, and on average 4 of the 6 were able to return out of the 5 flights performed. Next to this, we have also experimented with configurations with 2 and 4 crazyflies, which resulted in 15 test flights in the real-world environment, backed up with hundreds of simulated environment flights with greater quantities.
Although we are very happy with the autonomous exploration by our swarm of MAVs, we see ample space for improvement, ranging from more robust obstacle detection and avoidance to more accurate intra-swarm distance sensing. On the long run, we envisage also vision-based navigation for small MAVs without a beacon at the base station. Still, for the time being, the proposed navigation method is already suitable for practical swarm navigation of small robots, as a single beacon at the base station is not a very limiting factor. Moreover, we hope that the main concept behind SGBA – trading off the accuracy of highly detailed navigation maps against substantially less computational requirements – will inspire others to tackle similarly complex missions with swarms of tiny robots.
For details on the experiments and SGBA, please check the paper:
Minimal navigation solution for a swarm of tiny flying robots to explore an unknown environment K.N. McGuire, C. De Wagter, K. Tuyls, H.J. Kappen, G.C.H.E. de Croon
Science Robotics, 23 October
