RF/ultrasonic relative location sensing that would actually work.
Idea: two or more active chirp boards and a homebase. All boards have both an rf and an ultrasonic transceiver, and a unique ID. Homebase sends an rf signal "Board 1 chirp." Upon receipt of signal, Board 1 chirps, all others start timer, listen, and wait for Board 1's chirp to arrive. When it does, they stop timer, and send time-of-flight to Homebase. This gives you distance from Board 1 to all other boards. Repeat for Board 2...Board N, and get a full distance matrix, which Homebase can solve for relative location of each using least-squares or whatever they use for GPS these days.
Echoes are not a problem (as in ultrasonic distance sensing) because you are only interested in the first-arriving acoustic signal (echoes will come later). Zigbee may be problematic as latency is unknown... but could be experimentally determined; if it's consistent or at least predictable it would work, or could use cheap 900 mHz transceivers.
I sat down and solved the 2-D position from distance. (This turns out to actually be harder than the GPS problem because satellites know where they are, and the only unknowns are the single GPS receiver position and clock skew.) For three points you can do it closed-form, but note that that's six unknowns (x and y for three points A, B, C) from only three distances d(AB), d(AC), and d(BC). So you have to assume a fixed translation (say, Ax = Ay= 0)) and rotation (say, Bx = 0) This makes an argument for a fixed base station, because otherwise we can't detect when the whole fleet moves in the same direction. And we probably want another fixed base station to keep the fleet rotation from drifting. But that could be as simple as just two sensor boards on poles (which would be as robust -- or not -- as robot-mounted ones).
Re acoustics, as I understand it ultrasonic transceivers have a pretty narrow resonance around 40 kHz and all you do is hit them with a approx 10-15 VRMS square wave at that frequency. (I'm not sure how well you can modulate them -- at least the cheap ones -- because they will ring for a ms or two.) I've heard of people using max232s to get a nice beefy drive voltage on the cheap. On the receiver end my first hack would be to XOR the received signal down to baseband from the local driver frequency rather than using fancy bandpass analog filters or DSP. It will be worth checking out some ultrasonic distance sensor schematics and see what we can steal, um, what inspires us.
The nRF24L01 Single Chip 2.4GHz Transceiver is something to look at as an alternative to Zigbee
There's no obvious reason this wouldn't work. I've seen a working proof-of-concept with Olivetti research "bats" location sensing (fixed recievers, mobile transmitter).
From the HBR list comes this: http://www.convict.lu/htm/rob/ir_us.htm
And also this guy's masters thesis. (This confirms my hunch that the order-of-gnarl of this project is roughly MIT Master's level.)