# Swarm

This week we have a guest blog post from Jiawei Xu and David Saldaña from the Swarmslab at Lehigh University. Enjoy!

## Limits of flying vehicles

Advancements in technology have made quadrotor drones more accessible and easy to integrate into a wide variety of applications. Compared to traditional fixed-wing aircraft, quadrotors are more flexible to design and more suitable for motioning, such as statically hovering. Some examples of quadrotor applications include photographers using mounting cameras to take bird’s eye view images, and delivery companies using them to deliver packages. However, while being more versatile than other aerial platforms, quadrotors are still limited in their capability due to many factors.

First, quadrotors are limited by their lift capacity, i.e., strength. For example, a Crazyflie 2.1 is able to fly and carry a light payload such as an AI deck, but it is unable to carry a GoPro camera. A lifter quadrotor that is equipped with more powerful components can transport heavier payload but also consumes more energy and requires additional free space to operate. The difference in the strength of individual quadrotors creates a dilemma in choosing which drone components are better suited for a task.

Second, a traditional quadrotor’s motion in translation is coupled with its roll and pitch. Let’s take a closer look at Crazyflie 2.1, which utilizes a traditional quadrotor design. Its four motors are oriented in the same direction – along the positive z-axis of the drone frame, which makes it impossible to move horizontally without tilting. While such control policies that convert the desired motion direction into tilting angles are well studied, proven to work, and implemented on a variety of platforms [1][2], if, for instance, we want to stack a glass filled with milk on top of a quadrotor and send it from the kitchen to the bedroom, we should still expect milk stains on the floor. This lack of independent control for rotation and translation is another primary reason why multi-rotor drones lack versatility.

## Improving strength

These versatility problems are caused by the hardware of a multi-rotor drone designed specifically to deal with a certain set of tasks. If we push the boundary of these preset tasks, the requirements on the strength and controllability of the multi-rotor drone will eventually be impossible to satisfy. However, there is one inspiration we take from nature to improve the versatility in the strength of multi-rotor drones – modularity! Ants are weak individual insects that are not versatile enough to deal with complex tasks. However, when a group of ants needs to cross natural boundaries, they will swarm together to build capable structures like bridges and boats. In our previous work, ModQuad [3], we created modules that can fly by themselves and lift light payloads. As more ModQuad modules assemble together into larger structures, they can provide an increasing amount of lift force. The system shows that we can combine weak modules with improving the versatility of the structure’s carrying weight. To carry a small payload like a pin-hole camera, a single module is able to accomplish the task. If we want to lift a heavier object, we only need to assemble multiple modules together up to the required lift.

## Improving controllability

On a traditional quadrotor, each propeller is oriented vertically. This means the device is unable to generate force in the horizontal direction. By attaching modules side by side in a ModQuad structure, we are aligning more rotors in parallel, which still does not contribute to the horizontal force the structure can generate. That is how we came up with the idea of H-ModQuad — we would like to have a versatile multi-rotor drone that is able to move in an arbitrary direction at an arbitrary attitude. By tilting the rotors of quadrotor modules and docking different types of modules together, we obtain a structure whose rotors are not pointing in the same direction, some of which are able to generate a force along the horizontal direction.

H-ModQuad has two major characteristics: modularity and heterogeneity, which can be indicated by the “Mod” and “H-” in the name. Modularity means that the vehicle (we call a structure) is composed of multiple smaller modules which are able to fly by themselves. Heterogeneity means that we can have modules of different types in a structure.

As mentioned before, insects like ants utilize modularity to enhance the group’s versatility. Aside from a large number of individuals in a swarm that can adapt to the different scales of the task requirement, the individuals in a colony specializing in different tasks are of different types, such as the queen, the female workers, and the males. The differentiation of the types in a hive helps the group adapt to tasks of different physical properties. We take this inspiration to develop two types of modules.

In our related papers [4][5], we introduced two types of modules which are R-modules and T-modules.

