Category: Loco Positioning

We have now worked a few weeks on the new TDoA 3 mode for the Loco Positioning System. We are happy with the results so far and think we managed to do what we aimed for: removing the single point of failure in anchor 0 and supporting many anchors as well as larger spaces.

 

We finished off last week by setting up a system with 20 anchors covering two rooms down in the lunch area of the office. We managed to fly a scripted autonomous flight between two rooms.

Work so far on the anchors

Messages from the anchors are now transmitted at random times, which removes the dependency on anchor 0 that used to act as a master that all other anchors were synchronized to. The drawback is that we get problems with collisions when two anchors happens to transmit at the same time. Experiments showed that at 400 packets/s (system rate) we ended up at a packet loss of around 15% and 340 TDoA measurements/s sent to the kalman filter for position estimation.  We figured that this was acceptable level and added an algorithm in the anchors that reduces the transmission rate based on the number of anchors around them. If more anchors are added to a room they all reduce their transmission rate to target 400 packets/s in total system rate.

The anchors continuously keeps track of the clock drift of all other anchors by listening to the messages that are transmitted. We know that clocks do not change frequency suddenly and can use this fact to filter the clock correction to reduce noise in the data. Outliers are detected and removed and the resulting correction is low pass filtered. We have done some experiments on using this information and compare it to the time stamp of a received message to detect if the time stamp is corrupt or not, but this idea requires more work.

One interesting feature of the anchors is the limited CPU power that is available. The strategy we have chosen to handle this fact has been to create an algorithm that is efficient when handling messages. A timer based maintenance algorithm (@1 Hz) examines the received data and makes demissions on which anchors to include in the messages in the future as well as purges old data.

The Crazyflie

The implementation in the Crazyflie is fairly straight forward. The biggest change to TDoA 2 is that we now can handle a dynamic number of anchors and have to chose what data to store and what to discard. We  have also extracted the actual TDoA algorithm into a module to separate it from the TDoA 3 protocol. The clock correction filtering algorithm from the anchors has also been implemented in the Crazyflie. 

An experimental module test has been added where the TDoA module is built and run on a PC using data recorded from a sniffer. We get repeatability as well as better tools for debugging and this is something that we should explore further.

Work remaining 

The estimated position in the Crazyflie is still more noisy than in TDoA 2 and we would like to improve it to at least the same level. We see that we have outliers in the TDoA measurements that makes the Crazyflie go off in a random direction from time to time, we believe it should be possible to get rid of most of these.

The code is fairly hackish and there are no structured unit or module tests to verify functionality. So far the work has been in an exploratory phase but we are getting closer to a set of algorithms that we are happy with and that are  worth testing. 

We have not done any work on the client side, that is support for visualizing and configuring the system. This is a substantial amount of work and we will not officially release TDoA 3 until this is finished.

How to try it out

If you are interested in trying TDoA 3 out your self, it is all available on github. There are no hardware changes and if you have a Loco Positioning system it should work just fine. There is a short description on the wiki of how to compile and configure the system. The anchor supports both TDoA 2 and TDoA 3 through configuration while the Crazyflie has to be recompiled to change between the two. The support in the client is limited but will basically handle anchors 0 – 7.

Have fun!

First of all we are happy to announce that (almost) all products have been stocked in the new warehouse and are now shipping! The last orders that were on hold are on their way out and new orders placed in the store will now be shipped again within a few days.

We released the TDoA mode, a.k.a. swarm mode of the Loco Positioning System back in January. TDoA supports positioning of many Crazyflies simultaneously which makes it possible to fly a swarm of Crazyflies with the LPS system. The release in January was actually the second iteration of the TDoA implementation (the first iteration was never publicly released) and it is also known as TDoA 2.

TDoA 2 works well but there are a couple of snags that we would like to fix and we have now started the work on the next iteration, TDoA 3. 

Single point of failure

TDoA 2 is based on a fixed transmission schedule with time slots when each anchor transmits its ranging packet. All anchors listen to anchor 0 and use the reception of a packet from anchor 0 to figure out when to transmit. The problem with this solution is that if anchor 0 stops transmitting for some reason the full system will stop transmitting positioning information. This is clearly a property that would be nice to get rid of.

Limited number of anchors

The packets in the TDoA 2 protocol have 8 slots for anchor data that are implicitly addressed through the position in the packet. First slot is anchor 0, second slot anchor 1 and so on. This setup is easy to use but creates an upper limit of 8 anchors in the system.

