Embedded Motion Control 2015 Group 3: Difference between revisions

From Control Systems Technology Group
Jump to navigation Jump to search
Line 276: Line 276:


Main reason for failure is thought to be the node placement. The first T-junction that the robot encountered made PICO go into its collision avoiding mode, which might have interfered with the commands to place a node. It is also possible that this actually happened, but that the localization went wrong because of all the lateral swaying to avoid collisions with the wall. It was clear that the combination of localisation, the maze-solving algorithm and the situation recognition by LRF was not yet ready to be implemented as a whole. Therefore, we decided to make the second run with a more simple version of our software, running only the core-modules that were tested and found to be reliable.
Main reason for failure is thought to be the node placement. The first T-junction that the robot encountered made PICO go into its collision avoiding mode, which might have interfered with the commands to place a node. It is also possible that this actually happened, but that the localization went wrong because of all the lateral swaying to avoid collisions with the wall. It was clear that the combination of localisation, the maze-solving algorithm and the situation recognition by LRF was not yet ready to be implemented as a whole. Therefore, we decided to make the second run with a more simple version of our software, running only the core-modules that were tested and found to be reliable.
== Run 2==


= Experiments =
= Experiments =

Revision as of 21:40, 22 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:

  1. The laser data from the laser range finder
  2. 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.

  1. Scan directly gives information to 'drive'. Drive uses this to avoid collisions.
  2. The scan sends its data to 'decision' to determine an action at a junction for the 'drive' block.
  3. 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.

Detecting doors

PICO has to be able to detect and open doors to get tot the end of the maze. Before opening a door, it has to be detected first as a possible door or a dead end. The door can be dectected using the LRF data using a specific profile which qualifies as a door or a dead end. By sending the door request and waiting for a few seconds, PICO will detect whether it is a door or not. If it is a door, PICO must go thru, if not, PICO has to turn around and keep searching for an other door.

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.

...

A-maze-ing Challenge

For the a-maze-ing challenge we decided on using two versions of our software package. In the first run (see section Video's further down on the page), we implemented Tremaux's algorithm together with a localiser that would together map the maze and try to solve it. Our second run was conducted with the Tremaux's algorithm and localisation algorithm turned off. Each time the robot encountered a intersection, a random decision was made on where to go next.

Run 1

The first run is taped on video and can be seen here. The robot recognizes a four-way cross-section and decides to turn to the left corridor. It then immediately starts do chatter as the corridor was more narrow than expected. Next, it follows the corridor smoothly until it encounters the next T-juction. The robot is confused because of the intersection immediatly to its left. After driving closer to the wall, it mistakes it for a door. Because it (of course) didn't open, it decides to turn to right and explore the dead end. In the part between 20 seconds and 24 seconds in to the video, the robot is visibly having a hard time with the narrow corridor. It tries to drive straight but also evade the walls to the left and to the right. It recognizes another dead-end and turns around swiftly. It crosses the T-junction again by going straight and at 43 seconds it again thinks it is in front of a door. After ringing the bell, it waits for the maximum of 5 seconds that it can take to open the door. Now, it recognized that also this is a dead-end and not a door. After turning around it drives back to the starting position. Between 1:11 and 1:30, it explores the edges that he has not yet seen. Here, the Tremaux's algorithm and the localiser 'seem' to be doing their job just fine. Unfortunately, as can be seen in the rest of the video, something went wrong with the other nodes to be placed. It decides to follow the same route as the first time, fails to drive to the corridor with the door in it and eventually got stuck in a loop.

Main reason for failure is thought to be the node placement. The first T-junction that the robot encountered made PICO go into its collision avoiding mode, which might have interfered with the commands to place a node. It is also possible that this actually happened, but that the localization went wrong because of all the lateral swaying to avoid collisions with the wall. It was clear that the combination of localisation, the maze-solving algorithm and the situation recognition by LRF was not yet ready to be implemented as a whole. Therefore, we decided to make the second run with a more simple version of our software, running only the core-modules that were tested and found to be reliable.

Run 2

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

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

Videos

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

Maze challenge: Tremaux's algorithm, but failing to solve the maze. June 17, 2015.

Maze challenge: Winning attempt! on June 17, 2015.

Archive

This page contains alternative design that is not used in the end. To see what we have worked on during the entiry process, it can be interesting to look at some of these ideas.

EMC03 CST-wiki sub-pages