Embedded Motion Control 2019 Group 4

This is the CSTWiki page for group 4 of Embedded Motion Control 2019.

Group members

Marcel Bosselaar	0906127
Ruben Sommer	0910856
Jeroen Setz	0843356
Bram Grolleman	0757428
Martijn Tibboel	0909136

Deliverables

• Design Document
• Interim presentation
• Final presentation

Escape Room

The following ideas are used for the excecution of the Escape room.

Escape Room - Plan

The initial strategy that is formulated is as follows:

This plan is updated to gain more insights and control over the different situations that can happen.

[PLAATJE]

Escape Room - Exit recognition

Firstly walls are created from the lrf data. Next, these small walls are merged into large walls. For this, the 'split and merge' method is used as shown below.

• 

  Example first step

• 

  Example second step

• 

  Example third step

Then the corners are recognized. The 2 different kind of corners are recognized and from the right kind of corners the exit is generated. This is visualised below.

Animation of the exit detection flow

At last, the center point of the exit is calculated together with a point in front of this center point. This point in front is sent to the movement part of the PICO.

Escape Room - Finite state machine

A finite state machine is introduced in order to maintain control over what is happening at all times.

After the challenge, an alternative FSM was thought of that reduces the number of states required and vastly improves accuracy.

• 

  Diagram of the finite state machine used in the escape room competition.

• 

  Diagram of an improved FSM, thought of after the competition.

Escape Room - Testing

The following testing dates have been set. Also the goal of each testing date is put behind in order to stay on track of the global planning of the project.

PICO Test 1 (2019-05-08)

Goal

Have PICO detect the exit, and perform simple motion towards it.

PICO Test 2 (2019-05-13)

Goal

Use a more advanced algorithm to detect and move.

PICO Test 3 (2019-05-16)

Goal

Test improvements done based on competition results. If available, test ideas that were previously generated but would only be useful for the final competition.

Escape Room - Competition

In the escape room competition, we were potentially the team that had the highest high and the lowest low.

The algorithm we had designed worked perfectly and very quickly. The door was found as soon as it came into view, and PICO decided to move toward the correct location in front of the door. The door was then immediately found again, and PICO's position in front of the door was made more accurate. Then, the exit of the hallway was detected immediately, and PICO drove towards its end goal.

However, due to the fact that we had not managed to implement the odometry into PICO, distances traveled were around 30% too short, meaning PICO stopped well before the detected end of the exit hallway. In addition, telling PICO to drive straight didn't actually make it drive straight, making it graze the wall.

The first improvement we will need to make is the odometry, as we're confident PICO would have exited the room within 30 seconds if it actually was were it thought it was. Secondly, we should use the laser data more frequently, and create new plans during movement to keep things moving in the right direction. Improving the finite state machine to use fewer states and being more circular might also be a good addition.

Hospital Challenge

The following section explains the different functions build and used in the hospital challenge.

Hospital Challenge - Software architecture

The figure below gives an overview of the elements present in our software, with some of the most important functions these elements run, the data present in them, and the data sent around between them.

Overview of the software architecture

The control over which function is allowed to use what data comes from the definition of the functions. Each function gets access to certain variables that are relevant for their functioning.

Standard access is read-only, so the function basically creates a local variable that can be accessed by elements within the function.

Data that should be altered, represented by the arrows returning into the world model, is fed into the function with write permissions.

Hospital Challenge - Finite state machine

Due to the hospital challenge requiring different functionality from the escape room challenge, a new finite state machine was developed, visible below.

Diagram of the finite state machine used in the hospital challenge

Explanation

In this state machine, there is once again an initialization state, called init. Once PICO has been initialized, which is checked by grabbing LRF and odometry data and seeing whether it is correct, the event initialized occurs, and the state is set to initMap.

With the initialization of the state initMap, the localization flow has been started. This flow works by using the initMap state to have PICO gather LRF data, until such a time that the desired data has been collected. Once this happens, the initFit state is used to attempt to fit this data to the map, and orient the map correctly with regard to PICO. Should a fit prove impossible, the state initRepos will become active, in which PICO will attempt to reposition itself in a different location, and try to map and fit itself again.