The maximum radio reach of an anchor depends mainly on the transmitted power and the environment. This distance, in combination with a maximum of 8 anchors and that all anchors must be in range of anchor 0, sets an upper limit of the volume that an LPS system can cover, basically one large room. When we designed TDoA 2 we were happy to be able to support a swarm of Crazyflies and did not really bother too much about the covered volume. We get more and more questions about larger areas and more anchors though and it would be nice to have a positioning system that could be expanded.

The solution – maybe…

What we want to do in TDoA 3 is to transmit packets at random times and add functionality to handle the collisions and packet loss that will happen in a system like this. The idea is that the even if some data is lost, the receiving side will get enough packets to be able to calculate the distance to other anchors or a position as needed. By removing the time slots and synchronization to anchor 0, we get rid of the single point of failure. 

In the TDoA 3 protocol, we have added explicit ids to the anchor data, and thus removed the implicit addressing of anchors. We have 8 bits for anchor ids and the system will handle 256 anchors for sure. We do think that it will be possible to design larger systems though by reusing ids and making sure that the radio ranges of anchors with the same ids do not overlap.

The UWB radios have a nice property that makes this a bit easier to handle collisions than one might first think, if they receive two packets at the same time, they will most likely “pick” one of the packets and discard the other. The drawback is that it is likely that the receive time of the packet will be less accurate. We are not completely sure it will be possible to detect and handle the added noise in the time stamps but we have good hope!

The current state of the project

Last week we did a proof of concept hack when we modified the old TDoA 2 implementation to transmit at random times, as well as minor modifications to handle random receive order of packets. It all worked out beautifully and we could fly a short sequence in the office with the new mode. The estimated position was a bit more shaky which is not surprising, considering that the receive times are more noisy.

We have just started with the real deal.  We have designed a draft spec of the protocol and have also started to implement the new protocol on top of the old TDoA2 algorithms in the anchors and the Crazyflie to get started. Next steps will be to introduce random transmission times, dynamic anchor management and better error handling. The TDoA 3 implementation will exist in parallel with the current TDoA2 implementation and should not interfere.

If you want to contribute, are interested in what we do or have some input, please comment this blog post or contact us in any other way.

 

 

 

I’ve spent the last 5 years of my career at Microsoft on the team responsible for HoloLens and Windows Mixed Reality VR headsets. Typically, augmented reality applications deal with creating and manipulating digital content in the context of real-world surroundings. I thought it’d be interesting to explore some applications of using an augmented reality device to manipulate and control physical objects and have them interact with the real world and/or digital content.

Phase 1: Gesture Input

The HoloLens SDK has APIs for consuming hand gestures as input. For the first phase of this project, I modified the existing Windows UAP/UWP client to handle these gestures and convert them to CRTP setpoints. I used the “manipulation gesture” which provides offsets in three dimensions for a tap-and-drag gesture, from the point in space where the initial tap occurred. These three degrees of freedom are mapped to thrust, pitch and roll.

For the curious, there’s an article on my website with details about the implementation and source code. Here’s a YouTube video where I explain the concept and show a couple of quick demos.

As you can see in the first demo in the video, this works but isn’t entirely useful or practical. The HoloLens accounts for head movements (otherwise moving the head to the left would produce the same offset as moving the hand to the right, requiring the user to keep his or her head very still) but the user must still take care to keep the hand in the field of view of the device’s cameras. Once the gesture is released (or the hand goes out of view) the failsafe engages and the Crazyflie drops to the ground. And of course, lack of yaw control cripples the ability to control the Crazyflie.

Phase 2: Position Hold

Adding a flow deck makes for a more compelling user experience, as seen in the second demo in the video above. The Crazyflie uses the sensors on the flow deck to hold its position. With this functionality, the user is free to move about the room and make shorter “adjustment” hand gestures, instead of needing to hold very still. In this mode, the gesture’s degrees of freedom map to an x/y velocity and a vertical offset from the current z-depth.

This is a step in the right direction, but still has limitations. The HoloLens doesn’t know where it is in space relative to the Crazyflie. A gesture in the y axis relative to the device will always result in a movement in the y direction of the Crazyflie, which begins to feel unnatural if the user moves around. Ideally, gestures would cause the crazyflie to move in the same direction relative to the user, not relative to the ‘front’ of the Crazyflie. Also, there’s still no control over yaw.

