Absolute positioning hardware and software

The machines we build here are mostly based on dead-reckoning: We start at a known position, and then keep track of how far we travel in each direction. This works great, until a stepper misses a step, and then we never recover. I've been thinking about how to close the control loop, give our controllers information on the absolute position of our robots. I plan to develop just such a system, here.

I'm planning to use a class of sequences called deBruijn sequences to make 2-meter long barcodes that will give a position accurate to about 0.1mm, if I can manage it. A 2-window deBruijn sequence is a 5 bit sequence in which any possible 2 bit subset occurs exactly once. Eg: 00110. Ok, so that's a pretty trivial example, but with planning, you can construct much larger sequences with much larger windows. So my goal is to create a sequence about 30,000 bits long that is a 15-window deBruijn. If I can create a barcode 2 meters long with the lines 0.1mm wide, I could make a barcode reader that can only read 15 bits at a time, and then calculate the absolute position within that 2 meters.

This is totally a work in progress, but there's 4 components to be designed and built:
1) software to generate long deBruijn sequences. Actually, this is mostly done GitHub - emteeoh/deBruijn-Sequences: This is my fiddling attempts to implement the deBruijn decoder described in Mitchell et al, A method for construction decodable deBruijn sequences, 1996. Lots of extra bits in that repo, so I'll clean it up as I go.
2) software to calculate position from a 15-bit sample. This is called "decoding" and its a work in progress. I have papers that describe the algorithm, I just need to translate that into *functioning* code.
3) Hardware to output the barcode. My first attempt will be to mark up a roll of masking tape. I have ideas for other media: Steel, aluminum, vinyl, cellulose. I think being able to buy V-Slot with the barcodes etched into it would be kinda amazing.
4) hardware to read and decode the position. I beleive this will amount to a diode as a light source, a photodiode to read the barcode, and a small microcontroller to generate a 15-bit position number that it outputs over some kind of serial link as often as possible. A few hundred times a second should be possible.


---
I thought I'd throw in a less trivial example. Consider the sequence
00000100110110101011100101000011001111101001000101100011101111.
Choose any sequence of 6 bits, and that sequence will be in one unique spot on the sequence above. Go on, try it!
Up on the github link, I have sequences for 2,3,4,6,8,12,16 and 24-bit windows. Generating the 24bit sequence takes about 5 seconds on my laptop, but really, it only *needs* to be done once, and never more. 24-bits is 1.5km at a 0.1mm resolution. I think it is WAY beyond what we need. I just kinda did it because I could. I ran out of RAM when I tried to go higher, too.

The decoder is kinda sorta written, but not debugged. Also, there's some equations to solve that I have brute-forced. For the 16-bit window, it could take something like 65000 iterations to solve them. I'm *CERTAIN* there are better ways to solve this, but right now I'm just trying to get it to *WORK*.

November 25th, 2017

It’s been a little while since I updated, but I haven’t been idle. Last night, I tested decoding a 6-window deBruijn and it works! The code is all over the place messy, and I need to write some docs, but progress! This weekend, I plan to test 8-window decodes, make sure it recurses correctly. If it does, 16-window should be trivial. I still don’t have decoding for non-trivial odd-windows, but 16 bits is more than adequate for me.
Incidentally, somewhere in there I rewrote the generators, and they use way less memory and run faster. I have no idea how big a sequence I can generate, but it’s at least anything up to 24, and it happens in a blink of the eye, so I can probably go much higher. It’s far beyond what we need, but if the hobby is worth doing, it’s worth overdoing.

Next, I have pieces of a barcode making machine. I went to the dollar store and got two tape guns. 3 bucks each, and now I have reels that tape spools fit on, with spring loaded tensioning. I need to order a much weaker laser. My 10W would be tough to modulate down to “etch, don’t cut the masking tape”. Here’s a kinda almost mock-up:

November 26th, 2017
So I got decoding for D8 and D16 working! I could spend a few minutes working out S' and T and trying out D32 (and beyond), but I don't think we'll need it...
I've attached a span-16 sequence for your enjoyment. The README on github is reasonably up to date, too.

December 24th, 2017
I did some experiments with a USB microscope today. At 100x magnification, it was giving me about 100 pixels per mm. I figure I need 70 per mm to do a decent decode... So that's good.
Looking around on banggood, I found several endoscopes for about 10 bucks. They come with very long USB cables (up to 10m!) . Gonna try those out as soon as they arrive.

January 8th, 2018
Today, the endoscopes arrived today. They're nearly perfect. they've got crazy long USB leads, and the camera end is only 8mm wide and is threaded, so mounting would be easy... The only problem is focus. they have a fairly wide angle lens with about a 5mm focal distance, but it's really not enough magnification. That was disappointing, but later in the evening, we had an idea: acrylic light pipes! a smooth piece of acrylic with a few rough spots is an easy way to make light pipes. We had some 1/4" acrylic rod, put a light at the end, and scribed a line into it, and then took photos with the microscope and the endoscope. Wow! This is all hand-held tools, no polish whatsoever...
Also, on youtube, I found a number of videos of people using a hard-drive motor as a rotational encoder... I have an idea about using that, combined with 2 H-bridges, to make a reel-to-reel tape marker that can run in either direction... Assuming I bother building it.

1st photo: acrylic light from far end, no ambient lights, microscope.


2nd photo: no ambient light, acrylic lit from far end, endoscope. The light is adjusted differently, and you can clearly see the acrylic acting as a light pipe in general, but the scribed line is much brighter.


3rd photo: ambient light, acrylic lit from near end, microscope. It's still pretty clear.


4th photo: this is the same conditions as the 3rd photo, but it's a line scribed in the aluminium.


5th photo. ambient light, acrylic lit at the near end, endoscope, held a bit further away. the dark black line is the line scribed in the aluminium, and the single bright line in the approximate centre of the image is the line scribed in the acrylic.