Path Planning and Optimization Techniques

Path Planning and Optimization Techniques: History

Please note this is an old version of this entry, which may differ significantly from the current revision.

Subjects: Automation & Control Systems

Contributor:

The optimization algorithms for pathfinding for ground robotics [20,21,22,23,24], aerial vehicles [25,26,27], and underwater vehicles [28,29] includes a wide range of applications. The most well-known applications for autonomous vehicles are obstacle avoidance, path planning, localization, navigation, sensing, and communication, which works on pre-essential maps related to the environment; they also play a vital role in communication relay, aviation industry for surveillance, and loitering dominated missions.

path planning
ground vehicle
underwater vehicle
UAV
robotics
numerical techniques
bio-inspired techniques
hybridization
non-linearity

1. Introduction

The 21st century is the century of autonomy, which accounts for the revolutionary turn in science and technology. The first autonomous guided vehicle was introduced in the 1950s when Barrett Electronics of Northbrook devised a trailer truck that can follow a wire on the ground instead of a truck [1]. Advancement in research and commercial technology made it conceivable for UAVs, robots, and their related application to appear in our daily life activities at an unprecedented rate [2,3]. For UAVs, Dull Dirty and Dangerous (DDD) missions [4,5,6,7,8,9,10,11] are the most prominent applications, whereas for robotics, iRobot applications [12] and Self-Driven cars [13] have gained much importance in research area as well as in commercial technology. Such vehicles require autonomous path planning algorithms to be energy/time efficient for their implementation.

The vehicles are equipped with intelligent equipment to localize their position, detect obstacles, and control the motion utilizing suitable navigational techniques to perform navigation tasks. Hence the selection of appropriate navigational techniques is essential for path planning, optimization, and obstacle avoidance. For path planning and motion control of the vehicle, it is envisaged that the vehicle possesses the capability of detecting the obstacle during motion and judge the environment for traveling. So the question becomes, what is expected from such vehicles?

The primary objective of researchers is to develop a real-time autonomous guided vehicle that can travel and can interpret the information gathered from the environment to precisely determine the position and direction towards the goal in both structured and unstructured (obstacle cluttered) environments [14]. The next objective is to achieve all these tasks with the shortest, safest, and most economical route, which ensures the computational and space complexity without anybody’s intervention [15,16].

Traditionally, path planning involves (a) acquiring information from surroundings, (b) localization of current position, and (c) cognitive mapping helps in taking the required decision satisfying algorithm and executing the task [17]. The autonomous guided vehicle research area lies in formulating computational, algorithmic structures that must be applied to hardware structures utilizing minimum resources. By optimization, further enhancement can be made. An efficient path planning technique of autonomous vehicles can reduce search time and minimize the capital investment of autonomous robots. Optimizing autonomous vehicle path planning involves various practical applications, e.g., disaster management, rescue operations, job performance in industries and factories, agriculture, restaurants, homes, and many others. Due to their applicability and diversity, it has gained importance for researchers to explore the various branches. Autonomous vehicles do not need human assistance for their operation. Any autonomous vehicle needs a path planner to determine the next movement in any indoor/outdoor environment. The definition of path planning differs from researcher to researcher [18,19].

2. Numerical Techniques

Vehicle trajectory optimization is treated as an optimal control problem [9]. Except for simple problems, optimal control problems must be solved numerically. Numerical methods for solving optimal control problems are divided into three methods: indirect methods, direct methods, and dynamic programming [79]. These three methods are then further sub-categorized into different sub-categories, which are graphically depicted in Figure 4 and elaborated in the following section.

Figure 4. Numerical approaches for the control problem [9].

