# Swarm

This week we have a guest blog post from Enrica Soria from the Laboratory of Intelligent Systems Faculty of Ecole Polytechnique Fédérale de Lausanne (EPFL) . Enjoy!

From Star Wars to Black Mirror, sci-fi movies predict a future where thousands of drones will fill our sky. Curving sharply around trees or soaring over buildings, they fly just like a flock of starlings. To turn this vision into a reality, real drone swarms need to increase their autonomy and operate in a decentralized fashion. In a decentralized swarm, each robot makes its own decision based only on local information. Decentralization not only allows the swarm to be more robust to the failure of single individuals, but also removes the dependency from a single computing unit, thus making the swarm more scalable in terms of size.

We at LIS (EPFL) have shown that predictive controllers can improve the safety of aerial swarms by predicting and optimizing the agents’ future behavior in an iterative process. However, the centralized nature of this method allowed us to only control five drones and prevented us from scaling up to a large number of drones. For this reason, we have worked on a novel decentralized and scalable swarm controller that allows the safe and cohesive flight of aerial swarms in cluttered environments. In our latest article, published in IEEE Robotics and Automation Letters (RA-L), we describe how we designed the controller, show its scalability in size, and demonstrate its robustness to noise. We studied the swarms’ performance and compared how it changes in two different environments: a forest and funnel-like environment.

The Crazyflie 2.1 was the perfect platform for our experiments. They are lightweight, modular, and tough. This quadcopter can survive big hits when things don’t go as planned… and, if you work on swarms, things can go wrong!

With our algorithm, sixteen robots were able to fly through an artificial forest that we set up in our indoor motion capture arena. In our previous work, we installed four markers on each quadcopter and used the rigid body tracking from Motive (the Optitrack software). The large volume of our experimental room required the usage of big markers for long-distance detection, which added considerable weight to the drone. Hence, in our new work, we use a single marker per drone. Tracking is supported by the ‘crazyswarm’ package and communication with the entire swarm only requires two radio links. However, despite our model being decentralized, in our implementation robots relay the information to an external brain, which does the computations for them. In the future, all the necessary code will be embedded onboard, removing the dependency on external infrastructure.

This work is a step forward towards the fully autonomous deployment of drone swarms in our cities. By enabling safe navigation in cluttered environments, drone fleets will be able to integrate with conventional air traffic, search for missing people, inspect dangerous areas, transport injured people to hospitals quicker, and deliver important packages right to our doors.

For further details, check out our article here!

Ever since we released the Lighthouse deck back in 2019, we’ve wanted to offer a bundle with the deck and the base stations. There’s multiple reasons for this, but the main reason was that we wanted users to be able to buy a full swarm (like the Loco Positioning Swarm) directly from us, without having to find the base stations separately. Initially this seemed easy to do, but it turned out to be a bit tricky. This post is about how we finally managed to get the Lighthouse Swarm Bundle finished and into the E-store.

When the Lighthouse deck was initially released it only had support for Lighthouse V1 base stations, but Ligthouse V2 was already out. Since the V1 base stations were already in short supply, we wanted to support V2 since this was what would be available in the future. We had started looking at V2 support, but there was still ongoing efforts from us (and others) to reverse engineer the protocol. After some prototyping we had some initial support, but there was still a lot of infrastructure work to be done before it could be released.

In parallell with this work we started trying to buy the Lighthouse V2 base stations. Normally there’s two options here, either buy from local distributors or buy directly from the manufacturer. Buying from local distributors wasn’t a good option for us since these will only have local power plugs and buying directly from the manufacturer often requires very large orders. So this process quickly stalled. But after a couple of months we got an offer to buy a bulk shipment of Ligthouse V2 base stations (without box or power adapters) which we finally decided to accept. And yeah, that’s me looking really happy next to a bunch of base stations…

With a bunch of base stations at the office, work with sourcing a power adapter and creating a box started. Unfortunately the number of COVID-19 cases started rising again shortly after receiving the base stations, so we started working more from home again. And with only 2 persons at the office at a time, it’s hard to work with hardware. Different team-members needs access to different resources, like the electronics labs, flight arena or packing orders. So getting box/adapter samples from manufacturers, doing testing and getting input on physical objects from other team-members quickly went from days to weeks.

Finally, after a couple of months of testing, evaluating and learning lots about adapters and cardboard, we had good candidates. But then, literally as we’re ordering the power adapters, it turns out the certification was not good for all the regions we wanted. Thankfully this time around we already had other options so we quickly decided on the second best option (now the best option) and ordered.

In the meantime work was underway finalizing the implementation of Lighthouse V2, including client support, firmware updates of the Lighthouse deck and documentation/videos. Finally in the beginning of 2021 we got documentation and the full implementation (although only for 2 base stations) in place (blog post).

