1.1 Project Overview
The Micro Mouse Project was a one year project at Monash University in 2000, which aimed to combine all the hardware and software development techniques taught by the faculty in the previous years. This was a team project, consisting of members Andrew, Peter and myself. Several other competing teams received the same microprocessor equipped robot vehicle, called the Micro Mouse. The objective was to equip the robot with sensors so it can explore a large maze from a start position (at the corner of the maze) and find the goal position located somewhere in the centre.
Each team had to decide on a particular wall sensor technology to be used with the Micro Mouse. The individual teams had to design the sensors, prototype it on a breadboard and eventually test it on the robot. The implementation of the sensors involved a lot of electronics and PCB work. Our team opted for using ultrasonic sensing technology, because it was fairly straightforward to implement, and prototypes were easy to build.
In addition to designing the sensors, the team was required to develop software that controlled the robot's motion and an algorithm that solved the maze. Hence it was necessary to study the underlying hardware present on the Micro Mouse robot, especially the microprocessor and additional chips responsible for motor control.
1.2 The Robot and the Maze
The maze itself was basically a large flat table, consisting of 256 rooms in a square array. The dimension of each room was 180 x 180 mm, with a wall height of 50 mm. The whole maze was re-configurable, it was possible to insert or remove walls to form different paths and rooms. The walls were painted in a white colour, whereas the top of the walls was red and the floor itself was black.
The Micro Mouse robot measured 120 x 80 mm, with no sensors attached. The chassis of the robot balanced on two independently controlled wheels. The front and the back of the Micro Mouse had a small castor which provided the robot some stability. The wheels were controlled by two HCTL-1100 motion controller chips. These could be programmed by the on-board processor, allowing it to move the wheels at various speeds, acceleration and distances.
The microprocessor was a Motorolla MC68HC11F1, based on an 8-bit architecture. The processor contained a lot of built-in features such as, three 8-bit and one 5-bit bi-directional I/O ports, two 8-bit output ports (address bus), one 8-bit input port, an ADC, pulse accumulator/timer circuitry, 512 Bytes of EEPROM and 1024 Bytes of static RAM.
The processor could be programmed externally with a PC by using a serial communications interface. The Micro Mouse main board also contained 32 kB of SRAM and a 32 kB EPROM. A small operating system, called BUFFALO, was permanently stored in the EPROM. The BUFFALO operating system contained serial interfacing and debugging facilities, which allowed new code to be uploaded from the PC onto the Micro Mouse.
2 Sensor Hardware
It was my responsibility to design the sensor hardware. I also had to write the necessary drivers in assembler to get the sensor system integrated with the Micro Mouse.
The sensor system was based on the ultrasonic echo location principle. This type of system transmitted directional sound waves at 40 kHz, which eventually reflected off nearby objects. This reflection (or echo) was then picked up by a receiver. The time delay between the transmitted and reflected sound was used to compute the distance of the object.
Figure 3 shows a block diagram of a simple wall sensing circuit. A single measurement began with the CPU resetting the counter to zero. The CPU also issued a burst enable signal to the control circuit. The control circuit immediately sent a burst signal to the transmitter, while simultaneously enabled the free running counter. The free running counter began to increment at a fixed time interval.
The burst signal was generated by mixing the 40 kHz square wave, obtained from the oscillator with the actual width of the burst pulse (see Figure 4). This was sent to the transmitter, which consisted of a power amplifier that drove the ultrasonic transducer.
In the meantime, the receiver listened to a 40 kHz echo signal reflected from a nearby wall or an object. The echo was an analogue signal, usually weak in amplitude, especially for reflective objects located far away. This weak signal was amplified and then converted to a series of digital pulses, which were fed back to the control circuit.
As soon as the control circuit was issued a signal from the receiver circuit, it disabled the binary counter. The CPU detected that the counter was stopped and it read the 8-bit count value. Each count increment represented a fixed distance the sound has travelled. Therefore the total count value could be used to determine the echo location in millimetres.
A more detailed version of the sensor block diagram is illustrated in Figure 5. The basic functionality of this system was the same as the block diagram illustrated in Figure 3. The system was extended to manage four transmitter/receiver (TX/RX) circuit pairs through a multiplexing circuit. Each transmitter and receiver pair was located on one of the four sides of the Micro Mouse robot. The TX0/RX0 pair resided at the front, while the TX1/RX1, TX2/RX2 and TX3/RX3 pair were located at the left, right and backside respectively.
In this multiplexed configuration, the CPU selected just one of the TX/RX pairs for measuring at any given time. Meanwhile, the Pulse Accumulator was counting until an echo was detected. An echo event would cause the Pulse Accumulator to trigger an interrupt, allowing the CPU to read the raw count and calculate the echo distance. If there was no response from the sensor receiver, the Pulse Accumulator kept counting until it overflowed, which in turn triggered an overflow interrupt. This indicated to the CPU that no wall was detected.
After servicing each interrupt, the CPU selected the next TX/RX pair to repeat the whole measuring process. In other words, the whole system cycled through the four TS/RX pairs in a sequential fashion, almost like an ultrasonic radar sweep.
The control circuit, the transmitter circuits and the receiver circuits were implemented on independent circuit boards. The four receiver circuits were assembled on separate PCB modules. The four transmitter circuits were integrated on a single board. The control circuit board acted as a motherboard. It had five sockets to accommodate the transmitter and the four receiver boards. Figures 6 to 11 illustrate the schematics and the PCB layouts developed in Protel 98.
This separate module approach of implementing the sensor circuit was intended to minimize noise pick-up in the receiver circuits. The receiver circuits were sensitive analogue systems, therefore it was important to keep them separated from the digital devices.
Figure 12 shows the assembled sensor circuit, sitting on top of the Micro Mouse robot. The four receiver modules were slotted into the control board on the left. The transmitter circuit board was slotted in the centre. The large electrolytic capacitors on the right filtered the 12 V supply which powered the sensor boards. The grey ribbon cable at the bottom was connected to the Micro Mouse's CPU board underneath, as seen in Figure 13.
The sensor system worked quite well without too much modifications to the original design. It was immune to sound noise generated by devices such as ringing mobile phones, background music, and so forth. But the sensors did respond to ringing keys and shattering glass. Since the last two situations occur rarely, it wasn't necessary to provide any form of filtering for the system.
A stable measurement could be obtained up to 1 meters, which was more than enough for enclosed environments such a maze. In ideal situations, the front and back sensors responded to distances up to 2.5 m (measured by a ruler). However, it was impossible to measure distances more than 1.410 m using the CPU, because the 8-bit counter would overflow before the receiver circuit could detect an echo. The closest distance that could be measured was around 7 mm on average; walls any closer would start to muffle the transmitted signal and the echo would also drop in strength. This was an unavoidable effect caused by the physical separation between the transmitter and receiver modules.
The accuracy of the system was typically around ±5 mm for distances between 10 and 100 mm. This was sufficient to keep the Micro Mouse away from the walls. However, the error margin increased beyond 100 mm, reaching as high as ±15 mm at distances around 200 mm.
There were some undesired situations where stray reflections would interfere with the measurements. For example, posts that kept the walls in place also have a groove which acted like reflectors. Since sound waves tended to spread out a little, some would clip a corner post and produced a stray echo as shown in Figure 14.
To combat stray reflections, plastic earlobes were attached to the transmitter module in order to keep the sound somewhat more directional (see Figures 15 and 16). However, this solution came at a cost. It occupied a significant amount of room in confined spaces, leaving less space for the robot to manoeuvre around, as seen in Figure 17. Unfortunately, this became the downfall for our mouse project.
There was also a rare bug in the system, which caused the sensors to stop responding at random. The cause for this bug is still unknown, although the bug is suspected to be located in the actual software driver.
3 Motion Control
Andrew took charge of the motion control aspect of the mouse. The robot was driven by two independent motors, which in turn were controlled by two independent HCTL-1100 devices. These were interfaced with the CPU, allowing programmers to issue various motion control commands directly to the chips.
The HCTL-1100 was capable of providing position and velocity control for various motor types, including DC, DC brush-less and stepper motors. It also featured four control modes, including Position Control, Proportional Velocity Control, Trapezoidal Profile Control (for point to point moves), and Integral Velocity Control with continuous velocity profiling using linear acceleration.
It was necessary to implement an algorithm that allowed the mouse to perform basic tasks such as moving backwards, forwards and perform 90° turns. It was also necessary to add safety code that prevented potential damage to the HCTL-1100 chips in case of a stall (i.e.. wall collisions). Furthermore, these safeguards also prevented the mouse from being physically damaged due to sudden acceleration. These motor controllers were quite powerful; mice shooting off the table during testing was not unheard of. Thankfully our team did not experience this misfortune.
Figure 18 shows the top level algorithm that managed the motion control. It was quite straightforward, the main loop checked for a stall condition (or collision); then the program obtained the sensor data to see how close the walls were; then finally moved the mouse forward. In the case of a stall, the mouse would stop and the motion controllers were shut down. If the robot was too close to a wall, the program would adjust its position in the maze room to prevent collisions.
4 Maze Navigation
The maze navigation was a fundamental aspect of this project that could not be overlooked. Peter took charge of its implementation.
The basic idea was letting the mouse loose at the corner of the maze, allow it to explore the maze until it located the goal in the centre. Once the maze was solved, the mouse was supposed to perform a "fast run" back to the starting position.
Various algorithms were investigated that appeared to be a possible solution for the maze solving problem. These included Bellman's Advance Algorithm, Tremaux's Algorithm and the Blind Alley Filler Algorithm. Some of these algorithms were quite advanced and required a substantial amount of memory.
The memory budget on the Micro Mouse was rather limited. Hence, our team opted for a custom algorithm that was fairly robust and simple to implement. The algorithm can be described as follows:
The maze was divided into 16 x 16 cell blocks (or rooms). Each cell was given a number, indicating the number of times the cell was visited by the mouse. The initial state of each cell was reset to zero.
As the mouse visited each cell, the algorithm incremented the cell's count, giving it a lower priority. Therefore, cells with a lower count had a higher priority, which influenced the robot's decision making while the maze was explored.
When the mouse faced the decision of taking two or more possible directions, it would choose the cell that was either not visited before or had a lower count.
When faced with the decision of two or more equally weighted possible routes, the cell closer to the centre of the maze was given a higher priority.
During the exploratory stage, the cells that directed the mouse to the centre of the maze were now assigned with a non-zero count. These cells allowed the mouse to navigate back to the starting position during the "fast run" phase. It simply followed the cells with the lowest count, excluding the unexplored regions assigned with zero. If the mouse encountered a junction with equally weighted cell values, it would temporarily revert back its main maze solving algorithm for finding the way back home.
The overall performance of the Micro Mouse during the experimental stage was surprisingly successful, considering the problems our team encountered with the ultrasonic sensors. The robot managed to explore the maze effectively and reached its target in the centre.
Unfortunately, the mouse robot did not perform as well during the evaluation (or assessment) stage. The final maze configuration was rather challenging for the Micro Mouse. One portion of the maze had dead-end passage, which included a junction leading to more dead-end regions. The mouse could not successfully exit this region, because there were no guiding walls that would keep the robot aligned in the centre of the path. The mouse eventually clipped one of the wall posts and became stuck. The robot was given several attempts to run the maze, but unfortunately none of those attempts were successful. This was a rather disappointing result.
This experience illustrates that using ultrasonic methods can be problematic when it comes to accuracy and reliability. Ultrasonic sensors were effective as far as maximum range is concerned; however, such systems are plagued with issues relating to beam directionality and picking up interference from stray echoes.
Perhaps a laser or infra-red based system (such as the ones used by rival teams) would have been a better choice. We were quite impressed with most optical implementations used by rival teams. Of course, their maximum range was more limited than ours, but it seems accuracy rules over range when it comes to a tight maze environment.
Those who are attempting to undertake a similar acoustic project should consider using smaller ultrasonic transmitter and receiver modules. The larger transducers used in this project had a cross section of approximately 15 mm and were roughly 10 mm high. The smaller transducers were half that size at the expense of signal sensitivity.
The physical size of the sensor hardware within a maze will have a significant influence on the manoeuvrability of the robot. Free space around the robot becomes especially important if the sensor hardware exhibits a large margin of error. Measurement errors can impede alignment accuracy of the robot within the maze cell, and bulky hardware can increase the chance of collision. Alignment accuracy can also influence room tracking ability and cell count accuracy — all of which is essential for solving the maze during the exploration stage.