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.

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.

Navigation

We will navigate based on the lines recognized from the laser scanner data. The number of lines and the specific configuration of the lines will give us information on the type of junction or corner. Based on this information, the navigator will send messages to the base_controller to take a certain action. The information obtained from the recognized lines will also provide the information to be able to drive straight between the two parallel walls.

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 he 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.

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:

http://youtu.be/_IEYQ-DFs94

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...