From Experimental Robotics

Introduction

The history of the DARPA challenge has revolved around traditional driving. One competition was focused on long distances and rough terrain. The other was focused on urban driving and the challenges that come with traffic rules, other vehicles, pedestrians, etc.

Our project hoped to focus on the elements of a car chase, utilising obstacle avoidance, localisation, traffic laws, distinguishing vehicles, and cooperation. Map information was to be pre-supplied, as is normal for GPS systems. We hoped to build on previous projects in this course, such as Urban Grand Challenge A and Urban Grand Challenge B.

In reality, we set the bar too high. We only ended up implementing a subset of traffic rules. Stopping at stop lines, obeying the speed limit, following lanes (generally), localising, crossing intersections, and path following. We used some of the lower level functions from last year's code, but since we were doing mapping and localisation very differently, we weren't able to use much more.

Group Members

• The Urban Challenge 2008 Project group was composed of the following individuals:
  • जयेन आशर (Jayen Ashar)
  • Andres Kauts
  • Sweta Maira
  • प्रेरक परिख (Prerak Parikh)
  • Jack Shi
  • Andrew Weale

Environment Layout

The project was carried out on Pioneer Robots within the UNSW CSE robotics lab. Our trial course involved a 7m X 7m field, marked out with white masking tape to represent roads (lanes and stop lines).

Our A4 paper sized speed signs are pasted on card board boxes and facing where the robot is expected to look as it drives.

Tri-coloured cylinder beacons around half a meter high are placed at strategic positions around the field for the purpose of localisation.

Aims

We aimed to have a robot that is able to:

• drive around the course unaided
• follow and drive in the left lane
• at an intersection, navigate through and continue in the left lane
• obey speed signs after seeing them
• follow (red and green) traffic signals at an intersection
• avoid other robots (and other obstacles)

For the above goals, we broke our aims into the follow sections.

1. Lane recognition and following
   • As the robot drives, it should be able to process its camera input to determine lane boundaries and drive within them.
2. Intersection detection and navigation
   • At an intersection, the robot should be able to correctly drive into its target 'next' lane.
3. Speed sign recognition and obedience
   • At different sections of the road, the robot should be able to correctly pick up and identify speed limit signs placed on the side of the road and adjust its speed accordingly.
4. Traffic light recognition and obedience
   • At an intersection, if there's a traffic light, it should correctly identify its state and stop if red or go if green.
5. Localization and Path Planning
   • The robot should be able to identify its current position on the map at each intersection, with the help of the beacons.
6. Obstacle avoidance
   • When a obstacle is detected in the robots driving path, the robot should be able to avoid it by either stopping or navigating around the obstacle.

Background

Lane Recognition and Following

Existing Tools

• Last year's code
  • We started by looking at last year's code Urban Grand Challenge A which is available at /data/cs4411-2007-s2/z3182217/demo/openday. Using this code and talking with Theo provided us with information with which to base our lane following code. Theo's group had done an edge detection, then used the pixels on the edges to find the white borders of the lanes. They would take the center of their image and expand to the left and right, looking for lane markings, and then, for all the rows where both a left and a right lane marking was found, would compute the average point of these rows and use that as the coordinate to head towards. Then, they would take their current coordinate, and plan to take a circular arc towards that point, maintaining their current speed and only changing their heading. If there was no right lane markings found, they would look forward to determine if they were at an intersection or in a curve.

Proposed Implementation

• Convert lane markings into solid lines, to connect dashed lines.
• Scan just one row for lane markings, since we expect there to be no "holes" in the lines.
• Use the stop lines to find intersections.
• If a lane marking isn't found on either side, we must be at an arc.

Speed Sign Recognition

Existing Tools

