In Which I Rant About Monopoly

2013-09-10

It happens to all of us. We’re sitting around the house with friends, when suddenly, one of the dimmer house guests says “Let’s play Monopoly!”

If things were just in the world, it would be legal to shoot them dead with malaria. Instead, everybody meekly decides that, yeah, Monopoly sounds good, let’s do it.

And you start setting up the board, and somebody insists on being the car, because reasons. And then somebody else gets the bright idea of putting a $100 in the middle. This person should be shot dead with rabies.

Yes, I know what you’re thinking. The $100 in the middle is for Free Parking. When you can find me an official rulebook that tells you to do that, I’ll take the rabies needle out of your arm.

There is no benefit from Free Parking. It’s just Free Parking. That’s it. This universal house rule should die, and Monopoly should die with it.

It’s not that it’s a terrible game, provided you can get people to stop using the house rules they grew up with. Everybody complains about how long Monopoly takes, but then they add these rules that makes it take longer. The logic is simple:

1. In Monopoly, the last one standing wins
2. This means people have to drop out of the game for it to end
3. When you can get a big wad of cash on Free Parking or by some other unofficial house rule, it tends to keep people in the game who should have dropped out
4. If people are staying in the game, it takes longer. QED.

You can have your money on Free Parking, or you can have a game that doesn’t take all night and into the next day to finish. You cannot have both.

The most genius thing in recent Monopoly variants is the electronic banker. This might seem like a cheap gimmick, but it isn’t to me. The reason is that without physical pieces of cash, there’s nothing to stuff into the center. If you wanted to follow the Free Parking house rule, you’d have to keep track of it separately, and people tend not to want to bother.

But still, don’t play Monopoly. Like I said, it’s not a terrible game, but there are million better ones.

Underappreciated Perl Modules--Tree::Trie

2013-09-09

Before the Perl community settled on the term “hashes”, many called them “associative arrays”. This was a common term for an array that looked up elements by a string among dynamic languages in the old days, such as Tcl.

Although the hash algorithm is the popular choice in modern times, it wasn’t always this way. Binary search trees were also popular, but have the disadvantage that they have a worst-case time of O(n), and an average time of O(log(n)) (where n is the number of elements). Hashes lookup keys in constant time; they stay the same speed no matter how many elements you have.

There’s a caveat to hashes though: they have large constant factors, so a binary search tree tends to be faster for a small number of elements. They also don’t come back in any obvious order unless you make them that way by alternative means.

Hashes also have a problem where the value a string hashes to may collide with another string’s hash. When that happens, the value is appended to the list. On lookup, we then have to walk that list. This means that while hashes are generally close to constant time, they actually have a worst-case time of O(n), just like binary search trees. Since hashes are used so much on Perl, it tends to be very careful about colliding hash values, but it’s still a weakness in the algorithm.

This is where the trie comes in (usually pronounced “try”). A trie will lookup keys in O(m) time, where m is the length of the lookup string. Note that hashes actually have this limitation, too. It takes at least O(m) time to hash the string so we can look it up.

Oh, and you can get back the keys in sorted order by doing a pre-order traversal.

Oh, and you can get back a list of keys that match a prefix with practically no additional overhead.

All else being equal, a trie will be on par or better than the speed of hashes. However, in Perl, not all is equal. Perl’s hash implementation is handled by the language internally at the C level. Any trie library you use will go through subroutine/method lookups, which will be substantially slower. If we were rewritting Perl from scratch, maybe you could argue for replacing hashes with tries. But if you were rewritting Perl from scratch, that’s probably pretty low on the list of changes.

But never mind that. Sorted returns and prefix matching are still pretty cool if you need that sort of thing.

Tree::Trie looks like a good place to start experimenting with tries. To get behavior equivalent to hashes, you need to use the methods marked *_data. The other methods only store keys without a value.

Some example code

my $trie = Tree::Trie->new;
$trie->add_data( foo => 1 );
$trie->add_data( bar => 2 );
$trie->add_data( qux => 3 );
$trie->add_data( quuux => 4 );

say $trie->lookup_data( 'bar' ); # Prints "2"

my @qu  = $trie->lookup( 'qu' );
# Prints:
# qux: 3
# quux: 4
say "$_: " . $trie->lookup_data( $_ ) for @qu;

$trie->delete_data( 'qu' ); # Deletes 'qux' AND 'quux'

That’s all I have to say on tries. If you have suggestions for future underappreciated Perl modules, feel free to leave a comment below.

