Robotix.gr

XBot: An Autonomous Mobile Robot [Part 2]

By Dimitris Xanthopoulos

1. Abstract:

This report is about an autonomous mobile robot which was designed and built in order to experiment with various navigation algorithms. The report consists of two main sections: 1) Hardware description of the robot's parts and 2) Programming techniques and algorithms that were used to implement various navigation routines.

2. Introduction:

The robot was a small two wheeled mobile platform which was controlled by a microcontroller. The robot could sense its surroundings with the aid of various electronic sensors while mechanical actuators were used to move it around. Figure 1 shows robot's design overall.

Figure 1: Design Overall

The program that each time was downloaded into the microcontroller determined the robot's behaviour. Many navigation behaviours were implemented and tested but the main effort was to enhance the robot with a self-localization (Dead Reckoning) ability. (See Chapter 4.4)

3. Hardware

3.1 Chassis, Motors, Wheels

Figure 2 shows an illustration of the robot's chassis, motors and wheels. The chassis was constructed using hardened aluminium foil and had the geometry of a circle. The drive wheels and the tail caster were sitting on the perimeter of this circle hence the robot could rotate in its own space.

Figure 2: Chassis, Motors, Wheels

Two servo motors, modified for continuous rotation, were used to manoeuvre the robot in a dual-differential drive configuration. The motors were controlled by the microcontroller using a technique called Pulse Coded Modulation (PCM) (see Appendix 8.1.). The dimensions of the wheels are shown on Table 1.

3.2 Controller Board

Based on the experience gained from the first part of the project, it was judged necessary that the limited capabilities PIC16F84 microcontroller had to be replaced with a more powerful one.

In the new design Atmega8535 Active Micro Board (shown in Figure 3) was used to control the robot. This controller board used one of the latest, fastest Atmel Mega chips, the Atmega8535 running at 16 MHz and achieving almost 16 MIPS (Million Instructions Per Second). The specific board was also chosen because of its "In-Circuit Programming" capability which made the programming and debugging of the robot fast and easy. The Atmega8535 main features are listed on Table 2. (See Appendix 8.2. for the connections between the controller's ports and the robot's peripherals)

3.3 Liquid Crystal Display

The robot was also equipped with a 4 lines x 20 characters alphanumeric LCD (Liquid Crystal Display) which is shown in Figure 4. This display was mainly used for debugging purposes and this was due to the increased code size required for the display to be controlled. The display was controlled through seven output pins of the microcontroller, using the built-in LCD library functions of the 'C' compiler used.

3.4 Infa-Red Proximity Detectors

Four Infa-Red (IR) proximity detectors, one of them shown in Figure 5, were used for obstacle detection and avoidance.

Figure 5: Infa-Red Proximity Detector

Each detector had an emitter and a receiver side. The emitter continuously emitted IR light. When an object was in front of the detector and its distance from the detector was less than 15 cm, the IR light bounced off of the object and returned back to the receiver thus making the output of the detector go HIGH. When no object was detected the output was LOW.

In the first part of the project, these detectors were mounted on the top side of the chassis and as a result some small obstacles in the robot's path could not be detected. This problem was solved by mounting the detectors underneath the chassis as shown in Figure 6.

Figure 6: IR proximity detectors mounted underneath the robot's chassis

3.5 Ultrasonic Ranging Module

