Swarm localization

Hi all,

I am wondering if anybody has accomplished swarm localization with the DWM1000 (or other sensors). The idea is to find relative location between tags without the use of anchors, so that the task can be performed outdoors and in mobile/dynamic environments. Has anyone looked in to this?

Any research you could point me to or advice on getting started would be appreciated! I am thinking of using a TOF distance measurement from one tag to multiple others (for each tag) and then feeding that in to a particle filter algorithm that performs relative localization simultaneously for all tags. Anybody have thoughts? Would it be worthwhile to explore combining two or more DWM1000s into a single sensor package so that I could estimate angle of arrival as well as distance?

Please feel free to chime in! Also feel free to email me at kristo.jorgenson at gmail

Thank you,

Kristo

Additionally, does anyone know if it is possible to connect multiple antennae to a single DWM chip, such that angle can be calculated using PDOA but with a single DWM chip instead of two?

I’ve used a similar method for anchor surveying, 8 or more anchors all range to each other and then calculate their relative locations. In some tests I’ve had average 2D errors of under 5 cm from truth.
This was an addition to the system for diagnostics rather than its intended operating mode so it’s painfully slow and inefficient. It originally took fixed locations and calculated antenna delays but with enough data points you can open up the number of variables and also calculate locations. Not quite what you are aiming for but similar.

It would be hard to do a PDOA with only one chip and two antennas since you couldn’t receive the same packet from two antennas at the same time. You could do a basic angle of arrival system by ranging point to point, switching antenna, ranging again and looking at the difference. But measurement noise is going to cost you a lot of accuracy and possible changes to antenna delays would add a complication. My gut call would be that given the relatively low cost of the DW1000 it’s probably not worth the complication and performance drop to switch antennas.

Thanks for the tips, Andy! That sounds really encouraging that you were able to perform relative localization with a series of anchors. I’m still a bit confused what the difference between an anchor and tag is, since they are the same circuit after all… is it just the software?

Do you have any details about how you achieved this?

I see what you mean about PDOA with a single chip. Was just a thought, but you’re right given the cost and size I will at least initially start with multiple chips.

Thanks again and any details you can share about how to achieved relative localization would be super helpful!

Best,

Kristo

It wasn’t really anything clever.
I take a list of N tags. I instruct every tag to range to every other tag and store all of the results.
I then set up a least squares optimization to find the set of tag locations which minimize the errors between the expected and measured ranges. I fix the X/Y/Z location of the first tag and the heading from tag 1 to tag 2 and then let it vary the remaining variables without constraints.

It helps that I’m running a custom radio protocol rather than the decawave supplied one. I have a command packet that I can send telling a tag to range a fixed number of times to a different tag and then return the average and yield. It means that I can connect to any tag and have it drive the whole process, the rest of the system can sit in it’s normal idle state waiting for a command.

You are correct, a tag and an anchor are the same hardware only running different firmware (or the same firmware in a different mode) and normally one is static and one is dynamic.

This is great to hear, thanks for the info! Is your radio protocol running on top of the supplied firmware or is it lower level?

A little lower. Not a single line of decawave firmware/software anywhere in the product.

I think what you’re asking about is what I call Multi-Ranging.
Typically this uses a lot of air time, due to the separate ranging transactions that take place, as well as moving the location data to a particular node of interest.
There are ways of optimizing the on-air time of the units involved which can help this.
Usually the results are more robust, but power/time intensive than other methods.
+Paul

Hi Kristo,

something similar as Andy described is also in PANS (see MDEK1001) and it is called auto-positioning function. Basically each anchor do multiple measurements to the surrounding anchors and then calculate some average range and other parameters. These values are then acquired via Bluetooth to the Android application and the position of Anchors are estimated. The Bluetooth API is open and Android application is open-source so it might be a good starting point for you to do some tests.

This video might be what you are looking for: https://www.youtube.com/watch?v=V85wejcYyXs

Cheers,
TDK

Thanks all for the input. I realize air time is going to be an issue, especially if I hope to do this close to 5hz for hundreds of tags. TDK/leapslabs: Is there any more information available in regards to the video you posted?

Can anyone point me to some research around the air time issue?

Thank you

Kristo

Hi Kristo,

the article is here: http://ais.informatik.uni-freiburg.de/publications/papers/wendeberg12ipin.pdf
There are more articles from these guys which you can find on the internet. I have found also some patents related with that so better study them if you consider using it in a product.

