A review on path planning ai techniques for mobile robots

2.1.1. Fuzzy logic (FL)

L. A. Zadeh [14] introduced the concept of FL in 1965. FL has the capability to add more value when compared to traditional decision-making systems. The traditional approach works on binary output, whereas FL can give an output that ranges between 0 and 1. This makes the FL decision-making technique superior to the traditional approach. In terms of path planning, instead of stopping when an obstacle is detected, FL optimizes the speed of the robot and changes its trajectory according to the obstacle in order to reach the goal faster.

Shitsukane et al. [15] have demonstrated their work as a simulation on MATLAB and V-REP. They worked on Mamdami fuzzy logic type-1 in a static environment. They examined the extent with which they could reduce fuzzy rules that are applied to a robot. A. Pandey et al. [16] simulated their work on MATLAB using fuzzy logic. They conducted their research with different shapes and sizes of obstacles. They concluded their work by showcasing no collisions in the simulation.

Fig. 3Example for Fuzzy Logic for obstacle avoidance

Antonelli et al. [17] proposed a system with direction for next time interval as input and cruise velocity for safe drive as the output. They demonstrated the use of a fuzzy logic-based system for a camera-based lane detection robot. They carried out two experiments, one for lane detection testing and the second for tracking motion and velocity of the robot in real time, to validate their system. P. Reignier [18] demonstrated their model and highlighted the problem when using fuzzy logic. The experimentation with repeated iterations shows that the problem of local minima and oscillations still persists.

Saffiotti et al. [19] discuss the difficulties faced in path planning when using fuzzy logic. They demonstrated their work on Flakey, which is a mobile robot developed by SRI International. They showcase the benefits of the use of weighted combination over behavior-based combination in fuzzy logic control. Omrane et al. [20] demonstrates a trajectory tracking controller which is based on fuzzy logic for indoor path planning. They used MATLAB and SIMIAM for simulation and navigation respectively.

Li et al. [21] simulated a two wheeled mobile robot in an unknown environment. They showcased a significant decrease in the fuzzy logic rules applied to the robot due to their proposed system. Due to this decrease, they made the system faster compared to other systems. Faisal et al. [22] demonstrated the application of mobile robots in a warehouse setup, this setup contains a variety of static as well as dynamic obstacles for the robot to tackle. The proposed system developed by them generated smooth paths using fuzzy logic and the system was demonstrated using Scout-II robot.

Singh et al. [23] demonstrated a wheeled mobile robot using fuzzy logic in a static environment. The system was simulated using MATLAB with a varying number of obstacles for each iteration. Verification of the simulated system was carried out by a DANI robot with setups similar to the simulations. The proposed system was able to cut down the travel time, thus reducing the power consumption by robots to reach the goal. Yen et al. [24] proposed a system to reduce the information loss that occurs due to command fusion in mobile robots. The proposed system is based on Payton and Rosenblatt’s architecture. The system was tested by simulations where obstacles were set on the path and also close to the path, but the system was able to navigate through smoothly without collision.

2.1.2. Neural network (NN)

NN is an algorithm that takes its inspiration from the human brain [25]. NN consists of three layers: input, hidden and output layer, which represent neurons. In each layer there are pre-trained nodes with the help of data sets. The nodes in each layer are connected to each other and every connection line has weights, this helps in dynamic decision-making for the system. Neural Network can be further classified into three categories: Imitation algorithm, Reinforcement algorithm and Deep-Learning algorithm.

Fig. 5Neural network layers

2.2.1. Dynamic window approach (DWA)

DWA is a velocity space approach to path planning. In DWA the robot forms a window in the surrounding area that is being detected with the help of mounted sensors on the robot. The limit to this window is the distance that can be covered by the robot in the next time interval. Inside this window, all the possible trajectories are formed that the robot can use to reach the goal. So, whenever an obstacle is detected, trajectories with obstacles are discarded and the trajectory with the least distance to the goal is then selected.

Seder et al. [38] presents a system based on the DWA algorithm for obstacle avoidance and path planning. The system is capable of working with static as well as dynamic obstacles. Simulations were carried out to verify the system using a Pioneer 3DX robot with laser range finder. Brock et al. [39] presents a high velocity system for path planning using DWA. The paper displays the ability of DWA to plan circular or curved paths. The DWA can be carried out by two approaches: holonomic and non-holonomic. The holonomic approach was demonstrated in this paper using the Nomad XR4000 robot. The experiments verified the high velocity dynamic obstacle avoidance of the system.

