Programming Quadcopters, Part I

Video of my presentation for the Madison Perl Mongers about programming quadcopters. Part II will be given for the Millwaukee Perl Mongers on March 16th.

The quality isn’t up to snuff. I grabbed an action cam with a fisheye lens and a microphone that isn’t meant for this sort of thing. The brightness of the projector washes out the image of most of the slides. I’m putting it up for posterity, but I think I’ll redo it at home so people who weren’t there can tell what the hell is going on.

Low Latency FPV Streaming with the Raspberry Pi

One of the biggest challenges in running my local quadcopter racing group has been overlapping video channels. The manual for the transmitters list a few dozen channels, but in practice, only four or five can be used at the same time without interference.

The transmitters being used right now are analog. Digital video streams could make much more efficient use of the spectrum, but this can introduce latency. Of late, I’ve been noticing a few posts around /r/raspberry_pi about how to do an FPV stream with an RPi, and I’ve been doing some experiments along these lines, so I thought it was a good time to share my progress.

It’s tempting to jump right into HD resolutions. Forget about it; it’s too many pixels. Fortunately, since we’re comparing to analog FPV gear, we don’t need that many pixels to be competitive. The Fatshark Dominator V3s are only 800×600, and that’s a $600 set of goggles.

You’ll want to disable wireless power management. This will tend to take the wireless interface up and down a lot, introducing a delay each time. It’s not saving you that much power; consider that an RPi takes maybe 5 watts, while on a 250-sized quadcopter, the motors can easily take 100 watts or more each. So shut that off by adding this anywhere in /etc/network/interfaces:

And reboot. That should take care of that. Check the output of iwconfig to be sure. You should see a line that says “Power Management:off”.

You’ll want to install GStreamer 1.0 with the rpicamsrc plugin. This lets you take the images directly off the RPi camera module, without having to use shell pipes to have raspivid to go into GStreamer, which would introduce extra lag.

With GStreamer and its myriads of plugins installed, you can start this up on the machine that will show the video:

This will listen on UDP port 5000, waiting for an RTSP h.264 stream to come in, and then automatically display it by whatever means works for your system.

Now start this on the RPi:

Modify that last line to have the IP address of the machine that’s set to display the stream. This starts grabbing 640×480 frames off the camera with h.264 encoding, wraps them up in the RTSP protocol, and sends them out.

On a wireless network with decent signal and OK ping times (80ms average over 100 pings), I measured about 100ms of video lag. I measured that by displaying a stop watch on my screen, and then pointing the camera at that and taking a screenshot:


This was using a RPi Model 2, decoding on a fairly modest AMD A8-6410 laptop.

I’d like to tweak that down to the 50-75ms range. If you’re willing to drop some security, you could probably bring down the lag a bit by using an open WiFi network.

I’ll be putting together some estimates of bandwidth usage in another post, but suffice it to say, a 640×480@30fps stream comes in under 2Mbps with decent quality. There will be some overhead on that for things like frame and protocol headers, but that suggests a 54Mbps wireless connection will take over 10 people no problem, and that’s on just one WiFi channel.

New Module: Device::Spektrum — Control Common RC Quadcopter Flight Controllers

I’ve been wanting to put a Raspberry Pi on a quadcopter ever since I realized that the AR.Drone was too limited and poorly implemented.

It’s a bad idea to run everything off a Raspberry Pi running Linux. There are a lot of fine tuning PID-related adjustments every fraction of a second, and Linux could potentially delay the running process and cause you to crash (in the physical sense as well as the computational sense). So you need a flight controller like the Naze32, MultiWii, or AeroQuad that takes care that stuff in a dedicated processor.

How to communicate with a flight controller? The typical quadcopter sends PPM or Combined PPM to the FC. PPM sends pulses of a specific length, with one wire for each channel. Combined PPM is the same idea, but sends everything together and only needs one wire total. This is the oldest, most analog way of sending RC signals, coming from the days of brushed motors, NiCad batteries, and 27MHz radios with ten foot long antennas.

PPM/CPPM won’t work with a Raspberry Pi with Linux, either, for similar reasons as above. A delay in the timing of the signal throws the whole system off. It has been done on Arudino and Teensy.

The modern way is to use a digital serial protocol. One of these protocols is called Spektrum, and it’s implemented on the Naze32 FC, among others.

The Spektrum protocol has been implemented in Perl with Device::Spektrum. Should be hitting the CPAN mirrors shortly.

Quoting in Documentation

I just ran across a small niggle in the DateTime::Format::Strptime docs:

%N Nanoseconds. For other sub-second values use %[number]N.

I needed a 3-decimal sub-second value, so I went off and dutifully wrote:

Note my simple-stupid copy of the square brackets. This creates dates like:


Which is not at all what I had in mind. Then I smacked my forehead, remembering printf() conventions, and wrote:

No square brackets, and everything works fine.

This issue of direct quoting conventions reminds me of an entry on writing style from the Jargon File:

Consider, for example, a sentence in a vi tutorial that looks like this:

Then delete a line from the file by typing “dd”.

Standard usage would make this

Then delete a line from the file by typing “dd.”

but that would be very bad — because the reader would be prone to type the string d-d-dot, and it happens that in vi(1), dot repeats the last command accepted. The net result would be to delete two lines!

This isn’t quite a “standard usage” issue. It’s an American usage issue. British style for quotes sensibly puts the period on the outside, in agreement with the Jargon File above.

The problem with the Strptime method above is that the convention is ad-hoc, hoping that the reader will catch on to the author’s intent. This tends to cause problems for newer programmers, and even more experienced programmers may take a few iterations to catch on. In some cases, it could also confuse programmers with a different social background.