• One Grippered Bandit: This was a previous project of COMP4411 in which a pioneer searched for, and retrieved, coloured cans. The pioneer had to negotiate obstacles and these obstacles were distinguished by symbols that were written on them (eg, $, #). To recognise the obstacles, the group trained a Haar cascaded classifier. To recognise the coloured cans, they used pixel classification based on colour in the HSV colour-space and segment detection (blob finding).

Literature Review

• Road and Traffic Sign Detection and Recognition - Most research in this area approach sign reading as a two stage problem: sign detection and sign recognition.
• Examples of different approaches to traffic sign reading:
  • Sign detection - based on colour or shape detection.
  • Sign recognition - Neural networks, template matching, classifiers.

Proposed Implementation

• Sign detection - use OpenCVs Hough circles to detect speed signs
• Sign recognition - run a Haar classifier over the section of the image detected as a circle to read the speed sign

Localization and Path Planing

Existing Tools

• Player has an already built in amcl driver that uses the Adaptive Monte Carlo Localisation approach following the particle filter algorithm.
  • While this module has been tested to work with laser scans. It's manual mentions that it can only work with laser and sonar data, it seems that it does not take video data in a 3D environment as an input.
• Other existing projects also exists with localisation using laser/sonar data, such as the rossum localisation project. This paper describes how it works, and it can be download here.
• UNSW Robocup also use a tremendous amount of localisation to determine where the robodogs were on the field according to the cylinder deacons. Code from the competition might be use.

Literature Review

• According to the Particle Filters in Action at the UW RSE-lab RoboticsLab website of University of Washington, work has also been done on a variety of localisation techniques (including vision-based, and sonar-based ). Of which would be helpful.
• Research is also going on with Vision Based Localisation (ie: David Yuen's HomePage. However it tends to focus more on the vision aspect, exploring situations where the robot is in natural landmarks and with the use of triangulation. This will be out of the scope of this project.

Proposed Implementation

• Use particle filters for the implementation.
  • (Particle filters have advantages over extended Kalman filters (EKFs) since, with sufficient samples, they approach the Bayesian optimal estimate, so they can be made more accurate than an EKF.)
• Coloured posts on exterior corners of the map shall act as distinct points to aid the robot the process.
• If possible we plan to use the code from UNSW robocup for localisation.
• Proposed extensions
  1. Implementation of SLAM
  2. Localisation using Trilateration techniques

Obstacle Avoidance

Existing Tools

• Player provides VFH and SICKLMS 200 divers for obstacle avoidance.
• RRG Kinematix v4.0 (software package) developed at The University of Texas, Austin

Literature review and Proposed Implementation

It can be implemented in three ways:

• Using Pioneer sonar
  • Virtual force field (VFF)
    • Combines histogram grid world model with concepts of potential fields/force fields.
    • One stage data reduction.
    • Disadvantage: - tendency of robots to oscillate in narrow corridors (high repulsive forces from all the sides).
  • Vector Field Histogram (VFH)
    • Intermediate data structure called Polar Histogram is use.
    • Two stage data reduction.
    • First stage: - histogram grid --> polar histogram, Second stage: - steering control
  • Vector Field Histogram plus (VFH+)
    • Four stage data reduction.
    • First three stages: - 2D map grid --> 1D polar histogram
    • Fourth stage: - selection of most suitable direction based on masked polar histogram and cost function.
  • Histogram in-motion mapping
    • Focuses more on map building rather than obstacle avoidance.
• Using SICK LMS200 laser range finder
  • Laser Measurement System (time varying potential field algorithm)
    • Time of flight / Range
• Using Monocular Sonar Camera (visual sonar)
  • Monocular Vision - Method

• Use both VFH (sonar) and LMS (laser) for best results.

Car following

Existing Tools

• Jayen's "GPS" code from his summer work did something similar to track the location of a vehicle. He used a Kalman filter library and fed into the Kalman filter the odometry of the robot, as well as its position according to the laser. Since the cop shouldn't have access to the odometry of the criminal, it will have to rely solely on the lasers to keep track, but a Kalman filter would still enable a smooth tracking based on the laser readings and the "cop's" own odometry.

Cooperation

This section of the project shall only be considered once the main aims such as lane following and sign recognition are fully functioning. It is hoped that cooperation mechanisms will be used by the robots to communicate with their own kind, i.e. cops versus criminals. The communication between the cops will allow them to use tactics to round up the criminals. Similarly, the criminals can communicate to help each other out by providing cues to the location of cops so as to help the others avoid the cops.

Literature Review

• The thesis by Ray, Cooperative Robotics Using Wireless Communication, provides a review of the origins, approaches, behavior and communication elements involved in cooperative robotics.
  • Origins: The field of cooperative robotics began in the late 1980's with research into multiple mobile robot systems. Cooperative robotics (also referred to as distributed robotics) came about as a merging of research in single robot systems and distributed problem-solving involving non-robotic components. The work of two of the groups to first present the ideas of distributed robotic systems is outlined below.
  • Dynamically Reconfigurable Robotic System (DDRS) which allows a robot to autonomously reconfigure its parts based on the goals of a specific task. These cells communicate with each other and can approach, detach, and combine themselves in different ways depending on task definition and allowable workspace.
  • ACTor-based Robots and Equipments Synthetic System (ACTRESS) which is a distributed multi-robot system designed for maintenance tasks in nuclear power plants. The autonomous components of this system are termed “robotors” and can be mobile robots or any component that has at least two basic functions: 1) the ability to sense surroundings, make decisions, and act on these decisions and 2) the ability to communicate to other robotors for purposes of cooperation and interference avoidance.
• Approaches: Most of the work in cooperative robotics can be classified into two approaches:
  • The swarm-type approach deals with a large number of lower-level robots that are typically (though not always) unaware of each other’s actions. Cooperation occurs due to the statistical result of a large number of repeated actions.
  • Intentional cooperation, on the other hand, typically deals with a limited number of higher-level robots in which each robot is not only aware of the actions of other agents, but uses this information to determine its own best action.

• Types of robots used:
  • Homogeneous approaches consist of identical robots running identical code whereas heterogeneous robots may run different code and often have different sensing and/or manipulation capabilities.

• We would ideally like homogeneous robots for cops and criminals who have an intelligent coexistence. In the informed case robots are able to detect and yield to each other. They consequently spend less time avoiding and more time homing.

• Behaviour: There are a set of six behaviors for mobile robots interacting and moving around in a two dimensional plane.
  • Avoidance : keeps robots from hitting obstacles and other robots
  • Wandering : a behavior that keeps a robot in motion
  • Aggregation : form a group
  • Dispersion : spread out
  • Following : a behavior that is useful to avoid collisions
  • Homing : directs robots to a goal location (the goal is not always stationary)

• Communication : Two distinct types of communication are commonly used in many types of cooperative tasks, whether robotic or biological.
  • Explicit communication occurs with the sole purpose of transmitting a message, such as speech, growls, gestures, or radio transmissions. must remember that these types of communication are not always reliable in certain environments. Arkin and Diaz attempt to solve this problem in a multi-robot exploration task with the constraint that the robots must maintain line-of-sight.
  • Implicit communication, referred to as stigmergic communication in biology, occurs through an awareness of the side-effects of other actions—a “through the world” approach.

• Another research paper examined was of Cooperative Multi-Robot Box-Pushing, which deals with communication in task-sharing between two autonomous six-legged robots equipped with object and goal sensing, and a repertoire of contact and light-following behaviors. The performance of pushing an elongated box toward a goal region is difficult for a single robot and improves significantly when performed cooperatively, but requires careful coordination between the robots. They present and experimentally demonstrate an approach that utilizes cooperation at three levels: sensing, action, and control, and takes advantage of a simple communication protocol to compensate for the robots’ noisy and uncertain sensing.

Proposed Implementation

There are certain features that we would like to implement in our project.

• Intentional Cooperation
• Homogeneous robots for cops and criminals
• Intelligent coexistence
• Combination of explicit and implicit communication
• Use Push/Pull technology in communication.

Problem Decomposition

1. Lane recognition and following
   • Using previous year's code
   • Identifying lanes
   • Panning towards the road ahead
   • Controlling the motors
   • Spline movement
2. Intersection detection and navigation
   • Identifying stop lines
   • Stopping at stop lines
   • Panning the intersection for lane markings/beacons
   • Locating the lane to turn into
   • Turning into the correct lane
