Embedded Motion Control 2017 Group 1

Group Members

Name:	Student id:
Karel van de Plassche	0653197
Joey Hendriks	0773023
Ioannis-Dionysios Bratis	0978560
Jad Haj Mustafa	0979428
Jip Reinders	0853301
Juliana Langen	0988532
Yanick Douven	Tutor

 

Initial Design

Link to the PDF version of the initial design: PDF

Overview

In this article a summary of the embedded software design is presented.This software is used to solve the following problems:

1. Corridor challenge: The robot should autonomously drive through a corridor and take the first exit.
2. Maze challenge: The robot should autonomously drive through a maze and find the exit.

Requirements/Specifications

Type	Requirement	Specification
General	- Be able to 'solve' any given configuration of walls. - Do not bump into walls: Detect walls, define minimum distance. - Move autonomously: Detect openings, junctions, crossings, dead ends, open spaces etc. and make optimal decision. - Software easy to set up: As defined on general wiki page. - Only one executable is allowed. The software will be updated on the robot before the challenge starts. - Do not stand still too long: Detect time that robot is standing still, initiate movement after set time. - Stop movement after task is achieved.	- The maximal translational velocity of PICO is 0.5 m/s. - The maximal rotation velocity of PICO is 1.2 rad/s. - PICO should not stay still for more than 30 seconds. - Complete task within 2 attempts. - The LRF has a width of about 4 rad (from -2 to 2 rad), with a resolution of about 1000 points.
Corridor	- Finish the corridor challenge fast: Detect opening either on left/right, take turn, stop after finish line.	- Back wheel across finish line within 5 minutes. Terminate afterwards.
Maze	- Finish the maze challenge fast: Navigate maze, find exit, stop after finish line. - Be able to reconstruct maze. - Determine difference between dead end and door. - Deal with open spaces. - Deal with loops. - Be able to open doors.	- Back wheel across finish line within 7 minutes. Terminate afterwards. - Decide where to go when at a T-junction or crossing. - Ring a bell and wait at a dead end to check for a door.

Functions

	Function	Description
Low-level	initialize	Initialize actuators
	readSensors	Read the odometer and laser data
	turnLeft	Turn 90° left
	turnRight	Turn 90° right
	turnAround	Turn 180°
	stopMovement	Stop omniwheels
	driveForward	Accelerate or decelerate
	driveBackward	Drive backward
	driveLeft	Move left
	driveRight	Move right
	ringBell	Ring the bell of the door.
Mid-level	detectWall	Detect a wall (~30cm)
	detectCorner	Detect a corner (crossing of two walls)
	detectDeadEnd	Detect a dead end
	detectFinish	Detect the finish line
	detectOpenSpace	Detect an open space
	detectOpenWorld	Detect if in the open world (like the maxe exit)
	detectTJunction	Detect a T-junction (where three corridors meet)
	detectCrossing	Detect a crossing (where the four corridors meet)
	shutDown	Terminate robot, if required
	checkDoor	Send a signal and wait x seconds
	chooseCorridor	Choose which corridor to take
High-level	stayBetweenWalls	Stay in the center of two walls
	createMap	Build map of surroundings
	trackPath	track the path through the map
	detectLoop	Detect a loop in the maze
	detectStack	Detect if stuck
	optimalDecision	Decide next move based on given algorithm

Components

The PICO robot consists of multiple components which are listed below:

1. Sensors:
   1. Laser Range Finder (LRF): Through the LRF on the PICO one can detect the distance to an object.This is accomplished by sending a laser pulse in a narrow beam towards the object and measuring the time taken by the pulse to be reflected on the target and returned to the sender.
   2. Wheel encoders (odometry): Through the encoder one can obtain the speed of the wheels which can be used to control PICO based on the provided data.
2. Actuators:
   1. Holonomic base (omni-wheels)
   2. Pan-tilt unit for head
3. Computer
   1. Ubuntu14.04
   2. Intel I7

Interfaces

Intermediate Presentation May 14th, 2017

Presentation

