Embedded Motion Control 2015 Group 3
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 | |
|---|---|---|
| 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
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:
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:
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.
- 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.
The composition pattern of the drive block:
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.
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
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)
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].
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.
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.
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 [url:https://www.youtube.com/watch?v=fzsNA2OUwww here]
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.
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
- Drive <-- empty
- Scan
- Decision
- Mapping
- Experiments
- Archive
- Integration <-- needed?
- Localisation