3. Speed sign recognition and obedience
   • Pick up speed signs
     • Colour segmentation
     • Circle detection
   • Recognise and distinguish different speed signs.
   • Change robot speed after passing speed sign.
4. Traffic light recognition and obedience
5. Localization and Path Planning
   • Holding a map representation in the system
   • Set beacons / distinguishable object at significant points on the map.
   • Beacon detection
   • Use algorithm to link detected beacons with specific intersection on the map.
   • Determine shortest path from one position on map to another.
6. Obstacle avoidance
   • Getting readings from the laser/sonar
   • Integrating with motion

(Tasks not completed are in red)

Algorithm Development

Following lanes

Identifying lanes

• Thresholding

We thresholded the image to remove any background noise, such as the ruffles in the carpet, the cabinets, the corkboard.

• Edge detection

We ran an edge detection filter to get a clearer picture of the lane markings.

• Hough lines

We found lines in the edge detected image using a Hough transform.

• Mapping from camera space to overhead space

Because pixels at the top of the camera image are further away from the camera than pixels at the bottom of the image, the overhead image has a denser set of pixels at the bottom and a sparser set at the top.

We used the formulas provided by last year's team (Urban Grand Challenge A#Navigation_map_construction) to map the lines found by the Hough transform from camera space into overhead space, so that we could see the lanes' sizes and distances, relative to the robot.

• Map to global space

The image on the right shows a rotation and translation of the image on the left to map from the local coordinate frame to the global coordinate frame.

We rotated and translated the previous image into a global map, so that our robot would, in effect, be mapping out the lanes as it drove around. We used the robot's odometry as the point of rotation/translation, so it was not very accurate.

However, only the area around the robot is used for navigation, and not images we had seen at a position several feet away, so the error in the odometry didn't affect our navigations too much, and it was not using lines far away in the camera image, so the inaccuracy of the lines detected at a distance wasn't an issue, either.

The previously mapped lines were saved and the newly mapped lines were added, to build up a complete map of the global environment. A color gradient was used to visualize the "staleness" of the encompassed lines.

With panning the camera, we also had an issue where the image given from the camera was out of sync with the pan angle reported by the robot. We tried to decrease the pan speed to minimize this issue, but it still created errors. In an attempt to compensate for this, we decided to take all the lines found in the local map, and transfer them to the global map, but when we clear the old lines, we only clear away the lines that are far from the sides of the image. The exact padding used is dependent on the pan speed and direction.

Although dashed lane markings were connected using a Hough transform, when the space in the dashes lies at the bottom of the image, there is no dash at the bottom of the image to connect, and so when we update our global map, we lost these connections that we had previously made. In an attempt to compensate for this, we decided to take all the lines found in the local map, and transfer them to the global map, but when we clear the old lines, we only clear away the lines that are far from the bottom edge of the image. This led to a lot of noise and extra lines when there were dashes at the bottom of the image. We had to hand tune this padding to try and find a good balance between the noisy extra lines, and the missing/removed lines.

• Parsing the map

The original idea was to scan a circular arc around the robot, starting in front of it. We scanned to the left and right, looking for both lane markings. But we had to give up the idea because it would pick up erroneous white pixels as lane markings.

The new method that we came up with was to scan for lane markings but this time our scan lines were perpendicular to the robot's orientation. We scanned one line at a time working our way back to the robot until it detected both lane lane markings.

Both of the above methods used more than just the current camera image and rely on the global map to provide previously seen lane markings.

Now what we do is we calculates the middle point (p,q) of detected lane by averaging the two co-ordinates of the pixels of the lane markings that we found on both sides.

In the above figure :

• (x,y) - Robot position
• (p,q) - Center point of the detected lane lines
• (a,b) - A self-adjusting point in front of the robot
• yaw - Angle from the x-axis to the line joining (x,y) and (a,b)
• alpha - Angle from the x-axis to the line joining (x,y) and (p,q)

We calculate the angle to (p,q) relative to the robot's orientation which would help it to be in the center of the lane.

• Panning towards the road ahead

We set the pan towards (p,q).

• Moving

We set the forward speed which is inversely proportional to the intensity of the angle to (p,q). We vary the turn speed which is proportional to the angle to (p,q). This effectively means that we slow down the forward speed when the robot turns.

Stopping at stop lines

• Identifying stop lines

Here what we do is we scan vertically ahead of the robot, constantly look for a stop line ahead of it. A white pixel ahead of the robot would represent a stop line. To get this information of the stop line we use the global map instead of the current camera image.

Since we are remembering a global map, we have a good idea of where the line is, even though it is out of view of the camera.

Crossing intersections

• Panning the intersection for lane markings

When we stop at a stop line, we pan the intersection. This helps us to find lane markings that we hadn't seen before, so we can see down the lane we will be turning down. (The panning also helps us to find beacons and localize (see below)). These camera images are converted and added to the global map, as above, helping to create a map we can use for navigation.

• Locating the lane's center and angle

Once we know which direction we are turning, we project a circle into the lane we are going to turn into. We assume that we are turning from the left lane into a left lane and drop the center of the circle into where we expect the center of the lane to be, assuming the robot is currently aligned to the lane it is in. We expand this circle, looking for a lane marking. When a lane marking is found, this gives us the orientation of the lane, as the line from the center of the circle to the lane marking must be perpendicular to the lane. (We assume parallel lane markings.) Knowing one lane marking and the orientation, we then search in the opposite direction (from the center of the circle, away from the found lane marking) to find a lane marking on the other side of the lane. With both lane markings, we now have the the center of the lane and the orientation, and can use this information to move into the lane.

In the above figure :

• Projected point - The center of the projected circle; where we guesstimate the center of the lane to be; where we start looking for the lane
• First lane marking found - As we expand the circle, this is the first lane marking we find
• Second lane marking found - After finding the first lane marking, we return to the projected point and expand a line away from the first lane marking
• Center of found lane markings - This is the center of the lane, and the point we head towards
• The circle in the image is just to show us the center point. The radius represents the distance from the projected point to the first lane marking, and is for debugging.