The initial design was presented on May 17th, 2017. Link to a PDF copy of the presentation slides: File:Presentation EMC intermediate group 1 - final.pdf

Corridor Challenge 2017

Corridor Competition

During this competition we were supposed to have the robot autonomously drive through a corridor, identify an exit and take that exit in order to complete the challenge. The precise location of the exit as well as whether the exit is to the left or the right of the corridor are not known in advance. PICO uses the laser data for the implementation of the potential fields method in order to keep him in the middle of the corridor. Furthermore we used a sensing function to indicate whether there are walls or a gap in the corridor. Finally a state supervisor when should turn right or left according to where the exit(gap) has been placed

Navigation throughout the corridor

Potential Fields

After going through multiple ideas for moving between walls we finally decided to choose the potential fields method. The basic concept of this method is the following: For every laser point available a corresponding virtual repulsive force is applied to the PICO, that forces the robot to move away from obstacles or walls. Moreover, a virtual attractive force is applied to the robot in order to force it to move towards the setpoint, namely the desired direction. As soon as PICO gets really close to either a wall or an obstacle the repulsive forces grow bigger, whereas they become smaller when it is navigating in a safe distance from them. The exact opposite is occurring for the attractive force. Finally,The summation of the attractive force and all the repulsive forces will keep the robot in the middle of the corridor and navigating towards the given setpoint. As explained before, the potential fields method is used as collision avoidance as well, since with this method PICO will never drive into a wall.

Repulsive forces and attractive force on the robot, setpoint included.

Different weight constants were used for both the attractive and the repulsive forces as well as for the rotational and translational velocities. The total amount of forces for both the x and y direction are computed separately, and then transformed into velocities for which weighting constants are used again. By using the potential fields method the angle computed in comparison to the middle beam always tries to get a zero value and is used to compute the rotational velocity. Hence PICO will always turn in the desired direction and the bigger the angle, the faster will PICO complete the turn.The formulas for "translational","rotational" velocities are:

[math]\displaystyle{ v_x = w_{vx} * Ftot_{x} }[/math]

[math]\displaystyle{ v_y = w_{vy} * Ftot_{y} }[/math]

[math]\displaystyle{ w = w_{w} * \phi }[/math]

Finally in order to ensure that our code will work on simulations and on the actual robot all velocities are saturated within certain values, namely 0.5 m/s for the translational speed and 1.2 rad/s for the rotational speed.

The first thing we needed to test with this method was whether the collision avoidance skill works on the actual robot. After setting no setpoint, the repelling force seems to work sufficiently enough:

setpoint example chasing a carrot on a stick

By applying the potential fields method it is possible to solve a very simple maze with one possible direction to go. That is achieved by applying a small setpoint of 0.1("carrot on a stick method"), while at the same time PICO is guaranteed to never collide with the wall because of the repulsive force. A demonstration is presented below:

The potential fields code snippet is provided below:

potential fields

Sensing through Detection Circle

For the detection of the corridors, a limited range method for the laser data was used. Through this method possible corridors can be detected,which can be seen in the following figures.

The first step is to define the max range and check for all the beams which of them correspond to a lower distance than the max range.Then the maximum detection range is decreased until the percentage condition is met (60% of all beams). After that, all distances bigger than this max-range distance are adjusted to this max-range, including the very high distances. Finally an array is created that returns the number of gaps or walls, and in case of a gap it returns the x and y coordinates of the midpoint of that gap. This sensing function only sees a gap when the gap is atleast 150 lasers large: to prevent any errors due to laser inaccuracies or maze construction inaccuracies.

limited range detection.

midpoint detection.

State Supervisor

In this function the supervisor checks the number of gaps provided by the sensing function. In case there is a gap, the supervisor then checks the beams on the right and left side and according to the detected gap it decides to turn either left or right. A simulation of a corridor with a right exit is provided below.

corridor simulation with an exit on the right side of the corridor.

Midpoint Tracking

Since the sensing function always returns the x and y coordinates of the corridor’s midpoint, it can be tracked and used as new target point for our movement. During the the corridor challenge, the setpoint for the potential fields is replaced with the given midpoint. Such a simulation is provided below. Note that this movement has been slightly altered during the maze challenge. More on this in chapter “Final Presentation, Improvements”.

