In Which I Rant About Monopoly

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.

UAV/FOSS — ArduPilot

ArduPilot is a FOSS autopilot based around Arduino. It has different firmware builds to support helicopters, multicopters, planes, cars, and boats.

Since I’ve been mostly focusing on multicopters, I’ll stick with that. A basic, fully assembled quadcopter kit will run you about $600. This does not include a telemetry module for controlling from a computer, or an RC radio for controlling manually. The US-band telemetry module will run another $85. A cheap 2.4GHz RC radio can go for $50-75, though if you’re serious, you’ll probably want to run at least $150-250. Then there’s the battery, which goes for about $70.

That also doesn’t come with on-board video, which is another $190, and uses a secondary radio on 5.8GHz. The standard OSD module sold on 3D Robotics does not have HD resolution.

If you’re looking for something to play around with, the AR.Drone will cost about a third the price.

I don’t mean to be all negative about the ArduPilot. Clearly, ArduPilot does something much more serious than the AR.Drone. This is a platform you can hack. Change out motors, platforms, hexcopters, octocopters, camera gimbals, everything. It’s also designed with a GPS module that can be used to instruct the UAV to fly to a spot and fly back.

ArduPilot has a documented control protocol. At least, I think that doc is still relevant. The wiki page there says they’ve moved, but I couldn’t find anything more up to date on the protocol description. In any case, I’d love to implement this in UAV::Pilot someday.

The impression I’ve been getting is that if you just want to mess around (nothing wrong with that), buy the AR.Drone. If you want to get serious, buy the ArduPilot. Somehow, though, I think there should be a platform that starts as cheap as the AR.Drone but lets you work your way up.

Underappreciated Perl Modules–Tree::Trie

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

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

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:

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

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

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

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:

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

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:

Rhino UAV

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.

CycloneCloseup1

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:

Tri Copter

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:

ASV Roboat

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

Dynamic Perl Code Loading

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:

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:

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.