Well, here I go again. Hexapods are expensive!! I took a detour and looked into these things called MicroMice. At first, it didn't seem all that great. The robot runs around a maze and tries to find the center. Wee! Blindly follow a wall and always go right, right? Wrong! These suckers actually solve the maze using an heuristic algorithm. The Bellman algorithm is apparently the standard. Then, they improved on it with the modified "flood-fill" approach. Then, they got even smarter. The mice continue exploring after finding the center. They calculate the best route over several options. Then, they improved more. The mice calculate diagonal as well as strictly vertical/horizontal attacks. The Japanese competitions average around 15 seconds for a solve. Wow. This is way out of my league. But I do like the idea of having a little uMcu solve a maze. I whipped up a prototype in Python.
What I came up with is a bit daunting. I will need two arrays and a stack. The arrays need to be 256 bytes long. The stack needs to be at least 200 bytes. The maze I test solved ( from 1993 ) needed a stack of 148. It's pretty memory intensive stuff with a lot of recursion. I think I'll need to back-solve the recursion to just do straight loops. Ugh! It makes my head hurt to do that. I worked hard in college to get recursion. I never did get the hang of implementing the same solution in straight loops. Once I figured out how to do it with recursion, it always looked so neat and simple.
The short term plan is just to get the chips to solve the maze. Steps: First, I need some new chips. I'm sticking with the Ram deficient Pics. I ordered some 16F876 chips and some 32K I2C Ram chips. These will help alleviate the memory issues. I will get I2C working between two Pics. Then, I'll get it working with the Ram chip. Then, I think I will simulate movement in the maze from a PC over USART. I'll let the mouse solve the maze. It will stream it's arrays back to the PC ( walls located and the value of each tile ).. I'll need to write a program to crunch this stream and generate the maze. My simulator will help with that.
The actual robot to solve a maze is pretty complex. The motors/drivers must be able to know exactly how far they have traveled. They must be able to turn on a pin head. They can't be thrown off by rough terrain or miss-alignment. The two choices here are stepper motors ( slow and new programming ) or DC motors with encoders. I don't like the idea of encoders. Too many interrupts that can mess with other time-sensitive operations. Steppers, on the other hand are slow, expensive, and I can't seem to find good, cheap drivers.
For sensors, most seem to use line following type IR sensors. I'm thinking that three Sharp IR sensors might do the trick. I'll mount them fixed front, left, and right. That will only tie up three pins.
It looks like the mouse wants either 2 or 3 controllers. One will definitely be assigned to maze solving. Another will handle motor control/movement. The sensors could be handled by either of these chips or a third chip. We'll see.
I honestly don't know if I'll ever actually build this 'bot. I'm sure whatever I could cobble together on limited funds wouldn't be much. It'd be cool if it could just solve the maze, whatever the time.
No comments:
Post a Comment