corridor simulation with an exit on the left side of the corridor,midpoint tracking included.

After multiple testing, we realized a possible bug by using this implementation. If there is a jump in the midpoint's distance, leading to a midpoint which is located in an inaccessible location for the robot, this implementation might force PICO to run into a wall in order to access that midpoint. However, the repulsive forces of the potential fields will prevent the robot from crushing into the walls. Nevertheless, PICO will keep tracking that midpoint and hence leading to an undesired movement. This problem was fixed during the maze challenge, where we redesigned our whole strategy.

A different method of making a turn is to use the odometry data. However, this data is deemed to be very inaccurate, thus we’ve decided not to use any odometry data at all and instead use midpoint tracking.

Corridor Challenge Evaluation

The corridor challenge occurred on May 24th, 2017 and our design achieved excellent results. We managed to get the first place of the competition with a time of 14.66 seconds on our first implementation, which at that point of time had only been tested on simulation. During our second attempt, which was tested on the actual robot, but without using a decision algorithm, we managed to complete the corridor challenge successfully within a time of 18 seconds. In order to succeed finishing the corridor competition multiple corridors were created for testing.These included different widths, for both the corridor and the exit, cracks in the walls as well as walls not correctly aligned. Out of the ideas implemented we can use the potentials fields method also for the maze challenge. The sensing function needs to be adjusted in order to detect all kinds of junctions and open spaces and the supervisor needs to be upgraded in order to to solve the maze successfully.

1st attempt:

2nd attempt:

Maze Challenge 2017

Maze Competition

The goal of this competition is to let PICO autonomously drive through a maze and find the exit. In order to solve the maze PICO must identify a door, stop within 1.3 meters of the door and ring a bell to open the door. The maze is not solvable without passing through the door. The chosen maze solving algorithm must be able to solve mazes with both loops and open spaces. Each team gets two attempts to finish the maze. Both attempts combined (if necessary) must be finished in under 7 minutes. PICO can not bump into the walls during competition.

General Layout

The figure below shows the high-level design of our final solution. It shows the information/decision flow between the various blocks of code and to/from PICO. Each block will be described in more detail below. The team also developed custom debugging tools, which will also be described below.

Software Architecture (Skills)

Supervisor

The supervisor is the part where all pieces of written code come together. The sensing module gives the lay of the land in different types points. The DoorEdgePoints and DoorMidPoints define the doors, and the EdgePoints and MidPoints define all other junctions. This information is fed to the node recognition and door recognition modules, that use it to determine the specific type of node PICO is currently facing. Based on the node type, current state, and some global variables (last target midPoint, escaping the dead ends, leaving the door area) the supervisor asks the pledge module which direction to go. Based on this direction the supervisor determines the correct state for this loop. The states defines which command has to be send to PICO base.

The idea was to have clearly defined states, with clearly defined switches between them and as less dependency (and thus maximum modularity) as possible. We also prefer for a state to only depend on the previous state, so it only depends on the state maximum 1 loop ago. However, the presence of doors, which come in two types with different strategies to pass them, made this harder. This gave rise to the sub-states: Leave door area and escape dead end. These substates also had need for remembering the state of longer than 1 loop ago. Further complication came when different parts of the supervisor were written at different times, and by different people. As a result, sometimes the decisions of the supervisor are based on the angle to objects, sometimes to cartesian distance and sometimes it is based on a specific ray. Time constraints prevented to generalize the supervisor again, but we know the separate parts were pretty robust. As such, we decided to keep the supervisor as it is.

The supervisor decision diagram in all its complexity can be found below:

.

A snippet of the supervisor is provided below:

Supervisor

Low-Level Functions

Sensing

The gap and midpoint detection was the same as the corridor challenge. See the corridor challenge section for a more detailed description of these functions.

Corners

The corner detection is performed by comparing the slope of the laser data before the point in question and the slope afterwards. If the difference is higher than a certain threshold the point is identified as a corner. More detail on this procedure is described under the door detection section.