Dynamic programming: Dynamic programming [80] is an optimization approach that transforms a complex problem into a sequence of simpler problems. The optimality criterion in continuous time is based on the Hamilton–Jacobi–Bellman partial differential equation.
Indirect methods: In the indirect method [81], the calculus of variations is used to calculate the first-order optimality conditions of the original optimal control problem. The indirect approach solves the problem indirectly by converting the optimal control problem to a boundary-value problem. As a result, the optimal solution is found in an indirect method by solving a system of differential equations that satisfies endpoint and interior-point conditions.
Direct methods: In a direct method, the state and control of the optimal control problem are discretized in some manner, and the problem is transcribed to a non-linear optimization problem or non-linear programming problem (NLP). Direct methods are divided into three categories: direct shooting [82], direct multiple shooting [83], and collocation. Direct collocation methods utilize a polynomial approximation to the integrated state equations between the nodes, whereas direct shooting methods directly integrate state equations. Arguably, the most powerful methods for solving general optimal control problems are direct collocation methods [79]. A direct collocation method is a state and control parameterization method, where the state and control are approximated using a specified functional form. The two most common forms of collocation are local collocation [84] and pseudospectral (global orthogonal) collocation [84]. In optimal control, local collocation has been employed using one of two categories of discretization: Runge–Kutta methods or the orthogonal collocation method [85,86,87]. In the pseudospectral method [88,89], the optimal control problem is transcribed to a non-linear programming problem (NLP) by parameterizing the state and control using global polynomials (basis function are Chebyshev or Lagrange polynomials) and collocating the differential-algebraic equations using nodes obtained from a Gaussian quadrature. The collocation points are the roots of an orthogonal polynomial (such as Chebyshev or Legendre polynomials) and/or a linear combination of an orthogonal polynomial and its derivatives.

2.1. Applications to Aerial Vehicles

Researchers utilize different optimal control solvers to determine the optimal trajectories for UAVs in different conditions. Some related work is referenced below:

Using optimal control software, Sachs [90,91,92] calculated an energy-neutral trajectory. Trajectory finders include Graphical Environment for Simulation and Optimization (GESOP) [93] and Aerospace Launch Trajectory Optimization Software (ALTOS) [94]. ALTOS is an ideal trajectory finder and optimization tool for aeronautical vehicles. This is because, in the presence of multiple local minima, the initial guess might significantly impact the solution’s conclusion. Sachs [95] generated energy-neutral paths for trajectory optimization using two different optimization software: BOUNDSCO and TOMP. The first software, ’BOUNDSCO’, uses multiple shooting techniques, while the second, ’TOMP’, uses a parameter optimization strategy to determine optimal control.

Zhao et al. [96,97] used a collocation strategy to turn the optimal control issue into parameter optimization, which they solved numerically with the software Non-linear Programming Solver” (NPSOL) [98]. NPSOL employs a Sequential Quadratic Programming (SQP) technique, where the search direction is a quadratic programming sub-problem solution. The step size is repeatedly chosen at each iteration to create a suitable drop in the augmented Lagrangian merit function. The NPSOL program’s results represent a locally optimal solution to the non-linear programming problem after successful convergence.

2.2. Applications to Ground Vehicles

The concept started with the DARPA Urban Challenge. Later on, numerous controllers have been developed for dealing with the non-linear characteristics of autonomous vehicles. Different controllers has been designed for autonomous guided vehicles, e.g., PID controller [105], sliding mode controller [106], linear quadratic regulator [107], fuzzy logic controller [108], backstepping controller [109], adaptive control [110], and pure pursuit controller [77]. Some related work from the literature is referenced below:

Thaer et al. [111] studied the robotic arm control parameters with numerical solutions involved with the help of the Runge–Kutta method. The non-linear equations are incorporated with formulas of centrifugal effects, Coriolis, and gravitational torques. The method employed was an attempt to mitigate the error involved in the industrial robotic arm, which helps in the increased production system. The acquired results validate the effectiveness of the numerical method and help in analyzing the variations in position and velocity joints. The Runge–Kutta method output perfectly matches with actual velocities. PeiJiang et al. [112] used a backpropagation algorithm for the path planning solution in the autonomous robot. The path solution is presented by the numerical method. The concept is employed on the robotic arm manipulator. The industrial robot used for this purpose is the KUKA KR 210 R2700 EXTRA robot. Experiments are performed for validating the path tracking. The mean absolute error for a position is also presented. A comparison between the numerical solution based on the Newton–Raphson algorithm and the path planning solution demonstrates the high-end accuracy and efficiency of the path planning solution. Anirudha et al. [113] designed a stability controller by the use of a sums of squares set defined in Lyapunov inequalities. The proposed polynomial controller can be used for handling time-variant dynamics resulting from oscillations involved in trajectory formation. The approach is implemented on an under-actuated double pendulum (Acrobat) and validates that the proposed method performs efficiently. Azali et al. [114] solve the path planning issue iteratively using the numerical method. The Laplace equation is used to calculate the potential function. The author came up with a block iterative method known as 4 Point-EG to resolve the trajectory planning. The experiment shows that the proposed method can generate a clear path from the start to the goal position and validates that 4 Point-EG works better compared to previous methods involved in trajectory formation.

