Latest revision as of 15:32, 13 May 2021

Group Members

Luuk Verstegen - 1252488

Bob Bindels - 1246348

Stijn van den Broek - 1252011

Lars van Dooren - 1249169

Tjeerd Ickenroth - 1232296

Introduction

Design Document

A Design Document is created in order to elaborate the approach of the Escape Room challenge (also some Hospital challenge aspects). The document includes several topics such as the requirement, components, specifications, functions and interfaces. Download the file here: Design Document

Escape Room Challenge

The task of the escape room challenge is to find the corridor and exit the room through it. Since our group did not have much experience with C++ programming, it was decided to split up the work into a robust method (2 people) and a less robust method (3 people):

Robust: the first method is based on line segments and corner detection. From the LRF data the angle indices corresponding to start- and endpoints of line segments can be found. From these indices and the corresponding distances the location of the corridor entrance can be determined. The robot should drive to this position and from there on align itself with the walls of the corridor and drive parallel to the walls until the finish is reached. Since not a lot from the Wiki example can be used here, it was expected that this method would take the most time to get it properly working.

Less robust: the second method is based on the full example which has been placed on the Wiki. Here, wall detection, drive control and a finite state machine are already implemented and therefore it is relatively easy to adapt. The method for finding the corridor in this method is a relatively easy one: when a sudden distance jump is found between one LRF index and the next, then the corridor is found. To make sure that once the robot has found this sudden distance jump and drives towards the corridor, mostly changes in the finite state machine are required.

Robust method

For the first method, line segmenting is implemented. This is done as follows:

1. First, a line is drawn between the start point with index 0 and the end point with index 999.

2. Then, for each LRF data point, the distance perpendicular to the line drawn in step 1 is determined and both index and distance of the point corresponding to the largest distance are saved.

3. If the distance lies above a certain threshold value, then the point found in step 2 does not lie on the line drawn between points 0 and 999. In that case, the process is repeated from step 1 again, however now the end point is changed to the index determined in step 2. If the distance lies below the threshold value, then there is a line detected between the start and end point stated in step 1. The process is then repeated with the end point of the current iteration now being the start point of the next iteration.

4. The steps above are repeated until the start point index is equal to 999, which means that all line segments have been found.

Note that since all the start and end points of the line segments are saved, also the corner indices are known. A problem which had to be dealt with using this method is the fact that when the robot is driving in the open-ended corridor, certain distances in the LRF data are close to zero since the laser beams sent outside the corridor are not reflected by a wall or object. This resulted in the robot detecting the indices corresponding to angles pointed outside the corridor as corners, which obviously is not the case. Therefore, at each instance the robot receives new LRF data, the indices which correspond to a distance smaller than 0.1 m are stored and later taken out of the array of corner indices. The result is that only the indices of the actual corners remain.

Another problem, which was not solved at the time of the challenge, is the fact that not between all subsequent corner indices a line should be drawn. For example, when the robot is driving straight through the corridor it detects the ends of the left and right wall as corners, however in between these corners there is no wall. This distinction should be made such that the robot knows where a wall is located and where not, such that he can align to the walls in the corridor. At the time of the challenge it was not yet figured out how this should be done.

For the detection of the corridor two methods where thought of:

The first method for detecting the corridor is based on a jump in distance between subsequent corner indices which are within a certain index bound w.r.t. each other, this is visualized in Figure 1. When this jump is detected, the robot should rotate and drive towards the corner with the smallest distance and from there on perform a similar kind of movement as explained in the less robust method. When detecting the corridor in this way the main difference between the robust and less robust method is that the robust method only checks for a distance jump between the corner indices instead of all indices, thus saving computation time. A disadvantage of this method is that the robot cannot detect the corridor when it is right in front of the corridor, since then the index gap between the left and right corner is out of the specified bound.

The second method for detecting the corridor is based on convexity of the corner points. When a high-low-high sequence in distance is found between three successive corner points, then the middle corner is one of the corners at the entrance of the corridor. This is visualized in Figure 2. Unfortunately due to time constraints it was not possible to successfully implement this before the escape room challenge.

Figure 1: Illustration of the difference searching algorithm.

Figure 2: Illustration of the HLH searching algorithm.

Less robust method

