Palm OS Based Autonomous Robot Controller

For the Micro Mouse Autonomous Robot

Using the Palm M125

Undergraduate Senior Project by: Jimmy Moore

Computer Engineering 490A & B

Project Advisor: John Kennedy

San Diego State University May 19, 2003

Abstract

Many of the devices that we encounter in our daily lives contain embedded control systems. Every time that you press a button, something has to respond with an appropriate output. Automobiles, televisions, elevators, even modern washing machines must contain a control system that processes user input from some type of interface of push-buttons or sensors. These embedded control systems must contain a minimum of a processor, a memory device, and the ability to communicate with the device that is being controlled as well as the user or operator of the device. A personal digital assistant (PDA) contains all of theses features and more. Therefore, the PDA can be a low cost, self-contained control system capable of being incorporated into many devices.

In the development of the Micro Mouse autonomous robot that will be discussed in this report, the initial design team decided to use a personal digital assistant (PDA) as the system control unit. A personal digital assistant (PDA) contains all of the components necessary to handle operation of many devices. The purpose of this project, specifically, was to design search algorithms and execute these algorithms on a PDA in such a manner as to control a robot capable of competing in the Micro Mouse competition described below. For further information on design considerations of the robot chassis, please refer to the report titled Micro Mouse Control System, December 24, 2002 by Raied Salem, on file in the Senior Project Lab, room E217, San Diego State University College of Engineering.

The Micro Mouse Competition

Micro Mouse is an annual competition sponsored by the Institute of Electrical and Electronic Engineers. Design teams build robots with the ability to solve a maze in much the same way that a mouse will find its way through a maze to reach a piece of cheese. The strategy of the contest is to map the entire maze and determine the fastest route from the starting point to the destination. The winner is the robot that is able to complete a trip from start to destination in the shortest amount of time. While each team’s robot is allowed a total time of 10 minutes in the maze, each time the robot leaves the starting element a new timed run will begin in order to record the time of that trip to the destination.

The maze is comprised of a two dimensional array of squares. Each square, or element, of the array is 18x18 centimeters. The full maze is 16x16 elements. The points within the maze where the corners of elements come together are referred to as lattice points. Each lattice point will contain the end of at least one wall, except for the center or destination point. The destination will be four adjacent elements arranged in a square with no internal walls and will be the four elements at the center of the maze. Also, the starting point will be on one of the four corners of the maze and will be bounded by walls on three sides. This is all of the maze data necessary for this project. For full details, refer to Appendix A.

Figure 1: Array Used For Project Testing

For the scope of this project, the main requirement of the robot that must be considered is that it must be completely autonomous, no external communication of any kind during the contest. The only exceptions are that minor adjustments may be made when the robot is within the starting element, such as using switches to change operational settings. Full details of robot design specifications may be found in Appendix A.

Minimum Robot Requirements

The robot that this control system is being designed for will have a minimum of four sensors. Three of these are to be used to detect walls in front or to either side of the robot. No such sensor is required on the back since the robot does not have to travel in the reverse direction. This operation may be achieved by the control system by directing the robot to turn 180^o and traveling forward. By eliminating the need for a sensor on the back of the robot, cost was reduced by the price of the sensor as well as the extra data recording and processing that would be required by the sensor. The fourth sensor that is needed is a device that will measure distances traveled by the robot. Presumably, this sensor will be of the type used in an optical mouse and will be located in the bottom of the robot. By locating the sensor off of the center point of the chassis, it may also be used to measure the rotation of the robot while turning and to insure that the robot is traveling in a straight line.

The system designed by Raied Salem contains all of the necessary sensors, as well as implementation of a Field Programmable Gate Array (FPGA) to interface between the robot’s sensors/motor controller and the system being designed in this project. The embedded system to be designed here must be able to read the sensor values output from the FPGA and return the appropriate directional commands to the FPGA, which will control the motors. All processing of optical sensor feedback to maintain proper direction of travel will be handled by the FPGA.

Designing a Mapping Algorithm

Programming Language All software for this project was developed in the C programming language. Since the programs must be implemented to operate on a PDA, a language that could be easily converted for a PDA development environment was necessary. The C language met this requirement as well as being a language that is widely used by students in the San Diego State University engineering department.