One solution is to lay out a style guideline at the beginning of the documentation. Programming books will often do this. It’s also similar to the way RFC2119 lays out the definitions of “MUST”, “SHOULD”, etc. in a way that’s intended to be used by other RFCs.

The problem here is that you’re expecting your readers to know that much more before getting into the nuts and bolts of your library. Language and protocol definitions need to be specified very precisely, but library documentation doesn’t necessarily require that–clarity of understanding and succinctness can be better than rigor. Plus, there’s bound to be competing systems of style guidelines, and readers will have to know all of them, or at least the more popular ones.

Instead, it’s enough to give a quick example. Consider if the Strptime docs had said something like:

%N Nanoseconds. For other sub-second values use %[number]N. Example: ‘%T.%3N’

And now there is no question on the square brackets being included in the string or not. Everything the reader needs to know is encapsulated in a single location of the docs–no referencing back to other sections or documents.

Don’t use is() in Test::More

This results in:

The issue is fairly obvious when it’s laid out like this: is() does a string comparison, which means that trailing zero matters. One day, though, I promise you, you’ll hit a problem like this and will spend hours debugging it, only to smack your forehead when you finally see it. You can prevent that by explicitly giving a comparison operator to cmp_ok() instead.

This is somewhat similar to the issues seen in the ‘==’ operator in JavaScript and PHP, where the language makes a guess about how to coerce the types and gets it wrong (or at least, produces unexpected behavior). Those languages invented ‘===’ to solve that, which is madness.

Musings on Big-Oh and the Schwartzian Transform

Not a new topic, but one I’ve been mulling over recently.

Let’s start with a basic sort operation in Perl over a series of DateTime objects:

Perl 5.6 and earlier used quicksort, and after that used mergesort. There’s also a sort pragma if you want to specify something else.

Now, quicksort has an average runtime of O(n * log(n) ), but there’s a few terrible cases where it goes quadratic–O(n2). Quadratic is bad; the only good thing about quadratic is that it’s not polynomial (that is, O(2n), where the exponent is variable rather than the base, which makes us start using phrases like “assume we have until the end of the Universe to finish this run . . . “). The one nice thing is that quicksort has a few friendly cases where it’s O(n). With mergesort, almost everything is O(n * log(n) )–that is, giving up a few nice cases in exchange for never going quadratic.

What really is all this Big-Oh stuff? One way to think about it is that it’s the number of times you loop over something. It doesn’t tell you how long each iteration of the loop will take, just on how many times it will iterate. If you’re walking a list, that’s O(n), where n is the number of elements of a list. If you walk it twice, that’s O(2n). For an algorithm that runs in O(n * log(n)), things will take longer than O(n) when n > 10 (because log(10) == 1).

(This is why a hash lookup is sometimes slower than a balanced binary tree. Hash lookups are constant time, O(1) (well, it is if we squint a little), and balanced binary trees are O(log(n)) worst case. But that constant time in hashes is very big, and the tree’s loop is very tight. It doesn’t take many entries for hashes to catch up, though.)

So when we look at the sort above, we notice that we’ll want to keep expensive operations out of the subroutine we’re passing to sort. That subroutine will be called O(n * log(n)) times (roughly speaking), so let’s try to hoist expensive operations out of it.

This is exactly what the Schwartzian Transform does. Let’s start by having a map() execute before the sort to pull out some easily sortable data from our DateTime objects. The Unix epoch will do nicely for this (use hires epoch if you need to):

Now we can modify our sort algorithm to pull out that first entry in the arrayref and do a straight numeric comparison:

Perl’s spaceship (<=>) operator does a numeric sort, which will be faster than the lexicographical sorting of the cmp operator (which gets even more complicated if you’re Tom Christiansen). If you can sort based on numbers rather than strings, that’s always better.

Now we want to get at our original object rather than the arrayrefs we created, so we do another map() to pull that out:

Now let’s combine all that together in a single statement to get the Schwartzian Transform as it’s usually seen:

This ends up being O(2n) for the two maps, plus O(n * log(n)) for the sort. But we’re making that O(n * log(n)) cheaper per iteration, so it’s a win overall if @dates is big enough.

Can we take this further? If we can collapse that arrayref into a straight string or number, then we can remove the subroutine passed to sort entirely. This means perl will do a lexicographic sort completely within its internals without the extra time taken to call a Perl subroutine (which more than makes up for the extra time of a lexicographic sort rather than straight numeric). This isn’t always easy, but in this case we could do it by throwing away our DateTime objects entirely in the first map() (first by order of operations, that is), and then rebuilding it with the epoch data passed to the second map():

This form is called the “Guttman-Rosler Transform”. It may or may not be faster than an equivalent Schwartzian, depending on how expensive destructing/reconstructing the object is. That would also do all kinds of fucky things to runtimes with threaded garbage collectors, but it’s not too bad for a refcounting language like Perl5. If you’re serializing things into strings, care has to be taken that you’ll get the output objects deserialized the same way on the flip side. Big-Oh is the same as the Schwartzian.

One thing that I think is overlooked about the Schwartzian is improving separation of concerns. The sort routine is not responsible for formatting data in a way that’s sortable, and there’s no need to copy/paste the same code for $a and $b. That’s the sole job of the first map(). Once you recognize the idiom, your eyes can easily fall to the place where the data munging is happening. This makes the Schwartzian a nice idiom even when its performance improvement is marginal.

Welcome, Readers

The Wumpus Cave is‘s site of the day! Here’s a few links to old entries that y’all might be interested in:

Happy reading!