This algorithm works as follows. At first the robot will search for large differences between two subsequent points from the LRF. The program continuously look trough the data and if the range of two consecutive data points have a larger difference than 0.5 meter the program will assume that the corridor is found. This is illustrated in Figure 1. If initially no corridor is found the robot will rotate such that it has seen the entire view of 360 degrees. It could be the case that still no corridor is found because the room is too big. Then the robot will just drive forward and stop just before hitting a wall. It will then drive a bit backwards and search again for the corridor, this process will repeat until the corridor is found.

When the corridor is found the robot will rotate until the corridor is in front of it. The robot will now drive towards the detected corner point of the corridor. When the robot has reached the corner, it will drive a bit sideways until it has enough space to move forward. Now the assumption can be made with great certainty that the robot is located in the corridor. To drive out of the corridor the following steps are be taken by the algorithm:

If the robot almost hits a wall it will check which of the ranges depicted in Figure 3 is the furthest.

The robot will now drive in the positive x-direction, positive y-direction, or negative y-direction depending on which of the ranges in step 1 is the furthest.

This process keeps repeating, which results the robot to be driving out of the corridor in a zigzag like pattern.

In every of these states the robot will check if the finish line is reached. This is done by counting the amount of infinite values in the laser range data, once the counter surpasses a set value the end of the corridor is reached and thus the finish line is passed.

Figure 3: Range checking inside the corridor.

Results

Unfortunately the robust method could not be finished on time, however the less robust method was tested during the escape room challenge. The algorithm was able to pass the finish line within 20 seconds, this was enough for the second time of all the groups.

@@ Line 5: / Line 5: @@
 = Group Members =