High-Level Functions

Potential Fields

The same functions for both the repelling forces as well as the attractive force were used, since after multiple testing we are guaranteed to avoid obstacles while moving smoothly through every path.

Junction Detection

A very important part of the software is that, at every possible position the robot should always recognize all kind of features. In order to achieve that, the number of gaps provided by the sensing function is used. In addition to that, the total vision area of the robot is divided into three sub-areas, namely left, right and straight as it can be seen in the following picture.

Areas of node recognition.

Hence by using the number of gaps, the aforementioned beams and the location of the midpoint (in which of the aforementioned areas it belongs in) we can establish all types of junctions namely STRAIGHT, CORNER_RIGHT, CORNER_LEFT, T_JUNCTION_RIGHT_FORWARD, T_JUNCTION_LEFT_FORWARD, T_JUNCTION_RIGHT_LEFT and CROSS. For example the T_JUNCTION_RIGHT_FORWARD is determined by looking at the amount of gaps, namely 2. Furthermore it is decided if the first midpoint is located in the right area and the second midpoint is located in the straight area. If this is the case, then node recognizing sees the junction as a T_JUNCTION_RIGHT_FORWARD.

Besides the junctions that can appear in the maze, there are also open spaces that need to be detected. This is divided into three different cases, namely an open space on the right OPEN_SPACE_RIGHT while there is a wall on your left, an open space in the middle OPEN_SPACE_MIDDLE with no walls on the left or right of PICO and an open space on the left OPEN_SPACE_LEFT while there is a wall on your right. For example take the OPEN_SPACE_MIDDLE depicted here.

Open space in the middle.

An open space like this is defined an open space if all the laser beams corresponding to +90 degrees up until -90 degrees are at the maximum range set at 1.5 meters. This division in different cases is done so pledge can treat the different open spaces accordingly. An OPEN_SPACE_LEFT is treated as a T_JUNCTION_LEFT_FORWARD, an OPEN_SPACE_MIDDLE is treated as a CROSS and an OPEN_SPACE_RIGHT is treated as a T_JUNCTION_RIGHT_FORWARD.

Open Spaces

After the open spaces are detected in node recognising, the supervisor needs to do something with this. Pledge is called when an open space is detected to determine which direction PICO should go to. However to turn correctly in open spaces, another mechanism is needed instead of the midpoint tracking used in junctions since open spaces don't have meaningful midpoints. To track turning correctly in open spaces, any nearby corners or walls are used instead of the midpoints. This results in three different cases of which the first one is turning around a corner. This consists of 3 distinguishable stages depicted below. First it needs to track the corner on the left or right depending on the outcome of pledge (in this case on the right) which should be at a certain angle. When this is the case, PICO has moved far enough ahead to make sure it doesn’t bump into the corner. Next PICO keeps rotating until the angle θ is close enough to zero (- 20 degrees for the right turn) to indicate PICO has turned 90 degrees. After this PICO will move forward and depending on the turn it made, the turning sequence is done after the left or right laser beam (right in this case) is a wall instead of the fixed maximal range.

Turn around outer corner.

For the case when there is just a wall in front of PICO, the robot can either turn left or right. Once PICO is within 0.7m of the wall, the pledge algorithm decides whether to turn left or right. PICO now starts for example to rotate right. To make sure it turns around 90 degrees, PICO decides to stop turning when the laser at the left returns a distance of smaller than 0.7m, plus a small margin. This indicates that the wall should be at the left now, thus the turn is completed.

A different case is when there is also a wall beside PICO and a wall in front of him. For this turn the same approach is used for when there is just a front wall, but an extra state is added to prevent it stopping turning immediately. When PICO starts turning to the right for example, the most left laser should first become larger than 0.7m. Once this is true, PICO goes to the same state as the case described above, to finish the turn.

Turn around at one or two walls

