Q&A: would u help me with the algorithm of maze robots?

Category : Safety Security
Q&A: would u help me with the algorithm of maze robots?by Roxy-Publishingon.Q&A: would u help me with the algorithm of maze robots?Question by petlover_wspa: would u help me with the algorithm of maze robots? I have robotic compitition next month could u help me with the algorithm of maze robots? Best answer: Answer by maxfr8MAZE NAVIGATION ALGORITHM Part 1 A guaranteed way to to solve a maze is to stick to a wall and always try […]

Question by petlover_wspa: would u help me with the algorithm of maze robots?
I have robotic compitition next month
could u help me with the algorithm of maze robots?

Best answer:

Answer by maxfr8
MAZE NAVIGATION ALGORITHM

Part 1

A guaranteed way to to solve a maze is to stick to a wall and always try to turn one direction or the other. It is not the most efficient way but it works all the time. This is how the Boe-Bot solves mazes. It hugs the left wall. IR sensors are mounted on the left and front sides of the robot. It begins the maze with a forward movement. After that it checks the left IR. If left is open, it turns left, moves forward, and repeats the process. If left is closed, the robot checks the front. If front is open, the robot moves forward and repeats the process. If the front is also closed, the robot turns right. It then checks the front IR sensor to determine if the new front is open. If its open, the robot moves forward and repeats the process. If it is closed, the robot again turns right and moves forward (the way it just came) and repeats the process. The flow chart summarizes all these instructions. Each time the robot makes a movement (forward, left, or right) it records a F,L, or R to a memory block in the EEPROM by using the WRITE function in Stamp BASIC. The variable ‘total_moves’ is incremented each time a movement is written.

The forward, left, and right subroutines use the PULSOUT function to move the servos. The pulsout variables for each servo (eg. 699, 879) are not set in stone. They have been changed numerous times and will probably need to be played with more. We determined them partly by experiment and largely by trial and error. The results of those experiments are also published in this site.

At the beginning of the forward subroutine is the BUTTON function. Each time through this subroutine, the programs checks to see if the button has been depressed. If it has not, the program continues. If the button has been pressed, control is moved to the find_RR subroutine.

Part 2

When the program enters part 2, the robot has already left the maze and the button has been pressed. It enters the find_RR subroutine and first pauses for 10 seconds so the robot can be repositioned at the starting point to re-do the maze. Find_RR is a superfluous piece of code that originated from poor planning. It reads in the movement from each memory block and the following memory block (blocks n and n+1) and compares them to each other. If it detects a R,R combo, it replaces the first R with an A. It then copies each movement into the previous one. For example, it would change a FFRRFLF to a FFAFLF. Each time it finds an RR combo and replaces it with an A, all the code following the last R must be adjusted. Therefore, the ‘total_moves’ variable is reduced by 1 each time RR is detected. The write_A subroutine handles that task. If no RR combo is found (they’ve all been switched) control moves to the find_A subroutine.

Find_A searches each memory block for the ‘A’ movement. If no ‘A’ is found, control moves to the done subroutine. However, this will only occur after all the ‘A’ have been dealt with. When an ‘A’ is found, the memory location is stored in variable ‘counter’ and control goes to subroutine surround_A. The purpose of surround_A is to determine all of the movements before and after the ‘A’ that need to be ignored for successful completion of the maze.

After the robot completes the maze for the first time, and changes the ‘RR’ to ‘A’ the code will something like:

F F F L F A F R F F L F this is for the hypothetical situation shown here:

To eliminate the unwanted code, the pairs of movements surrounding A are examined and compared to the green, blue and purple patterns.

F F F L F A F R F F L F

0 1 2 3 4 5 6 7 8 9 10 11

Surround_A looks at the pairs surrounding the ‘A’. If it finds a ‘FF’, ‘LR’ or ‘RL’ combo, it skips it and keeps going. These pairs “match up” and indicate the robot reversing its original course. It only exits the loop when it finds a ‘FL’, ‘LF’, ‘FR’, or ‘RF’. These pairs indicate where the robot made the initial wrong turn because they don’t match up.

The program needs to keep track of which movements in the memory blocks to ignore to solve the maze correctly. To do this, it will write a zero into the blocks where that code needs to be ignored. In the above example, the solution to the maze is a ‘FRF’. Therefore, blocks 1,2,3,4,5,6,7,8, and 9 need to be overwritten with a ‘0’ and block 10 needs to be overwritten with an ‘R’. Here’s where the program gets confusing…