The flow deck has some limitation as well: The z-range only goes to 2 meters with any accuracy. The flow sensor (for lateral stabilization) has a strong dependency on the patterns on the floor below. A flow sensor is a camera that relies on measuring pixel deltas from frame to frame, so if the floor is blank or has a repeating pattern, it can be difficult to hold position properly.

Despite these limitations, using hand gestures to control the Crazyflie with a flow deck installed as actually quite fun and surprisingly easy.

Phase 3 and Beyond: Future Work & Ideas

I’m currently working on some new features that I hope will open the door for more interesting applications. All of what follows is a work in progress, and not yet implemented or functional. Dream with me!

Shared Coordinate System

The next phase (currently a work in progress) is to get the HoloLens and the Crazyflie into a shared coordinate system. Having spatial awareness between the HoloLens and the Crazyflie opens up some very exciting scenarios:

  • The orientation problem could be improved: transforms could be applied to gestures to cause the Crazyflie to respond to commands in the user’s frame of reference (so ‘pushing’ away from one’s self would cause the Crazyflie to fly away from the user, instead of whatever direction is ‘forward’ to the Crazyflie’s perspective).
  • A ‘follow me’ mode, where the crazyflie autonomously follows behind a user as he or she moves throughout the space.
  • Ability to walk around and manually set waypoints by selecting points of interest in the environment.

The Loco Positioning System is a natural fit here. A setup step (where a spatial anchor or similar is established at same physical position and orientation as the LPS origin) and a simple transform for scale and orientation (HoloLens and the Crazyflie define X,Y,Z differently) would allow the HoloLens and Crazyflie to operate in a shared coordinate system. One could also use the webcam on the HoloLens along with computer vision techniques to track the Crazyflie, but that would require constant line of sight from the HoloLens to the Crazyflie.

Obstacle Detection/Avoidance

Example surface map produced by HoloLens

The next step after establishing a shared coordinate system is to use the HoloLens for obstacle detection and avoidance. The HoloLens has the ability to map surfaces in real time and position itself in that map (SLAM). Logic could be added to the HoloLens to consume this surface map and adjust pathing/setpoints to avoid these obstacles without reducing the overall compute/power budget of the Crazyflie itself.

Swarm Control and Manipulation

As a simple extension of the shared coordinate system (and what Bitcraze has been doing with TDoA and swarming lately) the HoloLens could be used to manipulate individual Crazyflies within a swarm through raycasting (the same technique used to gaze at, select and move specific holograms in the digital domain). Or perhaps a swarm could be controlled to move out of the way as a user passes through the swarm, and return to formation afterward.

Augmenting with Digital Content

All scenarios discussed thus far have dealt with using the HoloLens as an input and localization device, but its primary job is to project digital content into the real world. I can think of applications such as:

  • Games
    • Flying around through a digital obstacle course
    • First person shooter or space invaders type game (Crazyflie moves around to avoid user or fire rendered laser pulses at user, etc)
  • Diagnostic/development tools
    • Overlaying some diagnostic information (such as battery life) above the Crazyflie (or each Crazyflie in a swarm)
    • Set or visualize/verify the position of the LPS nodes in space
    • Visualize the position of the Crazyflie as reported by LPS, to observe error or drift in real time

Conclusion

There’s no shortage of interesting applications related to blending augmented reality with the Crazyflie, but there’s quite a bit of work ahead to get there. Keep an eye on the Bitcraze blog or the forums for updates and news on this effort.

I’d love to hear what ideas you have for combining augmented reality devices with physical devices like the Crazyflie. Leave a comment with thoughts, suggestions, or any other relevant work!

We have been flying swarms in our office plenty of times. There is kind of a limitation to this though, our flying space is only around 4 x 4 meters. Flying 8 – 10 Crazyflies in this space is challenging and it is hard do make it look good. Slight position inaccuracy makes it look a bit sloppy. To mitigate this we decided to have a small swarm show using a a bigger flying space and to invite families and friends, just to raise the stake a bit.

As usual we had limited time to accomplish this, and this time the result should be worth looking at. Well, we have managed to pull off hard things in one day before so why not this time… The setup is basically a swarm bundle with added LED-rings. Kristoffer took care of the choreography, Tobias setting up the drones and Arnaud configuring the Loco positioning system.