Fox et al. [40] demonstrate the use of the DWA algorithm for indoor environments. The robot is capable of stopping in case the dynamic obstacle appears at a greater speed to avoid collision. The approach was tested on their mobile robot ‘RHINO’ which was capable of safely moving at a speed of 95 cm/s while avoiding dynamic obstacles in a populated environment. Tang et al. [41] developed a safety system based on improved DWA. They demonstrate how dynamic robot obstacles are different when compared with human obstacles. The system was developed for pedestrian safety when the robot is deployed in public places. The system was simulated using ROS (Robot Operating System) with the Gazebo environment.

Xie et al. [42] applies the DWA algorithm on a four wheeled Mecanum robot. They carried out system testing to reduce the energy consumption of the robot. The energy consumption of the robot was reduced due to the generation of a shorter path using DWA. Li et al. [43] applied the concept of DWA for a soccer robot. The task allotted to the robot was to take the soccer ball to the pre-described goal while avoiding obstacles in the field. The robot was equipped with vision sensors for obstacle detection.

Zhang et al. [44] developed a unique system based on DWA for obstacle avoidance and a QR code-based system for localization and navigation. The QR codes are placed on the ceiling and a vision camera is mounted on the two - wheeled robot. Each code contains the location information stored in it. A laser range finder is installed in the robot to 2-D map the unknown environment for obstacle avoidance. Yang et al. [45] propose a system that combines DWA with A* algorithm for improving the efficiency of path planning. The proposed system constructs a smooth path for the robot to follow. The search efficiency of the robot is improved when the robot is deployed in complex environments.

Fig. 4Example of dynamic window approach to reach its goal

Li et al. [46] develop an improved A* algorithm to increase its efficiency. The proposed algorithm is a combination of DWA and the A* algorithm. With this combination, the accuracy of the algorithm increases by three times. The system is capable of maneuvering in complex environments with dynamic obstacles. Hua Zhang et al. [47] discuss the drawbacks of the traditional DWA approach. They propose their self-adaptive system that has the ability to alter the objective function by the input of two parameters: velocity space and the distance between the goal and the robot. The proposed system is tested with the help of simulation and the problem of avoiding dense obstacles is resolved.

Sgorbissa et al. [48] develop a system for the application of transportation and assistance. They have developed an algorithm, Roaming Trails, that is a hybrid algorithm which is based on DWA. The proposed algorithm is capable of solving the problem of deadlock in path planning. They also experimented with the algorithm in the real-world with their robot, Staffetta. Yuan et al. [49] developed a hybrid system based on the Bat algorithm. The proposed system uses DWA for optimization of the bat algorithm. Upon testing, the results show that the hybrid system not only resolves the demerits of the bat algorithm, but also is better than the traditional DWA. Moon et al. [50] developed a system for collision avoidance in UAVs using DWA. The system uses hybrid DWA which combines the holonomic and non-holonomic approach. The improved algorithm benefits over the traditional DWA by extending the search from 2-D to 3-D.

2.2.2. Genetic algorithm (GA)

GA was introduced by J. H. Holland [51] in 1960. It is a technique which is inspired by the process of evolution or mutation. A set of possible outcomes for a given problem is first evaluated, out of which the best solution is selected. This process continues such that the next selected outcome is best when compared to the previous outcome. In path planning, we know that the shortest distance to reach a goal is a straight line. GA is used for optimizing the path in order to find the shortest path to reach the goal. When GA is used for path planning, the obstacles are also avoided by taking angular turns and not curves.

Fig. 6Example for genetic algorithm for path planning

Castillo et al. [52] describes a system based on GA to cater to multiple objectives. They discussed the point-to-point movement of an autonomous mobile robot. They simulated the model for both traditional GA and MOGA (multi-objective GA). The simulation proved both the systems to be capable of completing the task of point-to-point movement. Tu J. and Yang S. X. [53] propose their GA based novel approach for mobile robot navigation. The GA used here is set to have a variable chromosome length, this means that there will be an increased number of possibilities of mutation. This will help the system optimization so that a shorter path is created, a shorter path directly points out on faster goal completion. In this paper, the system with fixed length chromosomes in gg HV and variable length chromosomes are also compared.

