How to use Boe-bot to perform maze-solving?

Jay2111

Hi, Andy,

I am a engineering student from Calpoly, SLO.
I am currently working on using a boe-bot for maze-solving. Currently, I have installed
a qti line-reader, and I have configured its basic movements(going straight, left, right turns, etc).
However, I am not quite sure if you know of some interesting ways for it to navigate around a maze. I have done some preliminary research on MicroMouseinfo.com regarding to maze-solving algorithm, but it seems that some sort of distance measurement is neededto navigate the maze(implementing flood-fill algorithm, modified flood-fill algorithm)?

So, does it means that I need to add some additional stuff onto my boe-bot? My on-board wiring spaces is getting smaller and smaller. In summary, my questions are the following:

1) Do you have some hints on maze-navigation using just boe-bot and the qti line-reader.
2) If not, what other things can I try to make maze-navigation possible.

Thanks for your help.

Jay

Andy Lindsay (Parallax)

Hello Jay,

If you are navigating a true micromouse maze, you can use the QTI line follower parts to read the top edge of the maze walls. For practice, electrical tape delimited courses will work well, but I recommend building the micromouse maze as soon as you can. It's important to test as much as possible in the real thing to get a better understanding of the various challenges of the actual course.

Consider using the Parallax Encoder Kit for measuring distance. This will allow your program to calculate how many cells you have traversed in the maze. Knowing this information will make it possible for your program to map the maze in your BASIC Stamp's EEPROM. Each cell has four possible openings. You can map these openings with binary values in a nibble variable. For example:

walls·· VAR· Nib

north···VAR· walls.bit3
east··· VAR· walls.bit2
south···VAR· walls.bit1
west··· VAR· walls.bit0

With this, you can store two cells in one EEPROM byte. For example, %01101001 indicates that the first cell has openings in the north and west walls, and the second cell has openings in its east and south walls. Since there are 256 cells in the micromouse maze, you can store all the cells in 128 EEPROM bytes. You will need another 16 bytes (256 bits) of bit flags to check off which cells your bot has already been to.

Storage and retrieval of this information will be implemented with READ and WRITE commands. You will also need to apply masks to examine either the lower or upper nibble of a given EEPROM byte. Likewise for the bit flags for each cell.

You can cordon off portions of EEPROM for storage like this

CellBitFlags DATA 0·· (16)
CellInfo···· DATA $FF (128)

These DATA directives write 0 in the first 16 bytes, and hex FF in the next 128 bytes. That's fine before a run, but a separate program should be used to retrieve and display the recorded values. This will involve DATA directives that do not pre-write to EEPROM.· For example, these DATA directives, only reserv the space, but they don't touch any of the values your program stored there:

CellBitFlags DATA (16)
CellInfo DATA (128)

You can use a conditional compiler directive to choose between DATA directives like this:

' {$STAMP BS2}
' {$PBASIC 2.5}

#DEFINE DebugMode = 1

#IF DebugMode = 0 #THEN
· CellBitFlags DATA 0 (16)
· CellInfo DATA $FF (128)
#ELSE
· CellBitFlags DATA (16)
· CellInfo DATA (128)
#ENDIF

When you take a look at the memory map, you'll see that this only takes a small portion of the BS2's program memory. You'll need the rest for navigation, analysis and decision making.

The BS2's program memory brings us to a thorny point. The guy at micromouse.info claims that Riverside's Boe-Bot based "Dirty Rat"·robot had trouble finding the center of the maze because of the size of its processor.· I think they were using a BS2sx.··That assertion is just plain wrong.· My understanding from discussions with a couple of the Riverside team members was that they got stuck on navigation and didn't have time to flesh out their maze analysis algorithms.

The other point to take from this is be careful about your project schedule. If you get stuck on navigating turns, you may not have enough time to flesh out your maze analysis code.

If you'd prefer not to hedge your bets, consider upgrading to a BS2e, pe, or px. They all have more memory, and the pe and px also execute code at higher speeds. The nice thing about the BS2e is that you won't have to change any of your code timing for PULSOUT, FREQOUT etc. Even so, you will have eight times the EEPROM memory for program and DATA storage plus 64 additional bytes of scratchpad ram. I think my personal choice for this would be the BS2pe because I don't see processor speed as being an issue. It's also got all the program memory and DATA storage you could possibly need, plus 128 bytes of extra scratchpad RAM. If processor speed really is an issue, the BS2px is second only to the BS2pe in terms of memory, and it's program execution is super fast. The drawback of the BS2px is it takes 55 mA of current, which will reduce battery life. Considering the servos combined take 200 mA, maybe that's not such a·big deal.

I would recommend examining the comparison charts for the various BASIC Stamps modules before making your final decision.

If you want to randomize decisions about which way to turn, PBASIC has a·RANDOM command.

