Software
The software for this project can be divided into two main categories, the maze-solving algorithm software and the control software.
Flow diagrams of the software can be viewed by clicking below. These include a flow diagram for the main program and for
the movement control software:
Maze-Solving Algorithm Software
The method in which we used the robot finds a path to the center of the maze is called Bellman’s Algorithm. The robot looks at the entire maze as if there were no interior walls. It then assigns values to every block of the maze representing how many blocks it has to move to get to the center squares of the maze. An example of an initialized 8 x 8 block maze is shown below.
|
6 |
5 |
4 |
3 |
3 |
4 |
5 |
6 |
|
5 |
4 |
3 |
2 |
2 |
3 |
4 |
5 |
|
4 |
3 |
2 |
1 |
1 |
2 |
3 |
4 |
|
3 |
2 |
1 |
0 |
0 |
1 |
2 |
3 |
|
3 |
2 |
1 |
0 |
0 |
1 |
2 |
3 |
|
4 |
3 |
2 |
1 |
1 |
2 |
3 |
4 |
|
5 |
4 |
3 |
2 |
2 |
3 |
4 |
5 |
|
6 |
5 |
4 |
3 |
3 |
4 |
5 |
6 |
The robot starts to
follow the cells in descending order to reach the end of the maze (where the
value is zero). Eventually the robot
will encounter a cell in which it cannot go to a cell with a smaller value. The
robot then updates the cell value by looking at the smallest value that is
adjacent and open to the cell that it is currently updating and then
incrementing that value by one.
The rest of the
previous visited cells are then updated. This is accomplished by branching out
from the first cell that is updated until all visited cells have been
revised. Shown below is an example of a
maze where the robot has visited every cell and has assigned the correct value
to every cell in the maze.
|
4 |
9 |
8 |
7 |
8 |
7 |
8 |
9 |
|
13 |
12 |
9 |
6 |
5 |
6 |
9 |
10 |
|
14 |
11 |
10 |
11 |
4 |
3 |
10 |
11 |
|
15 |
12 |
13 |
0 |
0 |
2 |
3 |
12 |
|
16 |
17 |
18 |
0 |
0 |
1 |
4 |
5 |
|
17 |
16 |
19 |
20 |
13 |
6 |
5 |
6 |
|
18 |
15 |
12 |
11 |
12 |
7 |
6 |
7 |
|
19 |
14 |
13 |
10 |
9 |
8 |
7 |
8 |
Control Software
Movement and Motor Control
While trying to get to the center of the maze, the robot looks at the open, adjacent cells (cells that do not have walls blocking the path) to the cell that it is sitting in. It moves to the cell with the lowest value, and thus should take the least amount of moves to get to the center. The robot then determines if it should make a turn or go forward.
The movement control software communicates to the PLD, which drives the motors of the robot. When the robot wants to turn or move forward, it sends the appropriate signal to the PLD to move the respective motors. It then uses a counter for the correct amount of steps from the stepper motor to complete the move. The counter is decremented by an interrupt routine. The interrupt is called every time a clock pulse should be sent to the PLD through the TOC (Output Compare) pin. This provides the PLD the appropriate clock pulse to move through the state machine and change the state of the motors.
Sensor Input and Correction
Eight sensors are used to keep track of the maze and to maintain the robot’s straight path. Three sensors are located on the side wings and two on the front. The software performs processing at the approximate center of each cell. During this processing period all sensors are checked for wall information. The information gathered is then stored in memory in a matrix proportional to the size of the maze.
The sensors are also used in movement correction. Three types of correction have been implemented. The short front routine checks for a front wall during the aforementioned processing period. It compares the value it contains in memory against the reading reported from the sensors at that moment. If the values are different the robot will progress forward until the front wall is found. This serves to center the robot in the cell in forward/backward sense.
The second correction is front wall detection. Unlike the short front routine, the sensors are polled during all forward movement. When the front sensors are triggered, the robot checks the movement counter used to determine the number of steps in a forward movement. When this number is high, the assumption is made that the robot lost some distance and arrived at the cell short. The software makes the necessary modifications to ensure the program knows the robot’s position.
The
final correction is the side correction.
It aims to maintain a straight path for the robot in a left/right
sense. It also polls the sensors during
all forward movement. After testing the
robot three degrees of correction were implemented. A conceptual view is
depicted in the picture below. The
software compares the current state of the sensors with each of the
predetermined states in memory. After
the magnitude and direction of correction are determined forward progression
pauses while the robot spins a small distance.
In order to allow time for the corrections to be effective a pause must
be added until the robot can move back into a centered position. Side correction approximately three times
for every cell traveled.