Institute of Electrical and
Electronic Engineers
MicroMouse Competition Robot
Senior Project CompE490A
Report
by
Jimmy Moore
Project Development
Partner: Ray Salem
Project Advisor: John
Kennedy
The
objective of this project is to develop software for a Palm Operating System
based personal digital assistant (PDA) that will allow a robot with the
necessary sensors to map and solve a maze while connected to the PDA. The final outcome will compete in the
Institute of Electrical and Electronic Engineers MicroMouse competition in the
spring of 2003. The algorithms,
software and hardware are being specifically tailored for this
competition. Metrowerks Code Warrior integrated
development environment is being used for software development.
The Personal
Digital Assistant (PDA):
The Robot:
The robot consists
of a drive train and sensor array that will be controlled through a serial
connection by the PDA. An ultrasonic
sensor will be used on the front of the robot, allowing the distance to the end
of a path to be determined. The maze
that the robot will operate in consists of a grid of 18-centimeter squares and
will have a total maximum size of 16 X 16 squares. The longest distance that will exist in front of the robot will
be 288 centimeters, well within the range of the ultrasonic device. By measuring the distance to the end of the
pathway, a maximum speed may be determined for traveling down the path. The longer the distance the robot will travel,
the greater the velocity it will achieve.
As the robot nears the wall at the end of a path, it may safely be
brought to a lower speed.
Each side of the
robot will have two infrared sensors, located near the front and rear edges of
the chassis. Infrared sensors are used
for the sides because the distances that will be measured are less than 4
centimeters. An ultrasonic sensor
cannot be used to measure the small side clearances accurately and is also far
more expensive to purchase. As the
robot travels through the maze, these sensors will check for the existence of
walls on either side of the robot in order to determine alternate paths that
will need to be mapped. The mapping
algorithm will be discussed later. In
later stages of development, the infrared sensors may be connected through an
analog to digital (A/D) converter and each of the four sensor values will be
compared to keep the robot in the center of the pathway as it travels. As the sensors reflect values that show that
the robot is nearer to one wall than the other, a motor speed adjustment can be
made so that it will return to the center of the path. The sensors on one side can be compared in
order to see if the robot is parallel to the wall. In the early stages of development, these sensors will be used
only to determine a logic value, high if a wall is present and a reflection is
found or low if the square is open on a side and no reflection is found. The infrared sensors will require
calibration in both stages, first in order to determine the threshold between
logic high and low and later to set the analog outputs of the sensors so that
they are uniform while at equal distances from a wall.
The robot will not
travel backward and does not require a sensor to the rear. Rather than move backward, it will rotate
180 degrees around its center and travel in the opposite direction.
An optical sensor,
from an optical mouse, will be used in the bottom of the chassis to measure the
distance traveled by the robot. An
optical device was chosen because it doesn’t require physical contact to the
surface that it is traveling over and will not incur errors due to slippage
that are inherent in physical contact designs.
The optical sensor will be placed slightly forward of the center of the
chassis so that it may be used to measure an arc when turning the robot. The length of the arc will determine how
many degrees of rotation the robot has turned.
The final sensor
that will be used is an electronic compass.
When the robot is placed at the entrance of the maze, the compass
heading will be set as the “northern” direction of the maze. The compass will be used to make course
adjustments in direction, such as when the robot is turning to follow path
other that the one that is directly in front of it. Also, if the robot strikes a wall or other obstacle and the
bearings within the maze are lost, the compass heading will be used to
determine which direction it is facing and adjustments will be made to
determine its exact location.
The drive train of
the robot consists of two motors that are operated through one motor
controller. The robot will have one
wheel on each side of the chassis mounted on an axel that is placed in the
center of the robot from front to back.
Each wheel will be driven directly by a motor. To turn the robot, the speed and direction of the motors will be
controlled individually to achieve the necessary movement. To turn, one motor will be driven forward and
the other reverse to allow the robot to pivot around its center axis.
A Field
Programmable Gate Array (FPGA) will be used to interface between the
sensors/motor controller and the PDA.
The FPGA can take a drive command from the PDA and supply the necessary
voltages to the motor controller to carry out the function. The PDA cannot directly supply these
voltages. The FPGA will also act as a
set of registers that will hold the current output values of each of the
sensors. Sensor values in these registers
will be updated at regular intervals that will allow the stored values to be
accurate even while the robot is moving.
The PDA will
communicate to the FPGA through a serial connection using a protocol that has
been developed specifically for this project.
The Super Simple Serial Communication
(S^3C) protocol consists of three-wire communication sending 2 byte
packets. One wire sends data from PDA
to FPGA, the second from FPGA to PDA, and the third is a ground connection
between the devices. When the PDA
requests sensor data, the first byte of the packet will be the address OxOOOO,
indicating that the request is to go to the first register space in the
FPGA. The second byte will be the
address of the register containing the data that the PDA is requesting. The first register of the FPGA will be
reserved specifically for this operation and the data that has been requested
will be sent back to the PDA with the first byte being the register address and
the second byte being the sensor data currently stored in the register. After the packet is sent, the first register
will be cleared to indicate to the FPGA that no requests are pending. When the PDA determines that a change of
operation needs to be made, the first byte of the transmitted packet will
contain the address of the appropriate motor control register and the second
byte will be the new condition for the motor.
Mapping the Maze:
The strategy for
mapping the maze will start off as an exhaustive search of all possible routes
through the maze. As stated before, the
robot is being designed to solve a maze that consists of a grid of 16X16
squares. Mapping the maze will require
testing the condition of each of the 256 squares of the maze. Anytime the robot has an unmapped square in
front of it, it will continue to travel forward until it come to a wall. Each square that the robot travels through
will be updated in a 2 dimensional array in the PDA that records the conditions
of the walls of the squares with a 4-bit number. Each bit will represent a direction (north, south, east or west),
a 1 will represent a wall and a zero will represent an opening. At the time that a wall is reached, the
robot will check the status to either side and will take an existing route from
this point if possible. If a side opening does not exist, the robot will turn
180 degrees and the PDA will determine how far it must travel to return to the
nearest possible alternate route. As
the robot returns back to the last opening, the condition of each square is
verified and the square will be marked as unusable so that the route will not
be entered again. When a side opening
is reached, the robot will turn toward it and continue on in the same
manner. The robot will continue to map
the maze until the condition of all squares has been determined, even if the
destination has already been reached.
The destination of
the maze will consist of four unit squares with a pole at the center and no
internal walls. When the mouse records
this condition for the four squares with open adjacent sides forming one large
open square, the squares will be recorded as the destination of the maze. The robot will then leave the destination
and continue to map the remainder of the maze.
When the condition
of all squares has been determined, or when no opening to the remaining squares
exists, the robot will return to the beginning of the maze. It may be necessary to return to the
beginning before completing the mapping process if the destination has been
found. The robot can only be in the
maze for a total of 10 minutes (by rules of the competition) and the robot
should make one trip from start to destination taking the shortest route before
time has expired.
Determining the
Shortest Route:
The software
developed for the PDA must now determine the possible routes from the beginning
point to the destination of the maze.
If more than one route exists, the fastest route must be
determined. At this time, it is assumed
that the fastest route will always be the shortest in length. For first generation development, the
shortest distance to the destination will be determined by calculating the
length of all possible routes. The
robot will travel down this path at a safe operating speed. The winner of the competition is the robot
to travel from beginning to destination in the shortest time. Once the direct route is taken and a time is
recorded, the robot will return to the starting point and the speed will be
increased for the next run. With every
successful run, the robot will return and run again at a higher speed in order
to decrease the time required.
Error Correction:
The maze dimensions
may have a degree of error. Rather than
use the exact distances that are covered by the robot, as measured by the
optical sensor underneath, the squares covered will be determined by a
“landmark” system. When the robot
records an opening to either side, the beginning and end points of the opening
are known to be the length of a square.
The distance that the mouse has covered since the previous “landmark”
may be divided by the number of squares that have been covered and corrections
to the size of the squares can be made.
In this way, if a series of squares is slightly shorter than 16
centimeters due to the thickness of the wall at its end, a square will be
recognized even though the full 16 centimeters is not available. This correction method will have to be
implemented due to the accuracy of the optical measuring device used by the
robot in order to give flexibility for actual maze dimensions.
As of the writing
of this report, December 2002, all of the sensors described in the report are partially
operational with the exception of the infrared sensors, which have not been
implemented at this time. Also,
three-wire serial communication between the PDA and a desktop computer, as well
as between a desktop computer and the FPGA is operational. Serial communication with the PDA is still
in ASCII characters and the two-byte packet communication is in development.