• Moving

We set our forward speed relative to the speed limit, and our turn speed relative to the angle toward the point we are moving to.

• Aligning to lane

Since we know the lane's orientation, when we reach the calculated center of the lane, if we are already aligned to the lane, we switch into the lane following state directly. Otherwise, we have a lane alignment state, in which the robot pauses and rotates on the spot to be aligned with the lane.

Speed sign recognition and obedience

Haar Classifier

The Haar Classifier is a machine learning approach for visual object detection originally developed by Viola & Jones [pdf link]. The necessary applications for implementing a Haar classifier are included in OpenCV and these were used to train a classifier for detecting, and distinguishing between, the speed signs.

Using the Haar classifier involved collecting training images, marking the training samples to create a set of images of the sign we were training for, and running the Haar training on these images. We made 1000 positive and 1000 negative images, examples of which are shown below.

The result of this was a cascaded classifier that could be used when the robot was moving around the course for the purpose of detecting signs. Signs are detected in the image from the robot's camera by running the classifier over regions of the image. The power of the Haar Classifier is that it will quickly reject regions that are highly unlikely to contain the object. It does this by making use of the cascade of classifiers. In this cascade, the early stages will quickly reject the majority of false regions and the object detection can move on to other regions. The later stages however require progressively more computational effort in order to reject the region. By doing this, the Haar Classifier will only spend substantial time on regions that are likely to contain the object being searched for.

As a general rule, the more samples we provide it, the more accurate it will be. In the Classifier example based on face recognition, 5000 positive frontal face patterns and 3000 negatives sample images were used to get a good result and took 2 days to train on a modern computer.

Hard Coded Solution

Figure 4.1 : Speed sign number 2

The speed signs used in our scenario were the numbers (1) and (2) enclosed in a circle. These numbers were printed in black on a white piece of paper and angled slightly to the ground so that they could be easily seen by the robot as it moved along the road. As part of the lane following algorithm, the robot continuously scanned the region in front of it with the camera and provided these images to the lane following algorithm. These same images were also utilized by the speed sign recognition algorithm to detect for any speed signs along the road.

With the camera images as the input, the speed sign recognition algorithm conducted several steps of processing to obtain the number on the sign. These steps involved detecting the general sign region, finding a circle in this region and then finally running a vertical line scoring algorithm to calculate the appropriate number, 1 or 2.

Figure 4.2 : Speed sign number 2 after color segmentation and circle detection

Colour Segmentation. This was the first step in the image processing and involved applying color segmentation to the camera image to filter on all white. This allowed us to pick up the white paper on which the sign was printed on. It was found that the sign would not appear as purely white by the camera because of lighting effects and other discrepancies. So we had to provide a range of color from pure white to slightly gray in order to accommodate for this color noise.

Initially only the bottom half of the image was processed for the white segments because the upper region would often have white sections of the roof, cupboards etc. This tended to create extra confusion for the later sections of the algorithm such as circle detection. In the final submission, however, we did not need to discard the top half of the image since we found that the robot was generally facing down when running in order to follow the lanes. This meant that the white color noise of the roof and lighting was not visible anymore.

Circle Detection. After selecting only the semi white regions of the image, we had a black and white image. This image was then converted into a gray image using OpenCV cvColor and smoothed using OpenCV cvSmooth so that we would not detect so many false circles. Then we ran an OpenCV HoughCircle algorithm on this cleaned image. If a circle was detected, the next stage of the algorithm, the vertical scoring, would be conducted, else the image would be discarded.

Figure 4.3 : Signal recognition - Sign 1

Vertical Line Scoring. Once a circle is detected, the vertical line scoring algorithm is run exclusively within the region of the detected circle. The basic theory behind this algorithm is that the two numbers, 1 and 2, provide different patterns of color change if a vertical line is placed over the number. With the vertical line scan: For sign (1), the vertical line would only pick up the color pattern 'white-black-white' (black for when it intersects the number one); For sign (2), the pattern would be 'white-black-white-black-white'. The implementation of this algorithm is similar to state machine where if the state is that only the first black region has been seen, a positive score is given for every black pixel seen. Once the state shifts to the second black region having been encountered (as it would with the number 2), a severe negative score is given for every black pixel seen. With multiple vertical lines being run over the entire sign region, the scores of each vertical line are added together to give an overall score. If the score is positive above a threshold, the sign is deemed to be 1. Else, if the score is negative below a threshold, the sign is deemed to be 2.

Figure 4.4 : Signal recognition - Sign 2

It is assumed by the algorithm that the signs are always upright. Figures 4.3 and 4.4 display the vertical lines in red, which is how the algorithm will process the image. To counter the issue of noise, we created a buffer to store the last 10 results returned by this module. Then take the maximum occurrence of a particular result to be the current sign reading.

Beacon Detection

Localisation Beacon

We had 4 beacons situated around the map that were used for localisation. They are all of same size and shape, the only difference being their colour coding. The colours used on the beacons were blue, pink and yellow. Beacon detection consisted of two stages:

1. Colour segmentation to distinguish between the beacons and the background.
2. Reasoning which of the four beacons could be seen in the image.

Colour Segmentation

Colour segmentation was used to detect the beacons. In order to segment the image according to colour, it is necessary to be able to distinguish between the different colours used in the beacons. The image from the camera is a three channel matrix of values where each channel corresponds to a colour value in the BGR (Blue, Green, Red) colour-space and each element of the matrix corresponds to a pixel. The image from the Pioneer robot is in BGR.

Composite image of pink pixels

The colours used on the beacons are blue, pink and yellow. In order to identify these colours it is necessary to find a reliable method of distinguishing them from the background and from each other. To investigate any separation that could be done based on the values of the BGR channels, a number of sample images of beacons were taken with the robot under varying lighting conditions in the lab. From these the coloured part of the beacon of interest was cropped out and pasted into a composite image of same coloured pixels using the Gimp image editor. The composite image for the pink coloured part of the beacon is shown in figure 4.4.