-{| class="TablePager" style="width: 230px; min-width: 240px; margin-left: 2em; color: black;"
+Luuk Verstegen - 1252488
-|-
-! scope="col" | '''Name'''
-! scope="col" | '''Student Number'''
-|-
-| T.J.M. Snijders || 1017557
-|-
-| B.P.J. Reijnen || 0988918
-|-
-| J.H.B. de Zwart || 1020347
-|-
-| S.C.M. Mennen || 1004332
-|-
-| A.C.C.E. Vissers || 0914776
-|-
-| B. Godschalk || 1265172
-|}
+Bob Bindels - 1246348
+Stijn van den Broek - 1252011
-= Introduction =
+Lars van Dooren - 1249169
-This Wiki-page reports the progress made by Group 1 towards completion of the Escape Room Challenge and the Hospital Challenge. The goal of the Escape Room Challenge is to escape a rectangular room as fast as possible without bumping into walls. The goal of the Hospital Challenge is to deliver medicines from one cabinet to another as fast as possible and without bumping into static and dynamic objects.
-This year, due to COVID-19, all meetings and tests are done from home. The meeting schedule is shown at the end of the wiki. The software for the autonomous robot (PICO) is written in C++ and applied to a simulation environment since there has been no interaction with PICO. The simulation environment should represent the real test as closely as possible and therefore the information on this page should be applicable to the real test.
+Tjeerd Ickenroth - 1232296
-= Design document =
-In order to get a good overview of the assignment a design document was composed which  can be found [[:File:4SC020___Design_Document-v1.pdf|here]]. This document describes the requirements, the software architecture which consists of the functions, components and interfaces and at last the system specifications. This document provides a guideline to succesfully complete the Escape Room Challenge.
-= Escape Room Challenge =
+= Introduction =
-The Escape Room Challenge consists of a rectangular room with one way out. PICO will be placed on a random position on a map which is unknown to the challengers before taking the challenge. PICO should be able to detect the way out by itself using the Laser Range Finder (LRF) data and drive out of the room without hitting a wall using its three omni wheels.
-To create a solid strategy a number of options have been outlined. Two solid versions were considered; wall following and a gap scan version. After confirming that the gap scan version can, if correctly implemented, be a lot faster than following the wall, this option was chosen. Wall following does not require much understanding of the perception of PICO. By constantly looking at the wall and turning if a corner is reached, PICO will move forward as soon as no wall is visible in front of it indicating that the corridor is found. One other reason to use gap detection over wall following as a strategy is that the gap detection and moving to certain targets can later on be used in the Hospital Challenge. In the Hospital Challenge multiple rooms are present, objects are placed in the rooms and cabinets have to be reached which make wall following unapplicable.
+= Design Document =
+A Design Document is created in order to elaborate the approach of the Escape Room challenge (also some Hospital challenge aspects). The document includes several topics such as the requirement, components, specifications, functions and interfaces. Download the file here: [http://cstwiki.wtb.tue.nl/images/4SC020_Mobile_Robot_Control.pdf Design Document]
-The code is divided in multiple parts, or functions, which work together to complete the task. These functions are separated code-wise in order to maintain a clear, understandable code. Next, the state machine of PICO is elaborated. Finally, the simulations will be discussed together with the result of the Escape Room Challenge.
-== Functions ==
+= Escape Room Challenge =
+The task of the escape room challenge is to find the corridor and exit the room through it. Since our group did not have much experience with C++ programming, it was decided to split up the work into a robust method (2 people) and a less robust method (3 people):
-=== Finding walls and gaps ===
-Using the LRF, data points are obtained. To differentiate between the walls and the exit a least squares regression line algorithm has been written. This algorithm fits a line over all found data points in order to find a wall in the field of view (FOV) of the LRF. By connecting the walls together it can be possible that a gap occurs, which will be saved into the global reference frame. To collect the data, PICO starts with a 360 degree FOV rotation, while doing so collecting all gaps. When the scan stops, all the collected gaps are checked based on some criteria to see if it is an exit and if it is the best exit possible and, if needed, fixed (straightened based on the adjacent walls). This function is also used in the Hospital Challenge and elaborated in the section Perception.
-=== Path planning ===
-To let PICO move from the start location to the exit, a path was generated for PICO to follow. This path consisted out of two points, a pre target (denoted as target B) before the exit gap and a target in the center of the gap (denoted as target A). See Figure 1. This section describes how these points were computed.
-[[Image:Pathplan2.PNG | thumb | 400px | center | Figure 1: Path planning]]
+* Robust: the first method is based on line segments and corner detection. From the LRF data the angle indices corresponding to start- and endpoints of line segments can be found. From these indices and the corresponding distances the location of the corridor entrance can be determined. The robot should drive to this position and from there on align itself with the walls of the corridor and drive parallel to the walls until the finish is reached. Since not a lot from the Wiki example can be used here, it was expected that this method would take the most time to get it properly working.
-If a gap has been found by PICO, the corners of this gap are obtained. From this, target A can easily be computed by taking the average in both x and y direction. Target B is then placed perpendicular to the gap on a distance of 0.4 meters, which is the width of PICO. This is done to prevent PICO from attempting to drive to his target through a wall.
+* Less robust: the second method is based on the full example which has been placed on the Wiki. Here, wall detection, drive control and a finite state machine are already implemented and therefore it is relatively easy to adapt. The method for finding the corridor in this method is a relatively easy one: when a sudden distance jump is found between one LRF index and the next, then the corridor is found. To make sure that once the robot has found this sudden distance jump and drives towards the corridor, mostly changes in the finite state machine are required.
-Target B was computed as follows. First, the gap and the line between points A and B were denoted as a vector representation
-[[Image: vectorBgroup12020.png | frameless | 200px | center ]]
-Then, a and b were computed. Since it is known that the vectors are orthogonal, the inner product should be zero, resulting in
-[[Image: innerproductBgroup12020.png | frameless | 200px | center ]]
-Depending on the values of the x and y coordinates of the corners of the gap, either a or b was set to the value 1 in order to compute the other value. With a and b known, the direction of the vector AB is known. The length of this vector is also known, hence equating the two norm of the vector to the length of the vector results in
-[[Image: normBgroup12020.png| frameless | 200px | center ]]
-After these computations are completed, two possible locations for point B can be obtained. One before and after the gap. To determine the correct point, the distance from PICO to both points was computed. The point with the smallest distance will always be the point before the gap and thus the correct point B. Note that this will hold only when the room from which PICO needs to escape is a rectangle or when the corners of the gap are obtuse angles.
-=== Potential field corridor ===
+==== Robust method ====
-When PICO drives in the corridor, PICO starts to monitor the left and right wall to center itself between the walls of the corridor while moving towards the finish line. This is done using proportional control.
+For the first method, line segmenting is implemented. This is done as follows:
-== State machine ==
+'''1.''' First, a line is drawn between the start point with index 0 and the end point with index 999.
-In Figure 2, the flow chart is depicted which starts at 'Inactive' and ends at 'Move forwards' until PICO stops.
+'''2.''' Then, for each LRF data point, the distance perpendicular to the line drawn in step 1 is determined and both index and distance of the point corresponding to the largest distance are saved.
-The first step that will be executed is the 'Initialize' step. This step will be used to clear and set all variable values (the odometry data from the wheels as well as the LRF data) to the default state from which it will continue to the '360° scan', where using the LRF data all walls and possible gaps are detected. In this scan all LRF measurements will be mapped into wall objects if obtained data points connect. When data points do not connect, a gap occurs which can be a possible exit or a faulty measurement. When the scan can not find any gaps in the walls, PICO will move 1 meter to the furthest point measured in the scan and performs a new scan. If, for any reason, PICO tends to walk into a wall, the robot will move backwards and starts a new scan.
+'''3.''' If the distance lies above a certain threshold value, then the point found in step 2 does not lie on the line drawn between points 0 and 999. In that case, the process is repeated from step 1 again, however now the end point is changed to the index determined in step 2. If the distance lies below the threshold value, then there is a line detected between the start and end point stated in step 1. The process is then repeated with the end point of the current iteration now being the start point of the next iteration.
-The next step 'Gap?' is checking if the gaps found can be considered as an exit. If no gaps meet the specifications of a gap, the next step will be 'Move to better scan position' and PICO will redo the previous steps. If a gap meets the requirements of the exit, then PICO will move on to ‘Path Planning, which will be executed to calculate the best possible way to the exit. When the path is set the following step will be 'Move to gap'.
+'''4.''' The steps above are repeated until the start point index is equal to 999, which means that all line segments have been found.
-The final step will be 'Center?' which will center the robot in the corridor of the exit to prevent that incorrect alignment with the exit will result in a crash with the walls.
+Note that since all the start and end points of the line segments are saved, also the corner indices are known. A problem which had to be dealt with using this method is the fact that when the robot is driving in the open-ended corridor, certain distances in the LRF data are close to zero since the laser beams sent outside the corridor are not reflected by a wall or object. This resulted in the robot detecting the indices corresponding to angles pointed outside the corridor as corners, which obviously is not the case. Therefore, at each instance the robot receives new LRF data, the indices which correspond to a distance smaller than 0.1 m are stored and later taken out of the array of corner indices. The result is that only the indices of the actual corners remain.
-Parallel to this flow PICO will continuously keep track of objects with the laser range finder. Whenever a object is detected in a specific range of the robot a flag will be thrown. This flag can be used to update the path planning, which will prevent crashes when the robot is heading in the wrong direction.
+Another problem, which was not solved at the time of the challenge, is the fact that not between all subsequent corner indices a line should be drawn. For example, when the robot is driving straight through the corridor it detects the ends of the left and right wall as corners, however in between these corners there is no wall. This distinction should be made such that the robot knows where a wall is located and where not, such that he can align to the walls in the corridor. At the time of the challenge it was not yet figured out how this should be done.
-[[Image:Group1_ER_Strategy_update_1.jpg | thumb | 750px | center | Figure 2: Strategy for Escape Room Challenge ]]
+For the detection of the corridor two methods where thought of:
+* The first method for detecting the corridor is based on a jump in distance between subsequent corner indices which are within a certain index bound w.r.t. each other, this is visualized in Figure 1. When this jump is detected, the robot should rotate and drive towards the corner with the smallest distance and from there on perform a similar kind of movement as explained in the less robust method. When detecting the corridor in this way the main difference between the robust and less robust method is that the robust method only checks for a distance jump between the corner indices instead of all indices, thus saving computation time. A disadvantage of this method is that the robot cannot detect the corridor when it is right in front of the corridor, since then the index gap between the left and right corner is out of the specified bound.
-== Simulation ==
+* The second method for detecting the corridor is based on convexity of the corner points. When a high-low-high sequence in distance is found between three successive corner points, then the middle corner is one of the corners at the entrance of the corridor. This is visualized in Figure 2. Unfortunately due to time constraints it was not possible to successfully implement this before the escape room challenge.
-The result of the strategy and the implemented functions is shown in Figure 3 where one can see that a gap is detected. PICO moves to a point in front of the opening and rotates towards the opening. While driving through the corridor, PICO keeps its distance to the walls.
-[[File:Group1_ER_Simulation_1.gif| frame | 100px | center | Figure 3: Simulation in emc-sim for Escape Room]]
+[[File:beun_escape_room.png|400px|thumb|center|Figure 1: Illustration of the difference searching algorithm.]]
+[[File:HLH_sequence_v2.png|400px|thumb|center|Figure 2: Illustration of the HLH searching algorithm.]]
-In Figure 4 one can see how PICO behaves if no gaps are detected. PICO keeps on moving 1 meter from its scan location to scan again.
+==== Less robust method ====
+This algorithm works as follows. At first the robot will search for large differences between two subsequent points from the LRF. The program continuously look trough the data and if the range of two consecutive data points have a larger difference than 0.5 meter the program will assume that the corridor is found. This is illustrated in Figure 1. If initially no corridor is found the robot will rotate such that it has seen the entire view of 360 degrees. It could be the case that still no corridor is found because the room is too big. Then the robot will just drive forward and stop just before hitting a wall. It will then drive a bit backwards and search again for the corridor, this process will repeat until the corridor is found.
-[[File:Group1_NoGapRoutine.gif| frame | 100px | center | Figure 4: Escape Room no gap simulation in emc-sim]]
+When the corridor is found the robot will rotate until the corridor is in front of it. The robot will now drive towards the detected corner point of the corridor. When the robot has reached the corner, it will drive a bit sideways until it has enough space to move forward. Now the assumption can be made with great certainty that the robot is located in the corridor. To drive out of the corridor the following steps are be taken by the algorithm:
-== Escape Room Challenge results ==
+* If the robot almost hits a wall it will check which of the ranges depicted in Figure 3 is the furthest.
-The challenge attempt can be seen in Figure 5. As can be seen in the scanning, the robot rotates in a smooth counterclockwise rotation in which the gap detection algorithm detects the exit. After validation of the gap, a pre-target and target are placed in relation to the detected gap location. However, the movement towards it went wrong. Normally, the motion component of the software calculates the smallest rotation between the angle of PICO and the pre-target & target of the gap. During the development and validation of the written software in the simulator, this component worked as expected. However, during the challenge it emerged that the calculation did not work when comparing positive and negative angles. As a result, the calculation showed that a positive angle had to turn into the negative direction in order to reach its target. Because of this problem PICO started to rotate 270 degrees to the right instead of 90 degrees to the left. This problem came up 2 times, both after the 360 degrees scan and after reaching the pretarget.
-Immediately in the first attempt PICO moved out of the room in 55 seconds. However, PICO decided to align itself with the reference angle using the largest rotation which costed a lot of time. In the end group 1 is proud of the result.
+* The robot will now drive in the positive x-direction, positive y-direction, or negative y-direction depending on which of the ranges in step 1 is the furthest.
-After the challenge we looked at this problem and applied a possible solution. If the simulation would be performed again with the right rotations the simulation time could be reduced to 25 seconds which would have resulted in a 2nd place during the challenge, instead of our 4th place that we were placed this time.
+* This process keeps repeating, which results the robot to be driving out of the corridor in a zigzag like pattern.
-In summary, every software component worked fine without failing completely. However, after a bug fix in the motion component, everything works optimally without any known errors. The wall detection and motion software can be used for the hospital challenge and made usable with some additions without starting from scratch again.
+* In every of these states the robot will check if the finish line is reached. This is done by counting the amount of infinite values in the laser range data, once the counter surpasses a set value the end of the corridor is reached and thus the finish line is passed.
+[[File:beun_escape_room_corridor.png|300px|thumb|center|Figure 3: Range checking inside the corridor.]]
-[[file:Group1_ERC_result.gif | frame | 800px | center | Figure 5: Escape Room Challenge live stream result]]
+==== Results ====
+Unfortunately the robust method could not be finished on time, however the less robust method was tested during the escape room challenge. The algorithm was able to pass the finish line within 20 seconds, this was enough for the second time of all the groups.

Mobile Robot Control 2021 Group 4: Difference between revisions

Latest revision as of 15:32, 13 May 2021

Contents

Group Members

Introduction

Design Document