After a bit more than a month of waiting, the power adapters and boxes finally showed up at our office. With all the supplies in place, we started preparing for the packing. Since you can buy base stations for multiple sources, we wanted to keep track of the base stations that we were sending out to be able to debug issues users might have with these units. Also, even though the base stations had already been factory tested, we wanted to quickly test them before shipping them out. So our flight arena was turned into a makeshift assembly line and we had some outside help come in to do the packing.

Finally, the end result! We’re really excited to be able to offer yet another swarm bundle, the Lighthouse swarm bundle. And we’re pretty happy about how the packaging turned out :-)

If you haven’t visited our store in a while, you may have missed our new addition: the Lighthouse Swarm bundle!

We’ve been working for some time now on improving the Lighthouse decks and its positioning system. Earlier in the year, we have brought the Lighthouse deck out of early access. While working with it, we have seen the great possibilities and the accuracy of this new positioning system. Thanks to Steam’s VR base station that we use as an optical beacon, the Crazyflie calculates its position with an accuracy better than a decimeter and millimeter precision. It gives a tracking volume of up to 5x5x2 meters with sub-millimetre jitter and below 10 cm accuracy while flying. It’s perfect for a swarm, as it’s accurate, precise and autonomous. We’ve flown our Crazyflies with it a number of time and seen some awesome stuff with it!

As an example, here is a demo we’ve shown on a conference back in October. We’ve used 8 Crazyflies equipped with Lighthouse decks and Qi chargers, to make a spiraling swarm. A computer orchestrates the Crazyflies and make sure one is flying at all times, while the others re-charge their batteries on their pads. After a pre-programmed trajectory is finished or when the battery of the flying Crazyflie is depleted, it goes back to its pad while another one takes over. The demo had an all-in mode that runs the trajectory on all Crazyflie with sufficient charge at once, the result is quite impressive and demonstrate the great relative precision of the Lighthouse system:

After the launch signal is sent to the Crazyflies, the computer is not required anymore: the Crazyflie will autonomously estimate its position from the lighthouse’s signals. The Crazyflie can estimate its own X, Y and Z in a global coordinate system.

What’s great with the Lighthouse Swarm is that it allows you to do drone research even if you’re on a tighter budget.

And when we got the opportunity to acquire our own base stations (that are also available in the shop by the way), it seemed only logical to offer a Swarm bundle similar to our Loco swarm bundle. So what’s in it ?

While the positioning will work with one base station, two base stations will allow better coverage of the flight space and better stability; as Kimberly can attest, it’s even possible to set it in your kitchen. The Crazyradios allow communication between the Crazyflies and your computer.

We dedicated a lot of time to the Lighthouse this winter, writing a paper with the help of Wolgangs’ calibration expertise. In this paper, we compared both Lighthouse V1 and V2 with the MoCap system. In all cases, the mean and median Euclidean error of the Lighthouse positioning system are about 2-4 centimeters compared to our MoCap system as ground truth. You can check the paper here, but here is a brief summary we used for our ICRA workshop:

We are now quite excited to get to see what you will do with this exciting new swarm bundle !

And if you don’t know how to set up the Swarm, you can get started at least with your Lighthouse system in this tutorial or watch Kristoffer explain it in this video:

This week we have a guest blog post from Dr Feng Shan at School of Computer Science and Engineering
Southeast University, China. Enjoy!

It is possible to utilize tens and thousands of Crazyflies to form a swarm to complete complicated cooperative tasks, such as searching and mapping. These Crazyflies are in short distance to each other and may move dynamically, so we study the dynamic and dense swarms. The ultra-wideband (UWB) technology is proposed to serve as the fundamental technique for both networking and localization, because UWB is so time sensitive that an accurate distance can be calculated using the transmission and receive timestamps of data packets. We have therefore designed a UWB Swarm Ranging Protocol with key features: simple yet efficient, adaptive and robust, scalable and supportive. It is implemented on Crazyflie 2.1 with onboard UWB wireless transceiver chips DW1000.

## The Basic Idea

The basic idea of the swarm ranging protocol was inspired by Double Sided-Two Way Ranging (DS-TWR), as shown below.

There are four types of message in DS-TWR, i.e., poll, response, final and report message, exchanging between the two sides, A and B. We define their transmission and receive timestamps are Tp, Rp, Tr, Rr, Tf, and Rf, respectively. We define the reply and round time duration for the two sides as follows.

Let tp be the time of flight (ToF), namely radio signal propagation time. ToF can be calculated as Eq. (2).

Then, the distance can be estimated by the ToF.

