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: 0011. 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
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:
Absolute positioning hardware and software
Absolute linear positioning using deBruijn sequences.
- Build License:
- CC - Attribution - CC BY