This composite image was then analysed to determine the range and frequency of values across the blue, green and red channels. The results of this for the pink coloured part of the beacon is shown below.

The data from each different beacon colour was then compared to see if they had distinct channel values. As can be seen in the plot of the results below, there was significant overlap between the different beacon colours. So it was not possible to reliably distinguish between them using the BGR image from the robot in its current form.

The HSV colour-space is an alternative representation to the BGR. Instead of storing the Blue, Green and Red values in the image, the HSV colour-space stores the Hue, Saturation and Value. The HSV colour-space is an alternative representation of colour that attempts to represent colour in such a way that the effects of variations in lighting are minimised.

OpenCV includes a function (cvCvtColor) to convert an image from the BGR colour-space to the HSV colour-space. The results of converting the BGR image from the robot to HSV and analysing the colours of the beacons is shown below. As can be seen from the figure, the separation in the Hue channel between the different beacon colours in very distinct. Using this information the different colours of the beacons can be accurately distinguished from each other. Utilising the data to place bounds on the Saturation and Value channels, the beacons could be accurately distinguished from the background.

Identifying Beacons

A method of identifying beacons was developed which used the the fact that each beacon is characterised by a sudden change in pixel value from one colour to another in the vertical direction. For example the Pink-Blue beacon has a change from pink to blue. However at the low resolution of the robot's camera this change in colour is not so dramatic. There are pixels in the transition region from one colour to the next which are a mixture of both colours. To compensate for this a section of the image was analysed at a time and if a certain percentage of the pixels in this window corresponded to a particular beacon colour, the entire window was deemed to correspond to this colour. By doing this the transition region was filtered out and there was a distinct transition from one coloured region to another. This also had the effect of filtering out most of the noise.

Whilst the algorithm was doing a pass of the image and region filling according to colour, the colour of the previous window and the current region were compared. If there was a transition from one colour to another that corresponded to a beacon (e.g. blue to pink), that beacon was deemed to have been detected.

A representation of the beacon detection is shown below. The image on the right is the original BGR image from the robot's camera. The image on the left shows the pixel values after conversion to HSV colour-space and region filling based on the percentage of positive pixels. Some false positives were picked up due to the wall however these would have been ignored because they do not demonstrate a transition from one beacon colour to another. Of course if the beacon had been adjacent to these false positives, a false detection could potentially occur.

Localisation

When the robot comes to an intersection, the driving functions stop the robot, does a camera scan from left to right, and then takes an action based on what intersection it is at. The localisation is needed to tell the robot what intersection it is currently at so that it can make an appropriate decision on what action to take next (i.e., continue straight through the intersection, turn left, or turn right).

In order to determine which intersection the robot is currently at, the localisation algorithm uses the images from the scan taken at the intersection by the Crossing Intersections module. Originally we had the robot doing a scan for localisation at the intersection in addition to the scan performed by the Crossing Intersections module but changed this to reduce redundancy.

The localisation uses the beacon detection algorithm which determines which beacons are detectable in the image. Using this information and the pan angle of the camera at the time the image was taken, the localisation module can determine which beacons are on its left, which are on its right, and which are straight ahead. By careful placement of the beacons around the course, each intersection is characterised by a different and unique combination of beacons. Comparing the beacons (and their relative location) detected at the intersection to the knowledge of the beacons and their location hard coded into the localisation module, the intersection can be determined.

Path Planning

NB: Below describes our improvement on the hard coding of the localisation module, which were not fully implemented. Hence not used in the whole application.

To tackle the problem of localisation, we first had to have a map of our streets. We decided to do this with a graph data type.

A vertex represents any position in which a robot will have to make a decision on which way to go (i.e. at an intersection). The vertexes are marked with a number on the map. Each vertex has from zero to three edges, representing the roads on the map, that will lead to other decision points. Each vertex also has data about the location of the Localisation Beacons as it sees at that particular point. This will help the robot decide where on the map it is. (The Localisation Beacons are tri-coloured half meter tall cylinders placed in strategic location on our road, see Figure 5.1).

Localisation is carried out whenever the robot reaches an intersection. It will stop, process it's current image to determine where the different beacons are, then compare it against the graphed map to determine which node it currently is on.

Evaluation

Lane detection/Mapping

• Running the code on robot - The lane detection was not very efficient because we were performing many operations on each image and the robot wasn't powerful enough to process the information as fast as we would like.
• Running on a separate computer - We had a problem of network lag while running the code on a computer.
• Consequences of either - Because we were processing linearly and not in parallel, we waited until until each image was incorporated into the global map before we looked for the lane markings. As a result, the lane markings we were looking at were out of date since the robot was in motion while we were either processing, or waiting for the image. The lane detection worked okay, as long as the robot was moving slowly to account for this.

Lane following

Once we found the lane markings, actually following the lane was also a challenge. We used a hardcoded method to move forward and turn based on the angle of the lane relative to the robot. A spline motion would have been better than this hardcoded method, but because we weren't experienced with splines, we weren't able to implement such a motion.

Intersection crossing

The circle technique for locating the lane and its orientation worked out well. However, we had to hand-tune the starting center of the circle based on the smallest and largest intersections in our map. We only had three intersections, so this wasn't too much of a hassle, but it could have been better to perform a scan of the intersection to locate the exit lanes, and then to apply the circle method to find the center and orientation of the lane. This could have also helped us in localization as we could narrow down where we were based on which turning directions were valid.

Speed sign recognition and obedience

The hard coded number detection algorithm was chosen above the Haar Training for the following reasons:

• Time Limitation. The Haar Training algorithm required a great deal of time for training depending on the stage chosen from one day to more than a week.
• Accuracy. After running the Haar Classifier on the images, it was found that while the classifier was able to pick up the signs in the images, it was unable to differentiate between the Sign 1 and Sign 2 images. It was presumed that one reason for this was because of the similarity of the two signs. It was thought that because of the choice of fonts, the one and two were looking too similar for the classifier to differentiate. Thus, it was decided that a different sign 1 would be constructed using a sans serif font instead. It was also decided at this point that it would be too tedious to go through the entire process of marking the images for the Haar training again and so the hard coded algorithm was chosen. A video of the Haar Classifier trained to detect sign 1 is available here.

