Navigation
Objective
- Describe the problem of obstacle avoidance
- Discuss the relation between path planning and path execution / obstacle avoidance
- Describe the roles a local map can play in a navigation system and the challenges with fusing several sensors
- Discuss the difference between static and dynamic obstacles
- Basic understanding of "cost maps"
- Discuss considerations for exploration
References to Spring Handbook of Robotics (SHoR) refer to the 2nd edition.
Introduction
In the planning module we learned how to plan paths from A to B, taking into account both kinematic and dynamic constraints. When executing such plans one of the big challenges is to detect and avoid obstacles along the path and to actually follow the path that you planned.
The sensor that your are using often do not cover the full field of view. For example a laser scanner might have a 180 degree field of view, meaning that you do not see anything backward. In a practical application you need to ensure that the robot does not forget what it has seen in regions of space that are currently not in view of the sensors. To do so, a local map is use. This map accumulates sensors information in the local neighbourhood of the robot.
The most common assumption made is that the world is static. When obstacles are dynamic the path planning becomes more challenging, especially if the motion of the dynamic obstacles are hard to predict and costly to collide with.
In ROS the planning system makes use of so called cost maps. In its simplest form they are binary maps that define free space and obstacles but they could include more fine grained information. For example, in a rough terrain application different parts of the environment might have different cost to traverse (road is easier to drive on than grass for example). The classification of the terrain is an important subproblem for such a robot as driving in some regions could put the robot at great risk.
Path execution and obstacle avoidance
The path generated by the path planner can be executed in several ways. The traditional way would be to let the global plan describe roughly how to move from A to B and then let a so called obstacle avoidance method take care of producing the actual motor commands taking into account the sensor data. Another approach which is applicable if the motion path planning method is fast enough is to re-plan whenever the path cannot be followed as planned. In the latter case we make use of a path following strategy to calculate the motion commands so that the robot follows the planned path close enough.
Obstacle avoidance
Get an overview of obstacle avoidance and look at two example methods (potential field and dynamic window approach) in SHoR 47.7-9.1 + 47.9.4
Path following
This is a control problem where the aim is to make the robot follow a prescribed path. In many robot applications we want to ensure that the robot stays close enough to a certain path and that the speed along the paths stays within some bounds. We are typically also extra interested in the end configuration, such as when you do parking.
One of the basic methods for path following is the so called pure pursuit method https://se.mathworks.com/help/robotics/ug/pure-pursuit-controller.html Links to an external site.
Local Map
Read about occupancy grids which is the most common representation for local maps (SHoR 45.2.1).
The local map serves the purpose of integrating information from sensors and to represent the local neighbourhood of the robot. It moves with the robot and information beyond a certain distance are that forgotten. Care has to be taken when integrating information from different sensor modalities. They might see different parts of the environments, due to aspects such as the height they are mounted on and the properties of the object being observed (laser sees through glass). This means that two sensors could be pointing in the same direction, one saying the space if free and the other that it is occupied. You need to be able to handle this. One often keeps separate local maps fir different modalities and then fuse information on a map level instead.
The local maps are used as input for planning and obstacle avoidance and in ROS they are often referred to as cost maps. When used for planning algorithms you typically want to preprocess the map by inflating the obstacles by the radius of the robot, this way the robot can be treated as a point when planning. These cost maps can be either binary or give more fine grained information about the cost so that one can distinguish between driving on grass and concrete for example.
Given that ROS defines the current standard for robotics in research and in some parts of industry and that cost maps are a central concept in ROS, read about this at http://wiki.ros.org/costmap_2d. Links to an external site.
Static vs Dynamic Obstacles
The majority of methods for planning and obstacle avoidance assume that the world is static and if it is not we assume the planning / obstacle avoidance method runs often enough to keep the robot safe. However, by modelling the motion of the objects you can sometimes achieve better results. As always when you make assumptions, in this case about the motion, you risk making the system less stable. If the object does not move as predicted you might be worse off than without any assumptions. People and other robots are a particularly important class of obstacles. Especially people must be avoided, as such collisions can severely damage the acceptance in the system. What makes these objects special is that you can influence they motion. There is a big difference between a person blocking a path and a box. The person is much more likely to move away unaided than the box. You can even influence the motion of the person by the motion of the robot or by speaking to him/her.
Exploration
A robot that is thrown into a new environment for which it has no prior map information needs to build a map using SLAM. However, SLAM only tells us how to fuse the sensor information that we acquire but not how to acquire that information. For this we need an exploration strategy. This strategy need to take into account the constraints of the SLAM system such as the need to close loops, detect landmarks, etc as well as the need for a speedy exploration of the environment, especially when there are constraints on, for example, the battery life. When doing exploration we often think of the map as having three states, occupied, free and unknown and exploration can be thought of as the process of changing all parts from unknown to ether free or occupied. A concept used by many exploration algorithms is that of frontiers, defined by the border between the unknown and free space. These regions in space are good candidates for places to move to during the exploration.
Autonomous Exploration and Inspection Using Flying Robots
Links to an external site.
Besides coverage it is important to keep track of the uncertainty in both map and robot position estimate when performing the exploration.
SHoR reading instructions
- Obstacle avoidance 47.7-9.1 + 47.9.4
- Path following 49.1
- Grid maps 45.2.1
- Terrain classification 45.3.5