Using a different method than what you propose, achieving navigation by "bots" at the size you specify does meet your fair game" criteria - but it's almost certainly beyond what is reasonable now.
Note that the scale of your 'bot' is in the same order of size as a current IC transistor cell - so you are going to need some other technology changes along the way.
I am in the process of trying to explain to people how you can telemeter the position and orientation in space of say a cylinder 2mm in diameter and say 4mm long. That's 2000 micron x 4000 micron, so "rather larger" than what you have in mind but small by most modern standards. The system used should scale to your bots level, provided that you can fabricate to dimensions substantially smaller again - say 100 Angstrom or less wires :-).
A method that does work is to use orthogonal coils (2 or 3) and linearly varying 3D external fields to allow the 'bots' to determine their position. Fields are set up using various methods similar to those used for NMR (Helmhotz coils and other). This is not at all hard to do compared to the rest of the problem.
Good results are currently reported using coils of under 2mm diameter and the principle can be extended downwards in size. Also, systems like GMR. AMR and other can be used for field angle measurement. It is possible to determine position and orientation from such a system.
I have obtained several papers which I can provide references to which show what has been done recently. I can provide references in due course if of interest - rushing off elsewhere at present.
Note that powering is an issue at very small scales. Work out how much energy you can store electrochemically! Remote power transfer becomes attractive and is (probably) not too hard in comparison to all the other issues involved.
Some people are using magnets and gradient field methods to actually navigate devices internally in people ! :-).
One paper that I referred to is described below.
Their sensor coils are 2mm diameter.
They monitor the real time flight of a blow-fly with 1 kHz update or orientation and position in space. They are achieving 1mm positional accuracy, but that depends on aspects which will be makedly different in a much smaller system.
Their system has the massive advantage of having a "tether' - the wires are so light that the blowfly can free fly while trailing an "umbilical" cord. Your nanobots and my sensors do not have this luxury.
J Neurosci Methods. 1998 Sep 1;83(2):125-31.
Using miniature sensor coils for simultaneous measurement of orientation and position of small, fast-moving animals.
Schilstra C, van Hateren JH. Department of Neurobiophysics, University of Groningen, The Netherlands.
Abstract
A system is described that measures, with a sampling frequency of 1 kHz, the orientation and position of a blowfly (Calliphora vicina) flying in a volume of 0.4 x 0.4 x 0.4 m3. Orientation is measured with a typical accuracy of 0.5 degrees, and position with a typical accuracy of 1 mm.
This is accomplished by producing a time-varying magnetic field with three orthogonal pairs of field coils, driven sinusoidally at frequencies of 50, 68, and 86 kHz, respectively. Each pair induces a voltage at the corresponding frequency in each of three miniature orthogonal sensor coils mounted on the animal.
The sensor coils are connected via thin (12-microm) wires to a set of nine lock-in amplifiers, each locking to one of the three field frequencies. Two of the pairs of field coils produce approximately homogeneous magnetic fields, which are necessary for reconstructing the orientation of the animal. The third pair produces a gradient field, which is necessary for reconstructing the position of the animal.
Both sensor coils and leads are light enough (0.8-1.6 mg for three sensor coils of 40-80 windings, and 6.7 mg/m for the leads, causing a maximal load of approximately 5.7 mg) not to hinder normal flight of the animal (typical weight 80 mg). In general, the system can be used for high-speed recordings of head, eye or limb movements, where a wire connection is possible, but the mechanical load on the moving parts needs to be very small.
The abstract is available at a number of places including here and here. Cost of viewing the paper is about $US30 if you do not have a relevant academic or other access. I can comment on the content but NOT send you a copy. Contact me privately if you wish. See my profile page for my email address.
This is a harder problem than I think you realize. The basic Loc8tor system works primarily by virtue of a directional antenna in the receiver, and it doesn't really give you the position of the tag directly, it just indicates what direction it is from the location of the receiver, along with a very rough estimate of how far away it might be.
If you want to create a mesh of automatic receivers, each of these receivers will need to do direction finding, either mechanically by physically spinning its antenna in a circle, or by using multiple antennas and electrically "spinning" the reception pattern. Neither method is going to be simple to implement or particularly low-power.
It is only by combining direction information from two or more receivers (plus knowing exactly where these receivers themselves are located) will you be able to derive an absolute position for the tag.
Best Answer
It seems like there should be an easy answer to this problem, but it is actually hard to find a system that will give 0.5 meter positioning accuracy and be cheap.
GPS RTK
If you don't care about cheap, then you could use a GPS RTK system to get ~10cm level accuracy with a single base station. Here is the cheapest set I've ever seen...
http://store.swiftnav.com/
It includes the base and a single rover for about $1000. I got one from the Kickstarter campaign and was never able to get it working well enough to actually use. Presumably by now tit should work out of the box for that price.
GPS SBAS
Depending on where you live, you might be able to use a SBAS module on the rover to get sub-meter accuracy. Here is an example of a module that costs about $100...
http://www.u-blox.com/en/gps-modules/neo-6p/neo-7p.html
This would take a lot of time to get working and I have not seen a cheap work-out-of-the-box SBAS solution.
Atmel AT86RF233 chip
This is an Atmel chip that is cheap ($3 in quantity and $5 for 1) that has built-in distance measurement functionality. In theory, you should be able to built a board for $10 that could be either a base or a rover. With enough bases, you should in theory be able to cover any size field and get sub-meter accuracy.
Unfortunately, in practice the outdoor results are not great. It would take a lot of work to get a system capable of generating a reliable fix with 0.5 meter accuracy with these chips. You can read some of my test results here...
http://wp.josh.com/2013/05/23/first-look-at-distance-measurement-using-the-at86rf233-chip/
New DecaWave ScenSor DWM1000 Module
This is a very exciting development that only became available in the past few months. Here is the product page on DigiKey...
http://www.digikey.com/en/product-highlight/d/decawave/scensor-dwm1000-module
These modules cost $32 each for 1, or $20 each for 1,500. They claim to be able to range with an accuracy of 10cm over 300 meters indoors. No claims are made for outdoors, but hopefully results would at least be within 50% of the indoor performance, which would make this a fantastic option.
There is currently a KickStarter to sell an Arduino shield based on this module...
https://www.kickstarter.com/projects/pozyx/pozyx-accurate-indoor-positioning-for-arduino
...but for that leadtime and price I think it would make sense to just buy the modules and figure out how to connect them yourself. I've read the datasheets and it looks pretty straightforward - you should be able to power the module and connect to any SPI capable computer (Arduino & RaspPi included) with $1 in parts and a little soldering.
I hopefully will be getting some of these soon and will report back on how they work outdoors in practice. I have high hopes that they would be perfect for your application.
Optical Glyph Recognition
I've never done this, but I think in theory you could put QR codes all around so that there was at least one visible and decode-able from anyplace inside the range.
Then you could use a Raspberry Pi camera to look around and something like OpenCV to locate the visible QR codes in the environment. Once you knew which QR code you were looking at and where is was relative to your field of view, you could computer your location.
This option is especially nice because there there is no RF involved and the QR codes are essentially free (cost of a piece of paper and maybe some lamination).
Spinning Lasers!
I've never actually done this, but in theory you you should be able to get a cheap spinning construction laser and mount it on your rover. Then you'd set up a bunch of static laser detectors around your field. Each detector would have a very cheap radio to beep back to the rover whenever it saw the laser swipe past. By listening to the delay between the beeps, you could very accurately determine both your position and heading.
There was a company selling a system like this (but expensive) about 15 years ago, but they went out of business.
Alternately you could use retro reflectors around the field and have a single detector on the the rover. This would be cheaper and not need any RF, but would likely have shorter range and more complex maths.