Embedded Motion Control 2012 Group 7: Difference between revisions
(→Navigation: Added line detection algorithm) |
|||
| Line 105: | Line 105: | ||
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. <br> | 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. <br> | ||
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. | 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. | ||
<center> | |||
[[File:Solvetremaux.png|thumb|none|450px]] | [[File:Solvetremaux.png|thumb|none|450px]]</center> | ||
<br> | <br> | ||
| Line 112: | Line 112: | ||
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.<br> | 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.<br> | ||
An example of a maze solved by the Wall follower algorithm is shown below. | An example of a maze solved by the Wall follower algorithm is shown below. | ||
<center> | |||
[[File:Solvewall.png|thumb|none|450px]] | [[File:Solvewall.png|thumb|none|450px]]</center> | ||
==Image Processing== | ==Image Processing== | ||
Revision as of 14:38, 3 June 2012
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.
Image Processing
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].
Arrow recognition
We will only check for arrows in the neighborhood of a junction, to avoid unnecessary image processing. The arrows will be recognized on the basis of corners.
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 multiple 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.
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.
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. 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...