That's all I've got time to write about for now. Developing and trouble shooting circuits and code to make it possible to successfully navigate and map the course will take some concerted effort and time, so I'm going to hold off on an answer about which algorithm to use. I'm not really sure off the top of my head, and will have to snoop around a bit before deciding on an answer.

Keep making posts to this thread to keep us updated on how it's going. If you run into design issues along the way, post them here too.

Good luck!

Andy

Post Edited (Andy Lindsay (Parallax)) : 7/25/2005 7:33:59 PM GMT

Paul Baker

Andy Lindsay (Parallax) said...

walls·· VAR· Nib

north···VAR· walls.bit3
east··· VAR· walls.bit2
south···VAR· walls.bit1
west··· VAR· walls.bit0

Ah this brings back fond memories of coding in DikuMUD, each room had·a structure such as this to indicate possible exits and which room number that exit led to. Point is, this is a highly efficent method to store data about a maze that only permits movement in cardinal directions. Please, noone reply on this subject because the thread will quickly go off topic. If you want to discuss MUDs, PM me, if there is significant interest I can start a new thread in the Sandbox.

pBASIC

You said you wanted to·do some sort of distance measurement··I Believe·I might have the program for you.



' {$STAMP BS2}
' Program Listing 1.3 - Distance Detection.bs2
· counter····· VAR····· Nib
· IR_outputs·· VAR····· Byte
· IR_freq····· VAR····· Word
· OUTPUT 7
· main:
··· IR_outputs = 0
' Load sensor outputs into l_IR_outputs and r_IR_outputs
··· ' using a for...next loop,and a lookup table, and bit
··· ' addressing.
··· FOR counter = 0 TO 4
····· LOOKUP counter,[noparse][[/noparse]37500,38250,39500,40500,41500], IR_freq
····· FREQOUT 7,1, IR_freq
····· IR_outputs.LOWBIT(counter) = ~IN8
··· NEXT
··· ' Display l_IR_outputs and r_IR_outputs in binary and ncd
··· ' format.
··· DEBUG HOME, "Readings from IR detector", CR
··· DEBUG "Binary IR_outputs: ", BIN5 IR_outputs, CR
··· DEBUG "Object is in zone: ",DEC5 NCD(IR_outputs)
· GOTO main


················································································ Chris

Jay2111

Dear Andy,

I am currently having a problem using the qti line-readers for maze-solving.

The codes:

Right: HIGH 5: PAUSE 1: qti.BIT0 = IN3: INPUT 5
CenterSecond: HIGH 6: PAUSE 1: qti.BIT1 = IN3: INPUT 6
Center: HIGH 7: PAUSE 1: qti.BIT2 = IN3: INPUT 7
Left: HIGH 8: PAUSE 1: qti.BIT3 = IN3: INPUT 8

controls my four line-readers.

However, my problem is that let say I have a "T" interstection. My robot start from left end of a "T" going straight by reading
"0110" on the line-reader, and it stops at the intersection reading "1110", it would turn right, and if you design the turn perfectly, the robot will again read "0110" and keep going straight. Okay, the problem is this. I don't want the robot to keep going straight after the turn. I want the robot to STOP after making turn at the intersection. How do I do it?

I have been stuck at this problem for a while, and I have thought about several ways to go about it. Can you tell me if I am heading in the right direction in solving the problem.

1st option: find out what are the codes are doing above. Is there a way to control their input rate. I am sure I don't want
them to keep reading "0110" after turning the intersection when I want my robot to stop at an intersection.

2nd option: Instead of using line-readers to make the turn, use the encoder kit provided by parallax.

3rd option: Just use Infrared readers instead, but really, this is the last option I want to take, because I would have to scrap my
current project, and start from scratch again.

Really, I am trying to navigate the maze by pre-programming, but I would like to solve them separately by marking all paths on the maze as "segments" and all intersections as "nodes".

I look forward to hear from you, Thank you for your help.

Jay

Cal Poly Electrical Engineering Student.

Andy Lindsay (Parallax)

Hi Jay,

My thinking is that your robot needs to test to find out if it is at an L or a T intersection and update its map of the course accordingly.

SELECT qti
··CASE %0110
··· GOSUB Forward
· CASE %0111
··· GOSUB Test_L_Vs_T
··· GOSUB Update_Memory_Map
··· GOSUB Execute_Turn
··· GOSUB Back_On_Track
··· GOSUB Stop_The_Robot
· CASE %1110
···· .
···· .
···· .

You may not want or need the resolution the encoder gives you. It might be better to mount a pair of QTI modules behind the wheels, and then past a circle inside the wheels that's half black and half white. Or, at least separate it into some number of stripes that gives you a good indication of how many logic transitions you need to get to the next cell.

Does this answer the question?

Andy