Our customized algorithm on the sign detection (as described under 'Speed sign recognition and obedience' under the 'Algorithm Development' section) worked well in our situation since the robot is moving and the signs are upright. However here are a list of points to watch out for. I've also provided ways to improve it.

• Signs that are too close. For signs that are right to the side of the robot, the image is either tilted to the left or right. Since we are applying a vertical line reading process to the image it can gives error.
• Signs not front-facing. Signs that are not placed facing directly at the robot camera (i.e. signs that are placed at an angle of 45 degrees from the viewing position of the robot) means that the robot might think a (2) sign is one, since '(2)' when skewed horizontally narrow would look a lot like 'a vertical line'.

A way of improving the error for the customized algorithm could be to change the signs to 'horizontal stripes' of the same width that span the circle. This way regardless if it's slightly tiled or skewed, the vertical line detection would always see the number of stripes in the sign.

Beacon Detection

The beacon detection worked very well. The algorithm developed was able to discriminate the beacons from the background. This video of beacon detection during a pan shows the original BGR image from the robot on the left and a representation of the image used by the robot for beacon detection on the right.

While we didn't have any issues after using this algorithm. Since we didn't do any check to make sure what is being read is actually a cylinder like object - we simply check if we can read out specific color codes of the beacons while doing vertical image line scans after we have applied color segmentation and classified colors into chunks (see video mentioned above). So if there are ever cases where the background image somehow had the same color code as the beacons, it would be picked up.

Localization

Our strategy of localization was to determine what beacons were on the left of the robot, which were on the right, and which were in front. This was then compared to our hard coded knowledge of what combination of these we would expect to see at each intersection. This is different from the usual localisation strategy of finding two beacons, determining their distance and angle relative to the robot, and using knowledge about their absolute position in the world to triangulate the robots position.

The main problem with the method we used was that the robot could only localise at an intersection. Regularly the robot would mistakenly think that it was at an intersection, usually when it mistook a lane marking for a stop line. Having decided that it was at an intersection, the robot would localise. Since the localisation information hard coded into the robot is only valid at an actual intersection, it could not help the robot recover from its mistake.

The system was also restricted to it's path of travel, since its turns at each intersection is hard coded, this is where the map graph comes in to do things such as navigation of the robot from intersection to another intersection through the shortest path. However due to time constraints, it's not been fully implemented.

Conclusion

Following our project aim of building a self driving and navigating 'car like' robot, we decomposed the task into six problems. Literature review on each problem covered existing and potential solutions, of which some were used while others were completely re-evolved for a number of different reasons in our implementation. The evaluation would have given us a good idea of how each of the problem components measure, and whether it could be significantly improved via a different approach.

Overall the project went very well, we did over-estimate the amount of work we would be able to finish, but we did manage to get 4 of the 6 main problems finished.

Several issues were identified with in our evaluation process, which would give rise to future work and improvements:

• Speed sign recognition and obedience
  • The problem of Signs that are too close and Signs not front-facing can be solved by changing the signs to 'horizontal stripes' of the same width that span the circle. This way regardless if it's slightly tiled or skewed, the vertical line detection would always see the number of stripes in the sign

• Beacon Detection
  • The problem of having a background with the same color code as the beacons can be solved in several ways:
    • Do a rough check on whether the width of each of the color segments picked up for the beacon is of a similar size.
    • Use Haar Classifier.
    • Write own code to detect cylinder beacon before running color code recognition.

Of-course please note that these ideas could bring about other issues as well. For example, if we do our own cylinder beacon recognition, then we would have to take into account the tilting of the image when the robot gets real close to the beacon. So think about the solution throughly before implementing it.

• Localization
  • Auto navigation of robot according to a graph representation of map is not fully complete. The customized Graph data structure is complete, and a graph of the map with all its vertexes, edges and beacon locations for each vertex is done. The program can also tell which intersection a robot is at given the beacons observed. However, with out the shortest path algorithm and additional integration code, it won't work.
  • NOTE: during localization if using the same map as us, there could be a potential problem that vertex 1 and vertex 3 could potentially be mixed up, since they both see the 'yellow-pink' beacon to their right. We can solve this easily by having additional beacons. Or by not starting at vertex 1 and 4, and recording the last visited vertex/turning direction at last vertex to determine the next vertex.

• Traffic light recognition and obedience
  • This task in our aim was not implemented. We planned to have cards (with a big 'red' or 'green' circle) standing vertically on the side of different lanes at intersections. The robot will use color segmentation to detect these colors and run circle detection to verify that it's a traffic light. Once detected, it will stop or keep on moving.

References

DGC2008_OpenCV

Localization

Kalman Filters 1 Kalman Filters 2

Robot localization using a particle system monad

Practical Mobile Robot Self-Localization

Bayesian Filters for Location Estimation

Particle Filtering

Appendix

Contribution to wiki

OpenCV Guide:

• Detecting lines
• Detecting circles
• Haar classifier
• OpenCV Links

OpenVPN:

• new page
• CSE specific directions
• debian/ubuntu specific directions

Subversion:

• Added basic usage

Eclipse:

• new page
• installation instructions
• subversion plugin setup instructions
• subversion plugin usage instructions

Project timeline

• Week 1 (25/3-1/4): Background research, existing technologies, what and how we can do it.
  • Obstacle Avoidance - Prerak
    • overtaking
  • Localization - Jack
  • Lane following - Andres
  • Sign reading - Andrew
  • Distinguishing robots - Jayen
  • Cooperation/talking to each other - Sweta

• Week 2 (1/4-8/4): Proposal and Presentation and Experimenting
  • Running old code
    • Theodoros provided code for the openday demo of Urban Grand Challenge A. This code currently resides at File:Openday.tgz
  • DUC2008_Presentation
  • Figuring out how to save camera images to use in the Haar classifier