Variable ‘w’ represents movements (F,L,R, or A) that are prior to the target ‘A’. Variable ‘y’ represents movements after the target ‘A’. (‘A’ is represented as x) Index_w is the number of memory blocks prior to ‘A’ that need to get a ‘0’ written into them. Index_y is the number of memory blocks after ‘A’ that need a zero. However, in the event that one or more ‘A’ and its surrounding pairs have already been overwritten with zeros, variable ‘w’ will read in these zeros from the EEPROM. It does no good to compare a ‘0’ to the variable ‘y’…so w must keep reading in data from EEPROM until it reaches a non-zero character.

This will occur in the above situation. After the find_RR subroutine, the following code will be in EEPROM with the memory location displayed underneath…

F L F F L F A F R F F L F A F L F F R F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

The first time through find_A, counter=6. In surround_A, the pairs are compared:

n_y=1 and n_w=1 therefore…w=F and y=F so…loopback

n_y=2 and n_w=2 therefore…w=L and y=R so…loopback

n_y=3 and n_w=3 therefore…w=F and y=F so…loopback

n_y=4 and n_w=4 therefore…w=F and y=F so…loopback

n_y=5 and n_y=5 therefore…w=L and y=L so…set index_w=4 and index_y=4 because the IF statement is false.

After the IF statement become false, control leave surround_A and goes to the rewrite subroutine. This subroutine will be explained in detail later. For now, know that rewrite changes the data in EEPROM to…

F 0 0 0 0 0 0 0 0 0 0 0 F A F L F F R F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

The second time through find_A, counter=13. In surround_A the pairs are compared.

n_y=1 and n_w=1 therefore…w=F and y=F so…loopback

n_y=2 and n_w=2 therefore, w=0

because w=0, control enters read_again. n_w increments until w!=0. This occurs when n_w=13

n_y=2 and n_w=13 therefore…w=F and y=L so…set index_w=12 and index_y=1 because the IF statement is false.

After the IF statement become false, control leaves surround_A and goes to the rewrite subroutine

F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 R F F R F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

This is the final code. Failure to find another ‘A’ in find_A would send control to done. Essentailly, ‘n_w’ and ‘index_w’ are equivalent as are ‘n_y’ and ‘index_y’. One or the other can probably be eliminated without too much work to save memory.

The rewrite subroutine is fairly simple. When the program enters this part, values are already stored for ‘w’, ‘y’, ‘counter’, ‘index_w’, and ‘index_y’. Only one ‘A’ situation is rewritten at a time like in the above example. It will either correspond to a green, blue, or purple situation. The ‘if’ statements at the beginning are used to determine which of the three it is.

If (w=F and L=F) then subroutine rewrite_green is called

If (w=F and y=L) then subroutine rewrite_blue is called.

If (w=L and y=F) then subroutine rewrite_purple is called.

Example of situation green code:

F F L F R R F L F F

0 1 2 3 4 5 6 7 8 9

After the find_RR subroutine

F F L F A F L F F

0 1 2 3 4 5 6 7 8

After find_A, counter=4

After surround_A, w=F, y=F, n_w=2, n_y=2. We want spaces 2,3,4,5, and 6 to be written with ‘0’. After the ‘if’ statement fails, the following code is execuated:

index_w=n_w-1

index_y=n_y-1

Therefore, index_w=1, and index_y=1.

Inside rewrite, w=F and y=F so subroutine rewrite_green is called

For the decrementing loop, we need blocks 2 and 3 to be written with zeros. The following code is used to write the ‘0’ to EEPROM:

for dummy=1 to index_w+1

write counter-dummy,0

This will write zeros to memory blocks 3 and 2.

For the incrimenting loop, we need blocks 5 and 6 to be written with zeros. The following code is used to write the ‘0’ to EEPROM.

for dummy=1 to index_y+1

write counter+dummy,0

This will write zeros to memory blocks 5 and 6.

Lastly, ‘counter’ is written with a zero.

Example of situation blue code:

F F R R F L F

0 1 2 3 4 5 6

After the find_RR subroutine

F F A F L F

0 1 2 3 4 5

After find_A, counter=2

