Embedded Motion Control 2012 Group 7

Group Info

Group Members -	email (at student.tue.nl)	Sofware status
Siddhi Imming	s.imming	All software installed
Bart Moris	b.moris	All software installed
Roger Pouls	r.c.e.pouls	All software installed
Patrick Vaes	p.r.m.p.vaes	All software installed

Tutor

Rob Janssen - R dot J dot M dot Janssen at tue dot nl

Planning

General	Weekly meetings with group on Tuesday, Wednesday and Thursday. At least a weekly update of the wiki. Tasks are divided weekly.
Week 3 (7 may)	Write code to create a 2D map from the laser data. Write code for position control. Read chapter 9 from the book.
	Navigation team	Image processing team
Week 4 (14 may)	Recognize the direction of walls Recognize opening in walls	Install webcam in ROS gscam. Get familiar with openCV for image processing.
Week 5 (21 may)	Write code for the navigation for the corridor competition. Make sure the Jazz recognizes exits. Prepare the lecture.	Make algorithm in MATLAB on example images. Prepare lecture.
Week 6 (28 may)	Give the lecture. Finish and test the navigation for the corridor competition. Make sure Jazz takes the first exit.	Implement MATLAB algorithm in ROS with openCV.
Week 7 (4 jun)	Corridor competition. Write code for image recognition. Make sure arrows and their pointing direction are recognized. Discuss and choose a strategy for solving the maze. Start implementing the strategy into the navigation code.	Test algorithm with the Jazz Robot. Make images with Jazz Robot and test in MATLAB. Improve algorithm and test on Jazz Robot.
Week 8 (11 jun)	Continue implementing the strategy into the navigation code.
Week 9 (18 jun)	Finish implementing the strategy into the navigation code.
Week 10/11 (25 jun / 2 jul)	Final competition.

Progress

Week 1 + 2

	Ubuntu installation	Eclipse installation	Jazz Simulator installation	C++ tutorial	ROS tutorial
Siddhi Imming	Done	Done	Done	Done	Done
Bart Moris	Done	Done	Done	Done	Done
Roger Pouls	Done	Done	Done	Done	Done
Patrick Vaes	Done	Done	Done	Done	Done

Goals

Our main goal is to be able to solve the maze Jazz will be faced with during the final competition. As the philosophy in the world of robotics and also behind the ROS platform is to share knowledge and to use knowledge of others in order to speed up the design process. Of course, we take care of not just plugging in some code designed by others without really understanding what is going on and on what principles the process is based on. So our focus will be on designing a robust and fast navigation algorithm, rather than designing all kinds of new implementations of really nice functions that are already available for ROS.

Program structure

The scheme above shows the first proposal of the components of which the final program will consist. A more detailed overview will be published in the coming days or week(s). The components in grey are considered to be not very important in order to successfully complete the corridor competition. However, these components are necessary for a successful completion of the final competition.

Maze solving Algorithm's

There are many ways to solve a maze. These ways of finding the exit are translated into algorithm's. An overview of these algorithm's is given here: [1]. Based on this website and on the results shown in the paper "Simulated Maze Solving Algorithms through Unknown Mazes", presented in this pdf-file: [2], we probably will tackle the problem of solving the maze by means of the so-called Tremaux's Algorithm. As a backup plan the Wall follower algorithm is chosen.

Tremaux's Algorithm

The Tremaux's Algorithm solves a maze by marking how many time a passage has been passed, when a junction is encountered that is not visited yet a random passage is chosen. If the junction is visited before the passage with the lowest counts of visits is chosen (if there are multiple options a random choice between these options is made). Exception to this is if the passage which we are arriving from is only visited once, then we will go back through the same passage, this is to avoid going around in circles.
An example of a maze solved by the Tremaux's Algorithm is shown below, the green markers indicate a decision not made random but based on the number of visits of all the possible passages.

Wall follower algorithm

The Wall follower algorithm is a very simple algorithm to solve a maze. In the beginning a wall is chosen and this wall is followed, basicly this means start moving through a passage and if a junction is encountered alway turn right (or always turn left) if possible. Disadvantage of this algorithm is that it does not always find a solution, but the great advantage is that it is very simple to implement because it does not require a memory of which passages have been visited.
An example of a maze solved by the Wall follower algorithm is shown below.

