[MUSIC] In this section, we'll describe another approach to guiding robots into obstacle filled environments based on artificial potential fields. The basic idea here is to try to construct a smooth function over the extent of the configuration space, which has high values when the robot is near to an obstacle and lower values when it's further away. We also want this function to have its lowest value at the desired goal location. And it's value should increase as we move to configurations that are further away. If we can construct such a function, we can use it's gradient to guide the robot to the desired configuration. As usual, it's easiest to start with an example in a two dimensional configuration space, where we can more easily visual what is happening. This figure shows a typical two-dimensional configuration space, where the black regions correspond to configuration space obstacles and the red dot indicates the desired goal location. Let's start with the easy part. Building a potential function that will guide the robot towards the goal configuration. There are many ways to do this but one of the most popular is to construct a simple quadratic function, that is zero at the goal and increases as you move away from it, as shown here. In this expression, the vector x denotes the coordinates of the robot in the two dimensional configuration space. While xg denotes the coordinates of the goal location. Xi is simply a constant that we used to scale a function. This slide shows a plot of how this function varies over the two dimensional work space. Note that the function value is zero at the goal and increases rapidly as we move away. Note the bowl-like shape that is characteristic of a quadratic function. If the robot were to follow the gradient of this function downhill, it would guide it straight towards the goal. We refer to this function as fa to remind ourselves that this is a function that attracts the robot to the goal. Now in addition to getting to the goal we also want the robot to avoid the obstacles in the environment. For this purpose we propose to construct a second function fr to repel the robot from these configuration space obstacles. Let row denote a function that takes as input the coordinates of a point in our two dimensional configuration space and returns the distance to the closest configuration space obstacle. If we have explicit representations of our configuration space obstacles, we can sometimes construct such a function analytically. Alternatively, if we are willing to discretized our two dimensional work space into a grid, we can apply an operation from image processing called a distance transformation to compute this distance at least approximately at every grid location. However we choose to do it we can use this distance function to construct a repulsive function, fr, which gets larger as you approach the obstacles and smaller are you move away as follows. In this function, the parameter d zero controls the influence of the function. If the distance between the robot and the obstacle is greater than d zero, the function shuts off. So it is only relevant when the robot approaches the obstacles, then it increases rapidly as you get closer and closer to the obstacle's surface. Again, there are many ways to construct a smooth repulsive function that will guide you away from danger. This is a particularly popular and convenient way. Here's a surface plot, showing how this repulsive function varies over our example two dimensional work space. Given these two components, an attractive potential, which pulls the robot towards the desired configuration, and a repulsive potential, which steers the robot away from obstacles. We can simply add them up to construct a function which tries to do both. Here is a surface plot, showing the sum of the two functions. Now that we have this potential function, how can we use it to guide our robot? Here, we appeal to calculus and use the gradient of the function to steer the robot. More specifically, we choose the velocity of the robot v based on the gradient of the potential function as shown here. Note the use of the proportionality sign here to indicate that the gradient will be used to decide on the direction of motion, but the speed of the robot, which corresponds to the magnitude of the velocity vector Is up to the programmer. You could for example choose to move at a constant speed until you got close enough to the target. Or you could choose to scale your speed based on your distance to the target. So that the robot slowed down as it approached the goal to avoid overshoot or other undesirable effects. To summarize the algorithm, the robot continually evaluates the gradient of the artificial potential field and steps in that direction until it is close enough to the desired goal. One way to visualize the action of this algorithm or control strategy is to think about a marble rolling down the energy surface towards the goal location. This animation shows what that would look like in this example. This figure shows an alternate depiction of the same information. A quiver plot where the arrows indicate the direction of the gradient field at various locations in the configuration space. The red line shows a trajectory that was constructed form a start location to the goal by following this gradient field. Here are a few more example trajectories constructed from the same potential field. A really attractive feature of this procedure is that it only requires a robot to be able to evaluate the gradient of this artificial potential function f. More specifically, it implies that the robot would be able to follow this procedure using only knowledge of its position and local sensor data, a robot that US position in space to easily evaluate the attractive component to the potential function. A robot that could measure the range to all obstacles within a distance, d zero of its current position. Would be able to evaluate the repulsive component of the function. The required gradient could be approximated by evaluating the potential function at a few locations in the vicinity of the robot's current position and then applying simple finite difference methods. In point of fact, these potential field methods were initially developed precisely because they provided a simple, direct approach for guiding a robot towards it goal while avoiding obstacles based on local sensor data. This is sometimes referred to as sensor based planning. The readings from the robot's position sensor are used to pull it towards the goal. While the measurements from it's range sensors like laser scanners or stereo systems are used to push it away from the obstacles in the environment.