Choreography

Kristoffers pre-Bitcraze history involves some dancing and he has been playing a bit earlier with the idea of creating choreographies with Crazyflies. One part of this was a weekend-hack a few months back when he tried to write a swarm sequencer that is a bit more dance oriented. The goal was to be able to run a sequence synchronized to music and define the movements in terms of bars and beats rather than seconds. He also wanted to be able to define a motion to end at a specific position at a beat as opposed to start on the beat. As Kristoffer did not have access to a swarm when he wrote the code he also added a simple simulator to visualize the swarm. The hack was not a complete success at that time but turned out to be useful in this case.

The sequences are defined in a YML file as a list of time stamps, positions and, if needed the color of the LED-ring. After a few hours of work he had at least some sort of choreography with 9 Crazyflies moving around, maybe not a master piece from a dance point of view but time was running out.

The simulator is super basic but turned out to be very useful anyway (the color of the crosses indicates the color of the LED ring). We actually never flew the full sequence with all drones before the performance, but trusted the simulation to be accurate enough! We did fly most of the sequence with one Crazyflie, to at least make it plausible that we got it all right.

Short snippet from the simulation

Setting up drones

Handling swarms can be tedious and time consuming. Just making sure all drones are assembled, fully operational and charged is a challenge when the number increases. Tobias decided to do manual flight test of every drone. If it flies well manually it will most likely fly well autonomously.  The testing resulted in switching out some motors and props as vibrations is a crippling factor, especially for Z accuracy. Takeaway from this exercise is to implement better self testing so this can be detected automatically and fixed much quicker.

Loco Positioning System

We ran the positioning system with standard firmware in TDoA mode to support multiple Crazyflies simultaneously. The mapped space was around 7 x 5 x 2.5 meters and the anchors were placed more or less in the corners of the flying space box.

The result

The audience (families and friends) was enthusiastic and expectations high! Even though not all drones made it all the way through the show, the spectators seemed to be duly impressed and requested a re-run.
 

 

We have been writing a couple of times already about the new TDoA2 algorithm for the Loco Positioning System. A TDoA mode has been experimental from the day we released the LPS but we are now proud to announce that TDoA is an official positioning mode for the Loco Positioning System and the Crazyflie.

Practically it means that the Loco Positioning System now has an officially supported mode to locate and fly a swarm of Crazyflie 2.0.

We have worked these last weeks at updating documentation, the “Getting started” tutorial and releasing all the affected firmware and software. One of our goals was to make the new TDoA mode as seamless and as easy as possible to work with, this meant having everything working without having to recompile the Crazyflie or any other part of the system. The Crazyflie is now detecting the LPS mode automatically and it is possible to configure the anchors position and ranging mode remotely from the within Crazyflie client LPS tab.

What we have just released is:

If you have 8 anchors and want to convert your local positioning system to TDoA, this can be done very easily by following the new version of the getting started with loco positioning system guide.

If you want more information about the different positioning modes, we have also updated the system description.

 

This week we have a guest blog post by Ben, enjoy!

I’m Ben Kuperberg and i’m a digital artist, artist-friendly software developer and orchestra conductor. Being a juggler, I’ve decided to focus some of my work on the intersection between juggling and technology, and i’ve since been working more and more with jugglers, my last project being “Sphères Curieuses” from Le Cirque Inachevé, created by Antoine Clée. While the whole project is not focused on drones, a part of it involves synchronized flight of multiple drones and precise human interaction with those drones. Swarm flight is something already out there and some solutions already exist but the context of this project added some challenges to it.

Most work on drone swarms have been done by research group or school. They use high-grade expensive motion-capture system able to track precisely the drones and able to assign their absolute positions. While the quality of the result is undeniable, it’s not fit for stage shows : the setup is taking a lot of time which we can’t always have when the show is on the road. Moreover, the mocap system is too invasive for the stage if you want to be able to “hide” a bit the technology and let the spectator focus on what the artist wants you to see. Not to mention it costs an arm and a leg and Antoine needs both to juggle.

So we had to find other ways to be able to track multiple drones. That’s when we found out the [amazing] team at Bitcraze was working on the TDoA technology, which allows precise-enough tracking of a virtually unlimited amount drones, at reduced cost and with a fast and clean setup.

After some work we managed to have a first rough version of our swarm server made by Maxime Agor that allowed to connect and move multiple drones using the TDoA system, controlled from a Unity application.