Cheers,
TDK

1 Like

You are asking about what we call “mesh ranging”, computing the set of distances between peer nodes on a regular basis. We’ve built a system that works somewhat like this and it is deployed for a customer in their product.

The system works by each tag having a scheduled time to transmit. Say we have 5 tags, A, B, C, D, E. They will transmit in a schedule in sequence. Each packet will contain the serial number of the transmit packet, the local Decawave Time (DT) of the transmit, and a list of other nodes serial numbers and receive DT.

For example, when A transmits, the packet will contain A transmit time, and then B, C, D, E receive times, if they were heard. Then B will do the same, then C, D, and E. At whatever the repeat rate is set to, A will start over again.

A range can be computed between any two nodes knowing 6 timestamps (3 transmit, 3 receive). This takes two cycles of A and one of B to get enough data for B to compute the range A to B. It takes one more cycle for A to compute the range. Also, any other node, say C, can compute the distance between A and B just by listening to the packets exchanged between A and B. By keeping the cycle going, what was the third packet in a range computation one cycle now becomes the first packet for the next cycle. So each cycle produces a new set of range outputs.

The system has a present day capacity of about 300 Hz-tags. That means you can, for example, have 10 tags that cycle through at 30 Hz, or 30 tags that cycle through at 10 Hz, give or take. One issue is that as the number of tags grow, the size of the tag packets grow (more data being received). One effect is that transmit power gets reduced for larger packets and they become less reliable, so this can limit network diameter. Another is that your air time schedule has to allow for large packets. A further consequence is that the largest packet can only hold about 40 tag receptions in it.

Because tags have to keep their DT running, we can’t go below IDLE mode between UWB activity, so this lowers battery life on the tags. Also, since we are receiving a lot of the time, this hurts battery life as well. So mesh ranging tag battery life is not great and is not good for long lived tags. If the tags are fitted to mobile devices like robots or machinery, this is not an issue, or if the tags are used for relatively short duration events, then that isn’t a problem, either.

The system is not stand alone at present. There is one anchor which serves no locating purpose (though it can be mesh ranged to the tags). The anchor serves as the controller of the network, to send out tag configurations, and to keep network time the tags synchronize to for time slotting. The anchor also collects all the received packets and sends them to the back end server via Ethernet, which then does the range computations. The single anchor imposes a limitation that all tags need to be in range of the one anchor to operate. This particular architecture served the client’s needs well and made for an easy to manage and debug system. So in this respect, it doesn’t match your desired system architecture.

The system has obvious directions of improvement. One, we can improve air time efficiency which is presently under 50%, so doubling the capacity is possible. Two, we can define response packets which don’t need a slot for every tag and provide a selection process for which tags are sent back. This will shorten packet lengths, improve air time, and improve packet reception range. Three, allow more than one anchor to grow network physical size. Lastly, making a system that is fully anchorless would be possible, but introduces some complex distributed timing and control requirements that have to be solved, particularly if the nodes are distributed more than one network diameter apart.

The fundamental aspect of any mesh ranging system is that it takes a lot of data exchanged between nodes to do it. This necessarily limits capacity, uses up air time, and drives up battery usage. If you want to do this at 5 Hz for hundreds of tags, you have a problem if they are all in one area. If you have hundreds of tags so far spread out that any one node only sees a few others, then it might work using some sort of Aloha style system, but it will be low capacity.

If GPS or RTK GPS is an option, that wins hands down for outdoor swarm localization. I know it seems like cheating, but there’s no better way to get lots of locations than that. Then each node can broadcast it’s coordinates every so often and everybody knows where everybody is. Not every outdoor application is GPS compatible, of course, but something to consider.

That is potentially useful depending on your application. It would allow you to compute bearing for any packet being received. To be really useful, it needs to work 360 degrees, not just ~90-120 degree wedge the PDoA system currently does, which is something we are working on in our lab and should have out end of the year or early next. You would need only one short packet from every node to compute bearing to them, but that still doesn’t give you range until the packet grows and contains all the timestamps you need for that, so you still have the air time capacity issue even with bearing.

Mike Ciholas, President, Ciholas, Inc
3700 Bell Road, Newburgh, IN 47630 USA
[email protected]
+1 812 962 9408