Perl Modules: AnyEvent::ReadLine::Gnu

2013-09-06

REPLs (Read-Eval–Print Loop) can be handy little things. In UAV::Pilot, the uav shell takes arbitrary Perl expressions and eval()‘s them.

Before integrating with AnyEvent, handling the prompt was done by Term::ReadLine::Gnu. When AnyEvent was integrated, I wanted the shell to use AnyEvent’s non-blocking I/O, so it was migrated to AnyEvent::ReadLine::Gnu.

This also handles command history. Hit the ‘Up’ arrow to get your previous command. No code is necessary; AnyEvent::ReadLine::Gnu does it for you.

ReadLine also has options for tab-completion. I would like to add this to the uav shell eventually.

Using the AnyEvent version is quite simple. You pass a callback that takes input. In the uav callback, we only run the code when it ends with a semicolon (ignoring trailing whitespace). If it doesn’t, we save it in a buffer and wait for more input.

Here’s how this is implemented in UAV::Pilot:

    my $readline; $readline = AnyEvent::ReadLine::Gnu->new(
        prompt => 'uav> ',
        on_line => sub {
            my ($line) = @_;
            add_cmd( $line );
            if( $line =~ /; \s* \z/x ) {
                my $cmd = full_cmd;
                $readline->hide;
                my $do_continue = run_cmd( $cmd, $repl );
                $readline->show;
 
                $cv->send( $do_continue ) unless $do_continue;
            }
        },
    );

The add_cmd() method adds the input to the buffer. If that did end with a semicolon, then we call full_cmd() to get back the text of the code. It also clears the buffer. run_cmd() then eval()‘s the code. If we’re meant to exit the program, it returns false, which we handle with the $cv->send.

The $readline->hide and $readline->show calls stop ReadLine from outputting the prompt when we might have other output going.

UAV Basics -- Legality

2013-09-05

IANAL. I don’t even play one on TV. None of this is legal advice, and it only covers US regulations.

That said, FAA regulations on UAVs are pretty simple. UAVs are basically model aircraft, and the rules are:

• Below 400 feet
• Away from populated areas and full sized aircraft
• Not for commercial use

That last one is what’s giving everyone fits right now. As a private citizen, your options for flying UAVs commercially are limited. There is a process to get either an experimental aircraft certificate, or a wavier certificate. Experimental certificates are only granted for “R&D, market survey and crew training”, while waivers are usually only granted to government agencies. That includes local government agencies, so you could feasibly get a contract to survey land for a local town.

Some people have tried to skirt around things by taking aerial photographs on a hobbyist basis, but then claiming they charge a client for post-processing. I doubt the FAA or courts will agree with this reasoning; they’re really just hoping that they’re too small for the FAA to bother.

Short of government contracts, commercial use of UAVs is limited to selling them for now. The FAA is set to introduce new rules for commercial UAVs in 2015. Mark your calendars.

UAVs and FOSS -- AR.Drone

2013-09-04

This is the first in a series of articles about the state of FOSS software in terms of UAVs. We start with the place where I have the most experience, the Parrot AR.Drone.

On the client side, Parrot has released a complete SDK for controlling the AR.Drone. It includes support for the control protocol, the navigation protocol, and the video streams (which is handled by ffmpeg).

However, many people choose to make a clean implementation based on the SDK docs. This includes my own UAV::Pilot, and also NodeCopter, an implementation for Node.js. Both of these are under a BSD-style license. The parts of UAV::Pilot that interface to ffmpeg are LGPL.

Control is done over WiFi. It will create its own ad-hoc network by default. With some trickery, you can connect it to an open access point, though it doesn’t seem to support WPA authentication.

The on-board electronics for the AR.Drone has a Linux system with Busybox, which you can telnet into. This seems to be mostly useful for debugging the commands sent over the network, or configuring it to connect to an open access point. Hacking it to control external devices via USB seems like it should be possible, though I haven’t been able to find anybody who actually accomplished this. Just a lot of people talking about it. C’est la vie.

Version 2.0 of the AR.Drone includes front and bottom cameras, which can stream 720p video. They’re on par with cheap webcam quality.

As I’ve complained about before the AR.Drone’s SDK doc is rather poorly documented. The control protocol is mostly fine, but there are a lot of missing details about the nav data and video protocols. The information you need is spread out on the dev fourms, and it just shouldn’t be that way. I’m also dealing with the multiconfig options, which requires getting the ACK bit off the nav data stream, which seems all backwards to me even if it was well-documented. The config should have been handled over a TCP stream, especially when multiconfig was implemented.