2.3. Application to Underwater Vehicle

The autonomous underwater vehicle system’s (AUV) navigation and controllers have achieved the same importance as ground and aerial vehicles. They are also known as ocean vehicle navigation. It is equally important to address the related literature involved in the AUV system.

Similar to ground and aerial vehicles, autonomous underwater vehicles (AUVs) also need path planning to have an optimal path for their navigation. However, due to data transmission, the sensing range, and power constraints, the sea environment is vulnerable to numerous challenges compared to ground and aerial vehicles. When underwater, it is not easy to communicate effectively because of the continuous fluctuating bandwidth channel. This makes path planning of autonomous underwater vehicles a very challenging task. Motion planning can be categorized into path planning and trajectory planning, and the former can be defined as the course points that the vehicle has to travel to reach the destination point, whereas the time required to complete this journey is formally called trajectory planning. Since no global positioning system (GPS) and no external communication are available underwater, it is hard to acquire information with limited power, and thus, it is hard for an AUV to navigate. Primarily three navigation methods have been suggested [116,117]: (i) acoustic navigation, (ii) dead-reckoning and inertial navigation systems, and (iii) geophysical navigation. Based on the literature survey, they can be categorized as ‘close-to-bottom navigation’, ‘close to-surface navigation’, and ‘navigation in the mid-depth zone’. Figure 5 shows communication between an autonomous underwater vehicle with unmanned aerial-aquatic vehicle (UAAV) for its navigation purpose.

Figure 5. The communication between the autonomous underwater vehicle with the unmanned aerial-aquatic vehicle [118].

3. Bio-Inspired Methods

Siddique et al. [137] studied meta-heuristic and nature-inspired algorithms that imitate natural phenomena of natural sciences. Numerous researchers have addressed the ground and aerial vehicle trajectory planning and obstacle avoidance problem using the optimization algorithm that mimics the behavior of living things, such as fish, ants, bees, whales, wolves, and bats [138,139,140,141,142,143]. They are known as non-conventional methods. These algorithms are known as bio-inspired techniques and have been utilized in engineering to solve complex mathematical problems in research [144].

Bio-inspired computational-dependent techniques utilized the idea acquired from observing how nature reacts to different things and behaves to solve complex problems, which are considered and characterized with uncertainty and imprecision, to acquire robust solutions at a minimum cost [145]. The most prominent bio-inspired algorithms used in trajectory formation and obstacle avoidance for ground robotics include Artificial Neural Networks (ANN), Fuzzy logic, Genetic Algorithm (GA), Artificial Bee Colony (ABC), Simulated Annealing (SA), etc. The newly established algorithms include the Grey Wolf Optimizer (GWO), Moth Flame Optimization, Whale Optimization Algorithm (WOA), Ant Lion Optimizer (ALO), Dragonfly Algorithm, Grasshopper Optimization Algorithm, and Slap Swarm Algorithm. Bio-inspired algorithms are considered better for performing computational-based navigation for path defining as compared to conventional based algorithms, such as the Artificial Potential Field [146]. Many researchers integrate these non-conventional algorithms with reinforcement learning to increase the performing capability of ground vehicles in a cluttered obstacle environment. Some techniques are mentioned in Table 4 to give insight to the readers.

3.1. Application to Aerial Vehicles

Jesimar et al. [166] applied a Genetic Algorithm to path planning for UAVs during the emergency landing situation. Path planning uses a mathematical function, which caters to all constraints. Three different path planning approaches are used: the Genetic Algorithm, greedy heuristic approach, and multi-population algorithm. The greedy approach helps determine the quick solution, whereas the genetic algorithm returns a better quality solution, which helps mitigate the computational time. The methods were validated on a huge dataset with different levels of difficulty. Simulations were carried on the FlightGear simulator, where the behavior of UAVs was checked under different wind directions and velocity directions. The overall statistical analysis demonstrates that combining genetic algorithms with a greedy approach is beneficial for the path planning of UAVs.