While we were able to present a decent demo with this system, we were facing a major problem of reactivity. When working with artists and technology, reactivity is a key component to creativity. Because it can be frustrating and tense to stop each 2 minutes to make changes or fix problems. My first priority was therefore to prepare and design softwares that will allow me to spend most of the “creation time” on the actual creation aspect and not on technical parts. It is also essential that the artist performing in front of the audience can entirely focus on the performance and by fully confident in this technology. The last challenge is that as I focus my work on the creation and not touring, all my work needs to be easily understood and modified by both the artists and the technicians who will take over my work for the tour.

With all of that in mind, I decided to create a software with a high-end user interface called “La Mouche Folle” (« The Crazy Flie » in french) that allows to control multiple drones and have an overview of all the drones, their battery/charging/alert states, auto-connect / auto-reboot features, external control via OSC, and a Unity client to view and actually decide how to move the drones. All my work is open-source, so you can find the software on github.

There only is a Windows release for now but it should compile just fine on OSX and Linux, the software is made with JUCE, depends on OrganicUI and lib-usb. Feel free to contact me if you want more information on the software. Many thanks Wolfgang Hoenig for the support and the great work on the crazyflie cpp library i’m relying on.

So this is the basic setup of our project, but we needed more than that to control the drone. We wanted to be able to control them in the most natural way possible. We quickly decided to go with glove-base solutions, and have been working with Specktr to get our hands – pun intended – on developer versions of the glove. The glove is good but can’t give us absolute position of the hand, so we added HTC Vive trackers with the lighthouse technology and then were able to get both natural hand control and sub-millimeter precision of the tracked hand.

Then it was a matter of connecting everything together : for other projects for Theoriz Studio, I already developed MrTracker (used in the MixedReality project) that acts as a middleware between the Vive trackers and Unity.

I used Chataigne to easily connect and route the Specktr Glove data to Unity as well so we would have maximum flexibility to switch hardware or technology without breaking whole setup if we needed to.

 
A video of the final result
 

 

In the past years, i’ve come to work on a lot of different projects, with different teams, which i like very much, because each project leads to discover new people, new ways of working and new challenges to overcome. I’m having a great time working on this project and especially sharing everything with the guys at Bitcraze and the community, everyone has been so cool and nice. I’ve planned to go at the Bitcraze studios to work for few weeks with them and i’m sure it’ll be a great experience !

The Loco Positioning System (LPS) default working mode is currently Two Way Ranging (TWR), it is a location mode that has the advantage of being pretty easy to implement and gives good positioning performance for most use cases and anchor setups. This was a very good reason for us to start with it. Though, TWR only supports positioning and flying of one or maybe a couple of Crazyflies, while it is not a solution to fly a swarm.

One solution to fly a swarm is an algorithm called Time Difference of Arrival (TDoA). We have had a prototype implementation for a while but we experienced problems with outliers, most of them where due to the fact that we where loosing a lot of packets and thus using bad data.

To solve these issues, TDoA2 makes two changes:

  • Each packet has a sequence number and each timestamps is associated with the sequence number of the packet it has been created from
  • The distances between anchors are calculated and transmitted by the anchors

A slightly simplified explanation follows to outline why this helps (a more detailed explanation of how TDoA works is available in the wiki).

We start by assuming that all timestamps are available to the tag, this is done by transmitting them in the packets from the anchors to the copter.

The end goal is to calculate the difference of time of arrival between two packets from two different anchors. Assuming we have the transmission time of the packets in the same clock, all we need to do is to subtract the time between the two transmissions with the time between the two receptions:

0 – anchor 0, 1 – anchor 1, T – Tag (that is the LPS deck on the Crazyflie)

To do so we need to have the time it took for the packet to travel between the two anchors, this will enable us to calculate the transmit time of P2 in anchor 1, this can be done by calculating the TWR time of flight between the two anchors, this would require the tag to receive 3 packets in sequence:

So now for the part where TDoA2 helps: previously we had to have the 3 packets in sequence in order to calculate a TDoA, if any one of these where missing the measurement would fail or worse, it could give the wrong result. Since we did not have sequence numbers, it was hard to detect packet loss. Now that we have sequence numbers, we can understand when a packet is missing and discard the faulty data. We also do not have to calculate the distance between anchors in the tag anymore, it is calculated by the anchors themselves. This means that we can calculate a TDoA with only two consecutive packets which increases the probability of a successful calculation substantially.