Tuncer et al. [54] developed a system for path planning of mobile robots in dynamic environments based on GA. GA generally uses a random mutation operator for the generation of an appropriate path for movement of robots. The proposed system eliminates the possibility of the system generating a longer path. The convergence of the paths generated by the proposed system is rapid when compared to the conventional GA. Lambora et al. [55] discuss the concept of GA and explain the flow of GA. Furthermore, the application areas of GA are discussed. GA has a wide range of applications which range from image processing, path planning, search and optimization to recreational activities such as computer games.

Moreno et al. [56] demonstrated indoor experimentation of mobile robot using GA for path planning. The proposed system is equipped with ultrasonic sensors for obstacle detection. The GA generates good results when the population ranges from 100 to 250 chromosomes. Han et al. [57] proposed a GA based path planning system for mobile robots. The system proposes to reduce the time taken for path generation. For faster generation of path, the 2-D data collected by IR sensors are converted to 1-D data for faster processing. The proposed system was validated by simulation as well as real-world experimentation.

Ismail et al. [58] demonstrated their system based on GA, which was set up in maze environments. The population sizes were varied for the experimental evaluation. The environment was distributed with static obstacles in three different configurations: indoor-like, semi-clustered and heavy-clustered. The system performance was effective in all three configurations. Katoch et al. [59] discuss the concept of GA while keeping in perspective the history, current scenario and the future possibilities. The types of hybrid GA algorithms are discussed further in the paper. They also throw light on the wide range of applications like Supply-Chain, Healthcare and Navigation. In this paper, the research direction for future research is also stated. Kumar et al. [60] discuss the methodology used in GA for processing the data for training and learning iterations for the system to function precisely and generate accurate results.

2.2.3. Ant colony optimization (ACO)

Marco Dorigo [61] introduced the concept of ACO in 1992. This technique takes its inspiration from the movement patterns of an ant colony. The concept of ACO comes under swarm intelligence, which means it is used where there are multiple robots working in an environment. Whenever a group of ants travels towards food (goal) they may take different paths, the modes of communication in the case of ants is the pheromones released which are distinct to each ant. After a few iterations of travel from home to goal, the path with a greater number of pheromones is selected, which represents a shorter distance to reach the goal. This concept is visualized for path planning in mobile robot swarms.

Akka and Khaber [62] discuss the concept of ACO for path planning. They propose an improved ACO system, considering the merits and demerits of the traditional system. A grid map environment set up was used for simulating the path planning technique. The simulation results show that the improved ACO developed by the authors is better at fast and short path planning when compared with the traditional approach. Cong et al. [63] demonstrated ACO methodology for path planning using various previously constructed maps. The maps consist of a square grid having static obstacles along with walls, and the home and goal positions are also pre-defined. They test the feasibility of the system with varying complexity of the maps. The test results show that in the initial iterations, the ants tend to hit dead-ends but with increased iterations the ants reach the goal with obstacle avoidance and without hitting dead-ends.

Urjol and Moran [64] conducted testing on their ACO based system for path planning. They used varied shapes and sizes of static obstacles for setting up the grid map. They also changed the resolution of the map for testing. The system was then tested with linear and non-linear changes in the number of obstacles in the setup. With the varying map environment of static obstacles, the proposed system was able to generate a path near to the shortest distance path from home to goal. Gao et al. [65] demonstrate the working of an ACO based system for path planning in a complex environment. They reviewed the existing improved ACO algorithms for finding the gaps in the existing systems. They introduce four strategies for enhancing the performance of the traditional algorithm. The simulation results show the enhanced performance of the EH-ACO algorithm over traditional and existing algorithms due to integration of new strategies by decrease in time taken to reach the goal and distance covered for reaching the goal.

Fig. 7Ant Colony Tracing Path towards its goal

Ajeil et al. [66] propose an ACO based algorithm with static and dynamic obstacle avoidance. The proposed algorithm is modified with the ant’s age as input for the system. The algorithm is simulated and tested on MATLAB to obtain the results. They concluded by stating that the proposed algorithm is capable of path finding in a static and dynamic environment. The system was also found to be superior to other path planning techniques. Rashid et al. [67] demonstrated the comparison between the working of the ACO algorithm in simple as well as complex environments. The simulation results found that with the use of the ACO algorithm, there was a significant decrease in the time taken for goal fulfilment in both simple as well as complex work environments.