3.2. Application to Ground Vehicles

Farhad et al. [170] attempted to investigate the neural network technique with statistical dimension reduction techniques to execute the navigation task and obstacle avoidance for the robot. The proposed method uses two feed-forward neural networks with a back-propagation learning algorithm. Laser (SICK) is used with a 180

^{\circ}

range to visualize the surrounding environment. The algorithm checks on real-world and experimental results to prove the efficacy of the proposed algorithm. Lingyan Ran et al. [171] worked on vision-based lightweight robot navigation based on uncalibrated spherical images. To improve the trajectory formation, the navigation problem is divided into sub-classification tasks. A 360

^{\circ}

fisheye camera is introduced for acquiring spherical images in different heading directions. The classification is accomplished using a Convolutional Neural Network (CNN). The CNN tends to predict paths in different directions with high efficiency. Experimental results prove the validity of the proposed method. Ngangbam Herojit et al. [172] presented the problem related to the navigation of ground robotics and obstacle avoidance with an Artificial Neural Network. The entire area is divided into five segments, then MLP (Multilayer Perceptron) is activated to find the collision-free path. The simulation proves that the said algorithm gives optimal results for reaching the goal position.

3.3. Application to Underwater Vehicles

Carlos Miguel et al. [197] worked on underwater glider (UWG) vehicles to ensure their mission success and safety. UWG is considered energy-efficient vehicles, and for performing journeys, they are equipped with sensors that collect data from their surroundings. For a safe journey underwater, the vehicles need to maneuver with a low speed and cater to strong ocean waves, which require extensive path planning. Gliders are often involved in multi-objective functions, e.g., shortest path, obstacle avoidance, energy efficiency, etc. The proposed method involves the non-dominated sorting genetic algorithm II (NSGA-II) to support the motion of gliders in a 3D environment. Glider kinematic simulators coupled with NSGA-II were used to perform experiments for controlling multiple control parameters to perform trajectory optimization. The authors were able to configure the parameters for the desired trajectory and proved to perform a real-time experiment in the ocean.

4. Hybrid Algorithms

4.1. Application to Aerial Vehicle

Author Li et al. [207] discussed the engineering problems with the help of the Improved Moth Flame Optimization. The proposed algorithm is implemented on a Levy flight trajectory formation. Harun Ilango et al. [208] presented the comparison of the Moth Flame Optimization, Bats Optimization Algorithm, and Artificial Bee Colony Algorithm for the landing stage involved in UAV. The objective lies in determining the optimal landing path for UAVs in a minimum amount of time. The empirical results obtained from the Moth Flame Optimization Algorithm take less time to find the optimal path than the other algorithms. Rehan Tariq et al. [209] presented the Intelligent Moth Flame Optimization-Based Clustering (IMOC) for drone assistance. The technique is used for maximum coverage using the cluster head approach, which helps find the optimal route. The comparison was made with Ant Colony Optimization (ACO), Grey Wolf Optimization (GWO), and Comprehensive Learning Particle Swarm Optimization (CLPSO). When compared with these algorithms, the proposed algorithm IMOC outperforms the other algorithms in improving the path criterion for UAVs.

4.2. Application to Ground Vehicles

Hao Wang et al. [214] presented the integration of the Artificial Neural Network with Fuzzy Logic for path planning. The fuzzy neural network can process data in parallel form and can process fuzzy inference functions according to the need for planning the mobile robotics trajectory. The simulations were performed in an unknown environment with static obstacles. The results obtained from simulations show a fast convergence and high efficiency for finding the optimal path. Pengchao Zhang et al. [215] proposed that the integration of the traditional algorithm with the heuristic programming algorithm based on AI has beneficial results. The traditional rapidly exploring random tree algorithm is incorporated with a neural network to tune path smoothness and path planning functions. The simulations were performed in real-time to check the feasibility of the improved algorithm, which shows the improved results for handling navigation problems. Buddhadeb Pradhan et al. [216] investigates the problem of multi-robots for finding the goal point. Each robot’s motion is controlled by the Particle Swarm Optimization, which the Feeds Forward Neural Network tunes. The coordination algorithm is implemented by a coordinated, cooperative algorithm that maintains the step count of all robots. In the first step, the Artificial Neural Network (ANN) is hybridized with PSO to find the easiest path using acceleration and velocity constraints; the second step, the first and second-order stability analysis, is employed to carry out the convergence. The experiments performed with the proposed algorithm show efficacy and demonstrated promising results. Same as ground vehicles, researchers have also worked on autonomous underwater vehicles.