Representing the Maze Map Due to the limited size of the maze to be mapped, the maze may be represented very simply as a two dimensional array of C structures. Commonly referred to as structs, structures are an aggregate data type that may be defined to hold several variables of different data types. In the beginning, each element was mapped as a struct that contained boolean values to record the condition of each wall. Either a wall existed or did not exist, represented as the wall being true or false. As it became necessary to record more information in the map, such as whether or not the element is part of a desired path or how many times the robot has visited an element, more variable were added to the structs.

Decisions After the control system has recorded the current surroundings of the robot, a decision must be made on which direction to travel. Since all accessible elements of the array should be mapped in order to assure that all possible routes have been found, the most important consideration in moving through the maze is to attempt to travel to areas that have not yet been mapped. This called for the addition of an integer variable to each struct of the map that is incremented each time the robot enters the element. The values held in these variables for each accessible element from the current location can then be compared and the robot will be directed to the one with the smallest value. So, if the maze conditions are such that the robot may move to either the left or right, the decision will be made to move to the one that has been visited the fewer number of times. Default conditions exist in case the elements have been visited an equal number of times.

The function “NextStep()” will determine what direction to move. The function first determines which direction the robot is currently facing. This value is stored in a global variable and is changed each time the robot must change directions. If the wall in front of the robot is open and has never been visited, the robot will proceed forward. If the element in front has been visited, each side is check for accessibility and a lesser number of visits. If the element in front is not accessible, the element to each side is checked for accessibility and the fewest number of visits.

Eliminating Dead-Ends When the robot has reached a dead-end, the elements in front and on each side are not accessible, the element is made inaccessible to further movement and eliminated from the maze. Upon finding this condition, the global boolean variable “backtrack” is set to true and the function “CheckWalls()” is called. This function rotates the robot 180^o and moves it back to the previous element. The walls of the element on the end are set to true within the struct and the wall that is currently behind the robot is also set to true. Once this is done, the robot will no longer see the element as accessible when reading from the map array and will not enter it again. The function “CountWalls()” is now called to see if the dead- end condition still exists. If an integer value of three is returned, the same operation describe above will be repeated without the rotation. This process will continue until “CountWalls()” returns a value of less than 3. Then, “backtrack” is set to “false” and “NextStep()” is called to continue mapping.

Marking The Destination After every step, or movement from one element to an adjacent element, the robot takes, “CheckDest()” is called to determine if the destination has been reached. Since the destination is always in the center of the maze, it is possible to find that the center has been reached by checking for current coordinates of (7,7), (7,8), (8,7), or (8,8). Once the robot has successfully entered any one of these elements, the destination has been found and a global boolean variable “dest” is set to “true”.

Completion of Mapping When the robot has returned to the starting element, and the “dest” value is “true”, the map is complete. (This condition is true using the current algorithm and one useable path from start to destination. More intelligence is required for multiple paths to be properly mapped.)

Simulation

At this point in the project, it became necessary to run tests to verify that the algorithms that had been developed up to this point would actually work. But, as is often found in multi-layered projects with different engineers working on different layers, the robot did not exist and testing could not be performed. It became necessary to create a simulator to emulate the maze and robot with sensor array. The actual maze and robot can be completed later and the software can then be modified to operate properly with the hardware.

Simulation of the maze is obvious at this point. The maze can be represented by a two dimensional array of structs just as the map has been created. The representation of the maze may consist of only the existence of each wall of each element. No further information would be determined by the sensor array of the robot so no further data needs to be recorded in the simulator for the maze.

First Stage Testing In order to test the algorithms, a single application was created that contained the maze simulation and the map as well as all of the necessary functions for mapping. The application was designed to be executed on a desktop computer. (These tests can be found on the compact disk that accompanies this report) Each time the simulated robot takes a step, the appropriate coordinate is adjusted so that the new location is the maze is represented and the next determination can be made. As the test code executes, the map of the maze is drawn to the window on the desktop computer in order to see what is being executed by the code. The maze used for simulation in this project is shown in figure 1.

Second Stage Testing The next step in the process was to separate the simulation application from the control system. The source code for each operation was separated into two separate applications that can be executed on a desktop computer. Serial communication was established between the two applications by using the WriteFile(…) and ReadFile(…) system commands. One application was written to communicate with the COM 1 serial port and the other on COM 2. The serial ports were then connected together with a null modem cable to establish a connection. At other times, the applications were executed on two separate computers, connected with a null modem cable. The WriteFile() command of the mapping application is executed on starting the application, requiring that the maze simulator be running and waiting with the ReadFile() command. The mapping application sends the X and Y coordinates of the current location of the robot to the simulator. The simulator records these values and uses the WriteFile() command to send the boolean value of the walls of the corresponding element back to the control system. The control system records these values into the map element at the current location and executes NextStep() to determine where to move next. Later, when the robot development is complete, the control system will pass commands to the FPGA of the robot to move it to the desired coordinate and the sensor outputs will be used to determine the Boolean wall conditions that will be recorded in the map.