• Week 3 (8/4-15/4): Experimentation and familiarization
  • Presentation - All
  • Creation of physical map - Andres
  • Background lookup - All
  • More experimenting - All
  • Set up SVN - Jayen
  • Plan out code structure - Jayen

• Week 4 (15/4-22/4): Pre-Implementation
  • Familiarize ourselves with old Urban Grand Challenge A code - All
  • Pull in old code into new structure - Jayen, Prerak, Andres
  • Gather images for Haar classifier - Andrew, Sweta, Jack
  • Familiarise with OpenCV - Jack, Sweta, Andrew

• Week 5 (22/4-29/4): Post-pre-implementation
  • Locating lanes - Andres, Jayen, Prerak
  • Start Training Haar classifier - Andrew
  • Finish/clean up from previous weeks - Jayen
  • Customized sign detection - Sweta, Jack

• Week 6 (29/4-6/5): Lane Following and Haar Training
  • Training Haar classifier - Andrew, Sweta
  • Converting camera space to overhead space - Andres, Jayen, Prerak
  • Lane following - Andres, Jayen, Prerak
  • Customized sign recognition - Sweta, Jack

• Week 7 (6/5-13/5): Sign reading and mapping
  • Hardcoded Sign Reading and Interpretation - Sweta
  • Saving a global map - Andres, Jayen, Prerak
  • Create Model Map as a Graph Object and implementation - Jack

• Week 8 (13/5-20/5): Beacons and driving
  • Colour segmentation - Jack, Andrew, Sweta
  • Beacon determination - Sweta, Andrew
  • Pan camera - Jayen
  • Follow lanes - Andres, Prerak

• Week 9 (20/5-27/5): Tuning and stopping
  • Running natively on the robot - Jayen
  • Stopping at intersections - Andres, Prerak
  • Tuning sign detection - Jack, Sweta

• Week 10 (27/5-3/6): Integration and Testing
  • Crossing intersections - Jayen, Prerak
  • Localisation - Andrew
  • Speed sign tuning - Sweta
  • Demo - All
  • Presentation - All
  • Panic - All

Accessing the code

Accessing robolab from outside the uni (assume ubuntu)

Follow the directions on the openvpn page to connect to the CSE network from almost anywhere. This will enable you to access the robolab server from outside CSE (including from Uniwide).

Accessing the code from eclipse

If you have not already done so, install eclipse and the associated subclipse plugin.

• fetch the code
  • file->import
  • expand other
  • checkout project from svn
  • next
  • create a new repository location
  • next
  • svn+ssh://group03@robolab.ai.cse.unsw.edu.au/data/svn/comp4411/dugc2008
  • password: ....
  • ok
  • author name: <your name>
  • next
  • next
  • finish

Running the code from eclipse

• hit the run button (green part, not the down arrow)
• double click c/c++ local application
• search project
• double click uc2008
• run

Retrieving a new copy with subversion

locally from robolab:

svn co file:///data/svn/comp4411/dugc2008 new_directory

from elsewhere:

svn co svn+ssh://group03@robolab.ai.cse.unsw.edu.au/data/svn/comp4411/dugc2008 new_directory

File List

Makefile                      //compiles and runs
main.cpp                      //executes each piece of the code

include/globals.h             //defines the robot interface
include/sensors.h             //defines the sensor interface
include/vision.h              //defines the vision interface
include/map.h                 //defines the map interface
include/drive.h               //defines the drive interface

sensors.cpp                   //to avoid obstacles

vision/vision.cpp             //to initialize the vision
vision/image_grabber.cpp      //to grab images
vision/edge_detector.cpp      //to threshold and detect edges
vision/lane_detector.cpp      //to detect lanes and convert to overhead map
vision/color_segmenter.cpp    //to segment colors
vision/detect_landmarks.cpp   //to detect landmarks
vision/speed_sign_detector.cpp//to detect speed signs

map/map.cpp                   //to initialize the map
                              //to go from a local overhead map to a global map
map/direction_giver.cpp       //to provide directions to the driving module

driving/drive.cpp             //to initialize the driving module
driving/parse_map.cpp         //to parse the global map for information
driving/lane_following.cpp    //to follow the lane
driving/intersection_crossing.cpp//to cross intersections

utilities/Makefile            //compiles all utilities

utilities/spaceTransform.cpp  //converts from camera space to floor space
utilities/whiteDetector.cpp   //detects white lines in the image
utilities/HoughCircle01.cpp   //finds Hough circles in the image
utilities/grabImage.cpp       //grabs and saves images

Originally intended implementation

• Modules
  • Sensor model
    • Vision
      • Lane locations
      • Sign reading
      • Controls camera
    • Laser
      • Tracking criminal
      • Obstacles relative to robot
  • World model
    • Obstacles in the world
    • Self
    • Other cooperative vehicle(s)
    • Map
  • Localization
    • Pulls motor information
  • Path planning
    • Controls motors
• Connections
  • Pull technology, where the modules pull information as they need it
    • Sensor model pulls images from camera
    • Sensor model readings from SICK
    • World model pulls location from localization
    • World model pulls lane locations from sensor model
    • World model pulls criminal location from sensor model
    • World model pulls other robot(s) information from other robots
    • Localization pulls odometry from pioneer
    • Localization pulls laser readings, lane locations, signs from sensor model
    • Localization pulls map from world model
    • Path planning pulls lane locations, sign information, obstacles, criminal location from the sensor model
    • Path planning pulls map from world model
    • Path planning pulls location from localization
  • Push technology, where the modules push control to the hardware
    • Path planning pushes the motors
    • Sensor model pushes the pan tilt zoom

General Problems Encountered

There were some issues that came up during the project which hindered progress. These should be taken into consideration by other groups who want to undertake a similar project to help their work.

• Team size
  • Scheduling - It was often difficult to coordinate the different availabilities of different people so that we could all meet at the same time. It was soon seen that splitting the team into mini-teams according to the split in tasks worked out well. Those with similar available times were allocated the same task.
  • Workload breakdown - On certain tasks, it was not possible to break it up. Often it was found that when two people worked on the same code, one was usually typing, while the other checking, directing or researching. This peer-programming was quite helpful as a double checking mechanism.
