Embedded Motion Control 2018 Group 1
|1279602||Ahmed Hizar (A.H.) Ahmed Ajmalfirstname.lastname@example.org|
|0914013||Jari (J.J.) van Steenemail@example.com|
|0924842||Nazar (N.) Rozkvasfirstname.lastname@example.org|
|1279491||Arpit (A.) Aggarwalemail@example.com|
|1031018||Willem (W.) Verhoevenfirstname.lastname@example.org|
This part describes all of our progress in the first challenge of the course, which is the Escape Room challenge.
Before the software could be created that makes an escape possible, an initial design report was created to assist in the design of the software. This initial design report can be found here: Initial design report group 1. The most important points from this report will be given on the wiki page.
Requirements & Specifications
The first step in the design process is the creation of requirements for the software, which gives a way to express PICO's required behaviour in the Escape room challenge. To translate this into software, the requirements have to be specified, which is done via specifications. These specifications are used in the software design. Both the requirements and corresponding specifications are given here:
|PICO has to avoid all walls at any time.||PICO should always stay always stay away from walls at least 15 centimeters.|
|PICO should aim for an equal distance to the right and left when moving through a corridor between 0.5 and 1.5 meters.|
|PICO should complete its task well independent of the initial conditions.||PICO has to scan its surroundings with a frequency of at least 5 Hz while moving to prevent bumping into a wall.|
|PICO should operate fully autonomously.||The final software should not make use of teleoperation.|
|PICO cannot translate or rotate faster than prescribed.||The maximum translational velocity of PICO is 0.5 m/s and the maximum rotational velocity of PICO is 1.2 rad/s.|
|PICO has to deal with small imperfections in the real world it operates in.||An uncertainty margin of 0.05 meter should be present when building a world model to deal with imperfections in the real world.|
|The software should be easy to set up.||The software should be set up according to the information on the wiki page.|
|PICO has to cross the finish line as fast as possible within the maximum time of 5 minutes.|
|PICO needs to stop when it crosses the finish line.||PICO needs to stop after it has entered the corridor and there is more than 1 meter distance to the left and to the right|
|PICO has to identify the exit of the escape room.||An algorithm is created which ensures that PICO identifies an exit between 0.5 and 1.5 meters wide when facing the exit under an angle of 60 degrees or less.|
|PICO has to keep looking for the exit if it cannot find the exit.||PICO will drive towards the point furthest away from at that moment if the exit is not detected.|
To escape the room as fast as possible for this challenge, a plan has been created on geometric level that makes PICO escape as fast as possible. This plan will be described here by first explaining the plan at the highest level and explaining some of the steps in more detail afterwards.
The highest level of this plan will first be described by a simple step-by-step algorithm.
- Initialize the sensors and actuators.
- Scan surroundings from the given position and orientation.
- Try detecting the exit.
- IF exit is found: Drive towards exit and skip to step 8. ELSE: Turn 180 degrees and perform step 2 and 3 once again.
- Try detecting the exit.
- IF exit is found: Drive towards exit and skip to step 8. ELSE: Move into the direction of the furthest point for a quarter of this distance.
- Return to step 2.
- Identify the 2 corridor walls and orient the robot to face the exit, then drive forward while remaining in the center.
- Stop once the finish line has been crossed.
The details of the steps performed in this plan are written below.
Some addition explanation on steps described in the overlaying plan will be described now, starting with the explanation on how to detect the exit and the data in the corridor of the maze.
Line fitting algorithm
As a groundwork of the detection methods, a line fitting algorithm has been created. This is required to localize the exit as well as detecting the walls of the corridor of the maze. This line fit will be based on saved data from the LRF that has been transformed to cartesian coordinates. The line fit algorithm tries to fit a line between 2 different points of the LRF data. To do this, the data between the first and last point is averaged into a smaller number of points. Between the first and last of these averaged points, a line is fitted, which is easy to do for 2 points. By checking that the root mean square of the distances from the other averaged points is smaller than a certain threshold, it is determined whether the initial points form a line. This threshold value is based on the total number of points and the number of averaged points. If this linefit does work, the mathematical formula of the line as y = ax + b can be passed.
A very important task in the overlaying plan is to detect the exit from a certain given orientation. The algorithm on how to do that, using the previously described line fitting algorithm, is described now. The exit detection starts by trying to make a line fit between the first LRF data point and around 30 points away. This number of 30 has been determined by looking at the size of the room and the total amount of LRF data points. If a line can be fit correctly between these points, it means that a wall is detected. If it cannot create a good line fit, no wall is detected.
When a wall has been found, the next step is to extrapolate this line, and check if the distance between this line and the points of the LRF data exceeds a certain threshold at some point for a minimum amount of points in a row. If this is the case, there is either a corner or the exit located here. If the distance from PICO to these points increases, this means that the exit is found, while a corner is found if the distance from PICO to these points decreases. If the exit is located, only one point of the exit is known. Therefore, the line will be extrapolated even more, until the LRF data gives new value that fit on the same line. When this happens, the second exit point has been found, and the location of the exit is fully known. The knowledge of finding a corner is largely ignored for this challenge, the only benefit of knowing the location of the corner is that a new linefit can be made starting at this corner point.
Furthest point detection
Once the exit has been detected, a plan for driving towards the target needs to be made, this plan depends on the required task. The different driving tasks will be expanded upon here.
Driving towards exit
In order to drive towards the exit, the coordinate in the center of the two corner points of the corridor is used as a setpoint. PICO will drive towards this setpoint by turning until the exit is faced and after that, continue to drive forward in an open-loop controlled way. However, since errors can be made in this way, this process is continuously executed when finding the exit. This means that a loop will be executed in which the exit is continuously detected, after which PICO faces the exit and drives forward. This process is executed until PICO has reached a certain distance (20 centimeters) of the exit.
Driving through corridor
If the corridor is entered, a different driving plan applies, where the aim is to drive through the center of the wall. In this case, the detection algorithm provides the data of the two lines corresponding to the walls where PICO has to drive through. The next setpoint that PICO drives towards is a small distance (30 centimeters) in front of the current location, and is located in the center of the two walls. Apart from driving towards this point, PICO also aligns its orientation with the two walls. This process is looped until it has been detected that PICO escaped the corridor.
Driving towards furthest point
When no exit can be detected from the current position, PICO has to move towards the furthest point for one quarter of the total distance. This means PICO drives towards the point that is furthest away from the current position based on 2 scans, one from the initial orientation and one from the orientation after a turn of 180 degrees. This point is supplied as a setpoint to which PICO will drive in an open-loop controlled way. Opposite to the other two driving methods, this setpoint is not continuously updated, as the accuracy of moving exactly towards this setpoint is much less important. This means one simple setpoint is supplied, and the task is finished once driving towards this setpoint is finished.
The program has been built according to the Initial Design (Initial design report group 1) having the following 3 structural blocks: Detection, Planning and Control. Each of these correspond to a separate class, connected via an additional class 'main'. The functionality of each class is described in more detail below.
Execution of the program is sequential, such that the methods are called one-by-one depending on the state of the robot. The states are controlled by boolean flags, which include:
- turn - a flag set to "true" by the planning block when no exit is detected and we wish to turn around to examine the other half of the room. It is unchecked when the control block completes the turn;
- drive_frw - a flag set to "true" by the planning block when exit is detected a PICO has to move in that direction or when no exit is detected and the robot should move in the direction of the furthest point detected;
- turned_once - a flag set to true by the planning block after the first turn in the case exit is not detected form the original orientation. This flag ensures that no continuous turning occurs. The value is set to "false" when drive_frw is set to "true";
- in_corridor - a flag set in the main function when the execution cycle for moving towards the exit it completed. This assumes that PICO is at the exit and a different algorithm for setpoints generation is executed in the planning block;
- escaped - a flag set by the detection block, when no reasonable data is detected after passing through the corridor. As this flag is turned to true, the program should stop executing.
The whole program consisted of 4 C++ classes:
- This is the main function where the program starts.
- It initializes objects that are required for the hardware components interaction and program execution (e.g. emc::Rate, emc::IO).
- It initializes the objects storing the sensor data, setpoint for the control loop and the furthest detected point. The later one has the same type as setpoints, however initialized separately since the furthest point is updated every iteration of the main while loop.
- Inside the while loop, the three classes are executed and are constantly updated (Detection, Planning, Control).
- This is the class that reads data from the sensors, filters it and does detection of primitive shapes and their interpretation. Output is wall line equation, corner points of the exit and one point for the furthest detected distance, with corresponding boolean flags
- Detection file includes methods to detect the walls, find exit and furthest point via line-fitting algorithm.
- The line fitting algorithm provides the equation of a line.
- Method to find exit compares the fitted lines with individual measurements, looking for large neighboring differences in the laser data.
- Method to find walls assumes that the data from the front and the sides of the robot should represent lines. This is verified by searching for laser data with distance closer than a specified value. It then fits the line over those points and spits them to the planning block.
- Method for the furthest point searches for the laser scan with the largest distance data.
- This is the class that interprets the data and sets the setpoints for movement. The output is relative angle to the setpoint and distance to it.
- It fully exploits the flag commands mentioned earlier and bases its decision on them.
- There are two algorithms between which, the distinction is done depending on the phase that the PICO is in.
- Room logic method checks all the data provided by the detection class and interprets it in destination points.
- A series of corridor following commands access the corridor data when the flag in_corridor is checked. It sets a setpoint based on the two parallel lines describing the walls, keeping the robot in the middle of the corridor
- This is the class that converts the setpoints to the commands to the actuators and tracks their execution.
- It heavily relies on the odometry data.
- Based on the flags turn or drive_frw it executes the functions for speed regulation till the odometry data states that PICO is at the desired position.
With the program described above, PICO was able to escape the room in the simulation.
Escape room challenge
Unfortunately, the program for the Escape room challenge was not written perfectly and PICO have failed the challenge, not being able to find the exit. As it was found later, the reason for that is the difference execution of the drive controls in the simulator and on the robot. The simulator was built in such a way, that PICO does not stop moving is a given direction till a command is changed. However, the real robot executed the drive commands only for a certain period of time and then it stops.
As a result, during the first operation stage facing the wall, it did not complete the full turn to scan the surroundings and proceeded to the next stage, moving to the furthest point. The furthest point was not selected properly and PICO have hit the wall.
Another conclusion that our group has made is that there should be a direct repulsion algorithm implemented such that in case PICO is located too close to the wall, the first command would be to move from the wall to the safe (predefined) distance and maintain it during the whole challenge. Only if this condition is achieved, the regular program can be run.
For the final challenge, the task is to explore a Hospital, which consists of corridor and few rooms. PICO has to explore the rooms, return to the initial position, park backwards to the wall and as a second phase of the challenge, find an object that is located somewhere in the Hospital. It is given that the object is placed in a room, for which the most doors have to be entered from the initial position.
Requirements & Specifications
For the hospital room challenge, new requirements and specifications have to be set.
The Hospital challenge is going to be completed with the following strategy:
- Move to the end of the corridor, meanwhile counting the number of doors in the corridor.
- When reached the end of the corridor, enter the closest room.
- In the room (not in the entrance of the room), scan the surroundings with the laser.
- If 2 corners of the room are identified, turn approximately 180 degrees and scan the environment again. Use few scans to precisely identify the features of the room and their coordinates. Disregard features that are identified only once or twice over all the scans. (When scanning surroundings, PICO should be stationary). When scanning and identifying features for the room corners, also search for the doors.
- When the room is scanned, go to the unvisited exit (if such exists). In case there are few exits that are not leading to the hallway, go to the first unvisited room on the right from PICO.
- If there is only one exit, go through the exit.
- Repeat the procedure for each room connected to the corridor. Write the data into the JSON file storing the information about the explored section of the hospital every time PICO return to the hallway.
- As all the rooms are visited, return to the initial position.
- Park backwards. Park "blindly", based on the distance to the back wall, obtained before turning around. Also, implement control effort algorithm to prevent PICO from continuously driving into the wall.
- Compute the destination to the furthest room as a stack of door coordinates that the robot has to enter. Use the known data about the hospital for accurate localization
- When in the room with the object, search for any unreasonably close laser scan data and consider that as the object.
- Move to the object and stop near it. Distance to the object is the same as the distance margin to the wall.
Detection / Mapping Strategy
<General plan of detection and mapping without diving into the code>
The detection strategy for the Hospital challenge was elaborated from the Escape Room challenge to account for the added complexity of the second challenge. As a result, some components of the detection strategy from the Escape room challenge were retained and improved, while the rest of the components were discarded due to their redundancy. The follow sections elaborate the new components employed in the detection strategy and the retained components from the previous challenge that were improved.
Retained and improved components
- Line fitting algorithm: The functioning of the line fit algorithm has remained the same from the Escape Room challenge, the description of the algorithm can be found Frog#Line fitting algorithm. The algorithm is still used to fit a line from the laser data, this line represents a wall of the hospital. The fitted line is then used as a base of comparison for laser data points which deviate from the fitted line, thereby indicating the presence of environment features.
The planning algorithm uses multiple setpoints where PICO drives to. The method to calculate a new setpoint depends on the phase of the 'overlaying strategy' where PICO is in, for example, when exploring the room low level detection data is used, while when moving through the known rooms, the known information from the previously created map is used. The strategy is fairly simple: first, one of the methods to determine the ultimate local destination is executed, producing the final setpoint for the current high strategy phase. Then, the local destination for PICO to travel for the current execution cycle is set. It always has a fixed distance with the angle in the direction to the high state phase setpoint. The new setpoint of PICO is always set to a distance of 0.2 meters away from the current position of PICO.
<To be changed, these are not assumptions, these are facts>
It is important to explicitly state the assumptions to the problem to define the working space of the object. From the description of the challenge the following assumptions were made:
- PICO always starts in the hallway
- Rooms might have nested rooms (entrance to a room is via another room)
Next, from the Exploration strategy described in one of the lower sections, the following assumptions are added:
Comparison with the Escape room challenge
The project in general consists of two challenges to test the PICO. Our group considered the challenges as highly interconnected in terms of developments sequence. The Escape room is viewed as a playground for the basic functions that are to be incorporated in the final Hospital Room challenge. It is clear, that in the Hospital challenge, some of the tasks are the same as in the Escape room challenge. Namely, the robot will have to identify the room properties (some of them are the same as in the Escape room challenge) and exit or "escape" the room, just as it have done in the first challenge. Therefore, it was decided to reuse as many developments from the previous part, as possible.
In this section, we define what are the changes comparing to the Escape room and what algorithms are reused.
Reused methods from the Escape room challenge
First of all, we maintain the detection algorithms for lines and objects such as exits of the room. The detection methods were proven to work for the previous challenge, however, needed more calibration for certain conditions. We also reuse the objects that are passed around the program that concern detection and setpoint planning. These are structures Exit, Point, Destination. The functions for the planning are also kept, however, the logic is reorganized for clearer code. Finally, the Control module has remained unchanged, since it was proven to work and direct the robot to a defined setpoint expressed as a turn angle and covered distance.
Innovations relative to the Escape room challenge
Comparing to the intermediate challenge (Escape room), there are few innovations that are employed in the program. These include both: new methods required to complete the challenge and new structure of the program execution. The structural changes mostly relate to the execution order and switching phases of the program.
First of all, since PICO has to perform repetitive tasks such as room exploration, passing through the doors in corridor or in the separate rooms, a State machine was added to the program. The State machine has 2-level states: high states for execution of general high tasks such as exploring the hospital, returning to the initial position, etc and low states that concern action planning within rooms or the corridor.
High states are:
- EXPLORE_HOSPITAL - high state that allows execution of all the low states for exploration phase (identification of the rooms, corridor).
- RETURN_TO_INIT - high state that changes the objective of the first part of the challenge from exploration to returning to the initial position.
- GO_TO_ROOM - the state that symbolizes execution of the second part of the challenge .
Low states are corridor-related and room-related:
- EXPLORE_CORRIDOR - this is the command that is first executed to go to the end of the hallway, counting the number of doors in the corridor. As it is mentioned previously, it is assumed that PICO always starts there. Therefore, this is also the initialized state.
- GO_TO_START - state that is active after all the rooms in the corridor (and, respectively, nested rooms) are explored and stored and the robot has to return to the starting point.
- PARKING - state to park backwards at the end of the first part of the challenge.
- EXIT_TO_PREV_ROOM - state that commands to go to the room one nesting level lower, e.g. exiting a nested room.
- EXPLORE_ROOM - state that enables execution of the room identification, which includes detection of features and mapping of the environment.
- GO_TO_NEXT_ROOM - state that is activated if there are more than one exit in a room, since according to the challenge strategy, we do not return to the hallway until all the nested rooms are fully explored.
- GO_INSIDE_ROOM - active when the actual movement through a door is happening. Initially, it was mean for the entrance based on the walls defining the exit, but later it was changed to just movement straight, parallel to the exit corners. This change was made because the walls are not thick enough to implement entrance algorithm similar to the one used in the Escape room.
- STAND_NEXT_TO_OBJECT - the state that commands PICO to go to the object if one is detected in the second part of the challenge.
The structure of the program was changed comparing to the escape room challenge. As it is shown on the picture on the right, there are few structural important blocks added. These are State machine, Monitoring, Interpretation, World model and JSON file block. Below we explain the role and the importance of each block.
- State machine - the block that regulates the progress of the PICO in the challenge. Based on the states defined earlier, the activity in all other blocks is regulated.
- Monitoring - it is the block that incorporates all the logic within the program. It is operated based on the state that the robot is in and decides for the routine to be called in order to complete the task.
- Interpretation/Mapping. Since the detection is outputting labeled features such as corners or exits, it is required to group those appropriately in order for other block to use the data. The Interpretation block is responsible for creation of the objects and their conversion to the absolute coordinates.
- World model - it represents a large database with the information about the environment. The World model includes information both, about the progress of the challenge (how many rooms have been visited, how many nested rooms there are, location of the PICO in general terms like room, corridor, nested room, current state of the State machine, etc.) and about the features of the place that it is currently in (room or corridor features). All the other blocks are communicating with the World model to retrieve information or to write it. The World model does not include any logic regarding the operations.
- Planning - the block which generates a set point where PICO should drive to according to the STATE it is in and the data from the world model.
- Control - it gives a control input to PICO.
- JSON file - it is chosen to use the JSON file to store the map in. It makes the program variable storage clear by separating the unused or irrelevant information from the main section of the program. It is also may be used to view the progress of the mapping over time.
The rest of the blocks keep their role in the software architecture from the Escape room challenge, but are extended with new functionalities.
< Contains some explanation of the code in each block, possibly with additional code snippets (not needed for every single block) >
Since the Hospital challenge consisted out of 2 parts: exploration and object search, 2 different main functions were defined. These are main_exploration.cpp and main_search.cpp The general structure of the two main functions was the same, except of the initial conditions that are set in the beginning of the program. The initialization for the exploration part stated that the first state is EXPLORE_CORRIDOR and set the necessary components of the World Model. The main_search.cpp, in turn, first parsed the JSON file to fill in the information based on the previous exploration and defined the Initial state and EXIT_CORRIDOR.
For the rest, both main functions have the following execution order in a while loop:
- Update the detection information.
- If there is a point detected that is too close to PICO, a method from planning is called to get away from the wall.
- If no such point detected, proceed to monitoring function.
- Update the states in the State Machine.
- Call drive function
- Check whether the program has to be stopped if the part of the challenge is completed (based on state machine)
The state machine is one of the crucial components that define the execution of the program. It includes the states evolution and location changes. Based on these parameters, other classes of the program can regulate their activity, for example, decision for a planning algorithm can be made (move further in a room/corridor or go through a door to enter another room).
The transition of the states is the following:
When exploring the Hospital:
- If the location of PICO is IN_CORRIDOR:
- Check whether the end of the corridor was reached once. If it was, never return to the EXPLORE_CORRIDOR state, needed to count the number of doors in the corridor.
- When reached the end of the corridor once, GO_TO_NEXT_ROOM.
- When at the entrance of the room, change to GO_INSIDE_ROOM for one cycle (given that the robot moves the same distance every time, it can be assumed that one cycle is enough to enter the room). Then change the location to IN_ROOM and state to EXPLORE_ROOM.
- If number of explored rooms, connected to the corridor is the same as number of doors n the corridor, then change the state to RETURN_TO_INIT.
- If the location of PICO is IN_ROOM:
- If the number of the detected room corners (besides exits) is 4, stop exploration and move to a different room/corridor.
- If there are more doors besides the entrance it came from, GO_TO_NEXT_ROOM; otherwise, EXIT_TO_PREV_ROOM.
- Similar to corridor exiting procedure with GO_INSIDE_ROOM and GO_TO_NEXT_ROOM (now also EXIT_TO_PREV_ROOM) applies for decision-making inside the room.
When returning to initial position:
- PICO is always located in the corridor when the state switched to RETURN_TO_INIT and GO_TO_START.
- When the global position of PICO is (0,0) with the margin of distance iteration set-point, switch to PARKING.
- PARKING state is executed for one cycle. Also the boolean to end the program is set to be true while setting to the state.
When searching for the object:
- First, GO_TO_NEXT_ROOM. When the distance to the entrance to the first room is closer than the constant set-point distance, switch to the GO_INSIDE_ROOM.
- When GO_INSIDE_ROOM is completed for one iteration, change the state to GO_INSIDE_ROOM.
- Every time entering a room, scan for an object. If an object is found, change the state to STAND_NEXT_TO_OBJECT. If close enough, also set the end of the program to true.
Monitoring is the function that chooses between the Planning block methods to execute based on the current state. This class does not introduce any new information, but rather serves as an structuring block for the planning methods.
Drive control class remained the same functionality as for the Escape room challenge. It is still getting a destination point in terms of distance and angle to it and drives for a fixed pre-defined distance in the direction of the point. It was improved, though, comparing to the Escape room in terms of reference tracking.
Previously, PICO could have exceeded the reference estpoint distance and angle parameters, since reference tracking was based on global coordinates. For the Escape room challenge, PICO first checked the odometry before moving and defined the desired final angle/distance in these global coordinates. When it reached the value, it stopped the movement. Such an approach worked well only for the first one or two destination commands, while making large errors later due to the global coordinates.
For the Hospital challenge, PICO's drive control class changed the reference tracking method, reseting the position and angle before the movement to 0. Again, the robot was moving till the reference is reached, however, now in local coordinates with 0 initial parameters. This resulted in accurate movement at any iteration of the program.
Testing against critical situations
While deciding on the strategy to complete the challenge, a brainstorm session was organized to think through practical aspects that might prevent us from completing the challenge. A short overview of these and their solutions are presented below.
If PICO is exiting a nested room and comes back to the main room, how to ensure that the it does not explore the room the second time and does not create a new object?
Among the other features of the room, it should also include a flag whether the room was previously explored or not.
How to ensure that the PICO is driving to the end of the corridor in the very first phase? What is the target point to move to?
The detection class also should output the point that is straight ahead of PICO.
Identification of rooms and corridor
A complication that could have caused a failure in our program is the initial location of the PICO in the Hospital. It is, indeed, given that PICO is located in the corridor at the start of the challenge, however, it is not specified whether the corridor has all the doors along a straight line from the initial position. For example, the robot might start in the appendix of the corridor, that has a only one "door" according to our conventions (corridor is the room that we start in and it ends in the opposite wall from the initial position). Since write-to JSON file only happens after we return to the corridor, how to store the data about the visited rooms efficiently without overwriting it?
Use a stack feature to store the properties of the "main room" (which is meant to be a corridor) such as number of doors. Visit each nested room and use a separate stack for those.
How to deal with T-junctions in the corridors?
Same approach as with the previous problem can be applied. The corridor is considered to be a room and the actual rooms become nested rooms in this interpretation.
If by the end of the exploration, PICO has 2 rooms with the same number of doors to be passed to reach that room, then it has to choose one and if the object is not found, a new path is constructed to the correct room.
Is it going to be a deadlock, when the destination point distance is smaller than the pre-set distance that PICO drives each iteration? (Referring to the drive control block description)
It will never happen, since critical decision-making functions incorporate this value in computations (e.g. change of low-state from EXPLORE_CORRIDOR to GO_TO_NEXT_ROOM, when moving through the corridor for the first time, is dependent on the pre-defined moving distance: the state changes when the corners of the corridor are closer than the pre-defined moving distance).
< Evaluation of our final challenge >