Once PICO has localized itself, the state will switch to goalSelect, leaving PICO in the global movement flow. Here, PICO will select the cabinet it should travel to from the array created by user input in the goalSelect state. Once this has been done, the goalPlan state will use our rapidly-expanding random tree algorithm to generate a path to the selected cabinet.

The goalMove state handles the actual movement along the generated path to the cabinet, as well as dynamic obstacle avoidance. From this state, two escapes are possible. The first and most important is the goalAvoid state, triggered by the goalEmergency event. As the event implies, this state is designed for avoiding an emergency, and should only occur when an object suddenly comes too close to PICO, as the dynamic obstacle avoidance should keep PICO from reaching the emergency state during normal operation. The goalAvoid state then reorients PICO to a safe location, and the goalPlan state becomes active again.

Should PICO get stuck in the goalMove state and not be able to reach its target, the objectFound event is triggered, setting PICO to the goalObject state. In this state, PICO will add the unexpected object to the map, and once this is done the goalPlan state will become active again, and will plan a path around the new object that was added to the map.

The end of the global movement flow is signified when PICO has reached a point of half a meter in front of the cabinet. From this point forward, PICO will use its LRF sensor to enable precise local movement. The first state in this flow is cabFind, in which PICO will attempt to recognize a cabinet from its LRF data. Once this cabinet has been found, PICO will move towards it in the cabMove state, once again with an emergency avoid state.

When PICO has reached the desired position in front of the cabinet, the cabStop state will become active, in which PICO will pause in front of the cabinet and exclaim what is happening. Then, in preparation for movement to the next cabinet, the cabTurn state turns PICO around by 180 degrees, so he's looking away from the cabinet, and the global movement flow is once again initiated when the event cabTurned is thrown.

Global and local movement will keep occurring just as long as there are more cabinets in the array of supplied cabinets, when the event goalReached occurs. This event leads to the done state, signalling PICO to say goodbye and terminate the program.

Implementation

The state machine as described above has been implemented in the software as an enum type variable for the events and for the states. This type of variable can only have the values of the states/events, declared in its generation.

The monitor function is the only function that can alter the states, and it will do so based on the events generated by the other functions. For instance, when the event goalSelected is thrown, by way of the variable E having value goalSelected, the monitor will change the state to goalPlan, by way of changing variable FSM to goalPlan.

The perception, planning, and control functions will then display different behavior depending on what the value of FSM is. This is achieved by creating multiple successive if-loops that describe the behavior in a certain state or states.

Conclusion

With the finite state machine as described above, we have developed a usable way of controlling PICO's discrete behavior. Due to multiple loops in the state flow we believe to have kept the states to a sufficiently low number, while still having very clear states for very clear behavior. The implementation is susceptible to errors, as the events are not coupled to the state PICO is currently in, but with the use of the figure no programming errors have occurred.

Hospital Challenge - Localization

For the hospital challenge localization is key to achieve goals. If everything works but you don't know where you are it is going to be a mess. The idea is to update the localization every time the robot needs to make a new path with the path planning. In between two setpoints of the path, the odometry is used to know the current location and this is assumed to be 'good enough'. When something goes wrong and it is not enough, the state machine compensates, because the robot goes to a 're-planning' state, where it also updates the location again. This way it is never a problem if the accuracy of the localization is a bit off.

Diagram of the localization flow theorized for the hospital challenge

Point matching

The idea that is used for localizing PICO's location is as follows.

When PICO is being initialized, a calculation is done over the map information. All corners are specified with the right corner type 'inside' or 'outside' corner, which is also done for the LRF data as explained in the escape room challenge. For all corners of the map is the distance between the point and all other points calculated for use in the future.

Within the localization script a loop is made through all corners of the map and all corners that are specified in the LRF data. A point of the LRF data is checked if it has the same kind of corner as the map point. If that is true, another point of both data sets is checked if this has the same kind. When this holds, a distance is calculated between the points of the LRF and then checked if this distance is near the distance that it should be compared to the map. (which is stored in the beginning) Summarizing, this means that a wall with 2 points of the LRF data is checked if it is suits to be fitted to a wall of the map.

Next, this is done for another three walls, while aborting if one of the statements does not hold. This reduces the amount of possibilities of the best fit and the possible fits are stored in an array. After this, the script uses the stored fits to calculate a location of PICO in the map with the given distances from the LRF corners that are fitted in the fits. The different that come forward are analysed on the amount of occurances and unfeasible locations (outside the map for example) are removed from the possibilities.