• Open CV bugs
  • cvWaitKey - We had to call this function in order to get windows to appear, and it applies a delay to the program. If we set the delay too small, the program would crash. If we set it too large, the program would not be as efficient.
  • version 0.9.7 - The Hough line transform caused the program to crash with the version currently installed on the robolab machines. We had to fetch, compile, and install opencv 1.0.0.
• Network lag - The network lag was a killer. Running directly on the robot alleviated the network lag, but then we were limited by the processing power of the robot. The program would have been more efficient as a single pass on the image, rather than the multiple passes we used by calling OpenCV functions.
• Player
  • poll call failed with error [0:success] - This error plagued us as we would frequently get disconnected with this "error" message.
  • disconnects - After about two minutes, the player server would simply exit, with no error message.
• Hardware issues
  • power/cords - With only one extension cable and and a few teams working on the robots, we were often running the robots on battery power, which didn't last very long. We now have three extension cables in the lab, so the new problem is tripping over them.
  • working robots - Sometimes the robots would simply stop working. Sometimes it was the wireless networking that was out, and a reboot might fix it. Sometimes it was the control board, and the reset button found on top of the robot would fix it. On burke, the camera would always zoom in on a pan command, rendering it useless for us, but a group who only set the pan once, could use the remote to unzoom before running the rest of their program.
  • differences between pioneer 2 and pioneer 3 - The biggest difference here is that if we commanded the robot to move at a slow speed, the pioneer 2s would twitch in place, although the reported odometry would say the robot had moved. The pioneer 3s did not exhibit this behavior, but there are only two pioneer 3s

Notes from the 2007 code

Download the File:Openday.tgz.

Window1:

wget http://cgi.cse.unsw.edu.au/%7Ecs4411/wiki/images/7/7c/Openday.tgz
tar -zxf Openday.tgz
cd openday/
make
./test flinders

Window2:

ssh group03@flinders.ai.cse.unsw.edu.au
d100 --power off
d100 --power on
cd /import/robolab/home/group03/openday/
player server.conf

This code runs fine and follows a lane. It does occasionally crash, however, and is hardcoded to the map from the previous semester. Still, we get live images from the camera, it does control the pan, tilt, zoom, and it does properly control the robot.

Just a reminder though... as I told you in class, we were able to take
only left turns because our camera was stationery. The other team panned
their camera constantly and thus had a broader field of view. They also
managed to build a cooler map. See if Claude or Brad Tonkes can show you
their code - it might give you some ideas (they unfortunately did not
upload their stuff on the wiki...).

So, here's a few words about our UGC code, in case there are any questions
about the many versions of it (please be patient):

We first split the work into two major parts:
a. Lower level stuff: get info from sensors, process, control the actuators
b. Higher level stuff: have an idea about the world and the goals in life,
   get info from the lower level, update robot perception about its
   position, think what to do next, send commands back to the lower level

As it perfectly makes sense, we managed to finish and combine both parts
just one or two days before the final demo. Yet, having anticipated that,
we tried to be independent and able to present both parts.

If I am not wrong, the code we submitted is in
blahblah/z3182217/final/code (btw final should have our reports and
presentations).

So, folder demo in code contains noplanner.zip and scenario.zip which
concern just the lower level. With "noplanner" the robot will just follow
the lane it is in while "scenario" has a predefined situation with turns
and stuff (like the openday one).

Similarly, folder simulation concerns just the higher level, implemented
by Jeff in Stage, considering that the simulated laser would do the job
that the camera does for the real robots. It is an interesting application
if you like planning but I guess that you may be using SLAM...

Finally, the combined work is again in folder demo: planner01.zip and
planner02.zip (planner02 should be the same with demo02 as stated in your
wiki) - Why two files? Well, we did not make the application accept
starting positions or goals from prompt but we wanted to have more flavors
than one.

There must be a couple or readme files concerning what to do for each zip
- I hope they help.

If I am not wrong, I sent you in November some thoughts about what faults
we had and what improvements we needed. Have a look at them again - one of
them was the thing with the stationery camera, which limited the abilities
of the planner (the planner might decide to take a right turn but we could
only make left ones - we just needed one more week I think). Jeff had to
change his configuration and make only left turns. The pictures on the map
here:
http://www.cse.unsw.edu.au/~trai151/robolab.html
may show you how narrow field of view the robots have.

Notes for next year's team

Getting started

• Compile and install OpenCV 1.0.0, or use the one installed in 2008s1 group03's home directory
• Grab the code from subversion, as in Urban_Challenge_2008#Accessing_the_code
• If you have laid out your own map, you need to modify map/direction_giver.cpp for the layout of the beacons, and the intersections, and the stop lines, and the valid directions.
• Run 'make all' to compile the code
• Edit the makefile for the desired robot to control (and to point to opencv 1.0.0)
• Run 'make' to run the code locally
• Run 'make runonrobot' to run the code on the robot

Picking up where we left off

The lane following code (Parsing the map) is probably in the biggest need of help. A better lane scanning mechanism would be good, probably something similar to the circle technique used in the intersection detection (Urban_Challenge_2008#Crossing_intersections) would be good, and then using a spline motion to the located center point. Motion similar to the last year would probably also work well, and it would be simpler to implement: Urban_Grand_Challenge_A#Navigation. Other methods for improving this:

• Use the arc scanning method originally devised, but instead the arc should be flatter (Parsing the map)
• A dual scan - Once the center point is found using the current technique, another scan is done using this new center point as the projected point/(a,b)/point in front of the robot.

Another piece to change is the multiple scans over the images that is done. Incorporating all the OpenCV functionality into a single pass over the image providing all necessary information would greatly reduce the processing power needed.

A graph representing the map and its intersections, beacons, etc. would be useful, as well as an easier way to update this information, such as a separate configuration file (which could be a text file that is parsed with cin/scanf, or a c++ file). Then, we could tell the robot to go to intersection X and it would figure out the best way to get there.