Arrow recognition

The detection of the arrows will be done by detecting the corners of the arrow. First, we did a simple test in Matlab with a photo of an arrow, using the Image Processing toolbox of Matlab. And now we are trying to write a corner detection algorithm for ROS. Probably using the "cornerSubpix"[3] function of the OpenCV library. We will use a simple webcam to test our algorithm. To be able to use a webcam in ROS the following tutorial is followed: [4].

Update* We will only check for arrows in the neighborhood of a junction, to avoid unnecessary image processing. Only a the time that a t-junction is detected by Jazz the Arrow algorithm will be called. Then the Arrow algorithm should detect the possible arrow between 1.2m (when the t-junction is detected) and 0.5m (when Jazz is commanded to take a turn) before the wall. How the arrow will be detected is described in 7.1, in this section a brief summary of the Arrow algorithm is given.

Compensate for distortion (fish-eye effect)

The provided images taken with the camera of Jazz have not a really high quality partially due to the so-called fish-eye effect which causes a distortion. Distorted arrows may be hard to recognize and as the camera properties will most likely not change, we have planned to solve this issue by correcting the distortion by a calibration as is described on this webpage: Information on distortion Correction

7.1 Arrow algorithm

Step 1.) Convert image to HSV image

HSV varies the hue component of the hue-saturation-value color model. The colors begin with red, pass through yellow, green, cyan, blue, magenta, and return to red. The advance of using HSV is that you can use a color for different illuminations by using a hue and saturation value.

	H = 180° (Cyan)					H = 0° (Red)
V \ S	1	¾	½	¼	0	¼	½	¾	1
1
⅞
¾
⅝
½
⅜
¼
⅛
0

	H = 210° (Blue-Cyan)					H = 30° (Yellow-Red)
V \ S	1	¾	½	¼	0	¼	½	¾	1
1
⅞
¾
⅝
½
⅜
¼
⅛
0

	H = 240° (Blue)					H = 60° (Yellow)
V \ S	1	¾	½	¼	0	¼	½	¾	1
1
⅞
¾
⅝
½
⅜
¼
⅛
0

	H = 270° (Magenta-Blue)					H = 90° (Green-Yellow)
V \ S	1	¾	½	¼	0	¼	½	¾	1
1
⅞
¾
⅝
½
⅜
¼
⅛
0

	H = 300° (Magenta)					H = 120° (Green)
V \ S	1	¾	½	¼	0	¼	½	¾	1
1
⅞
¾
⅝
½
⅜
¼
⅛
0

	H = 330° (Red-Magenta)					H = 150° (Cyan-Green)
V \ S	1	¾	½	¼	0	¼	½	¾	1
1
⅞
¾
⅝
½
⅜
¼
⅛
0

Step 2.) Convert red pixels to black and white image

From the HSV image we create a black and white image (binary image). In the tables above you can see which values to use if you only want to find red arrows. We implemented a track-bar for each parameter to find easily the ideal parameters settings for a variety of conditions. This resulted in the following boundaries for each parameter:

$[math]\displaystyle{ (H \leq 8 \vee H \geq 352) \land S \geq 0.3 \land V \geq 0.5 }[/math]$

Step 3.) Filter noise

We use the Erode[5] and Dilate[6] filter to filter out small red objects. Erosion shrinks image objects while dilation expands them.

Characteristics of Erosion

Erosion generally decreases the sizes of objects and removes small anomalies by subtracting objects with a radius smaller than the structuring element.
With grayscale images, erosion reduces the brightness (and therefore the size) of bright objects on a dark background by taking the neighborhood minimum when passing the structuring element over the image.
With binary images, erosion completely removes objects smaller than the structuring element and removes perimeter pixels from larger image objects.

Characteristics of Dilation

Dilation generally increases the sizes of objects, filling in holes and broken areas, and connecting areas that are separated by spaces smaller than the size of the structuring element.
With grayscale images, dilation increases the brightness of objects by taking the neighborhood maximum when passing the structuring element over the image.
With binary images, dilation connects areas that are separated by spaces smaller than the structuring element and adds pixels to the perimeter of each image object.

Step 4.) Find biggest contour