Figure 2: Separate Simulation and Mapping Applications Being Executed on Two Desktop Computers, Linked With a Null Modem Cable

Third Stage Testing At this point, the control system was to be adapted to be executed on a PDA. The design team selected the Palm M125. It uses Palm Operating System 4.0.1 and has a 33MHz Motorola Dragonball processor, 8 Mbytes of memory for storing/execution of the mapping application and the map array, and a serial communication port for transfer of data to and from an external device such as the robot’s FPGA. Metrowerks’ “Code Warrior for Palm OS” integrated development environment (IDE) was used for creating the application to be executed on the M125. Even the most simple of applications on the M125, or any PDA using the Palm OS, requires interaction between several system functions. By using source code written by Lonnon Foster, author of Palm OS Programming Bible, for establishing serial communication to transfer text from a PDA to an external device, many of these functions only needed to be adapted for the specific use required by this project. Once communication was established with the desktop computer, the system control functions were brought in from the desktop application to the PDA application. Functions calls were added in the proper areas of the main function of the PDA application to allow mapping to be performed, and the application was ready for testing. Code Warrior creates the equivalent of an executable file for the PDA, and that file was downloaded to the M125 through the normal synchronization process with a desktop computer. Since the M125’s primary means of connection to the desktop is through a Universal Serial Bus (USB) connection, a special cable was developed to connect to the serial port. Wiring diagrams of the cables designed for connection to the Palm 16-pin Universal Connector and a description of how the cable for this test was made are in Appendix B.

After connecting the M125 to the desktop, testing showed that the application ran in the same manner on the PDA as it had on the desktop computer. Some decrease in the speed of mapping was noted. This is believed to be caused by the slower speed of the PDA processor compared to that of the desktop. During simulations in which mapping was performed by the PDA, in situations where longer sections of code (200-300 lines) were required to determine which element to move to, the movement took noticeably more time to execute than those in which only one or two lines were required.

Using the Control System

The control system on the M125 is now ready for adaptation and testing in a robot. The source code for the control system may be modified to include additional sensors by increasing the amount of data that is read by each ReadFile() command. Modifications must be made to process data from each sensor, as sent by the FPGA, and save data to the appropriate variable within the element struct. The reply data from the control system to the robot will probably remain at very basic level of simply instructing the robot to move to the next element.

Further development is needed in order to completely map a maze with multiple paths from start to destination as well as to determine the shortest available paths. The control system developed for this project only works adequately with one path.

Conclusion

It has been determined through extensive testing during the completion of this project that a Palm OS based PDA like the M125 can be used as a system controller for the Micro Mouse competition robot. Other than limited processor speed, relatively small amounts of memory, and slow data transfer through serial communication, the system is very appealing for a multitude of applications. As newer PDA’s are becoming available, faster processors and larger amounts of memory are very common in devices that are more expensive than the M125. The serial communication problem can be avoided completely by using a USB interface that operates at much higher data transfer rates. Overall, the PDA appears to have many applications in the future of electronics other than those that are currently utilized.

Appendix A

Competition Rules

MICROMOUSE CONTEST RULES

REGION 6

These rules were revised November 30, 2001 and are valid for the Spring 2002 contest. The 2001 revisions are: (1) The MicroMouse competition is intended to be a design contest, culminating the aggregate knowledge earned in a typical undergraduate degree. To support this, the participants will submit a report including a summary of the project, schematics, layout, Bill of Materials (with costs), and software code. The participants will present their design for review and answer questions from the judges prior to competing on the maze. The following rules were adapted from 1986 OFFICIAL RULES for NORTH AMERICAN MICROMOUSE CONTEST.

OBJECTIVE

In this contest the contestant or team of contestants design and build small self-contained robots (micromice) to negotiate a maze in the shortest possible time.

CONTEST ELIGIBILITY

