Ok, newest maze solver simulator. I added an exploring routing that does up to 256 cells of exploring before using lowest value routines to get to its current target. If the mouse explores on the way to the target and back for maze2, it uncovers enough of the maze to solve it well on the speed run. It is still possible for the mouse to get stuck in a sequence of cells that are adjacent to accessible, unexplored cells when it is not in explore mode. I need to look into a "back track" routine that will handle this. In the meantime, here is the updated simulator:
Maze Sim With Explore
Maze File 2
I need to develop a "speed run" routine that doesn't flood, explore, etc. On press of a button, it would compute a single, shortest know cell path to the target and put that in a queue. It would then pull off turns from the queue ( only straight, right, and left ) to direct it to the target.
Tuesday, December 21, 2010
Sunday, December 19, 2010
Maze Solver - Not So Great...
Ok, so I solved one maze from 1993. It was a maze from a competition known to make hard mazes. I created another maze from a 2004 competition. It solved the maze. It back solved by a different route. It did its speed run on a totally new route and got stuck. I'm just starting to work this out. Here is the maze if you want to try it out:
Example Maze 2
On the other hand, it does solve this maze from 2002 that I recreated. It looks like I run into problems on two fronts. First, if the first run and back solve don't reveal enough of the maze. Second, if a run hits an unexplored region and the only open spaces available have cell values greater than the current cell. I need to solve the "stuck" problem for sure. I will also want to add more "exploration" to the back solve phase.
Here is the other maze I was able to solve successfully ( if not optimally; I haven't checked ):
Example Maze 3
Example Maze 2
On the other hand, it does solve this maze from 2002 that I recreated. It looks like I run into problems on two fronts. First, if the first run and back solve don't reveal enough of the maze. Second, if a run hits an unexplored region and the only open spaces available have cell values greater than the current cell. I need to solve the "stuck" problem for sure. I will also want to add more "exploration" to the back solve phase.
Here is the other maze I was able to solve successfully ( if not optimally; I haven't checked ):
Example Maze 3
More Maze Simulation
Okay, I made a slew of changes to the maze/mouse simulator. The key to backsolving the maze from goal to start is to reflood the maze, using the start as the target. I modified the flood method to take a target flag ( start or goal ) and a starting queue list ( either the start index or the goal indices ). The program moves the mouse to the goal. It then lets you back solve to the start. It then lets you do a "speed run", solving the maze with all the wall data it collected in the initial solve and backsolve. It was cool to see the mouse find a better back route than the initial solve route. Along the way, it tried a few unexplored areas. This led to the optimal 91 step route.
I changed the display code, too. The mouse is marked by the number 800. I have code in there to make the mouse marker red, using ascii escape codes. I commented these out, so everyone can run it ( and so it will display ok in the Eclipse console ). Uncomment them if you like. The maze file is unchanged. I put it here, so no one has to go hunt for it. Here is the new code:
Full Mouse Maze Simulator
Sample Maze File
Oh, I didn't even think about this. Windows users may have trouble seeing this maze file cleanly. There are no carriage returns. Don't let your editor add them. It may cause problems when loading the maze. I can't remember if I allowed for this or not.
New shots:
I changed the display code, too. The mouse is marked by the number 800. I have code in there to make the mouse marker red, using ascii escape codes. I commented these out, so everyone can run it ( and so it will display ok in the Eclipse console ). Uncomment them if you like. The maze file is unchanged. I put it here, so no one has to go hunt for it. Here is the new code:
Full Mouse Maze Simulator
Sample Maze File
Oh, I didn't even think about this. Windows users may have trouble seeing this maze file cleanly. There are no carriage returns. Don't let your editor add them. It may cause problems when loading the maze. I can't remember if I allowed for this or not.
New shots:
First Solve - Note the value at start cell
Back Solve Initial Flood Results
End Back Solve - Note New Values/Better Path
Speed Run - Note Better Path
Saturday, December 18, 2010
More on the Maze
I redid the mouse/maze simulator. It is much faster. I also wrote it in a more procedural fashion. I am getting a better idea of what the code will look like on the Pic this way. I just swapped the files, so the old code is no longer available. Instead, the new code is here:
maze and mouse simulator
This program parses a character based maze file. Here is an example file:
Sample Maze File
It should be easy to create new mazes with this format. Remember the IEEE rules. The middle four tiles are the goal and must have at least one way to enter. The start tile is in the lower left ( south west ) corner. It must have only one open direction. This simulator is only geared to the competition 16 x 16 mazes.
Screenshots:
The next step for me is to figure out why gpsim isn't working with the I2C eeprom 256k bit module. I can do everything but acknowledge polling. It always times out. This is odd since the code runs on a real Pic.
maze and mouse simulator
This program parses a character based maze file. Here is an example file:
Sample Maze File
It should be easy to create new mazes with this format. Remember the IEEE rules. The middle four tiles are the goal and must have at least one way to enter. The start tile is in the lower left ( south west ) corner. It must have only one open direction. This simulator is only geared to the competition 16 x 16 mazes.
Screenshots:
The Maze in its Initial State
The Maze After First "Flood" - no walls known
The Solved Maze - some unexplored cells
The next step for me is to figure out why gpsim isn't working with the I2C eeprom 256k bit module. I can do everything but acknowledge polling. It always times out. This is odd since the code runs on a real Pic.
Thursday, December 16, 2010
Some Code - Bootloader, I2C, Maze Solving (virtual)
Ok, time for some code updates.
First up is the bootloader. I rewrote my bootloader to accomodate my 16F877 and 16F876a chips. Unfortunately, this meant the USART speed went down to 2400. I didn't really notice much difference. One thing I did put in my bootloader, a true erase sequence. I made sure I wrote patch space ( 0x3FFF ) to every block from address 0x004 to the start of the bootloader code. Yes, I know that the '877 and '876a do an erase before write, but what about old code that might sit in between your new code? I opted for the safe route and made sure the space was clean. It adds about 30 seconds to the '877's program time. It adds about 10 seconds to the '876a. I can live with it. If you can't, just don't call the erase sequence.
You can download the assembly code for the 16F876a here.
The adjusted Python code is here.
Note that the command line looks something like this now:
icsp.py /dev/ttyS0 16f876a 2400 /path/to/hex/file.hex -d
for program name, serial port, device type, baud rate, path to hex file, and -d debug switch.
Next up is the test code I used to get the 32k eeprom working over I2C. This is pretty much taken whole cloth from application note AN976 from Microchip.
Assembly code for I2C master mode with 32k eeprom.
Last up is some test code I wrote. It started as just a quick way to generate a graphical maze like those used for micromouse competitions. I then patched in some maze-solving simulation. It needs a total rewrite, but I still think it's cool and useful.
Here is the maze code.
And here is a screenshot of maze after solving:
That's it for now.
First up is the bootloader. I rewrote my bootloader to accomodate my 16F877 and 16F876a chips. Unfortunately, this meant the USART speed went down to 2400. I didn't really notice much difference. One thing I did put in my bootloader, a true erase sequence. I made sure I wrote patch space ( 0x3FFF ) to every block from address 0x004 to the start of the bootloader code. Yes, I know that the '877 and '876a do an erase before write, but what about old code that might sit in between your new code? I opted for the safe route and made sure the space was clean. It adds about 30 seconds to the '877's program time. It adds about 10 seconds to the '876a. I can live with it. If you can't, just don't call the erase sequence.
You can download the assembly code for the 16F876a here.
The adjusted Python code is here.
Note that the command line looks something like this now:
icsp.py /dev/ttyS0 16f876a 2400 /path/to/hex/file.hex -d
for program name, serial port, device type, baud rate, path to hex file, and -d debug switch.
Next up is the test code I used to get the 32k eeprom working over I2C. This is pretty much taken whole cloth from application note AN976 from Microchip.
Assembly code for I2C master mode with 32k eeprom.
Last up is some test code I wrote. It started as just a quick way to generate a graphical maze like those used for micromouse competitions. I then patched in some maze-solving simulation. It needs a total rewrite, but I still think it's cool and useful.
Here is the maze code.
And here is a screenshot of maze after solving:
That's it for now.
I2C Working
Here's what we have so far. I got my bootloader working on the 16F876a chips on the first try. I took the sample code from application note AN976 and got the uCU working with the 32k eeprom. The next step is to start writing the maze solving code on the Pic. I'll have plenty of room now that the eeprom chip is working. I think the cell values want to live on the Pic's built in eeprom. That way, when it is time to run the maze, I won't need to access the eeprom chip. I'll store the wall values and a flags ( visited before, destination cell, start cell ) for each cell on the first 256 bytes of the eeprom. The rest of it can be stack space. I'll still need a counter word to guard against stack overflow. Most operations other than init will be single byte reads/writes.
I'll be able to compute "neighbors" by +1 for East, -1 for West, +16 for North, and -16 for South. If the boundaries cross, it won't be a problem because the walls will let me know not to bother with them. The initial load of the arrays will pre-fill the outer walls of the maze.
I'll need to stay aware of what operation I'm doing. If I try to read or write from the USART, I'll need to make sure and disable the I2C operation first. Otherwise, I run the risk of errors.
Order of operations:
1. take bearings ( walls )
2. partial flood fill ( update values )
3. determine next move
4. virtual move
5. repeat until destination.
This will be a fun first exercise!
I'll be able to compute "neighbors" by +1 for East, -1 for West, +16 for North, and -16 for South. If the boundaries cross, it won't be a problem because the walls will let me know not to bother with them. The initial load of the arrays will pre-fill the outer walls of the maze.
I'll need to stay aware of what operation I'm doing. If I try to read or write from the USART, I'll need to make sure and disable the I2C operation first. Otherwise, I run the risk of errors.
Order of operations:
1. take bearings ( walls )
2. partial flood fill ( update values )
3. determine next move
4. virtual move
5. repeat until destination.
This will be a fun first exercise!
Friday, December 10, 2010
Detour...Again... MicroMouse!
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.
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.
Subscribe to:
Posts (Atom)