We search in the binary image for closed contours, i.e. for object pixels that are connected with each other, using the FindContours[7] function of OpenCV. For each contours we calculate the area and store the biggest contour. We use a threshold value (a minimum area) the biggest object must have to proceed with the algorithm. Since from a far distance the shapes of an arrow are not clearly visible. This is also prevented by only calling the Arrow algorithm at a short distance from a t-junction. Since only the biggest contour remains the residual noise is filtered out and only a possible arrow is left.

Step 5.) Match the shape of the contour with a template arrow

Step 6.) Determine the arrow and direction with Rotation invariant moments (Hu)

It is possible to calculate moments which are invariant under translation, changes in scale, and also rotation. With these moment we can determine if the contour is a arrow. It is also possible to determine the direction of the arrow.

Overview proces

Original image

HSV image

Binary image

Filtered image

Biggest contour

Navigation

Line Detection

To help Jazz driving straight through corridors and detecting junctions a line detection algorithm is implemented. The hough transform algorithm is the algorithm we have chosen for this, how this algorithm works and is implemented is explained here. For every point that is detected by the laserscanner lines are drawn through that point with different angles, the distance perpendicular to the line is then measured. If for a certain angle the distances for two points are the same, these points are on the same line. This is further explained with some pictures.

From this example can be concluded that the points or on a line with angle 45° at a distance of 7. Of course in reality more lines per point are calculated depending on the required accuracy. Also the distance does never exactly match because of measurement noise and the fact that real walls are never perfectly straight. Therefore the distance does not have to be exactly the same but has to be within a certain tolerance.

How this works for the real laserdata is explained with some pictures. First for every point the distance is plotted as a function of the angle. This angle goes from 0 degrees to 180 degrees in steps of the desired accuracy. This range can describe all possible lines like shown in the pictures below.

The implementation of this algorithm is now further explained with a captured frame of the laserdata shown below.

First all the angles and distances for each point from the laserdata are calculated, then a raster is created with all possible lines. Each element of this raster represents a line with a certain angle and a certain distance to Jazz (measured perpendicular on the line). The size of the elements of this raster depends on the tolerances for the distance and angle that have been set. The number of points inside each element is counted. When the number of points is more than a certain threshold this is considered to be a line.

The first plot shows a graphical interpretation of all the lines that are calculated for each point. The second plot shows the raster and its elements, the points within each of these elements are counted. The elements which hold at least a certain amount of points represent a line, these are the peaks shown in the last figure.

Extraction of start and endpoints of the lines
The start and endpoints of a line are examined by appointing all the points from the laserscan to the lines the belong to. After this is done, two neighboring points are compared to see if there mutual distance is smaller than some tolerance in order to make sure that they lay on the same line section. For all the points belonging to one section, the first and last point are considered to be the start and endpoint of that particular section. The obtained information is sent to the navigation node which decides about the actions to take. The messages, defined by a new structure, that are sent by the line recognition node contain the number of lines, and for each line, the number of sections, and per section the coordinates of the begin and endpoint together with the number of points on the section.

Driving through corridor

To drive safeley through a corridor without colliding into walls a corridor is virtually divided into 3 different zones.

Safe zone:
This zone is in the middle of the corridor and the desired velocity here will be at maximum allowed velocity, the desired driving direction of Jazz will be straight ahead.

Attention zone:
These zones are a bit closer to the walls, therefore the desired velocity here will be half of the maximum allowed velocity, the desired driving direction will be slightly to the middle of the corridor to get into the safe zone again.

Critical zone:
These zones are so close to the wall that there is a severe risk of colliding with the walls. The desired velocity here will be set to zero if Jazz' driving direction is still directing to the wall. If the driving direction is directing from the wall the desired velocity will be half of the maximum allowed velocity. The desired driving direction will be pretty sharp to the middle of the corridor to leave the critical zone.

The zones are illustrated in the picture below.

Junction handling

In order to succesfully navigate through the maze, an appropriate junction handler has to be designed. In our opinion, the junction handling described below will do the job: There are basically 5 types of junctions Jazz will encounter during its drive through the maze as shown in the figure below. The red arrow indicates the direction from which Jazz approaches the junction. Note that a dead end is also considered to be and handeled is if it is a junction.

The recognition of the different situations is planned to do in the following manner:

First try to see if the first and last point appointed to a line at an angle of approximately 90 degrees has its first and last point approximately within the width of the corridor. This means that we have to deal with situation C.
If this is not the case, check whether the absolute value of the y position of either the first or last point of the line at an angle of approximately 90 degrees is larger than the width of the corridor > situation A or E
1. See whether all points are close to each other in y-direction. If this is the case, we are in situation A.
2. Otherwise Jazz is in situation E.
If this is not the case, check whether the absolute value of the y position of the first and last point of the line at an angle of approximately 90 degrees is larger than the width of the corridor > situation B or D
1. If all points of the line are close to each other in y-direction, we are in situation B
2. Otherwise we are in situation D

Based on the junction type detected, the appropriate action should be taken, such as drive forward, turn left/right, check for an arrow and check each passage for the number of visits.

Robustness Measures

In order to make the junction recognition robust and also working in case of minor deviations from the ideal situation we have taken some measures. The most important measures are explained below. Note that these are additions to the original proposed method, as this method worked fine in ideal cases but not for a whole maze with a seris of junctions connected to each other.

Paralell lines which are used by Jazz to recognize the walls between which it drives are limited to a distance of 1 meter, in order to make the right distinction between for example a corner and a dead end in case of coupled junctions.
Searching for an opening in the wall at 90 degrees angle is only done between the paralell lines, with an offset of 30 cm to both sides. This in order to prevent jazz from detecting an exit shifted to the side as being the current exit.
Checking for points of the line at 90 degrees to be on the paralell lines is done by taking the in to account at which side of jazz they are located (left or right). This is necessary in case jazz does noet drive through the center of a corridor.
For the check mentioned above there is also accounted for the orientation of jazz which may otherwise cause errors.
Decisions are made only after one type of exit is recognized 10 times, to prevent Jazz from taking a wrong decision if a line is once not recognized properly.
Finally, the line at an angle of 90 degrees is always the nearest line at 90 degrees, which may otherwise also cause trouble in case of connected junctions.

Simulation versus real world

Laserdata

Because we encountered some unexpected problems during the first test on the real robot we have made some modification to the simulator so it becomes a better representation of the real world. Our line detection uses the laserdata as an input and was optimized for the laserscanner of the simulator which returned 180 points. The real laserscanner returns 1080 points, which our program could not handle. To prevent this problem in the future an extra program is written that takes in the 180 points laserdata from the simulator and transforms this to 1080 points laserdata. This is done by lineair interpolation between the points of the simulated laserdata. The visualisation of the new laserdata is shown in de picture below, the red dots represent the points from the new simulated laserdata, the white dots are those from the old simulated laserdata.

Walls

We also made a corridor in the simulator that does not have perfectly straight walls, because in reality this is also not the case. For testing the robustness of our line detection algorithm this is very useful. The difference between the old and new corridor world is shown below.

Original corridor world with perfectly straight walls.

Modified corridor world with walls that are not perfectly straight.

Jazz's Blog

In this section I will publish all kinds of information on the things I am currently learning, I have learned so far and my further ambitions.

18th of June 2012 – First step towards Tremaux's Algorithm

In order to use Tremaux's Algorithm, I successfully can draw points on a map at the position I currently visit and store it in my memory. I will extend this tomorrow to coloring the full corridor and finally detecting the number of visits.

14th of June 2012 – Real world test 2

Today I had my second day of real life testing and I recognized all types of junction separately. However, some connected junctions gave some trouble but in the meanwhile I have figured out some measures to overcome the problem. There is also quite some progress made in the arrow recognition, as I can detect the arrows on almost all of the provided pictures, including their direction. I am still studying to improve the robustness and to see how I can make a map in my memory in order to apply Tremaux's algorithm. Will be continued...

12th of June 2012 – Travelled through the maze
autonomously

Finally, I have learned how to drive through the maze without any intervention from outside. I travelled through the maze by means of the wall follower algorithm, following the right wall. This strategy is also known as the right-hand-rule. I will post a video soon to give you some evidence...

Here my evidence is:

As in all cases, I can improve myself and I definetely will do during the coming days. Moreover I have planned to see if I also can learn how to apply to Tremaux algorithm to prevent endless searching in bigger mazes with more junctions and exits.

5th of June 2012 – Recognition of the junction types

