Path Planning Using Potential Field Algorithm
Abstract
Unmanned aerial vehicles (UAVs) have recently attracted the attention of researchers due to their various potential civilian applications. However, current robot navigation technologies need further development for efficient application in various scenarios. One key issue is the Sense & Avoid capability which is currently of immense interest to researchers. For autonomous decision making and control of UAVs, several path-planning and navigation algorithms have been proposed. The aim of this paper is to carry out a comprehensive study on UAV path-planning algorithms and how potential field algorithm works. The test case scenario presented in the experiment helps in understanding how the time complexity varies with the dimensions and provided space of the system.
Key Words
Path-planning, Robotics, Obstacle Detection, Potential Algorithm, A* Algorithm, Algorithm Efficiency
Introduction
Using robots to minimize human work has become a rising field of research in the past few years. From using mobile robots for military purposes on land as well as underwater to using them in restaurants for cooking food for customers, robotics has become an emerging field for human ease. However, one major problem while dealing with unmanned vehicles is path planning and obstacle detection while minimizing the input energy and getting the optimum results. Some recent literary works have been addressing this issue regarding how to use different techniques to create an obstacle distribution model and how we can get the desired results while making a few assumptions in a real-world system.
Potential Field Algorithm is one of the most fundamental and traditional algorithms used for such a problem. This paper will give a brief overview of how different algorithms can be used for path planning purposes and how the potential field algorithm helps us in Obstacle Detection in accordance to the literature sources used and the results achieved by the experiment conducted.
A Comparative Study of Different Path-Planning Algorithms
Several scientists have been dealing with path planning optimization and obstacle detection problems in the recent past. A number of algorithms can be used and manipulated in several ways in order to use them for path-planning of UAVs. The following is an overview of the family of algorithms and their features:
1. Potential Field
· Difficult to implement for a real-world application
· Poor performance in narrow passages
· Poor performance in a dynamic environment
· Prone to get stuck in local minima situations
· Problems in dealing with the symmetrical obstacles
· It is a subset of Dynamic Programming with optimal substructures
· It can lead to an optimal answer in a grid-based map
· Better performance compared to Dijkstra and Bellman-Ford algorithms[i]
· Capable of solving hard path-planning problem
· Due to high computational complexity, not a suggested method for on board implementation
· Highly capable heuristic method.
· Time of computation and algorithm complexity is highly dependent on the algorithm implementation.
· The recent combination of this algorithm with the learning process resulted in a very promising online application[ii]
4. A* Algorithm
· It can provide a general heuristic approach for the search of an optimal path
· It can potentially search a huge area of the map
· The worst case for this algorithm results in considering all the nodes and edges in the graph
· The solution time would benefit from a static environment
· Based on the scenarios, may lead to optimal or near-optimal solutions
· It solves a complex problem by breaking into a collection of sub problems
· It requires memories to save all the solutions generated from iterations
· Time of computation rises as the size of the problem grows
· The solution guarantees the optimal answer based on the implementation
Terminologies to Be Used
Potential field algorithm has been used for obstacle detection and path planning in robots traditionally. While studying the algorithm, a few terminologies must be defined to make the explanation straightforward. The following is a brief summary of the terms being used in the paper in order to explain the algorithm efficiently:
· World space is a space where the vehicle exists.
· Configuration is a vector containing the parameters required for defining the positional state of the vehicle which usually consists of three position coordinates and three orientation coordinates of an UAV.
· Obstacle space is the physical space occupied by obstacles.
· Free space is the physical space which is not occupied by obstacles.
· Path is the curve, in a physical space, traced by the vehicle.
· Path planning comprises determination of a path from the present state called the initial state to the final state called the goal state.
· Local goal refers to the intermediate goal that the UAV tries to achieve in order to transition from the initial state to the goal state. This involves solving a number of sub-problems to obtain the solution of the general overall problem. The overall objective is finding the path or trajectory for navigating the UAV to the global goal.
What is Potential Field and How Does it Work?
A potential field is any physical field that obeys Laplace’s equation. Some common examples of potential fields include electrical, magnetic, and gravitational fields. A potential field algorithm uses the artificial potential field to regulate a robot around in a certain space. For our ease, we consider a space to be divided into a grid of cells with obstacles and a goal node.
The algorithm assigns an artificial potential field to every point in the world using the potential field functions which will be described further in the explanation. The robot simulates from the highest potential to the lowest potential. Here, the goal node has the lowest potential while the starting node will have the maximum potential. Hence, we can say that the UAV moves from lowest to the highest potential.
Potential Fields Generated:
Two kinds of artificial potential fields are generated within the system: Attractive field and Repulsive fields.
The goal node exhibits an attractive field while the obstacles in the system produce repulsive fields.
Force of repulsion α 1/Distance from the robot to obstacles.
Hence, the generated total force at each point of the graph is:
Utotal=Uattraction+Urepulsion
Force of Attraction:
The following function can be used for generating the force generated by the goal node. Here, x and y are the coordinates of the starting node, (xgoal,ygoal) are the coordinates of the goal node and C is a constant.
Force of Repulsion
Two kinds of repulsive forces are produced within the system:
1. Repulsive forces by the boundaries:
This force remains uniform throughout the system and hence, doesn’t affect the calculations; this force is useful in keeping the robot away from the boundaries. The following equation can be used to find the repulsive forces exhibited by the boundaries:
where gi is a linear function that represents the boundary of the convex region, δ is a constant number with a small value and s is the number of boundary face segments.
2. Repulsive forces by the obstacles:
The force of repulsion from obstacles can be calculated through the formula given below. Here, pmax is the highest potential, (x0,y0) are the coordinates of the center of an obstacle and l is the side length of the obstacle:
Hence, the resultant force on the environment is:
P=P0 + Pgoal
Where,
P0= max{pi}
Local Minima Trap
A challenge for potential field algorithm is the local minima trap issue. This occurs when all artificial forces (attractive and repelling) cancel each other out such as in situations when an obstacle is located exactly between the UAV and the goal or when obstacles are closely spaced. Several approaches can be used to overcome this issue[iii]. The solution approach that we use here adds an imaginary obstacle in the local minima region to repel the traveling object.
Pseudo Code for the Algorithm:
Time Complexity of the Algorithm
Potential field algorithms require evaluating forces in the configuration space and the complexity of these algorithms can often be O(M^D ) where M is the total number of nodes in the space of computation and D is the dimension of the space. Successful application of this algorithm can be found in robot path-planning.
Results & Analysis of Algorithm
Consider the grid below with obstacles(yellow colored cells) and the goal node(blue colored cell):
Calculating the forces for repulsion by boundaries using the given formula:
Where:
The calculated forces of repulsion by the 3 obstacles are:
As shown in the picture above, we calculate g(x,y) for the center co-ordinates of each cell in the world.
Hence the potential generated by each obstacle Pi is given by:
The resultant force calculated by adding the attractive and repulsive forces is:
Hence the potential at each cell in the world is:
The arrows in the picture above represent the path followed by the robot. Here, we notice that the resultant path followed is the shortest possible path while ignoring the obstacles in the path. The time taken for solving the grid above is O(M^2).
Through the process of tessellation, the entire area is divided into cells. The only points considered in path planning calculations are the centers of each cell. The UAV is constrained to travel only from the center of one cell to the center of cells connected to the UAV’s currently occupied cell. Virtual objects are used to avoid local minima traps in the domain.
Conclusion
From the simulation study of the potential field algorithm, we found that this algorithm has a reasonable time solution, but it shows poor ability to overcome the local minima trap and provides non-optimal results. Different scenarios may yield different results as the algorithm is difficult to implement is real world scenarios. It is clear from the results that there is a trade-off between the optimality and computational time requirements. Choice of the algorithm in practice needs to be based on operational requirements in terms of computational time and optimality.
References:
[i] B. M. Sathyaraj, L. C. Jain, A. Finn and S. Drake, Multiple UAVs pathplanning algorithms: A comparative study, Fuzzy Optimization and Decision Making 7(3) (2008) 257–267.
[ii]N. Ernest, D. Carroll, C. Schumacher, M. Clark, K. Cohen and G. Lee, Genetic fuzzy based artificial intelligence for unmanned combat aerial vehicle control in simulated air combat missions, J. Def. Manag. 6(144) (2016) 2167–0374
[iii]N. Ahuja and J.-H. Chuang, Shape representation using a generalized potential field model, IEEE Trans. Pattern Anal. Mach. Intelli. 19(2) (1997) 169–176
Bibliography
Y. K. Hwang and N. Ahuja, A potential field approach to path planning, IEEE Trans. Robot. Autom. 8(1) (1992) 23–32.
Y. Koren and J. Borenstein, Potential field methods and their inherent limitations for mobile robot navigation, in Robotics and Automation,1991. Proc, 1991 IEEE Int. Conf. (IEEE, 1991), pp. 1398–1404.
Radmanesh, Mohammadreza & Kumar, Manish & H. Guentert, Paul & Sarim, Mohammad. (2018). Overview of Path Planning and Obstacle Avoidance Algorithms for UAVs: A Comparative Study. Unmanned Systems. 6. 1–24
Y. Koren and J. Borenstein, Potential field methods and their inherent limitations for mobile robot navigation, in Robotics and Automation, 1991. Proc, 1991 IEEE Int. Conf. (IEEE, 1991), pp. 1398– 1404. M. G. Park and M. C. Lee, A new technique to escape local minimum in artificial potential field based path planning, KSME Int. J. 17(12) (2003) 1876–1885.
G. Faria, R. A. F. Romero, E. Prestes and M. A. P. Idiart, Comparing harmonic functions and potential fields in the trajectory control of mobile robots, in Robotics, Automation and Mechatronics, 2004 IEEE Conf., Vol. 2 (IEEE, 2004), pp. 762–767