In our proposed Swarm Ranging Protocol, instead of four types of messages, we use only one type of message, which we call the ranging message.

Three sides A, B and C take turns to transmit six messages, namely A1, B1, C1, A2, B2, and C2. Each message can be received by the other two sides because of the broadcast nature of wireless communication. Then every message generates three timestamps, i.e., one transmission and two receive timestamps, as shown in Fig.3(a). We can see that each pair has two rounds of message exchange as shown in Fig.3(b). Hence, there are sufficient timestamps to calculate the ToF for each pair, that means all three pairs can be ranged with each side transmitting only two messages. This observation inspires us to design our ranging protocol.

## Protocol Design

The formal definition of the i-th ranging message that broadcasted by Crazyflie X is as follows.

Xi is the message identification, e.g., sender and sequence number; Txi-1 is the transmission timestamp of Xi-1, i.e., the last sent message; RxM is the set of receive timestamps and their message identification, e.g., RxM = {(A2, RA2), (B2, RB2)}; v is the velocity of X when it generates message Xi.

As mentioned above, six timestamps (Tp, Rp, Tr, Rr, Tf, Rf,) are needed to calculate the ToF. Therefore, for each neighbor, an additional data structure is designed to store these timestamps which we named it the ranging table, as shown in Fig.4. Each device maintains one ranging table for each known neighbor to store the timestamps required for ranging.

Let’s focus on a simple scenario where there are a number of Crazyflies, A, B, C, etc, in a short distance. Each one of them transmit a message that can be heard by all others, and they broadcast ranging messages at the same pace. As a result, between any two consecutive message transmission, a Crazyflie can hear messages from all others. The message exchange between A and Y is as follows.

The following steps show how the ranging messages are generated and the ranging tables are updated to correctly compute the distance between A and Y.

The message exchange between A and Y could be also A and B, A and C, etc, because they are equal, that’s means A could perform the ranging process above with all of it’s neighbors at the same time.

To handle dense and dynamic swarm, we improved the data structure of ranging table.

There are three new notations P, tn, ts, denoting the newest ranging period, the next (expected) delivery time and the expiration time, respectively.

For any Crazyflie, we allow it to have different ranging period for different neighbors, instead of setting a constant period for all neighbors. So, not all neighbors’ timestamps are required to be carried in every ranging message, e.g., the receive timestamp to a far apart and motionless neighbor is required less often. tn is used to measure the priority of neighbors. Also, when a neighbor is not heard for a certain duration, we set it as expired and will remove its ranging table.

If you are interested in our protocol, you can find much more details in our paper, that has just been published on IEEE International Conference on Computer Communications (INFOCOM) 2021. Please refer the links at the bottom of this article for our paper.

## Implementation

We have implemented our swarm ranging protocol for Crazyflie and it is now open-source. Note that we have also implemented the Optimized Link State Routing (OLSR) protocol, and the ranging messages are one of the OLSR messages type. So the “Timestamp Message” in the source file is the ranging message introduced in this article.

The procedure that handles the ranging messages is triggered by the hardware interruption of DW1000. During such procedure, timestamps in ranging tables are updated accordingly. Once a neighbor’s ranging table is complete, the distance is calculated and then the ranging table is rearranged.

All our codes are stored in the folder crazyflie-firmware/src/deck/drivers/src/swarming.

The following figure is a ranging performance comparison between our ranging protocol and token-ring based TWR protocol. It’s clear that our protocol handles the large number of drones smoothly.

We also conduct a collision avoidance experiment to test the real time ranging accuracy. In this experiment, 8 Crazyflie drones hover at the height 70cm in a compact area less than 3m by 3m. While a ninth Crazyflie drone is manually controlled to fly into this area. Thanks to the swarm ranging protocol, a drone detects the coming drone by ranging distance, and lower its height to avoid collision once the distance is small than a threshold, 30cm.

## Build & Run

Clone our repository

git clone --recursive https://github.com/SEU-NetSI/crazyflie-firmware.git

Go to the swarming folder.

cd crazyflie-firmware/src/deck/drivers/src/swarming

Then build the firmware.

make clean
make

Flash the cf2.bin.

cfloader flash path/to/cf2.bin stm32-fw

Open the client, connect to one of the drones and add log variables. (We use radio channel as the address of the drone) Our swarm ranging protocol allows the drones to ranging with multiple targets at the same time. The following shows that our swarm ranging protocol works very efficiently.

## Summary

We designed a ranging protocol specially for dense and dynamic swarms. Only a single type of message is used in our protocol which is broadcasted periodically. Timestamps are carried by this message so that the distance can be calculated. Also, we implemented our proposed ranging protocol on Crazyflie drones. Experiment shows that our protocol works very efficiently.