2.2.4. Particle swarm optimization (PSO)

The concept of PSO was introduced in 1995 by Eberhart et al. [68]. This algorithm is inspired by the movement pattern in birds. The swarm of birds has the ability to optimize the path for them to reach the goal. The particle here represents every bird in the flock, each particle tries to get the best possible position, which inspires the neighbouring birds randomly. This can be visualized in terms of mobile robot fleets, such that each robot points in the direction of the goal when assigned. Then each robot will keep moving towards the goal, avoiding obstacles as well as neighbouring robots.

Fig. 8Representation of particle swarm optimization

Dewang et al. [69] presented an approach based on PSO called Adaptive PSO. The proposed algorithm works, considering the distance from the goal and obstacle simultaneously. They have compared the proposed algorithm with traditional PSO in terms of distance travelled and time taken to reach the goal in a static environment. The Adaptive PSO performs better than traditional PSO in all types of static environments with varied complexity both in terms of distance and time. Li and Chow [70] discuss their proposed PSO based algorithm, SLPSO. The objective function is formed on the basis of three parameters: degree of collision risk, distance travelled and path smoothness. Simulation as well as real-world experimentation is carried out to validate the system. The simulation was carried out on Gazebo. Through simulation data and experimentation data, it is found out that SLPSO performs better when compared to PSO and GA.

Deepak et al. [71] discuss their PSO based model for the control mobile robot swarm. They have implemented a fitness function to convert the existing PSO into a multi objective algorithm. The fitness function runs on the basis of: distance of each robot from the goal and the nearest obstacle. Simulations were carried out to validate the proposed model in various different environments. The simulation results show that the algorithm is suited for path planning in unknown environments but needs more work to tackle irregular obstacles. Qin et al. [72] propose a novel approach based on the PSO algorithm that uses the MAKLINK graph to demonstrate the working environment of the robot. The simulations are carried out on MATLAB, using Dijkstra as the path planning algorithm. The system is coupled with GA to help in the learning of the system for optimized path planning. The simulation results show considerable improvements over traditional PSO, but the system is capable of further optimization with some parameter variation.

Alam et al. [73] proposes an algorithm to tackle the path planning problem of a mobile robot using the PSO algorithm. They use convex objects as their static obstacles for testing their proposed algorithm. The simulations are carried out in MATLAB with varying position, number, shapes and sizes of the obstacles. The system uses grid lines to find the optimum path to reach the assigned goal. The simulation results show the effectiveness of the system to find the path with optimum or near-optimum path length to reach the goal with varied convex static obstacles. Chen and Li [74] demonstrate their algorithm that is based on the PSO algorithm to control a small swarm of mobile robots. The proposed algorithm is capable of generating smooth paths for the mobile robots to follow using a cubic spline function integration. The system is capable of working in an environment with static obstacles. The system is tested and validated using MATLAB for simulation of the proposed algorithm.

Li et al. [75] discuss the limitations of the existing traditional PSO algorithm and demonstrate their improved PSO algorithm. The proposed algorithm uses parameters like cubic spline function, uniform distribution, inertia weight and learning factor for enhancing the performance of the algorithm. The proposed algorithm solves the time-consuming problem of the traditional PSO algorithm. They demonstrate their results with the help of simulations which show significant decrease in iterations, path length as well as time taken for simulation. Das et al. [76] proposed a novel approach based on the PSO algorithm. The proposed methodology uses a gravitational search algorithm for optimization of the traditional PSO algorithm. In this paper, the system developed by the authors is compared with other hybrid algorithms to test the feasibility of the system. The simulations show that the system developed is better when compared with improved PSO and improved GSA in terms of path planning. Shiltagh and Jalal [77] studied the application of modified PSO algorithm for path planning. They conducted a simulation on MATLAB with varied static maps. The system is capable of sensing when it reaches a dead-end and no path is available for reaching the assigned goal. The modified PSO shows that it is able to perform the path planning tasks with increased speeds and reduced path lengths.