All contestants must be an undergraduate IEEE student member at a Region 6 school from within the Area of Region 6 in which contest they will compete at the time of entry in the MicroMouse contest. Any student who graduates anytime during the Fall-Spring academic year in which the contest is held is eligible to enter the contest. A student graduating after competing in the contest still remains eligible to compete in succeeding Area, Region, and higher contests as an undergraduate student. Up to two graduate students per team are also allowed as stated in Rule A.4 below, providing they meet all other requirements.
All contestants must be an IEEE Student Members or must have submitted an application for membership (and have it accepted by their Student Branch Counselor) prior to entry in the Student Branch and/or Chapter Contest.
The contestant(s) will submit their design in a document that will include a summary description of their mouse, schematics, layout, Bill of Materials (with associated costs) and code prior to the competition. This information will be presented, in five minutes or less, and the contestant(s) will answer any questions posed by the judges of their design.
The MicroMouse entry may be the effort of an individual or a team. In the case of a team it should be possible to demonstrate that each individual made a significant contribution and that they are all IEEE members.
A team may consist of up to five people. A team of four or five people may include no more than two graduate students. A team of two or three people may have no more than one graduate student. A team consisting of a single graduate student is not allowed.
All entrants to the Student Branch Area contests must declare their intention to enter the contest at least 2 weeks before the date of the Area contest. This notice must be submitted to the current Student Activities Coordinator, appropriate Area, Region 6, by mail, email, or phone (see the names and addresses at the end of this document).
If the total number of declared mice, from all schools, is less than the number of eligible schools to compete in that Area, all shall be eligible to compete in the area contest. Two or more mice of near identical design from the same school are not allowed. If more mice than the number of eligible schools to compete are entered in the contest (ie., four mice from the same school), a qualifying competition will be held in the morning. A qualifying contest might involve, for example, having the mice transverse a specific numbers of cells.

RULES FOR THE MicroMouse

A MicroMouse shall be self-contained (no remote controls). A MicroMouse shall not use an energy source employing a combustion process.
A MicroMouse shall not leave any part of its body behind while negotiating the maze.
A MicroMouse shall not jump over, fly over, climb, scratch, cut, burn, mark, damage, or destroy the walls of the maze.
A MicroMouse shall not be larger either in length or in width, than 25 centimeters. The dimensions of a MicroMouse that changes its geometry during a run shall not be greater than 25 cm x 25 cm. There are no restrictions on the height of a MicroMouse.
The total cost of the mouse (in materials, labor is assumed to be free) may not exceed $500.00. This is judged on actual cost and market value of any donated materials used in the mouse. Contestants should be prepared to present a list of materials and their market values to the judges upon request. Since market values may vary from source to source, contestants should be prepared with catalogs or quotes to confirm unusual prices. The judge's decision shall be final in these matters.
Any violation of these rules will constitute immediate disqualification from the contest and ineligibility for the associated prizes.

RULES FOR THE MAZE

The maze is composed of multiples of an 18 cm x 18 cm unit square. The maze comprises 16 x 16 unit squares. The walls of the maze are 5 cm high and 1.2 cm thick (assume 5% tolerance for mazes). The outside wall encloses the entire maze.
The sides of the maze walls are white, the tops of the walls are red, and the floor is black. The maze is made of wood, finished with non-gloss paint.

WARNING: Do not assume the walls are consistently white, or that the tops of the walls are consistently red, or that the floor is consistently black. Fading may occur; parts from different mazes may be used. Do not assume the floor provides a given amount of friction. It is simply painted plywood and may be quite slick. The maze floor may be constructed using multiple sheets of plywood. Therefore there may be a seam between the two sheets on which any low-hanging parts of a mouse may snag.

The start of the maze is located at one of the four corners. The start square is bounded on three sides by walls. The start line is located between the first and second squares. That is, as the mouse exits the corner square, the time starts. The destination goal is the four cells at the center of the maze. At the center of this zone is a post, 20 cm high and each side 2.5 cm. (This post may be removed if requested.) The destination square has only one entrance.
Small square zones (posts), each 1.2 cm x 1.2 cm, at the four corners of each unit square are called lattice points. The maze is so constituted that there is at least one wall at each lattice point.
Multiple paths to the destination square are allowed and are to be expected. The destination square will be positioned so that a wall-hugging mouse will NOT be able to find it.

RULES FOR THE CONTEST

