Revision as of 10:53, 16 June 2015

This is the Wiki-page for EMC-group 3.

Checklist Wiki contents

		$[math]\displaystyle{ {{Check}} }[/math]$
1.1	Overview software architecture and approach
1.2	How does it map to the paradigms explained in this course?
2.1	Description why our solution is awesome (nice images)
2.2	Why unique/ what are we proud of?
3.1	What difficult problems and how solved?
4.1	Evaluation maze challenge (well/wrong/why/improvements?)
5.1	videos / gifs / animations / diagrams / pictures
6.1	Link to interesting pieces of the code (use snippet system like https://gist.github.com)
6.2	Comment the code and add introduction/explanatory
6.3	Make seperate section called 'code'

Group members

Name	Student number	Email
Max van Lith	0767328	m.m.g.v.lith@student.tue.nl
Shengling Shi	0925030	s.shi@student.tue.nl
Michèl Lammers	0824359	m.r.lammers@student.tue.nl
Jasper Verhoeven	0780966	j.w.h.verhoeven@student.tue.nl
Ricardo Shousha	0772504	r.shousha@student.tue.nl
Sjors Kamps	0793442	j.w.m.kamps@student.tue.nl
Stephan van Nispen	0764290	s.h.m.v.nispen@student.tue.nl
Luuk Zwaans	0743596	l.w.a.zwaans@student.tue.nl
Sander Hermanussen	0774293	s.j.hermanussen@student.tue.nl
Bart van Dongen	0777752	b.c.h.v.dongen@student.tue.nl

General information

This course is about software designs and how to apply this in the context of autonomous robots. The accompanying assignment is about applying this knowledge to a real-life robotics task.

The goal of this course is to acquire knowledge and insight about the design and implementation of embedded motion systems. Furthermore, the purpose is to develop insight in the possibilities and limitations in relation with the embedded environment (actuators, sensors, processors, RTOS). To make this operational and to practically implement an embedded control system for an autonomous robot, there is the Maze Challenge. In which the robot has to find its way out in a maze.

PICO is the name of the robot that will be used. Basically, PICO has two types of inputs:

The laser data from the laser range finder
The odometry data from the wheels

In the fourth week there is the "Corridor Competition". During this challenge, students have to let the robot drive through a corridor and then take the first exit (whether left or right).

At the end of the project, the "A-maze-ing challenge" has to be solved. The goal of this competition is to let PICO autonomously drive through a maze and find the exit.

Design

In this section the general design of the project is discussed.

Requirements

The final goal of the project is to solve a random maze, fully autonomously. Based on the description of the maze challenge, several requirements can be set:

Move and reach the exit of the maze.
The robot should avoid bumping into the walls.
So, it should perceive its surroundings.
The robot has to solve the maze in a 'smart' way.

Functions & Communication

The robot will know a number of basic functions. These functions can be divided into two categories: tasks and skills.

The task are the most high level proceedings the robot should be able to do. These are:

Determine situation
Decision making
Skill selection

The skills are specific actions that accomplish a certain goal. The list of skills is as follows:

Drive
Rotate
Scan environment
Handle intersections
Handle dead ends
Discover doors
Mapping environment
Make decisions based on the map
Detect the end of the maze

Blockdiagram for connection between the contexts

Software architecture

The problem is divided into different blocks. We have chosen to make these four blocks: Drive, Scan, Decision and Mapping. The following is an overall structure of the software:

Cohesion of Drive-, Scan-, Decision- and Mapping block

Calibration

In the lectures, the claim was made that 'the odometry data is not reliable'. We decided to quantify the errors in the robot's sensors in some way. The robot was programmed to drive back and forth in front of a wall. At every time instance, it would also collect odometry data and laser data. The laser data point that was straight in front of the robot was compared to the odometry data, i.e. the driven distance is compared to the measured distance to the wall in front of the robot. The following figure is the result:

Difference between odometry and LRF

The starting distance from the wall is substracted from the laser data signal. Then, the sign is flipped so that the laser data should match the odometry exactly, if the sensors would provide perfect data. Two things are now notable from this figure:

The laserdata and the odometry data do not return exactly the same values.
The odometry seems to produce no noise at all.

The noisy signal that was returned by the laser is presented in the next figure. Here, a part of the laser data is picked from a robot that was not moving.

Static LRF

The maximum amplitude of the noise is roughly 12 mm.
The standard deviation of the noise is roughly 5.5 mm
The laser produces a noisy signal. Do not trust one measurement but take the average over time instead.
The odometry produces no notable noise at all, but it has a significant drift as the driven distance increases. Usage is recommended only for smaller distances (<1 m)

Software implementation

In this section, implementation of this software will be discussed based on the block division we made.

Brief instruction about one block can be found here. In addition, there are also more detailed problem-solving processes and ideas which can be found in the sub-pages of each block.

Drive block

Basically, this block is the doer (not the thinker) of the complete system. In our case, the robot moves around using potential field. How the potential field works in detail is shown in Scan. Potential field is an easy way to drive through corridors, and making turns.

Two other methods were also considered: Simple method and Path planning. However, the potential field was the most robust and easiest method.

Link to drive page

The composition pattern of the drive block:

CP of Drive

Scan block

The block Scan processes the laser data of the Laser Range Finders. This data is used to detect corridors, doors and different kind of junctions. The data that is retrieved by 'scan' is used by all three other blocks.

Scan directly gives information to 'drive'. Drive uses this to avoid collisions.
The scan sends its data to 'decision' to determine an action at a junction for the 'drive' block.
Mapping also uses data from scan to map the maze.

Composition pattern Scan

Potential field

By splitting up the received laser data from the LRF in x and y, and summing them up results in a large vector containing the appropiate angle for PICO to follow. In other words, PICO moves always to the place with the most space. Note, the actual magnitude of this resultant vector is of no importance, since the Drive block has is own conditions for setting the velocity.

In straight corridors PICO will drive in the middle in a robust manner with the help of the potential field. In the case that PICO approaches a T-junction or intersection a decision must be made by the decision maker.

Constructing virtual walls

At junctions and intersections the current potential field is unable to lead PICO to the desired direction. Therefore, an extra layer is added to the scan data which enables editing of the LRF data that pico will see. The main advantage of introducing this second layer is that the actual measured data still is availble for all different kind of processes used at different blocks. By modifying the data virtual walls are constructed, this will steer pico into the desired direction by using the potential field. The 'decision maker' in combination with the 'mapping algorithm' will decide were to place the virtual walls.

Collision avoidance

To create an extra layer of saftey avoidance collision has been added on top of the potential field. In general the potential field avoids collisions, however when constructing virtual walls fails the robot may crash into a wall and the turn of solving the maze is over. This avoidance collision is fairly easy, when the distance of multiple oextensive LRF beams is below a certain value PICO will move in the opposite direction. The usage of multiple beams is used to make this method more robust. The current parameter for activating avoidance collision is set at 30 centimeters measured from the its scanner, note that this valued is based on the dimensions of PICO.

Decision block

The decision block contains the algorithm for solving the maze. It can be seen as the 'brain' of the robot. It receives the data of the world from 'Scan'; then decides what to do (it can consult 'Mapping'); finally it sends commands to 'Drive'.

Input:

Mapping model
Scan data

Output:

Specific drive action command

Composition pattern Decision

The used maze solving algorithm is called: Trémaux's algorithm. This algorithm requires drawing lines on the floor. Every time a direction is chosen it is marked bij drawing a line on the floor (from junction to junction). Choose everytime the direction with the fewest marks. If two direction are visited as often, then choose random between these two. Finally, the exit of the maze will be reached. (ref)

Link to decision page

Mapping block

This block will store the corridors and junctions of the maze. Therefore, the decision block can consider certain possiblilities, to ensure that the maze will be solved in a strategic way.

As is said in the previous paragraph, the Tremaux algorithm is used: [1].

Map&solve algorithm (update?)

The maze will consist of nodes and edges. A node is either a dead end, or any place in the maze where the robot can go in more than one direction. an edge is the connection between one node and another. An edge may also lead to the same node. In the latter case, this edge is a loop. The algorithm is called by the general decision maker whenever the robot encounters a node (junction or a dead end). The input of the algorithm is the possible routes the robot can go (left, straight ahead, right, turn around) and the output is a choice of possible directions that will lead to solving the maze.

The schedule looks like this:

Updating the map:
- Robot tries to find where he is located in global coordinates. Now it can decide if it is on a new node or on an old node.
- The robot figures out from which node it came from. Now it can define what edge it has been traversing. It marks the edge as 'visited once more'.
- All sorts of other properties may be associated with the edge. Energy consumption, traveling time, shape of the edge... This is not necessary for the algorithm, but it may help formulating more advanced weighting functions for optimizations.
- The robot will also have to realize if the current node is connected to a dead end. In that case, it will request the possible door to open.
Choosing a new direction:
- Check if the door opened for me. In that case: Go straight ahead and mark the edge that lead up to the door as Visited 2 times. If not, choose the edge where you came from
- Are there any unvisited edges connected to the current node? In that case, follow the edge straight in front of you if that one is unvisited. Otherwise, follow the unvisited edge that is on your left. Otherwise, follow the unvisited edge on your right.
- Are there any edges visited once? Do not go there if there are any unvisited edges. If there are only edges that are visited once, follow the one straight ahead. Otherwise left, otherwise right.
- Are there any edges visited twice? Do not go there. According to the Tremaux algorithm, there must be an edge left to explore (visited once or not yet), or you are back at the starting point and the maze has no solution.
Translation from chosen edge to turn command:
- The nodes are stored in a global coordinate system. The edges have a vector pointing from the node to the direction of the edge in global coordinates. The robot must receive a command that will guide it through the maze in local coordinates.
The actual command is formulated
A set-up is made for the next node
- e.g., the current node is saved as a 'nodeWhereICameFrom', so the next time the algorithm is called, it knows where it came from and start figuring out the next step.

Link to mapping page

Localisation

The localisation algorithm is explained in the section below, by separating and discussing the important factors.

The purpose of the localisation is that the robot can prevent itself from driving in a loop for infinite time, by knowing where it is at a given moment in time. By knowing where it is, it can decide based on this information what to do next. As a result, the robot will be able to exit the maze within finite time, or it will tell there is no exit if it has searched everywhere without success.

Link to localisation page

Code

This section highlights several interesting parts of our code.

...

Evaluation Corridor- and A-maze-ing Challenge

....

Experiments

Seven experiments are done during the course. Here you can find short information about dates and goals of the experiments. Also there is a short evaluation for each experiment.

Files & presentations

Initial design document (week 1): File:Init design.pdf
First presentation (week 3): File:Group3 May6.pdf
Second presentation (week 6): File:Group3 May27.pdf
Final design presentation (week 8): File:EMC03 finalpres.pdf

Videos

Experiment 4: Testing the potential field on May 29, 2015.

https://youtu.be/UAZqDMAHKq8

@@ Line 267: / Line 267: @@
 = Evaluation Corridor- and A-maze-ing Challenge =
+....
 = Experiments =

Embedded Motion Control 2015 Group 3: Difference between revisions

Revision as of 10:53, 16 June 2015

Contents

Checklist Wiki contents

Group members

General information