To reduce packet loss even more, we have also added functionality to automatically reduce the transmission power of the NRF radio (the one talking to the Crazyradio dongle) when the LPS deck is detected. It has turned out that the NRF radio transmissions are interfering with UWB radio reception, and since most indoor use cases does not require full output power we figured that this was a good trade-off.

The results we have seen with the new protocol is quite impressive: TDoA is usually very sensitive to the tag being inside the convex hull, so much so that with the first TDoA protocol we had to start the Crazyflie from about 30cm up to be well within the convex hull. This is not required anymore and the position is still good enough to fly even a bit outside of the convex hull. The outliers are also greatly reduced which makes this new TDoA mode behave very close to the current TWR mode, but with the capability to locate as many Crazyflies as you want:

Added to that, we have also implemented anchor position handling in the TDoA2 protocol and this means that it is now as easy to setup a system with TDoA2 as with TWR:

We are now working on finishing the last functionality, like switching between algorithms (TWR and TDoA) and on writing a “getting started guide”. When that is done TDoA will become an official mode for the LPS.

In the mean time, if you are adventurous, you can try it yourself. It has been pushed in the master branch of the Crazyflie firmware and the LPS node firmware. You should re-flash the Crazyflie firmware, both STM32 and nRF51, from master and the anchors from master too.

As I wrote about in a previous blog post, I have been working on an anchor position estimation algorithm in the Crazyflie Client. The algoritm uses ranging data from the Loco Positioning system to estimate where the anchors are located, and thus remove the need to measure their positions in the room. I have finally reached a point where I think it is good enough to let it out from the lab and it has been pushed to the client repository.

A button has been added to the Loco Positioning tab that opens a wizard. In the wizard the user is asked to place the Crazyflie in certain positions to record ranges and define the coordinate system. If all goes well, the estimated anchor positions are transfered to the anchor position fields in the Loco Positioning tab. If the user is happy with the result the next step is to write the positions to the anchors and start flying!

Now to the disclaimer: the results may not always be perfect – surprise! We have not tested the algorithm a lot but it seems to give decent results, at least it can be useful as a base for manual corrections and sanity checks. Some of the estimated positions are pretty good, while others might be a meter or so off. The conclusion is that you should not trust it blindly, check that the estimated positions seem reasonable before flying.

Currently the system only supports Two way ranging, but extending it to TDoA should not be too complicated. There are probably many possible improvements that can be done, and we hope that everyone that finds this interesting and have ideas of how to do it will give it a go. After all, it is open source and we would love to see contributions refining the functionality, now that there is a base to build from.

Any feed back is welcome, let us know if it works or not in your setup!

One of the pain points when setting up the Loco Positioning system is to measure the anchor positions and enter them into the system. I wanted to see if I could automate this task and let the system calculate the positions, and if so understand what kind of precision to expect. I have spent a few Fun Fridays playing with this problem and this is what I have found so far.

The problem can be broken down into two parts:
1. How to calculate the anchor positions. What data is required?
2. How to define the coordinate system. To make it useful the user must to be able to define the coordinate system in a simple way.

Anchor and ruler

How to calculate the anchor positions

The general idea of how to calculate the anchor positions is to set up a system of equations describing the distances between the anchors and/or the Crayzflie and solve for the anchor positions. The equations will be non linear and the (possibly naive) plan is to use the Gauss Newton method to solve the system.

To understand how to calculate the anchor positions we must first take a look at the data that is available. The Loco Positioning system can be run in two different modes: Two Way ranging (default mode) and TDoA.

Two way ranging

In the Two Way ranging mode we measure the distance between each anchor and the Crazyflie and to get enough data we must record ranging data for multiple positions. The anchor positions are unknown, and for each new Crazyflie position we add yet a new unknown position, on the other hand we measure the ranges to the anchors so these are knowns. 

The equations used are simply to calculate the distance between the assumed position of each anchor and the Crazyflie and then subtracting it from the measured distance.

TDoA

In TDoA we measure the Time Difference of Arrival, that is the difference in distance to two anchors from the Crazyflie’s position. It is probably possible to use this information, but I was looking for a different solution here. In our new TDoA implementation that we have been playing with a bit, we get the distance between all anchors (calculated in the anchors) as a side effect. 