4.3. Application to Underwater Vehicles

Daqi Zhu et al. [219] have demonstrated the autonomous underwater vehicles (AUV) in two steps by proposing Glasius Bio-inspired Neural Network (GBNN): (i) the construction of a grid map is done via discretization of 2D environment, (ii) then the neural network is constructed on the grid map. At the final stage, a full path is converged using GBNN, and obstacles are avoided using path templates. The simulations show that AUV can fully cover the environment and shows exceptional maneuverability when stuck in a deadlock situation without delay. The results also demonstrate a low overlapping rate with minimum path planning time when using the proposed algorithm.

5. Challenges Involved in Path Planning Methods

Though many researchers have studied the path planning for ground, aerial, and underwater vehicles, no algorithm/technique can guarantee 100% results; moreover, the tendency to get stuck in local/global optima or the incapability to judge the obstacle in front may lead to numerous challenges involved with these techniques. These drawbacks significantly affect the performance of the autonomous guided vehicle. Some challenges are mentioned below:

The most used approach for detecting obstacles or planning a path is the deployment of sensors or cameras around any vehicle [236,237]. However, these sensors’ readings are neither accurate nor reliable as they are integrated with noise, temperature, and system oscillations, etc. This leads to uncertainty in the system output, which causes unintentional error in the output of the algorithm [238]. The vehicle may produce oscillations and noise, which affect the real-time efficiency related to the data acquired from the environment [239]. Plenty of research has been performed to mitigate and cater the noise occurrence in the vehicle system; however, this is still a challenge. These problems and plenty others widely disturb the implementation of any algorithm in real-time [240]. In vision-based algorithms, the problem lies in identifying pairs of points in the same dimension [241]. This causes ambiguity in identifying points, which results in inconsistent interpretation of any image [242].

Another problem lies in some algorithms that rely on the surrounding environment map for the vehicle to make any decision for navigation. This leads to unnecessary halts in the motion of the vehicle. Baldoni et al. [243] demonstrated this challenge through simulations and shows that the generation of the optimal path for any vehicle is complex, and even if the vehicle reaches the desired destination point, it does not produce smooth navigation.

ANN may have a lot of advantages, as stated earlier, but they require an extensive data set of the surrounding area for the adjustment of hidden layers [244]. The famous backpropagation algorithm has its disadvantages, as it quickly converges to the local minima problem [245]. Table 7 depicts the challenges involved in path planning.

8. Conclusions

Trajectory planning is often required in autonomous vehicles. Over the last decade, a lot of research has been performed to address the strengths and challenges involved in autonomous vehicles. This paper comprehensively discussed and summarized the numerical techniques and optimization techniques involved in ground, aerial, and underwater vehicles. Some strengths and challenges are mentioned in Table 9. The most pertinent conclusion points are summarized as follows:

Consolidation of available information: A detailed review of the trajectory planning and optimization is presented from the application point of view on ground, aerial, and underwater vehicles. The DARPA challenge 2007 related to robotics, Lord Rayleigh work related to dynamic soaring in 1883, and some extensions related to the underwater vehicle are elaborated. Algorithms, i.e., numerical techniques for implementing the path planning, are discussed.
Survey of trajectory optimization techniques: A comprehensive overview related to optimization algorithms and numerical techniques that have been utilized for performing trajectory formation and its optimization.
Problem formulation and generation of optimal trajectories: An explanation of how different algorithms can be integrated to build a mathematical model for planning and the formation of trajectory components can be achieved presented with a literature survey.
Limitations and a way forward: Though numerous works review robotics, aerial and underwater vehicle systems have been presented together with optimization techniques and numerical methods, and it has been observed no single algorithm produces desired results or accurate output; therefore, a hybridization of different algorithms has been used by researchers. Two optimization algorithms or two numerical methods together can be integrated, or a mix and match of techniques can be achieved for obtaining the desired characteristics results.

This entry is adapted from the peer-reviewed paper 10.3390/electronics10182250

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.