The robot was also equipped with a rotating ultrasonic ranging module with the aid of which it could measure the distances of the objects in front of it. (See Appendix 8.3. for ultrasonic ranger's schematics and theory of operation).

Ultrasonic ranging (Figure 7) entailed transmitting an ultrasonic wave (a sound wave at frequencies above human hearing) and measuring the time that it took for the ultrasonic wave to reflect off of an object and return back to the origin.

Figure 7: Ultrasonic Ranging

The distance (d) of the object from the origin was proportional to the reflection time ("time of flight", t):

(1)

where v is the speed of sound: (2)

T is the temperature in °C. Assuming an operating temperature of 20 °C, the speed of sound is:

(3)

and equation (1) becomes:        (4)

3.6 Wheel Encoders

Two wheel encoders were used to accurately measure the rotation of the robot's wheels and provide feedback information about robot's displacement to the microcontroller. The key element of each wheel encoder was the optical switch shown in Figure 8. (See Appendix 8.4. for the internal circuit diagram of the optical switch)

Figure 8: Optical Switch

The operation of the optical switch was simple: whenever a photo-reflective object (such as white paper) was in front of the switch and in close proximity (approximately 10mm), the Infa-Red light emitted from the emitter was reflected back to the receiver thus making the switch's output HIGH (and vice-versa for a non-photo-reflective object). The encoders were mounted on the robot's chassis as shown in Figure 9

Figure 9: Wheel Encoders mounted on the robot's chassis

Two encoder discs of 72 alternating black and white (non-photo-reflective and photo-reflective) segments were attached to the wheels. Thus, as the wheels were rotating, the output obtained from the encoders had the shape shown in Figure 10.

Figure 10: Encoder's Output

3.7 Battery Level Sensor

A battery level sensor was implemented by simply feeding the positive battery terminal via a potential divider to one of the microcontrollers Analogue to Digital Converter (ADC) pins. The potential divider was used in order to reduce the battery voltage (13.5 Volts with the battery fully charged) to 5 Volts which was the maximum allowable input voltage to the ADC.

3.8 Passive Infa-Red (PIR) Detector

PIR detectors are heat sensitive sensors. They detect the Infa-Red light that is emitted by warm objects (like humans). The PIR detector shown on Figure 11 was used in order to detect human presence.

3.9 Line Sensor

The purpose of the Line Sensor (see Appendix 8.5. for the sensor's schematic and theory of operation) was to enable the robot to follow a black (or white) line drawn on white (or black) background.

3.10 Radio Link

A pair of Ultra High Frequency (U.H.F.) radio transmitter and receiver modules (shown in Figure 12) was used to implement a basic form of telemetry between the robot and a remote computer. The maximum data rate between the transmitter and the receiver was 160 Kbits/sec and approximately 128 bits needed in order to describe robot's status. This meant that the robot's status could be updated 160000/128=1250 times per second which was more than sufficient. Finally, using a simple helical antenna, the radio link coverage was about 300 metres in open ground.

3.11 Push-Buttons

Three push-buttons were used in order to provide a basic user input unit. Using these buttons and with the visual aid of the LCD it was possible to alter some program variables without having to reprogram the microcontroller which was very useful during debugging.

All the hardware parts described above were put together as shown in Figure 1. The next step was to write source code in order to interface the robot's peripherals with the microcontroller.

4. Programming

4.1 Advanced Line Following

In the first part of the project, a simple line following algorithm was implemented allowing the robot to follow a black (or white) line drawn on white (or black) background. This was done by continuously monitoring the two (left and right) outputs of the line sensor and accordingly turning left or right in order to keep the robot centred with the line. Although these outputs were analogue, the microcontroller "considered" them as digital due to the lack of an Analogue to Digital Converter.

Figure 13: Advanced Line Following Flow Chart

A more sophisticated line following algorithm (Flow Chart shown in Figure 13) was implemented taking advantage of the ADC embedded to the Atmega8535. The variable Error kept the difference between the two analogue outputs of the line sensor (i.e. Error = Left Output - Right Output). Ideally, when the robot was centred with the line, Error was zero. When Error was positive the robot had bore to the left and when Error was negative the robot had bore to the right. The absolute value of Error provided to the microcontroller a measure of "how much" the robot had bore from the line. Hence the robot could turn more rapidly in sharp turns and make small adjustments when it was moving in small curves.(Note: Lspeed, Rspeed in Figure represent the robot's left and right wheel speed respectively)

4.2 Obstacle Avoidance

The robot should be able to navigate avoiding any obstacles in its path. This was done using the four IR proximity sensors. The pseudo-code shown below describes how the obstacle-avoidance behaviour of the robot was implemented:

START:

• IF no obstacles detected THEN move forward (see Chapter 4.5.)
• IF obstacle detected on the left side AND no obstacle detected on the right side THEN turn right
• IF obstacle detected on the right side AND no obstacle detected on the left side THEN turn left.
• IF obstacles detected on the left AND right side THEN turn towards the opposite direction from the one that the obstacle was first detected. (i.e. if an obstacle was first detected on the right side then turn left )

Go to START

The obstacle avoidance actual routine is included in the source code on Appendix 8.6.

4.3 Distance Measuring

As mentioned before, the robot could measure the distances of obstacles in front of it with the aid of its ultrasonic ranging system. The maximum detectable distance of this system was approximately 2m (or 4m round-trip). Referring back to equation (4) the maximum time of flight, was calculated:

ms     (5)

In order to measure the time of flight an 8-bit (256 steps) timer was used. This timer increased by one every 0.063 ms and when it overflowed (after 0.063x256=16.128ms) it was automatically reset (timer = 0). Only the first 185 steps of the timer were useful since after 185 steps the measured time was 0.063x185=11.655ms which was approximately equal to the maximum time of flight. Hence the resolution of the ranging system was cm

The algorithm that was used in the distance-measuring routine is shown below:

1. The microcontroller generates three driving pulses at 40 kHz which are fed to the ultrasonic transmitter.
2. Microcontroller initiates the timer (timer=0)
3. If an echo is returned, timer stops increasing and its value represents the distance of the obstacle detected in cm (optionally output the result on the LCD)
4. If timer <= 185 go to step 3
5. If timer > 185 (i.e. no obstacle detected) go to step 1

The main drawback of the ranging system was its instability. In other words, its measurements for the same distance could differ up to 10cm. This problem was significantly reduced by taking several measurements and outputting their average.

4.4 Dead Reckoning (Lundgren, 2003)

Dead Reckoning is a process of estimating the position of a vehicle based solely on speed, direction and time elapsed since the last known position. The simplest way to implement Dead Reckoning is called odometry. Odometry is a method to provide information about vehicle displacement based on the rotation of its wheels. The rotation is measured by wheel encoders. The encoders count the number of rotations of the wheels, providing data that combined with forward kinematics equations (see chapter 4.4.2.) can be translated to information regarding the change in position and heading of the vehicle.

4.4.1 Robot's Coordinate System

Before examining the differential drive equations, a coordinate system for the robot's world had to be defined. It was assumed that the robot "lived" in a two-dimensional world. This meant that at any given time its position could be defined in terms of two-dimensional Cartesian coordinates and the direction it was facing could be defined as an angle measured from one of the axis.

Figure 14: Robot's Coordinate System

In order to keep with mathematical conventions, it was assumed that the angle that defined the orientation of the robot (θ) was measured counter clockwise from the x-axis as shown in Figure 14. It was also assumed that the position coordinates, x and y, were in metres, and that the orientation angle, θ, was in radians.

4.4.2 Differential Drive Kinematics

The theory behind differential drive kinematics is straightforward. The robot in a state of motion must always rotate about a point that lies somewhere on the common axis of its two wheels. This point is often called the Instantaneous Centre of Curvature (ICC). In order to derive the differential drive equations, the model shown in Figure 15 was used.

Figure 15: Differential Drive Model

Each wheel follows a path that moves around ICC at the same angular rate ω, thus:

(6)
(7)

where L is the distance between the centres of the two wheels (see Table 1) and are the right and left wheel speeds respectively. R is the distance from the ICC to the midpoint between the wheels. Combining the above two equations:

(8)
(9)

Two special cases had to be considered:

• :          the radius R is infinite and the robot moves in a straight line. (division by zero occurs. This must be avoided during programming)

• :        the radius R is zero and the robot rotates around its centre.

In all other cases the robot moves in a trajectory around ICC in some angular rate ω.

The next step was to find out how robot's coordinates (x,y) and its orientation (θ) changed with respect to time. If m(t) and θ(t) are the functions of time representing speed and orientation of the robot, then the solution will be in the form:

(10)
(11)

The change of orientation with respect to time is the same as the angular rate ω:

(12)

Integrating this equation yields a function for the robot's orientation with respect to time. The robot's initial orientation θ(0) is replaced by :

(13)

Since the velocity in functions (10) and (11) above simply equals the average speed for the two wheels, that is , integrating this in equations (10) and (11) yields:

(14)
(15)

Integrating equations (14) and (15), and taking the initial positions to be and yields:

(16)
(17)

The final step was to express equation (13), (16) and (17) in terms of the distances that the left and right wheel had travelled, and . This was simply done by substituting and [in equations (13), (16) and (17)] by and respectively and as a result dropping the time t to get:

(18)

(19)

(20)

4.4.3 Pulse Counting

Working from the lowest level of functionality upwards, the first thing that had to be done in order to implement a successful odometry system was accurate pulse counting from the wheel encoders. Although the encoders could measure the wheels rotation, they could not provide information about the direction of rotation. This problem was solved in programming level using the fact that the direction that each wheel should be rotating was known.

In order to monitor the outputs from the wheel encoders, Interrupt Service Routines (ISR) were used. Atmega8535 was equipped with two external interrupts (PortD, Pins 2&3) where the outputs from the wheel encoders were connected. These interrupts were set to trigger in any logical change. In other words, whenever a LOW to HIGH or a HIGH to LOW transition occurred to the encoders, the corresponding Interrupt Service Routine was called. The variables Lenc, Renc were used as counters for the left and right encoders respectively. The pseudo-code shown below describes the line sensor's left and right Interrupt Service Routines

• IF left wheel should be rotating forward THEN increase by one Lenc
• IF left wheel should be rotating backward THEN decrease by one Lenc
• IF right wheel should be rotating forward THEN increase by one Renc
• IF right wheel should be rotating backward THEN decrease by one Renc

4.4.4 Pulses to Distances Conversion

The next step was to "translate" the readings obtained from the wheel encoders into distances that the left and right wheels had travelled (). This was done in the following way:

or (21)

or (22)

where Lticks, Rticks are the number of encoder pulses since the last sampling, D is the diameter of the wheels (refer to Table 1) and resolution (=72) is the number of black and white segments on the wheel encoder discs. By combining the above two equations with equations (18), (19) and (20), the robot coordinates and orientation could be deduced.

4.4.5 The "GetCurrentPosition" Routine

The "GetCurrentPosition" routine was the centrepiece of the robot's dead reckoning ability. It accepted as inputs the readings from the wheel encoders, performed the above calculations and as result yielded the robot's current position (x, y, θ). The pseudo code shown below summarizes this routine. (See Appendix 8.6. for the actual source code of the routine)

GetCurrentPosition: START

1. Disable interrupts


2. Sample wheel encoders
   1. Lticks = Lenc
   2. Rticks = Renc
   3. Lenc = Renc = 0


3. Enable interrupts


4. Convert encoders readings into distances
   1. 
   2. 



5. Update robot's position
   1. If then the robot moves in a straight line:
      1. 
      2. 
      3. 
   1. If then the robot moves in a curve:
      1. 
      2. 
      3. 



6. Keep θ in the range 0 to 2π
   1. If  θ > 2π then θ = θ - 2π
   2. If  θ < 0   then θ = θ + 2π

GetCurrentPosition: END

Note that special care is taken in order to avoid division by zero in step 5.1.

4.4.5 Target Acquisition

Once the robot "knew" its current position, it could navigate towards a predefined point by altering its direction (θ) as necessary. This point was defined by the coordinates which were assigned with the values indicating the robot's starting point. In other words, the robot was able to make a small trip and, after a certain distance travelled, return back to its initial point. This was done in the following way:

Figure 16: Target Acquisition

Assume that the robot's position is the one shown in Figure 16. Its distance, r, from the starting point is given by:

(23)
and the angle φ is given by:
(24)

The angle ω = φ + π denotes the direction that the robot should have in order to be facing towards its starting point. The variable heading_error was defined as the difference between the angle ω and the robot's current angle, θ, i.e.:

(25)

When heading_error was positive (Figure 6) the robot's angle was smaller than the desired angle and hence a left turn was generated and vice-versa for a negative heading_error.

Combining the above dead-reckoning and target-acquisition algorithms with the obstacle avoidance behaviour (see Appendix 8.6. for the complete source code) the robot could return to its base even if obstacles were in its path. This was the most interesting behaviour of all since the robot could choose different paths on its way home depending on the obstacles that were in its path.

4.4.7 Dead Reckoning Errors

The odometry system that was implemented was not flawless. Ideally, the robot should be able to return to its exact starting position after travelling some distance. In practice though, there was always a small difference between its initial position and the arriving position. This was mainly due to the factors listed below:

• Unequal wheel diameters (very small difference)
• Uncertainty about the actual wheel diameter
• Uncertainty about the actual axle length
• Misalignment of the wheels
• Finite encoder resolution

Furthermore, the dead reckoning error grew bigger with the distance travelled (due to error accumulation). Hence the odometry system that was implemented was reliable only for short-term localization.

4.5 Going Straight

The driving servo motors, even though they were identical, did not have equal speeds for a specific pulse width (see Appendix 8.1.). For example, the maximum speed of the left servo motor was approximately 75 Revolutions Per Minute (RPM) while the maximum speed of the right servo motor was approximately 72RPM. As a result the robot slightly bore to the right even when it was supposed to move straight. This problem was solved using the readings from the wheel encoders as shown below:

1. Sample the wheel encoders
2. If  Lenc>Renc then increase right wheel speed
3. If  Lenc<Renc then increase left wheel speed
4. Go to step 1

4.6 Telemetry

Using the radio link pair, a basic form of telemetry was attempted. The purpose was to wirelessly transfer the robot's status (i.e. battery level, coordinates, orientation) to a remote computer.

The data receiver output was connected to one pin of the computer's parallel port. A basic terminal program was written in ANSI C in order to serially read the data receiver output. For that purpose very accurate timing routines (accuracy of microseconds) were required. Unfortunately though, such accurate timing routines were almost impossible in C due to other processes running in parallel with the terminal program. Hence, synchronization between the transmitter and the receiver could not be achieved and the telemetry routine was left aside.  

5. Conclusion

The robot was able to perform most of the navigation routines which were satisfactory. Some of the objectives that were initially set though could not be implemented and this was mainly due to the limited time available. Overall the project was a success partly due to the fact that experience and ideas for future work was gained.

6. References

Leang, K. (1994) "Sonar Sensor for the MiniBots",   
URL: http://www.leang.com/robotics/info/articles/minison/minison.html

Lundgren, M. (2003) "Path Tracking and Obstacle Avoidance for a Miniature Robot",
URL: http://www.cs.umu.se/education/examina/Rapporter/465.pdf

7. Bibliography

Braunl, T. (2003) "Embedded Robotics"

McComb G. (2000) "Robot Builder's Bonanza"

Nehmzow U. (2000) "Mobile Robotics: A Practical Introduction"

Ruocco S. "Robot Sensors and Transducers"

Walters D. (2000) "Implementing Dead Reckoning by Odometry on a Robot with R/C
Servo Differential Drive", URL:http://www.seattlerobotics.org/encoder/200010/dead_reckoning_article.html

8. Appendix

8.1. Pulse Coded Modulation

The servos had a control line where a pulse was expected every 20ms. The width of this pulse determined the direction and the speed of the servo shaft as shown in Figure 17 below:

Figure 17: Pulse Coded Modulation

• A pulse width of 1.5ms made the servo shaft stay still (Figure 17a neutral position).


• A pulse width between 1.25 and 1.5ms made the servo rotate anti-clockwise.
  • When pulse width --> 1.25ms, speed --> maximum (Figure 17b).
  • When pulse width --> 1.5ms, speed --> minimum.


• A pulse width between 1.5 and 1.75ms made the servo rotate clockwise.
  • When pulse width --> 1.5ms, speed --> minimum
  • When pulse width --> 1.75ms, speed --> maximum (Figure 17c).

8.2. Ports Table

The table below shows the connections between the microcontroller's ports and the robot's peripherals.

8.3. Ultrasonic Ranger Schematics and Theory of Operation

The transmitter's schematic is shown in Figure 18 (Leang, 1994). The microcontroller was used to generate three driving pulses at approximately 40 kHz (the nominal receiver frequency). The maximum "time of flight", was 11.64ms (see equation 5).

Hence the 40 kHz driving pulses had to be repeated every 11.64mS in order to allow for the maximum detectable distance to be obtained.

The microcontroller pin could only source a few milliamps. There was the need for a current amplifier to drive the 500Ω ultrasonic transducer and hence the 2N3904 general purpose NPN amplifier was used.

Figure 19: Ultrasonic Receiver

The receiver, shown in Figure 19, (Leang, 1994) simply "listened" for the return echo after it bounced off of an object. The small echo signal, when detected, was amplified 1000 times using a standard operational amplifier (LM741). The signal was then fed into a tone decoder (LM567) which was set to lock onto a 40 kHz signal. The output from the tone decoder could be directly fed into the microcontroller. To help minimize false triggering, the output from the tone decoder was fed into a voltage comparator (LM311) which was set to trigger at the appropriate level. The output of the voltage comparator was HIGH when no echo was detected and swung LOW when an echo was detected

8.4. Optical Switch Internal Circuit

Figure 20: Optical Switch Internal Circuit

8.5. Line Sensor Schematics and Theory of Operation

The line sensor (Figure 21) operation was based on two Cadmium-Sulphide (CdS) photo-resistors (R2 - R4). The values of these photo-resistors depended on the incident to them light. When the light was dim, their values increased and when the light was bright their values decreased.

Resistors R1-R2 and R3-R4 form two potential dividers:

and similarly:                

(V=5volts)

From the above two equations o the signals ( and ) which were fed to the microcontroller pins depended on the values of and (i.e. depended on how much light was incident to them).

When the robot was centred with the black line (Figure 22a), the light emitted from the LED was not reflected back to any of the two photo-resistors: High resistance HIGH

When the robot had bore left (Figure 22b), the light emitted from the LED was reflected back only to the left () photo-resistor and hence LOW

When the robot had bore right (Figure 22c), the light emitted from the LED was reflected back only to the right () photo-resistor and hence LOW

8.6. XBot Source Code

The full source code of the bot can be downloaded here: XBot2 Source Code