An example T-module is shown in the figure above. As shown in the image, the rotors in a T-module are tilted around its arm connected with the central board. Each pair of diagonal rotors are tilted in the opposite direction, and each pair of adjacent rotors are either tilting in the same direction or in the opposite direction. We arrange the tilting of the rotors so that all the propellers generate the same thrust force, making the structure torque-balanced. The advantage of the T-module is that it allows the generation of more torque around the vertical axis. One single module can also generate forces in all horizontal directions.

An R-module has all its propellers oriented in the same direction that is not on the z-axis of the module. In this configuration, when assembling multiple modules together, rotors from different modules will point in different directions in the overall structure. The picture below shows a fully-actuated structure composed of R-modules. The advantage of R-modules is that the rotor thrusts inside a module are all in the same direction, which is more efficient when hovering.

Depending on what types of modules we choose and how we arrange those modules, the assembled structure can obtain different actuation capabilities. Structure 1 is composed of four R-modules, which is able to translate in horizontal directions efficiently without tilting. The picture in the intro shows a structure composed of four T-modules of two types. It can hover while maintaining a tilting angle of up to 40 degrees.

## Control and implementation

We implemented our new geometric controller for H-ModQuad structures based on Crazyflie Firmware on Crazyflie Bolt control boards. Specifically, aside from tuning the PID parameters, we have to change the power_distribution.c and controller_mellinger.c so that the code conforms to the structure model. In addition, we create a new module that embeds the desired states along predefined trajectories in the firmware. When we send a timestamp to a selected trajectory, the module retrieves and then sends the full desired state to the Mellinger Controller to process. All modifications we make on the firmware so that the drone works the way we want can be found at our github repository. We also recommend using the modified crazyflie_ros to establish communication between the base station and the drone.

## Challenges and Conclusion

Different from the original Crazyflie 2.x, Bolt allows the usage of brushless motors, which are much more powerful. We had to design a frame using carbon fiber rods and 3-D printed connecting parts so that the chassis is sturdy enough to hold the control board, the ESC, and the motors. It takes some time to find the sweet spot of the combination of the motor model, propeller size, batteries, and so on. Communicating with four modules at the same time is also causing some problems for us. The now-archived ROS library, crazyflie_ros, sometimes loses random packages when working with multiple Crazyflie drones, leading to the stuttering behavior of the structure in flight. That is one of the reasons why we decided to migrate our code base to the new Crazyswarm library instead. The success of our design, implementation, and experiments with the H-ModQuads is proof of work that we are indeed able to use modularity to improve the versatility of multi-rotor flying vehicles. For the next step, we are planning to integrate tool modules into the H-ModQuads to show how we can further increase the versatility of the drones such that they can deal with real-world tasks.

Reference

[1] D. Mellinger and V. Kumar, “Minimum snap trajectory generation and control for quadrotors,” in 2011 IEEE International Conference on Robotics and Automation, 2011, pp. 2520–2525.

[2] T. Lee, M. Leok, and N. H. McClamroch, “Geometric tracking control of a quadrotor uav on se(3),” in 49th IEEE Conference on Decision and Control (CDC), 2010, pp. 5420–5425.

[3] D. Saldaña, B. Gabrich, G. Li, M. Yim and V. Kumar, “ModQuad: The Flying Modular Structure that Self-Assembles in Midair,” 2018 IEEE International Conference on Robotics and Automation (ICRA), 2018, pp. 691-698, doi: 10.1109/ICRA.2018.8461014.

[4] J. Xu, D. S. D’Antonio, and D. Saldaña, “Modular multi-rotors: From quadrotors to fully-actuated aerial vehicles,” arXiv preprint arXiv:2202.00788, 2022.

[5] J. Xu, D. S. D’Antonio and D. Saldaña, “H-ModQuad: Modular Multi-Rotors with 4, 5, and 6 Controllable DOF,” 2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 190-196, doi: 10.1109/ICRA48506.2021.9561016.

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.