It is relatively cheap, though, at $300. A basic ArduPilot setup will be around $700 if you include the telemetry module and a cheap 6-channel radio. That setup wouldn’t even have a camera.

All things said, I think the AR.Drone is a good way to get started considering what’s out there right now. But it could definitely be improved.

Underappreciated Perl Modules: File::HomeDir

2013-09-03

Problem: your module needs to save a config file. Where should it go?

Obviously, the user’s homedir, but the exact conventions differ between platforms. On Unixy things, it’s usually a dot file. Windows has a more complex layout for User directories, which Microsoft seems to change with every new version.

Instead of guessing, ask File::HomeDir where it should go. UAV::Pilot needed this for the joystick config, so it does something like this:

use File::HomeDir;
use File::Spec;
my $dir = File::HomeDir->my_dist_config( 'UAV-Pilot', {
    create => 1,
});

my $file = File::Spec->catfile( $dir, 'sdl_joystick.yml' );

File::HomeDir also has functions for my_music, my_pictures, etc., and also for getting the homedir of another user. It should always Do the Right Thing on any platform you throw at it.

UAV Basics -- Types of UAVs

2013-09-02

This will be the first of a series of articles about the basics of UAVs. Today we start with the different types out there.

The first is your standard airplane model. This one is the Rhino UAV, which is a project intended to help anti-poaching efforts:

The design is similar to all the model airplanes that have been out there for years. The only real difference is that the on-board electronics can be made sophisticated enough to fly to a destination without any human input.

The other kind of flying UAV is the helicopter type, though the traditional helicopter doesn’t seem too popular to build. The multipod design, especially quadcopters, seem more widespread.

There were a number of historical attempts to build a multipod, but the single-rotor helicopter became preferred in general aviation, despite the problem of the torque on the blades inducing it to spin. The reason seems to be that slight differences in motor speed, weight balance, and propeller shape tend to make multipods unstable. The pilot has to make constant corrections for this, and it becomes too much of a mental load. Meanwhile, the helicopter’s torque problem was solved with a simple rear vertical propeller, so everybody just did that.

Now we have cheap microcontrollers, gyros, and accelerometers for automatic stabilization. That takes the load off the pilot, making this a viable design. Quadcopters have particularly grown in popularity of late.

One variation I’m interested in is this 3-armed, 6-propeller design from 3D Robotics:

The dual prop design lets it have high lifting capacity in a small package.

UAVs don’t just fly, though. They drive and swim, too. Google’s self-driving car is essentially a UAV. The ASV Roboat is an autonomous sailboat used for research into the endangered harbor porpoise in the Baltic Sea:

Most of what I’ll be working on is the flying variety, though.

Dynamic Perl Code Loading

2013-08-30

There’s a trick done by mod_perl for running old-style CGI scripts. These have to be loaded on-demand, but how do we load code into the parser at runtime?

Well, eval(STRING), of course. Really, there’s no magic to it beyond that. This often maligned feature is at the heart of not just mod_perl, but also pretty much any templating system that embeds Perl code inside. Isn’t that dangerous, you ask? Not really; you presumably trust the code coming from template files on your own server. It’s no more dangerous than downloading a random CPAN module and loading it up.

Generally, they don’t eval the straight code. They wrap it up inside a package and a subroutine, then call the sub. Something like:

my $loaded_code = ...;
my $full_code = <
# Sometime later
Known::Package::Namespace->run;

Things can get more sophisticated than this. Perhaps you expect to load up multiple code files, so you generate a predictable package name for each one (maybe based on the file name). Maybe the run() sub takes an argument, like $request for the Apache request object, which will then be available to the loaded code.

One problem with the above as written is that it screws up error messages for the filename and line number reporting. If you use the debugger, it’ll screw up it outputting the code you’re stepping through. This is where a trick with Perl comments comes in handy, where the line number and file in error messages can be set in a comment. It’ll work something like:

sub run
{
    # line 1 $filename
    $loaded_code
}

And all is well in the world. In the case of templating systems, you might want to keep track of the line number you’re getting the code from, and fill that into the line directive, too.

Underappreciated Perl Modules: File::ShareDir

2013-08-29

Problem: you have some kind of data that needs to be distributed with your Perl module. Where do you put it in a cross-platform way?