When moving next to a wall and the open space is large enough, PICO doesn't always stay close or nicely aligned to the wall. To make sure PICO stays for example close to the wall at his left, the supervisor checks if the distance of the left laserbeam has become slightly larger compared to the last iteration. If this is the case and the distance to the wall has become large enough, PICO will slightly move and rotate to the left for one iteration, while also continuing moving forward. If on the other hand PICO gets to close to the wall, the potential field will simply move him back again.

alignment to the wall example

However when all these separate parts where merged together, there were some conflicts which resulted in a simulation that ended after the first turn it made. Due to the short amount of time left to fix this part, we decided to leave out the open spaces for the supervisor. PICO will continue straight within an open space until it sees a junction or a wall. This resulted in a confused PICO during the maze challenge of this year in open spaces. If however there would have been more time to fix this, it would have been nice to use these corners for junctions crossing as well instead of the midpoints. This way the turning of PICO would be a more general concept.

Dead End Detection

To detect a dead end, PICO checks the amount of gaps provided by the sensing function. If the amount of gaps is zero and the distance to the front wall is close enough, the recognized node is a dead end.

After that, PICO follows the steps for the door detection: it stops moving, rings the bell and waits 5 seconds. If the recognized node is no longer a dead end anymore, a door has been opened and PICO continues moving forward. If it’s still a dead end, PICO turns 180 degrees. The turn direction depends on the pledge function. The robot stops turning when the amount of gaps is no longer zero and when the found midpoint of a corridor is right in front of PICO.

dead end testing

Door Detection

One major challenge of solving the maze is correctly identifying a door area. The door must be identified, opened and passed through in order to solve the maze so robustly being able to identify the door is of critical importance. Several attempts were made before coming up with the final used solution.

Door Profile.

Data Jump when Approaching Door.

The first attempt involved comparing adjacent laser scan beam distances and determining when there is a jump in the data. As can be seen in the figure below as a door is approached there will be a significant jump in distance measurement of two adjacent laser beams. By identifying when this happens the first edge of the door can be identified. This was implemented in C++ code however several problems were encountered with this method. The first was that only one edge of the door could be identified with this method therefore it was difficult to determine where the middle of the door area was to determine where PICO should stop and ring the bell to open the door. The second problem was that one PICO passes this front edge of the door the jump in data does not occur anymore and the door edge must either be identified with another method or the location of the door edge must be “remembered” by PICO. The third problem is that this method only works if PICO approaches the door from a sufficiently long corridor where the door is on the side. If the door was near a junction where PICO approaches it “head on” the jump never exists so the door would never be identified. Clearly this method was not robust so a new approach was taken.

The second attempt was taken that involved identifying points at which the distances for the laser scan data switched from increasing to decreasing and vice versa. The red dots in the figure below show the points at which this would happen when PICO is beside a door. Points of increase and decrease would also occur in junctions and corners however a door area is the only feature of the maze that would produce 5 (or 4 if the door is part of a maze corner) “change points” with no large jumps in distance data between these points. Several attempts were made to implement this with PICO by summing the differentials in distance over several laser scan beams however the laser data is noisy. Even after passing the data through a Gaussian filter to remove some of the noise, the noise caused this method to be unreliable.

"Change Points" for Data Increase/Decrease.

After several unsuccessful attempts the simulation data was exported into Matlab to visualise it more clearly. The top left plot of the figure below shows the data that is gotten from PICO when a door is to it’s left. From this plot it is clear that the corners should be easily identifiable by comparing the slope of data before and after it. Other points where the data changes from increasing to decreasing and vice versa do not show such pronounced features therefore they would be very hard to identify. This also shows why attempt 2 to identify the door failed. The corners were now identified by approximating the slope of the line before the point by taking the difference of the laser scan data at this point and that of 20 points prior to it and dividing this difference by 20. The same was done but for 20 points after the point in question. The slope before and after the point was compared and if the difference was large enough it was determined to be a corner. Normally this method produced multiple points around the corner that are identified as the corner. This is shown in the top right plot. These points are further filtered by removing points that are within 7 laser beams of each other. This produces the plot on the bottom of the figure. This was the final method used to identify corners in the maze.

Door Detection Data in Matlab.