Today, I have learned to recognize the different types of junctions described in the section junction handling. I have only to pay some more attention to see at which side the corner (junction type A) is directed and at which side the exit is in case of junction type E. Will be continued soon...

In the meanwhile, I have also overcome the challenge of detecting the side of the exit for junction type A and E. Now, I only have to recognize arrows and look at the map to take appropriate actions according to Tremaux's Algorithm

4th of June 2012 – I passed the corridor challenge!!

A small step for men, a huge step for me: Today I passed the corridor competition in 1 minute and 40 seconds. This was not the fastest time, but that was due to the fact that I had no time to practice due to an error. See the video below of me going through the corridor.

1st of June 2012 – Drove autonomously through the corridor and exit

I drove autonomously through the corridor and turned towards the exit. I also kept aligning myself during my drive in the corridor, such that I drove at the center of the corridor. See this video for a prove:

During the real world tests, I had a memory problem so this test failed for me but I have solved this yet. So hope for better luck on Monday. To be continued...

31th of May 2012 – Driving centered through a corridor

I made again a leap forward in solving the maze problem. I succeeded in driving at the center of the corridor and staying at the center while driving on. Hope to learn also to make a turn at a junction later today...

30th of May 2012 – Wall detection 4

Yesterday, I finally managed to find the begin and endpoints of the walls in a proper way. To see how I can detect lines now watch the video below:

Currently I am trying to figure out how I can ride through the maze without bumping into the walls while making nice corners at a junction. In the meanwhile I am also still studying how to process my camera images to detect the pointing direction of the arrows. To be continued soon...

24th of May 2012 – Wall detection 3

Today, I have detected the direction of and distance to walls, seen from processing the laser scan data. I now only have to figure out where the walls end in order to recognize an exit and pass the corridor compition succesfully!! Recognition of the end of a wall I will do by selecting the laser data points which belong to a certain line and looking at the first and last point of the selection. Therefore I also have to check whether a line is splitted in to more sections, or wheter it is just one solid line. Hope to get this done by the weekend!!

22th of May 2012 – Wall detection 2

I am still struggling with detecting all the walls from the laser scan data. I changed my plan and I will probably use a homemade piece of code to detect the lines, based on the socalled Houghtransform. I prefer this method above the ransac method, as I mentioned last week, since it is capable of detecting more lines at one evaluation. Besides, I am still trying to make the arrow recognition more robust. However, I can recognize an arrow with some images stored last week, but it does not work with all new images.

I hope to have some progress in the coming days, as the corridor competition comes closer and closer! To be continued...

18th of May 2012 – Detecting the walls

Today I managed to find the position of the walls of the corridor while I was walking through. Even without hitting the walls, which is of course a big leap forward on the way to my ultimate goal: escaping from the maze. I employed the point cloud library of ROS and especially the RANSAC method in order to detect the position of the walls.

16th of May 2012 – Thoughts about maze solving algorithms

Yesterday I watched the fairy tale ‘Hans and Gretel’ and I was intrigued by their idea to mark the path they had walked to find their way back. However they were not solving a maze, I can use this path marking to help me solve the maze. Of course, because I am a robot without arms I cannot drop pebbles like Hans did, but because I already learned how to create and remember a map, I can use this map to mark the passages I have already visited.

Because I also have to recognize walls and junction to solve the maze I am now trying to recognize lines in the laserdata which I receive from my sensors. Once I have learned all this I can use the Tremaux’s Algorithm to solve the maze. If I am not able to learn all these things in time I can use the Wall follower algorithm as a backup plan. These algorithms are further explained in the ‘Maze solving Algorithm's’ section.

11th of May 2012 - Created my first map

Today, I created my first map while being controlled by some keyboard inputs to steer forward, left and right. Here is a movie of this mapping process:

Currently, I am busy with learning how to process the map to enable navigating trough the maze. Moreover I am learning how to process images captured by my camera, such that I can recognize arrows and their pointing direction.
Next week, I'll update you about my progress...

8th of May 2012 - Learning how to make a map

Today, I have been busy with learning how I can produce a 2D map of the data I receive from all my sensors. I hope to succeed in making a map before the end of this week. Besides, I will try to succeed in driving a predefined distance or angle. This should eventually help me following the instructions of my navigation program.

I hope to have more exciting news soon...