In this case the Crazflie is not really needed and the equations describe the distance between assumed anchor positions versus measured distances.

How to define the coordinate system

To get a useable positioning system, the coordinate system must be well defined and oriented in a practical direction. For example when writing a script you probably want (0, 0, 0) to be at some specific spot, the X-axis pointing in a certain direction, the Z-axis to point up and so on. My initial idea was to use the anchors to define the coordinate system, use anchor 0 as (0, 0, 0), let the X-axis pass through anchor 1 and so on. Just by looking at our flight lab I realised that this would be too limiting and decided that the coordinate system should be completely disconnected from the anchor positions, but still easy to define. I also realised that a really good way to tell the system about the desired coordinate system would be to move the Crazyflie around in space to show what you want. The solution is to place the Crazyflie at certain positions and click a button to record data at these positions. The steps I have chosen are:

  1. Place the Crazyflie at (0, 0, 0)
  2. Place the Crazyflie on the X-axis, X > 0
  3. Place the Crazyflie in the XY-plane, Y > 0
  4. Move the Crazyflie around in the space with continuous recording of data

In this scheme the XY-plane is typically the floor.

Results

I have written basic implementations for both the Two Way ranging and TDoA modes and they seem to work reasonably well in simulations. I have also tested the Two Way ranging algorithm in our flight lab with mixed results. The solution converged in most cases but not always. When converging the estimated anchor positions ended up in the right region but some were off by up to a meter. Finally I did run the algorithm and fed the result into the system and managed to fly using the estimated positions which I find encouraging.

I will continue to work on this as a Friday Fun project and maybe it will make its way into the client code base at some point in the future? There are probably better ways to estimate the anchor positions and more clever algorithms, feel free to share them in the comments.

 

 

We have had an implementation of a Time Difference of Arrival algorithm (TDoA) in the Crazyflie 2.o and the Loco Positioning System for quite a long time. The coolest feature of the TDoA algorithm is that it can be used to position virtually unlimited number of Crazyflies concurrently as opposed to the standard Two Way Ranging algorithm that is limited to one (or very few Crazyflies). The original implementation is working pretty well but contains some flaws that we are not completely happy with, hence we have not released it officially and are still calling it experimental. Since support for tracking multiple objects is a requirement for flying swarms and we like swarms, we have started to iron out the problems. 

A small swarm using the old TDoA algorithm, from February 2017.
 

In the current implementation each anchor transmits the time of the transmission and the times of the latest reception of transmissions from all other anchors about every 16 ms. From this information it is possible to calculate the difference in time of flight for the radio waves from two anchors to the Crazyflie. When we know the difference in time of arrival, by multiplying with the speed of light we get the difference in distance and can calculate the position of the Crazyflie. This all sounds fine and dandy but the set up has some problems, the biggest one being error handling. If one or more packets are lost, either from anchor to Crazyflie or anchor to anchor, there is no deterministic way to detect it in some cases. The current algorithm relies on sanity checking the calculated result and discarding data that looks suspicious, which is usually easy as the distances quickly gets unrealistic (several thousands of meters!). We suspect that some erroneous values slip through the check though and we would like to be able to really understand when data is valid or not.

TDoA 2.0

What we are working on now is to add a sequence numbering scheme to enable the receiving party to understand when a packet has been lost. With this information it will be possible to discard bad data as well as use the available information better. While we are re-writing the code we are also moving a part of the algorithm from the Crazyflie to the anchors, after all there is a CPU in the anchors that is not fully utilized. The idea is to let each anchor continuously calculate the distance to all other anchors and add this information to the messages it transmits, which will reduce the work in the Crazyflie.

This is work in progress and we are not completely sure where we will end up, but we are aiming at making the TDoA mode part of the official release at some point.

Sensor fusion

Related to the Loco Positioning system is our line of other positioning sensors; the Z-ranger deck and the Flow deck. The Flow deck has really good precision at low altitudes but can not provide absolute positioning while the Loco Positioning system does not have the same precision but absolute position capabilities. So what if we fuse the information from the Flow deck with the Loco Positioning system? We have tried it out and it works pretty well, we can get the best of two worlds! The Z-ranger can also be used in the same way to improve the Z component of the estimated position when flying bellow ~1m.

Even though it works using multiple positioning sensors at the same time, there is room for improvements and some tweaking will be required to make it rock solid.