From the locations that are found a mean location is calculated together with the guess (from the odometry data) where PICO possible could to obtain the final location of PICO. Accordingly to the location of PICO the map is translated and rotated in order to fit the map over the LRF data. This way the planning can be done easier, because it is assured that PICO is at the origin of the plot.

A problem occured while making this way of localizing. The localization had a lot of 'unwanted' locations, so that is why the above filters were added. This solved the problem, but still a offset remained within the localization. Later on it appeared to be a problem within the shifting of the map, because we were using multiple coordinate system which made reasoning pretty hard. In the beginning we thought it was the uncertainty of the found points that gave this offset, that is why we also looked at other localization options. Which in the end, turned out to have the same problem.

Alternatives

• Cabinet and Door recognition
• Particle filter

Hospital Challenge - Path planning

Path planning is defined here as finding a way from point A to B based on a known map while avoiding obstacles on this map. In general there are four different approaches to path planning for mobile robotics:

Cell decomposition

Divide the map into a grid and define obstacles as cells which can not be used for movement. Then an algorithm as A* or Dijkstra can be used to find the (optimal) path from A to B.

Potential fields

A map is converted to a potential field map in which obstacles have high values and free space low. This way a path from A to B can be created which follows the lowest potentials.

Sampling based

A sampling based algorithm finds points in the free space of a map and tries to connect them. Then a path is found from A to B following these points. Examples are a Rapidely-expanding Random Tree (RRT) or a probabilistic roadmap.

The requirement set for a path planning algorithm was to avoid a grid (to prevent scalability issues and limited cell resolution) and potential fields (as followed from the Do's and Don'ts lecture). Therefore one candidate remained: sampling based. The choice was made to use a RRT algorithm as is seemed easier to implement compared to a probabilistic roadmap. The benefit of using such a path planning algorithm is the generality. It does not need any predefined points, cells or possible paths. It can find a path on any given map with obstacles.

Rapidly-expanding Random Tree algorithm

A RRT algorithm starts with a root node. In this case the initial position of PICO. Each iteration a random point is created in the space of the map. The closest node of the tree to the random point is chosen to extend the tree in the direction of the random point. The connection of the newly placed node will be checked for validity (i.e. not colliding with obstacles on the map). This way the random tree will eventually span the complete free space. The algorithm terminates if the goal point B is reached with the tree. An open-source existing algorithm is used which creates a basic random tree. This is modified to work with our software. Two (major) additions are done to the existing algorithm.

RRT end point bias

To ensure a quick convergence of the tree towards the end goal (point B), an endpoint bias is used. This means that every few iterations the algorithm does not use a random point is space but the end goal. This way the tree will be extended in the direction of the goal. This proved to achieve a much faster algorithm which required a lot less iterations to find a path. The end point bias may to be too large (i.e. take every other random point as the end point) as the algorithm can get trapped in corners between obstacles.

RRT path splitting

A drawback of the RRT algorithm is that it will find a path which is generally not optimal. To optimize the found path, a splitting algorithm is used similliar to the splitting algorithm used to find walls in LRF data. It first tries to connect the start and end point of the path to see if it can be connected with a straight line without colliding with obstacles. If this fails, the check is done using the middle point of the path. This is done recursively to optimize the path. In the worst case scenario the original path will be retrieved again. The RRT splitting method showed to create nice straight lines between all points on the path, this still does not create an optimal path, but an optimized version of the original found path.

Resulting pathplanner

Using the two discussed additions to the random tree path planner, the final result is shown below. A path is created based on the obstacles (walls and cabinets) in the JSON file of the hospital challenge from initial position to cabinet 0. First a random path is found, in which the influence of the endpoint bias is clearly visible. Afterwards the path is approximated by straight lines using the path splitting algorithm. This results in points which can actually be followed smoothly by PICO. The path is shown not to cross any obstacles. Obstacle lines are slightly extended to prevent pico from driving too close to wall corners. This could be improved by blowing up obstacles instead of just extending them. When the path is created, is consists of an array of points. An extra orientation is added to these points in order to let PICO orientate itself in the direction in which it will drive to the next point. (Note: The image visualization is not the actual speed of the pathplanning algorithm, this could be much faster or slower depending on the map.)