Once the corners are identified this information must be used to identify a door. In order to distinguish a door from other maze features that have corners (such as turns or junctions) the long edge and short edge of the door were sought. The data between two identified corners were checked to make sure there are no jumps in the data between these two corners. The distance between these two points was calculated. If no jumps in data occurred and the distance was between 0.2-0.5m, the short edge was found. Similarly if no jumps in data occurred and the distance was between 0.5-2m the long edge was found. If both a long edge and short edge were found and they were adjoining, a door was identified. This was the final solution implemented with PICO.

Maze Solving Algorithms

Pledge Algorithm

Last year's maze solved using the pledge algorithm

To prevent PICO being stuck in loops, the pledge algorithm was used as the decision making strategy. Pledge counts the amount of left or right turns the robot took. Based on this count, the algorithm decides whether to turn left, right or continue straight. Pledge works as followed:

• Initially the counter is 0, thus the initial direction that PICO is facing is remembered.
• Whenever the counter is 0, PICO moves straight unless this isn’t possible anymore, for example due to a right turn.
• Every time PICO turns 90 degrees right, the counter is increased by 1.
• Every time PICO turns 90 degrees left, the counter is decreased by 1.
• When for example the counter was increased from 0 to 1 due to a right turn, PICO follows the outer wall until the counter is 0 again. Apart from certain U-turn cases depicted in the figure, this means that when the counter is -1 or smaller, PICO prefers to turn right whenever possible.
• When the counter is 1 or larger, PICO prefers to turn left whenever possible.
• At a dead end, PICO turns 180 degrees right or left depending on the counter. The counter is increased/decreased by 2.

The advantage of the pledge algorithm was that it doesn’t require any mapping, it was only required that PICO recognizes the junctions and the turns. Pledge however doesn’t work when the robot starts outside the maze and has to find its way in: the algorithm is only valid when starting inside the maze and the exit is on the outside. According to the rules of this project, it was guaranteed that PICO always start in the inside and had to move out, thus pledge was a safe choice as the maze solving strategy.

Special U-turn direction cases regarding pledge.

A demonstration of the pledge algorithm for a test case is provided below and the overview of solving last years maze is provided on the right. It remembers the last turn it took to make sure it doesn't miss any parts of the maze as you can see in the figure on the right below the maze of last year. Here it makes a U-turn to the left since the last turn it took was to the right. Furthermore a special case of two dead ends placed opposite of each other is introduced on the right as well. To guarantee that PICO doesn't get stuck in a loop it takes two U-turns to the left.

pledge algorithm tester.

Random Walk Algorithm

In the case that PICO doesn’t recognize a junction completely and drives through it using just the potential field, the counter of the pledge algorithm will no longer be valid. In some mazes this could mean that due to a wrong counter, the robot will be stuck in a loop. If this happens during the first attempt, the random-walk algorithm will be used during the second attempt instead of pledge.

As the name suggests, the random-walk algorithm randomly chooses one of the available directions at a junction. Every time the random-walk algorithm is used, the seed of the random-function is changed to keep it actually random. Though since it is random and PICO doesn’t make any “smart” decisions, it isn’t the most robust method in terms of how long it will take till PICO reaches the exit. However. the main idea is that PICO will eventually reach the exit despite the time. This is a very simple algorithm and doesn’t require a counter. The random-walk algorithm is thus mainly used as a back-up plan.

A snippet containing both the pledge and the random walk algorithm is provided below:

Pledge and random walk Algorithm function

Debugging Tools

Visualization

To better understand the world seen by PICO, we developed a tool to quickly plot points of interest using the ROS message system. In this way, we can visualize exactly what goes on in the algorithms we developed, and thus can quickly fix errors in detection and recognition. In these pictures, the blue dots are the dots given by the laserData itself. In red are the points as given by the detection circle. The other colors are recognized points. In yellow, the edgePoints detected by the detection circle, and in pink the associated midPoint. The points in green form up a potential door, while the bright blue dot is the detected midpoint if a door is really detected.

Python plotter looking at a cross-junction

Python plotter looking at a (fake) door

Python plotter looking into an open space