After surround_A, w=F, y=L, n_w=2, n_y=2. We want spaces 2,3, and 4 to be written with ‘0’ and space 5 to be written with a ‘R’. After the ‘if’ statement fails, the following code is executed:

index_w=n_w-1

index_y=n_y-1

Therefore, index_w=1, and index_y=1.

Inside rewrite, w=F and y=F so subroutine rewrite_blue is called

For the decrementing loop, we need block 1 to be written with a zero. The following code is used to write the ‘0’ to EEPROM:

for dummy=1 to index_w

write counter-dummy,0

This will write zeros to only memory block 1.

For the incrementing loop, we need block 3 to be written with a zero, and block 4 to be written with a ‘R’. The following code is used to write the ‘0’ and ‘R’ to EEPROM.

for dummy=1 to index_y

write counter+dummy,0

write counter+index_y+1, R

This will write a ‘0’ to block 4 and a ‘R’ to block 5.

Example of situation purple code:

F L F R R F F

0 1 2 3 4 5 6

After the find_RR subroutine

F L F A F F

0 1 2 3 4 5

After find_A, counter=2

After surround_A, w=L, y=F, n_w=2, n_y=2. We want spaces 2,3, and 4 to be written with ‘0’ and space 1 to be written with a ‘R’. After the ‘if’ statement fails, the following code is executed:

index_w=n_w-1

index_y=n_y-1

Therefore, index_w=1, and index_y=1.

Inside rewrite, w=F and y=F so subroutine rewrite_purple is called

For the decrementing loop, we need block 2 to be written with a zero and block 1 to be written with a ‘R’. The following code is used to write the ‘0’ and ‘R’ to EEPROM:

for dummy=1 to index_w

write counter-dummy,0

write counter-index_w-1, R

This will write a zero to only memory block 2 and a ‘R’ to block 1.

For the incrementing loop, we need block 4 to be written with a zero. The following code is used to write the ‘0’ to EEPROM.

for dummy=1 to index_w

write counter-dummy,0

When the program is finished rewriting either situation green, blue, or purple, a ‘goto’ command sends control back to the find_A subroutine. If the process is repeated for all the ‘A’ present. After the last ‘A’ has been corrected, control goes to the done subroutine.

Part 3

Done is nothing more than a debugging tool. It reads each memory block and prints it too the screen. When the Boe-Bot is attached to the computer, this is a convenient way to see the final code.

At the beginning of the re_do_maze subroutine, the Boe-Bot pauses for 10 seconds to allow the user to reposition it in the maze. On the second time through, the IR sensors are not used. The subroutine loops from 0 to ‘total_moves’-1. For each iteration, the movement (F, L, R, or 0) is read from EEPROM and then evaluated in the ‘if’ statements. Those ‘if’ statements then determine which of the subroutines to call, either forward2, left2, or right 2. The code for forward and forward2 are the same however because of the craziness of the BASIC language, separate labels and identical code is required (likewise for left2 and right2).

General Notes On The Program

Through out the program there appears to be unnecessary ‘debug’ and ‘pause’ commands. When you run the Boe-Bot attached to the computer, they may come in useful in helping to understand how it works, of course. When the robot is free of the computer they seem useless, however, they do serve a critical function. We spent many long and frustrating days debugging this program. Even when we knew exactly what the robot should do, it wouldn’t. The solution we found almost accidentally was the debug and pause commands you see. My theory is this…

The Stamp BASIC brain is not the most sophisticated in the industry. There are several limitations to its performance. As I mentioned earlier, this program takes almost 85% of the memory on the chip. I believe the program is too large and too involved for the Stamp BASIC. Therefore, I had to slow it down a great deal. Each time the debug and pause are executed, it slows the program momentarily. This allows the Stamp chip to “catch up with the program.” If you remove these commands you will witness some very unpredictable behavior. In the middle of the loop, control will leave the loop for no apparent reason and the program resets. There is no pattern to which iteration control will leave the loop either. Keep in mind that function like ‘pulsout’, ‘read’, and ‘write’ take a few mili-seconds to execute. Also, do not replace the ‘debug’ functions in forward, right, left, forward2, right2, or left2 with a ‘pause’ command. From our experience, only the debug would do the job for some strange reason.

What do you think? Answer below!

Share

Related Posts

Comments are closed.