# Embedded Motion Control 2012 Group 7

(Difference between revisions)
 Revision as of 12:48, 15 May 2012 (view source)S080282 (Talk | contribs)← Older edit Revision as of 16:32, 16 May 2012 (view source)S095753 (Talk | contribs) (→Maze solving Algorithm's)Newer edit → Line 100: Line 100: ==Maze solving Algorithm's== ==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: [http://www.astrolog.org/labyrnth/algrithm.htm]. 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: [http://www.astrolog.org/labyrnth/algrithm.htm]. - Based on this website and on the results shown in the paper "Simulated Maze Solving Algorithms through Unknown Mazes", presented in this pdf-file: [http://csp2009.mimuw.edu.pl/csp09vol1_v2_numbered.pdf], we probably will tackle the problem of solving the maze by means of the so-called Tremaux's Algorithm. + Based on this website and on the results shown in the paper "Simulated Maze Solving Algorithms through Unknown Mazes", presented in this pdf-file: [http://csp2009.mimuw.edu.pl/csp09vol1_v2_numbered.pdf], 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. + + [[File:Solvetremaux.png|thumb|none|450px]] +
+ + '''Wall follower'''
+ 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. + + [[File:Solvewall.png|thumb|none|450px]] ==Image Processing== ==Image Processing==

## 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 wallsRecognize opening in walls Install webcam in ROS gscam.Get familiar with openCV for image processing.Make algorithm in MATLAB on example images. Week 5 (21 may) Write code for the navigation for the corridor competition. Make sure the Jazz recognizes exits. Prepare the lecture. Implement MATLAB algorithm in ROS with openCV.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. Test algorithm with the Jazz Robot.Make images with Jazz Robot and test in MATLAB.Improve algorithm and test on Jazz Robot. 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. 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
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].

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

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