Final Presentation & Improvements

Our final design was presented on June 7th, 2017. Link to a PDF copy of the presentation slides: File:Presentation EMC final group 1 - final.pdf

Based on this presentation we discovered some flaws in our design and decided to re-think our whole strategy while keep some working parts of the code. The robot moves inside a corridor while it is in the state LOOKING_FOR_SIDE and when it is close enough to the corridor to detect the nodes correctly, it will call the node recognizing function to determine which junction is present. This function as mentioned before, recognizes all available nodes namely:

STRAIGHT, CROSS, T_JUNCTION_RF, T_JUNCTION_FL, T_JUNCTION_RL, CORNER_LEFT, CORNER_RIGHT, DEAD_END, OPEN_SPACE_LEFT, OPEN_SPACE_RIGHT, OPEN_SPACE_MIDDLE

Then as soon as PICO recognizes a junction it calls the pledge algorithm in order to determine which direction it will follow. Based on this information, the desired midpoint is stored for future use. The next step includes PICO going to MOVE TO MIDPOINT state if pledge says PICO should turn left or right. In this state, the midpoint is updated to the closest midpoint available (by comparing the distance formed by the initial midpoint and the new ones). After that, the x coordinate of the updated midpoint is checked in order to establish whether the robot has reached the middle of the junction. Then, according to which midpoint you have (left or right) you enter the state ROTATE_LEFT or ROTATE_RIGHT. PICO will continue to turn until it reaches the point where the updated midpoint lays in front of PICO (midpoint y-coordinate is close to 0). Finally the robot will move forward towards the corridor until it detects walls on both left and right side, guaranteeing thus, that a complete turn is accomplished. When pledge says PICO should move straight it will first move ahead to make sure it is in the junction and after that detect if the right and left laserbeam are walls or still gaps to indicate if the crossing went correctly.

File:Final Idea design EMC group 1 sketch.pdf

After integrating everything multiple tests were conducted. A simulation of last years maze is provided below:

maze2016.

Code Snippets

Pledge and random walk Algorithm function Potential fields Supervisor Corner Detection

Maze Challenge Evaluation

The maze challenge took place on June 14th. A Figure of the maze used that day is provided below.

Maze Challenge 2017 map

Only two teams succeeded in getting out of the maze in the given time. We in particular managed to get the second place with our second attempt with a time of 4 minutes and 8 seconds in total.

The videos for both attempts are provided below:

1st attempt :

2nd attempt :

A video of both attempts from an above view is provided below:

Many parts of the code used in the Maze challenge were not thoroughly tested with PICO. Therefore the behavior of PICO differed from what we saw in simulations. One example of this was the door detection. What seemed to be quite robust in simulation was not as robust in practice. PICO identified many more doors than existed in the maze, which slowed down it's progress significantly when navigating the maze. Due to the fact that PICO moves towards a door when one is identified and has to stop to ring the bell, identifying false doors and moving towards them could also have caused problems with the Pledge algorithm count.

A simulation of this years maze is illustrated below :

The second flaw was that the open space movement was incomplete and not tuned yet. This became apparent in the second attempt, where PICO was temporary stuck in a loop between the two open spaces. While the open space detection was already implemented, the open space was actually too small to be recognized as an open space. Instead PICO mostly saw a T-junction with at one end a dead end , if he was aligned correctly that is. When PICO entered an open space for the first time, he went straight towards the “dead end”, as expected when following the pledge algorithm. However, it went wrong when doing the U-turn. Since PICO turns until it reaches the midpoint, the midpoint is at a weird place due to the shape of the open place. Thus the robot only makes a ~135 degree turn and it went downhill after that, going several times back and forth between the two open spaces. Eventually PICO managed to find its way out, which can only be explained why by summarizing the events in this loop (neglecting door recognitions):