Hospital Challenge - Movement

The movement of PICO from a start position to a cabinet is divided into two parts; global and local movement. This is also shown in the visualization of the finite state machine. The global movement is defined as following the path created by the pathplanner. This results in a path to a location which is 0.5 meter in front of the cabinet. Once this location is reached, PICO switches to the local movement flow. This basically means it has to find the cabinet and drive to the required distance of approximately 20 centimeter in front of the cabinet.

Hospital Challenge - Global movement

The global movement flow is visualized in the finite state machine diagram. It starts with selecting a goal (State = goalSelect), this is done based on the list of cabinets that should be visited. A counter is used which keeps track of how many cabinets are already visited and the next one is selected as goal. If all cabinets are already visited, the program is shut down. Once the goal is selected, a path to this goal is planned using the RRT pathplanner (State = goalPlan).

Once the global path is created, PICO has an array containing positions (x,y) and an orientation which should be reached. The trajectory() function in the control section sets the velocities needed to reach the next point in the path. Once PICO is at a distance of 0.5 meter of the point in the path, the next point is selected to drive to (State = goalMove). This prevents PICO from stopping in between points and ensures he moves smoothly along the path. Once PICO is driving to the final point of the path, the required distance to the point is much smaller to ensure it actually reaches his final position. During the goalMove state, two situations can apear: Emergency or Stuck. The emergency state requires PICO to stop and plan its path again. The Stuck situation appears when PICO does not move significantly for a certain amount of time. This means PICO has probably encountered an obstacle in its path which was not on the map. PICO will scan the room and add obstacles in sight to the map. Then the state is set to goalPlan again. The obstacles found in its path will be taken into account when planning a new path. When the final location is reached, PICO will switch to the local movement flow.

Hospital Challenge - Local movement

As stated in previous section, after PICO has reached its destination determined by the RRT, PICO switches to local movement flow. In this flow, PICO moves towards the cabinet based on LRF-data. This is done in a few steps: firstly, PICO scans the room. In this step LRF-data is updated and the algorithm is started which finds walls, doors, corners etc, which results in an updated world model. Secondly, PICO searches for corners in the world model with certain requirements (distance to PICO, distance between corners and corners of type "outside") to find the front wall of the near cabinet. If this step might fail, PICO starts rotating and executes this step again until the cabinet is found. Thirdly, PICO moves to the desired position in front of the cabinet on odometry data.

Hospital Challenge - Obstacle avoidance

Hospital Challenge - Dynamic obstacle avoidance

The avoidance of obstacles during driving, and which does not require PICO to stop and plan a new route, has been labeled dynamic obstacle avoidance.

Two different algorithms were developed, with a similar thought behind them. The first was to look at the nearest point to PICO, and push PICO away from this point. The biggest issue with this method was that PICO will jitter immensely when moving through narrow hallways or similar features. In order to solve this, a second algorithm was developed. This second algorithm has a similar functionality, but it looks at all points that lie within a certain safety range, and pushes PICO away from them simultaneously. Different strengths of the repulsion are defined in x and y-directions, allowing finetuning of the avoidance behavior.

GIF?!

Implementation of the dynamic obstacle avoidance has been done as follows:

First, the trajectory function determines the velocities required to move to the next point in the path, including initial acceleration and final deceleration. These velocities are entered into the avoid function, which uses the data from the LRF readings to push PICO away from any objects that are too close for comfort by altering the velocities that were input. Finally, the slow function slows PICO down when too close to objects, to ensure PICO can stop quickly when emergency situations might occur, and to scale the velocities down to the maximum when the avoid function has been too aggressive in its avoidance.

Hostpital Challenge - Testing

The following tests were planned and performed for hospital functionality

PICO Test 5 (2019-06-03)

Result

The software was not ready for testing, so the test was cancelled at the last minute.

Minutes

• Meeting 1 (2019-04-29)
• Meeting 2 (2019-05-06)
• Meeting 3 (2019-05-08)
• Meeting 4 (2019-05-13)
• Meeting 5 (2019-05-20)
• Meeting 6 (2019-05-27)
• Meeting 7 (2019-05-29)
• Meeting 8 (2019-06-03)
• Meeting 9 (2019-06-05)
• Meeting 9 (2019-06-12)

Tips & tricks

Install Qt