Solution #1: Put it in a giant datastructure inside some module. This ends up with a big .pm file that chews up memory.

Solution #2: Put it in a __DATA__ section. But you only get one of those per module, and binary data might get hairy.

Best solution: File::ShareDir.

If you’ve ever looked through your Perl module directory, you’ve no doubt seen a directory called ‘auto’. This was used for a few different autoloading systems, but there’s no reason you can’t use it for your own module.

When I added SDL navigation data output to UAV::Pilot, the text overlayed on the screen needed a specific font. SDLx::Text can take a path to a TrueType font file, but where do you put that file?

The answer is that you create a ‘share/‘ directory in your project and drop it in. The files there will be placed in your module’s ‘auto/‘ entry. You can then get the path to the file with:

use File::ShareDir 'dist_dir';
use File::Spec;

my $dir = dist_dir( 'UAV-Pilot' );
my $file = File::Spec::catfile( $dir, 'font.ttf' );

Thus providing a safe, cross-platform way of storing module files.

Musings on Hackable UAVs

2013-08-04

Programming the AR.Drone has been a mostly fun challenge, and occasionally a frustrating challenge. The nav data is particularly under-documented, and UAV::Pilot still suffers from a few video parsing issues, probably because the documentation doesn’t fully explain the PaVE headers. But I pushed through them, figured it all out, and now there’s a release that I would consider close to feature-complete.

I never intended to stop with just the AR.Drone. It was a cheap way to get started–cost about $300 rather than $500-700 for a some other types–but it’s ultimately a toy. I don’t have a problem with big-boy toys; in fact, I own quite a few of them. But it’s a bit limited.

More “serious” UAV platforms, such as Ardupilot, often use some kind of mission planner software that allows you to put in a path of GPS coordinates and do something at the waypoints (like take pictures). With a GPS attachment and the right software, this is technically possible with the AR.Drone, but not out of the box.

The AR.Drone also has decent but somewhat limited hacking potential. If you’re willing to void your warranty, you can set on-board scripts to connect to AP-mode WiFi, add cheaper high-capacity batteries, or use the USB port to run attached devices. But it’s ultimately a closed platform with all the limitations that implies.

I find some of the other autopilots out there just as frustrating, for a somewhat opposite reason. They allow you to do anything, but their starting point is more sophisticated and need some work to dial them back down. The Ardupilot hardware, for instance, needs a compass, GPS, barometer, and some other assorted electronics. Not all this stuff is necessary for all uses. If you’re flying lower than 20-50 feet or so, the barometer isn’t much use and is too inexact. An ultrasonic range finder would be better for that case.

It’s all FOSS, so I’m sure you can get it all to work one way or another, but it isn’t designed for it.

By way of analogy, for years before the iPad, Microsoft had tried pushing tablets by taking their desktop OS and scaling it down to a tablet. They were largely ignored. What Apple (and later, Google) showed was that the correct strategy was to take a smartphone OS and scale it up.

That’s similar to the strategy I’d like to try with UAVs. If you want a toy UAV like the AR.Drone, you should be able to put it together cheaply without a GPS or barometer or anything. But if you want to get more serious, you should be able to add all that stuff without much trouble.

The platform should allow you to alter every aspect of the design, allowing the frame to be fully 3D-printable. Some printable UAV designs are already out there, such as the PL1Q Vampire, though often under a non-commercial license, which doesn’t meet widely accepted definitions of FOSS.

My goal is to build a UAV platform with the following requirements:

• Complete design is under FOSS-compatible licenses, allowing modification for personal or commercial use. Licenses like BSD, Lesser GPL, or CC-BY[-SA] (but not CC-NC).
  • Software will probably be BSD, with CC-BY for hardware
• On-board systems controlled by cheap and easily available computing platforms, such as Raspberry Pi, Arduino, and/or ATtiny.
• Frame is fully 3D printable
• Wide choice in attaching hardware; GPS, barometer, cameras, nerf guns, etc.
• Wide choice in control methods; WiFi, XBee, cell phone towers, etc.
• Complete documentation on control, navigation data, and accessories

I respect the work that’s already gone into projects like Ardupilot, but they don’t seem well suited for toy UAVs. And there’s nothing particularly wrong with toy UAVs; they are bound to have some rather un-toy-like uses, and even if not, there’s nothing wrong with a few toys. This looks like an open niche among the FOSS autopilots, which I intend to fill.