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 in the context of planning and navigation
Basic understanding of "cost maps"
Discuss considerations for exploration

References to Spring Handbook of Robotics (SHoR) refer to the 2nd edition.

Pre-Lecture reading Material

Look at the material on this page but you do not need to go into SHoR.

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

The problem can be defined as given sensor measurements, the position of the robot and the goal (could be the next way point along a path) calculate an appropriate control signal so that the robot moves towards the goal without colliding with obstacles.

Here we will mentioned three obstacle avoidance metods briefly.

In potential field methods you can think of the robot as a ball rolling on a surface towards lower ground (lower potential). The potential increases the closer it comes to obstacles and reduces closer to the goal. When turned into a practical control system you often formulate it as forces acting on the robot. The goal attracts the robot and obstacles repell the robot. You get the resulting motion vector by vector summation. It is very simple to implement and works well in simple cases but i) It is a challenge to tune parameters such as how the force depends on the distance to the obstacles and ii) the resulting motion often has sudden changes in direction and oscillations. The figure below (from Polvara et al 2017) gives a simple illustration
urn-cambridge.org-id-binary-20171219070016527-0192-S0373463317000753-S0373463317000753_fig10g.jpeg

The vector field histogram (VFH) method was developed to address some of the the shortcomings of the potential field method. You calculate the forces acting on the robot from the obstacles in N direction to generate a histogram (the vector field histogram). You then threshold this histogram to classify the different directions as either drivable or not. In the resulting binary histogram you look for "valleys" in the histogram that are wide enough for the robot to pass through there and then pick the valley closest to the direction of the goal. The images below are from the VFH paper by Borenstein and Koren. where you see the polar histogram with the threshold on the left and on the right you see the robot and the active window of the local map and the forces generated by the obstacles (dots). The letters allow you to see the correspondence between the peaks in the histogram and the right side image. The robot would most likely pick a motion direction which is to the left of A in this case given the location of the target.
Screenshot 2022-09-24 at 20.32.53.png

The dynamic window approach (DWA) is an optimisation based approach. The parameters that you typically optimise for are the translation speed (v) and rotation speed (w). Looking at the so called velocity space, spanned by these two quantities the dynamic window is defined by the values v,w that can be reached from the current speed (v_curr, w_curr) within a certain amount of time. The size of the window thus depends on the acceleration. You decretive the values inside the window to allow. search. You map the obstacles into the velocity space so that the (v,w) combinations that lead to collision can be made invalid. To find the best speed you do an exhaustive search for the best tuple (v,w) within the window. The objective function is a weighted sum of factors such as i) closest distance from obstacles, ii) speed and iii) progress towards goal. Below are three figures from the original DWA paper by Fox et al., where Fig 2 shows the robot in a scenario and Fig 4 and 5 show the velocity space with the obstacles mapped into it and the dynamic window respectively.
Screenshot 2022-09-24 at 20.23.30.png

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

Local Map

You know about occupancy grids (SHoR 45.2.1) from the previous lecture (Mapping and SLAM). An occupancy grid is the most common representation for local maps .

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.

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.

Rapid Exploration with Multi-Rotors: A Frontier Selection Method for High Speed Flight

Autonomous Exploration and Inspection Using Flying Robots

Besides coverage it is important to keep track of the uncertainty in both map and robot position estimate when performing the exploration.

Uncertainty-aware Receding Horizon Exploration and Mapping using Aerial Robots

SHoR reading instructions

Terrain classification 45.3.5
Obstacle avoidance 47.7-47.9.1 + 47.9.4
Path following 49.1