• PICO enters the first open space. Pledge counter is correctly at 0.
• Due to PICO’s entering location it makes a “U-turn” of 135 degrees to the right. Pledge counter is 2.
• PICO sees a wall to the front left and thus detects a right turn. PICO turns right 90 degrees and the pledge counter is 3.
• PICO detects a T-junction: to his left towards the second open space and to his right the road to the door. However since the pledge counter is messed up, PICO turns left. Pledge counter is 2.
• PICO enters the corridor towards the second open space, though it doesn’t see it as a right turn but as a straight corridor. This is due to the midpoint tracking of the previous left turn, aligning PICO to the corridor instead of making a complete 90 degrees turn. Due to the current pledge counter the robot doesn’t enter the starting location again. Pledge counter is still 2.
• At the second open space, PICO detects a dead end again and makes a U-turn to the left. However, this time the position of PICO is so that it actually makes a complete 180 degrees turn. Making it going back towards the first open space. Pledge counter is 0.
• At the first open space, it detects a dead end again and makes a U-turn to the right, little over 180 degrees. It should’ve actually turned left due to triggering one of the “special U-turn cases” described in chapter “Pledge Algorithm”. However, the code didn’t take into account for the case when the counter is exactly 0, which is a bug. It was forgotten to test this case. Due to the right turn, PICO doesn’t want to turn right towards the door due the new pledge counter. Pledge counter is 2.
• After the U-turn, it comes across a wall to the front right, thinking it’s either a T-junction or a left turn. PICO turns left towards the other dead end corridor. Pledge counter is 1.
• At the second open space, it detects a dead end again and makes a U-turn to the left, correctly 180 degrees. Due to the new pledge counter, PICO doesn’t want to turn left towards the door. Pledge counter is -1.
• At the first open space, PICO sees the front and right wall, but also still the gap to the left. PICO detects the open space as a left turn and finally goes towards the door. Pledge counter is -2.
• The pledge counter should’ve been -1 and not -2 when passing the door. However this didn’t matter, since it would’ve followed the same path towards the exit for this maze.

At the end PICO still bumped once at a wall, resulting in a 10 second penalty, which happened after a left turn. We assume that the potential field is still not completely tuned correctly yet. The repulsive force of the potential field now consists of a peak when you're at x centimeter of the wall. this peak probably needs to be shifted to a slightly different distance and the peak needs to be leveled off for smaller distances. The latter is to prevent PICO still bumping into a wall when it somehow passed the repulsive peak.

Conclusions and recommendations

What went well:

-The supervisor was very robust. Even when other aspects of the code didn't work as expected, the supervisor did not end up in a deadlock state and PICO was able to eventually find its way out of the maze.

-The modular code separated key tasks. This helped with debugging and work load distribution.

-The developed debugging tools greatly helped the team figure out how the code functioned both in simulation and in real life and whether there were errors in the algorithm implementation.

What went wrong:

- Open space implementation not finished completely and open space detection needs some tuning for smaller open spaces: U-turn method not valid for open spaces.

- Underestimated turning and open spaces. A lot of focus towards several door detection cases.

- Node recognizing mostly worked, needs some tweaking looking at the first attempt.

- Door Detection was not fully tested with PICO. Real behavior of PICO differed from simulation causing problems in the maze challenge.

- Generally time management for code development needed improvement. Many aspects of the code were not fully developed in time to test on the real PICO so the implementation was reliant on the simulations.

Lessons learned and Advice for Future Groups

Testing time with PICO is precious and should not be wasted. The simulator is very useful for general debugging however a lot of PICO's behaviour is not captured in the simulator. As a consequence all parts of the code should be tested on the real thing prior to the challenges if possible. Make a testing schedule early in the project and enforce this schedule so code development keeps up with testing sessions and all components are thoroughly tested with PICO.

Take the time to master Gitlab early in the project. This will avoid headaches when merging code and testing with your teammate's code.

Modularize your code with clear definitions of the inputs and outputs of the code. This will help with debugging and dividing the tasks among the team.

Make sure you all understand what each other’s idea’s, tasks and output are. Time could be lost by double work or doing the wrong task. Communication is key.

Do not underestimate the importance or difficulty of any task. Until the final solution has been worked out, nothing is guaranteed to be easy to solve.

And to conclude on a happy note,here are two pictures of our group right after the corridor and the maze competition.