Each contesting MicroMouse is allocated a total of 10 minutes of access to the maze from the moment the contest administrator acknowledges the contestant(s) and grants access to the maze. Any time used to adjust a mouse between runs is included in the 10 minutes. Each run (from the start cell to the center zone) in which a mouse successfully reaches the destination square is given a run time. The minimum run time shall be the mouse’s official time. First prize goes to the mouse with the shortest official time. Second prize to the next shortest, and so on. NOTE, again, that the 10-minute timer continues even between runs. Mice that do not enter the center square will be ranked by the maximum number of cells they consecutively transverse without being touched. All mice who enter the center square within their 10 minute allotment are ranked higher than those who do not enter the center square.
Each run shall be made from the starting square. The operator may abort a run at any time. If an operator touches the MicroMouse during a run, it is deemed aborted, and the mouse must be removed from the maze. If a mouse has already crossed the finish line, it may be removed at any time without affecting the run time of that run. If a mouse is placed back in the maze for another run, a one-time penalty of 30 seconds will be added to the mouse’s best time.
After the maze is disclosed, the operator shall not feed information on the maze into the MicroMouse however, switch positions may be changed. See Rule D.1.
The illumination, temperature, and humidity of the room shall be those of an ambient environment. (40 to 120 degrees F, 0% to 95% humidity, non-condensing).

BEWARE: Do not make any assumptions about the amount of sunlight, incandescent light, or fluorescent light that may be present at the contest site.

The run timer will start when front edge of the mouse crosses the start line and stops when the front edge of the mouse crosses the finish line. The start line is at the boundary between the starting unit square and the next unit square clockwise. The finish line is at the entrance to the destination square.
Every time the mouse leaves the start square, a new run begins. If the mouse has not entered the destination square, the previous run is aborted. For example, if a mouse re-enters the start square (before entering the destination square) on a run, that run is aborted, and a new run will be deemed begun, with a new time that starts when the starting square is exited.
The mouse may, after reaching the destination square, continue to navigate the maze, for as long as their total maze time allows.
If a mouse continues to navigate the maze after reaching the destination square, the time taken will not count toward any run. Of course, the 10-minute timer continues to run. When the mouse next leaves the start square, a new run will start. Thus, a mouse may and should make several runs without being touched by the operator. It should make its own way back to the beginning to do so.
The judges reserve the right to ask the operator for an explanation of the MicroMouse. The judges also reserve the right to stop a run, declare disqualification, or give instructions as appropriate (e.g., if the structure of the maze is jeopardized by continuing operation of the mouse).
A contestant may not feed information on the maze to the MicroMouse. Therefore, changing ROMs or downloading programs is NOT allowed once the maze is revealed. However, contestants are allowed to:
Change switch settings (e.g. to select algorithms)
Replace batteries between runs
Adjust sensors
Change speed settings
Make repairs
However, a contestant may not alter a mouse in a manner that alters its weight (e.g. removal of a bulky sensor array or switching to lighter batteries to get better speed after mapping the maze is not allowed). The judges shall arbitrate.
There is only one official IEEE MicroMouse contest each year in each Area or Region. All mice, whether or not they have competed in previous contests, compete on an equal basis. All mice must be presented to the judges by the original design team, which must meet all other qualifications. First prize will go to that mouse which travels from the start square to the destination square in the least amount of time. Second and third prizes will be awarded to the second and third fastest respectively. As stated in Rule 4.1, mice that do not enter the center square will be ranked by the maximum number of cells they consecutively transverse without being touched.
A rotating trophy is awarded to the first place mouse. Verbal recognition and certificates will be given to the top three mice among those who are competing for the first time. If you and your mouse are first-time contestants, be sure to so stipulate when you register for the contest and notify the contest judge at the time of the contest.
If requested, a break will be provided for a mouse after any run if another mouse is waiting to compete. The 10-minute timer will stop. When the mouse is re-entered, the 10-minute timer will continue. The judges shall arbitrate on the granting of such breaks.

Appendix B

Wiring Diagram

Wiring Diagram of the Palm 16-Pin Universal Connector to a DB-9 Serial Connector

Description of Cable Construction:

Starting with a Targus USB Hotsync cable, disassemble the connector that attaches to the PDA. The pins in the connector may be pulled out of the connector block from the inside. Pins are then reinserted in the appropriate locations to connect to the 16-pin Universal Connector as desired. For this project, only pins 1, 10 and 11 are used. All others were removed from the connector. The USB connector on the opposite cable end was removed and replace with a generic DB-9 connector using only pins 2 and 3 and the shield.