Optimizing Path Planning for Smart Vehicles: A Comprehensive Review of Metaheuristic Algorithms

The advent of technologies such as big data, cloud computing, 5G networks [1], the Internet of Things (IoT) [2], and artificial intelligence (AI) [3], [4] has been instrumental in the evolution of smart vehicles. These vehicles leverage these technologies to mitigate human error in driving, navigate traffic in self-driving modes, assist in industrial logistics and manufacturing processes as Automated Guided Vehicles (AGVs), and operate in challenging terrains as Unmanned Ground Vehicles (UGVs). Furthermore, their applications extend into healthcare, domestic settings, and e-commerce through Autonomous Mobile Robots (AMRs).

In the domain of self-driving vehicles, technologies like Light Detection and Ranging (LIDAR) sensors [5], cameras integrated with deep learning algorithms [6], and ultrasonic sensors [7] are employed for vehicle and object detection, traffic alerts, zebra crossing recognition, and collision avoidance with pedestrians. AGVs, utilized in warehouse logistics and material handling, navigate using lasers, magnets, vision cameras, or by following marked lines or wires. The role of AI, particularly reinforcement learning, has become prominent in route planning for AGVs [8]. AMRs have a wide array of applications including inspection [9], surveillance [10], monitoring [11], logistics, and service [12], [13], [14], [15]. They are categorized into holonomic and non-holonomic types [16], [17], with holonomic robots having controllable degrees of freedom equal to their total degrees of freedom [18], allowing movement in any direction within their configuration space. Non-holonomic mobile robots, on the other hand, have constraints on their velocities and derivatives of position [19].

For effective navigation, smart vehicles must comprehend the nature of their environment to adapt their actions for optimal goal attainment. Critical to this process are three fundamental components: mapping, localization, and path planning [20]. Mapping involves the creation or retrieval of environmental maps, providing location and orientation data for the vehicles. Localization is essential for vehicles to ascertain their position on the map, a task accomplished using cameras, GPS, and various sensors like laser, vision, and ultrasonic sensors. The location may be expressed in absolute coordinates (longitude, latitude, altitude), as a reference relative to the environment, or as topographical coordinates (e.g., in a room). Path planning is the process of determining a viable, obstacle-free route in typically congested real-world environments [21].

Path planning in the context of smart vehicles is categorized into two primary approaches: global and local. Global path planning is concerned with deriving the optimal path using extensive environmental data. This approach is most effective in static environments that are well-defined and familiar to the smart vehicle. Here, path planning algorithms generate a complete route from an origin to a destination, thereby determining the optimal trajectory for the vehicle. In contrast, local path planning is pertinent in environments that are either unfamiliar or subject to change. It involves real-time computation while the vehicle is in motion, utilizing data from onboard local sensors. This enables the smart vehicle to adaptively generate new routes in response to dynamic environmental changes. A wide array of path planning methods and algorithms have been explored in the field of robotics. Factors influencing the selection of an appropriate algorithm include the kinematics and dynamics of the environment, the computational capabilities of the smart vehicles, the type of sensors employed, and the availability of other sourced information. The decision-making process regarding the choice of an algorithm also involves considering the trade-offs between algorithmic performance and complexity, which vary depending on the specific application [22]. As illustrated in Figure 1, path planning methods and algorithms can be divided into several categories, such as classical methods like cell decomposition, metaheuristic algorithms including the genetic algorithm, machine learning approaches like reinforcement learning, and sampling methods exemplified by probabilistic roadmaps [22], [23], [24], [25].

Metaheuristic algorithms represent a class of high-level heuristic approaches that are designed to provide suitable solutions to optimization problems, particularly those characterized by incomplete information or limited computational resources. When applied to path planning, metaheuristic algorithms demonstrate proficiency in managing environments that are partially known or contain moving obstacles. This is in contrast to classical algorithms, which typically necessitate prior comprehensive knowledge of the environment [23]. Metaheuristic algorithms are categorized into two main groups: population-based methods like Particle Swarm Optimization and trajectory-based methods such as Simulated Annealing, as depicted in Figure 2 [26]. Population-based metaheuristics operate by generating multiple points within the search space, whereas trajectory-based methods progress through the search space by navigating a trajectory via a single point at each time step.

The GA, an optimization methodology, draws upon the principles of genetics and natural selection, first conceptualized by Bremermann [27]. Holland was the pioneer in adapting the genetic algorithm to computer science [28]. Its applications have since permeated various domains, including robot navigation and numerous scientific and technological fields. This algorithm focuses on optimizing complex problems where the objective function needs to be maximized or minimized within specified constraints. The method starts by defining a population size, where chromosomes (sets of genes) are formulated based on the given problem. Each chromosome in the population is assigned a fitness value, contingent upon the objective function. Chromosomes are then selected based on their fitness, allowing them to propagate their genes to subsequent generations through crossover processes. Mutation is employed to maintain population diversity and avert premature convergence. Table 1 elucidates the pseudocode of the genetic algorithm. The algorithm concludes its process once the population has converged [29].

The recent focus on GA-based methods, particularly in the realm of optimization problems like path planning, highlights the potential of GA in addressing these challenges [6]. This is evidenced by the success of GA in various applications, as discussed in Table 2, which outlines different studies that have employed GA for path planning. This table includes the variables considered in each study and provides insights into their findings. Moreover, the hybridization of GA with other intelligent algorithms has been an area of considerable research interest. Notable examples include the integration of GA with Fuzzy Logic [30], Intelligent Water Drop [31], and Neural Network [32], aiming to enhance the efficacy of the solutions. In the utilization of GA-based methods for path planning, distance often emerges as a common parameter [33], [34], [35], [36], [37], alongside other considerations such as path smoothness and clearance [34], [36], [37], energy evaluation [38], and factors related to robot speed. A noteworthy study by Liu et al. [39] presented an improved GA to tackle the appointment order allocation and route planning issues of Cainiao unmanned vehicles. Additionally, Wang et al. [40] proposed an optimized approach using GA to implement the Multi-Objective Evolutionary Algorithm (MOEA) for planning the trajectory of a mobile robot in a known environment. This experiment involved a two-wheeled mobile robot using the ArUco system within the Robotic Operating System (ROS). However, it's important to note the limitations of this method, particularly its unsuitability for rough terrains due to the omission of the mobile robot's dynamics in the planning process. Furthermore, the algorithm's deployment on a console computer, rather than within the robot's embedded system, is attributed to the limitations of the embedded system's low-end hardware.

The concept of ACO was first introduced by Dorigo in his Ph.D. dissertation in 1992 [45]. This algorithm is inspired by the sophisticated social behaviors exhibited by ants during their search for food. A key element of this behavior is the deposition of pheromones, which serve to guide other ants by creating a trail to the food source. The trail's pheromone concentration intensifies as more ants traverse it, thereby increasing the likelihood of it being followed by additional ants. Notably, the shortest route to the food source becomes the most popular among the ants, as it can be traversed in the least amount of time. This phenomenon was first observed in the renowned Double Bridge experiment [46], where ants consistently selected the shortest path over time when presented with multiple routes to a food source. Pheromone evaporation also plays a crucial role in this process. It serves as a mechanism to prevent the ants from getting trapped in locally optimal solutions [47]. As the pheromone evaporates, the attractiveness of a given path diminishes, reducing the likelihood of it being selected by other ants. Additionally, on the shortest path, the rate of pheromone deposition surpasses its rate of evaporation, ensuring that a high pheromone level is maintained. In the context of ACO algorithms, this concept is applied to the selection of paths between nodes. The probability of an ant, situated at node i, choosing to move to another node j in the network, is influenced by the level of pheromone deposition on the potential paths, as described in reference [47].

where, $\tau_{i j}^k$ denotes pheromone levels. Analogous to the natural tendencies of ants, paths with elevated pheromone concentrations are more likely to attract ants in the algorithm, leading to a preference for these paths over others with lower pheromone levels [48].

The heuristic function: $\eta_{i j}^k=\frac{1}{d_{j e}}$.

The pheromone update:

$\Delta \tau_{i j}^k(t)= \begin{cases}\frac{Q}{L_k}, & \text { if ant } k \text { passes node } i \text { and } j \\ 0, & \text { otherwise }\end{cases}$ is the quantity of pheromone deposited, where $Q$ is a constant and $L_k$ is the total length of the path that ant $k$ travels. A pseudocode of this algorithm is presented in Table 3.

Numerous scholars have conducted comprehensive research on the operational mechanics, structural design, and optimal parameterization of ACO, proposing various enhancements to address these areas, as detailed in Table 4. Additionally, a range of variables, as listed in Table 5, have been considered in these studies. Liu et al. [49] optimized cross-path nodes in the path search process using the ant colony algorithm combined with geometric optimization, which improved the algorithm’s effectiveness and path quality via pheromone updates. You et al. [50] developed a novel heuristic operator to augment the diversity and convergence of the population search. Dai et al. [51] addressed issues related to global convergence speed and path smoothing by enhancing an A* algorithm-based ACO and the maximum-minimum ant system, incorporating a retraction mechanism to circumvent deadlocks. Jiao et al. [52] proposed an adaptive state transfer and pheromone update method, enhancing the significance of heuristic information and pheromone strength in the iterative process of the algorithm, thereby improving its adaptability to diverse environments and its capacity to escape local optima. Akka and Khaber [53] refined the state transfer formula to prioritize the selection of neighbor nodes with the most exits as the subsequent node. This enhanced algorithm introduces diversity to the search process and mitigates the impact of ineffective pheromones by dividing the multi-heuristic function, separately rewarding and penalizing the worst path, as outlined by Yang et al. [54].

PSO is inspired by the collective behavior of animals like birds, tetrapods, or fish in their pursuit of food. This approach mirrors the natural group dynamics observed in these species, where there is no singular leader guiding the group to the food source [60]. In such a group, each individual may not know the precise location of the food, but they can approximate their proximity to it. Independent efforts by each animal to reach the food source would be inefficient, leading to extended time frames and chaos. Consequently, the most effective strategy is for the members to follow those closest to the food source [29]. In PSO, each individual animal is analogous to a solution, possessing two critical pieces of information: Their fitness value, derived from the objective function; The velocities that guide the solution towards the target location.

The algorithm commences with a set of solutions or particles. Each particle navigates the solution space, returning their fitness value, known as pbest, in each iteration. The best pbest value from each iteration is recorded as the global best value, gbest. Based on these two values, the algorithm updates the velocity and position of each particle. The search process concludes either upon reaching the maximum number of iterations or upon identifying the optimal solution. The formulas for updating the velocity and position of particles in PSO are outlined subsequently.

The inertia weight is denoted as $w, c_1, c_2$ are the learning factors, $r_1, r_2$ are normal distribution random numbers within the interval $[ 0,1], \eta$ represents the velocity constraint proportional factor, $v_{i d}$ represents the velocity of the $i$-th particle in d dimension, and $x_{i d}$ represents the position of the $i$-th particle in d dimension. The procedure to implement this algorithm is described in Table 6.

The PSO is analogous to the GA in its initiation with a randomly formed population set, subsequently evaluated based on fitness values. This methodology has been effectively applied in various navigation contexts, such as aerial robot navigation in unknown three-dimensional environments [61], humanoid robot navigation [62], and industrial robot navigation [63]. The performance efficacy of PSO is contingent on the precision in adjusting, controlling, and updating its parameters.

Since its inception in 1995, numerous approaches have been suggested to refine these aspects and enhance the overall functionality of PSO. Traditional techniques for parameter adjustment and control include Fixed Inertia Weight (FIW) [64], [65], Linearly Decreasing Inertia Weight (LDIW) [64], [65], [66], [67], Time Varying Acceleration Coefficient (TVAC) [65], [68], Random Inertia Weight (RANDIW) [64], [65], [66], [68], Random Acceleration Coefficients (RANDAC) [69], and Fixed Acceleration Coefficients (FAC) [64], [65], [66], [68].

Table 7 compiles various studies that have proposed improvements and hybridizations of PSO to address path planning challenges. Dewang et al. [70] introduced an adaptive particle swarm optimization (APSO) that dynamically alters the inertia weight in each iteration, initiating the search with a high inertia weight to avoid local minima, and gradually reducing it to focus on exploitation as iterations progress. This strategy yielded superior results in comparison to standard PSO in terms of path length and planning time, as demonstrated in the environment depicted in subgraph (a) of Figure 4. Chai et al. [71] combined PSO with the Probabilistic Roadmap Method (PRM) to enhance sampling in PRM. This hybrid method leverages knowledge of sample points in obstacle-laden regions to refine sampling in open spaces, particularly in narrow passages, thereby improving connectivity. Masehian and Sedighizadeh et al. [72] utilized PSO to derive the shortest and smoothest feasible paths. Particles are initialized based on points identified in free space by a robot's laser sensor, with the optimal particle's position determined by the sensor readings. PRM serves as the local planner for obstacle avoidance, and simulation results indicate a more efficient runtime compared to the basic PRM approach. Li et al. [73] presented an improved PSO that initializes particles through uniform random distribution, employs an exponentially decaying inertia weight to enhance planning efficiency, and integrates cubic spline interpolation for path smoothing. This variant was benchmarked against other PSO variants, with comparisons based on performance indices and path planning metrics, where IPSO showed promising results. Song et al. [74] developed a fractional-order PSO variant (FOPSO) that introduces adaptive fractional-order velocity and utilizes Bezier curves for path smoothing. Its performance was evaluated against other PSO variants using benchmark functions. Finally, Alam et al. [75] implemented PSO for random sampling along grid lines between start and goal points, with an initial spacing of points along the Euclidean path. The effectiveness of this approach was validated through simulations in various environments with static obstacles.

The ABC algorithm, conceived by Dervis Karaboga for addressing polynomial mathematical problems [81], is inspired by the foraging behavior of honey bees. In their natural environment, honey bees use pheromones and a waggle dance to communicate information about food sources. When a bee finds a food source, it evaluates the nectar quantity, returns to the hive, and performs a waggle dance to convey information about this source. The quality of the food source is indicated by the vigor of the waggle dance. In the context of the ABC algorithm, the location of a food source represents a potential solution to an optimization problem, and the quality of the solution is analogous to the nectar content of the food source. The ABC algorithm categorizes bees into three roles: employed bees, onlooker bees, and scout bees. It is assumed that for each food source position, there is one corresponding employed bee. Employed bees share information about the location and quality of food sources with onlooker bees through the waggle dance. Onlooker bees then select food sources based on their perceived quality, meaning that higher-quality sources are more likely to be chosen. If employed bees abandon a food source, they transition into scout bees, embarking on the search for new food sources. Scout bees memorize the quality of discovered food spots and compare them with known sources to identify the most promising ones. The ABC algorithm's pseudocode is illustrated in Table 8. Initially, the ABC algorithm establishes a population of food source positions (SN), where SN represents the population size. Each food source, or solution, is a D-dimensional vector, with D being the number of optimization parameters. Each food source is linked to a probability value $p_i$, influencing the decision-making of onlooker bees.

where, $f i t_i$ is the fitness of solution $i$, and $SN$ is number of employed bees (population size). The generation of a new food source position from an existing one is determined using the following expression:

where, $k$ and $j$ are random values in sets $\{1,2 \ldots, \mathrm{SN}\}$ and $\{1,2, \ldots, \mathrm{D}\}$ respectively. $k$ should be different from $i$. $\emptyset_{i j} \in[-1,1]$ controls the production of a neighbour food source position around $x_{i j}$.

Research in the field of ABC for path planning has led to a variety of advancements and hybrid approaches, as detailed in Table 9. One notable development in the navigation of smart vehicles is the combined Artificial Bee Colony and evolutionary programming approach proposed by Contreras-Cruz et al. [82]. In this methodology, the ABC algorithm serves as the local search method, while evolutionary programming is employed to enhance the potential paths obtained. This approach was initially applied in multi-robot systems and later refined for use in unfamiliar environments with dynamic obstacles [83]. However, certain shortcomings were identified, such as neglecting the distance between new bee positions and obstacles. To address these issues, an improved ABC-Evolutionary Programming (ABC-EP) approach was proposed by Kumar and Sikander [84]. Further advancements include the Adaptive Dimension Limit-Artificial Bee Colony Algorithm (ADL-ABC), introduced by Kamil et al. [85] for optimizing the global path of mobile robots. This algorithm demonstrated its efficacy by finding solutions with fewer iterations and reduced computational time. Another development, the Directed Artificial Bee Colony algorithm, was shown to yield better results in dense environments, such as maps with numerous static obstacles, compared to other leading algorithms [86]. In an effort to curtail computational time, particularly crucial in real-time path planning scenarios, Szczepanski and Tarczewski [87] proposed a hybrid approach combining the ABC and Dijkstra algorithms. This amalgamation aimed to balance the comprehensive search capabilities of the ABC algorithm with the efficiency of Dijkstra's algorithm, particularly in environments where quick computation is vital.

The FA, introduced by Yang [89], is inspired by the bioluminescent communication of fireflies. The key aspect of this communication is the distinctive light patterns emitted by fireflies, where the intensity of the light is indicative of a firefly's attractiveness. In the context of the FA, this attractiveness is analogous to the fitness value of a solution. The algorithm operates on the principle that among any two fireflies, the one emitting brighter light will attract the one with dimmer light. The attractiveness of a firefly is quantified as per the following equation [90]:

where, $\beta$ denotes the attractiveness, $\beta_0$ represents the maximum attractiveness, which is typically set to $1, \gamma$ is the light absorption coefficient ranging between [0.1,10], and $r_{i j}$ is the distance between firefly $i$ and firefly $j$, calculated using the standard Euclidean distance formula:

where, $x_i$ and $x_j$ are the positions of firefly $i$ and firefly $j$ in the d-dimensional space, respectively; $\alpha$ and $\phi$ are random numbers in the distribution [0,1]. The pseudocode for FA is described in Table 10.

The FA has been implemented in diverse research areas, including robotics [91], [92], machine learning [93], journalism [94], and cloud computing [95]. Table 11 presents a compilation of techniques proposed for FA's application in smart vehicle navigation. In an effort to enhance the convergence speed and local search accuracy of the standard FA, Chen et al. [96] introduced a modified version (PPMFA) that incorporates a Gaussian random number into the fixed step size. This addition enhances the diversity of the firefly population, helping to prevent the algorithm from stagnating in dead-end zones. Additionally, a novel path center technique was employed to calculate distances between fireflies, essentially representing paths. This method involves connecting geometric centers of path segments to form new segments and repeating the process until a single segment remains, termed as the path center. The distance between two path centers is used as the measure of distance between two fireflies. The PPMFA showed superior performance in accuracy and convergence speed compared to PSO and the Standard SFA. Duan et al. [97] proposed a Developed Firefly Algorithm (DFA) to address multi-objective navigation challenges. The algorithm extends the grid map to create feasible paths and employs the Pareto dominance relationship for path comparison and segregation. Non-dominant fireflies are stored in an elite record library for comparison during iterations. DFA includes an evolutionary stage for optimizing paths by adding, removing, or swapping points. When tested against NSGA-II on a ZDT1 instance, the DFA demonstrated enhanced efficiency. Patle et al. [98] utilized the firefly algorithm for mobile robot navigation in dynamically obstacle-laden environments. An AI mechanism navigates the robot, while a controller based on FA detects and avoids obstacles, generating paths (fireflies) and selecting the optimum one using Euclidean distance from the nearest obstacle. This approach outperformed other intelligent methods in terms of path length in various scenarios. Experiments with the Khepera-II robot showed a deviation of about 5.7% from simulated results. Hassan and Fadhil [99] developed a modified firefly algorithm for path planning of mobile robots in 3D sphere-like, partially dynamic environments. In this approach, each firefly is viewed as an agent navigating around obstacles, with the generated paths considered potential solutions. The optimal path is selected based on path length and completeness. This modified approach was noted for its minimal memory requirement and effective performance in spherical spaces.

Developed in 2009, the CSA is a nature-inspired optimization technique designed to tackle complex problems [103]. Its conceptual framework is based on the intriguing brood parasitism behavior observed in certain cuckoo species. These birds are known for their strategy of laying eggs in the nests of other host species. Cuckoos often adapt the appearance of their eggs, mimicking the color and pattern of the host species' eggs [104], thereby reducing the likelihood of the host species detecting the foreign egg. In cases where the host species identifies and removes the cuckoo egg or abandons its nest to start anew, the cuckoo must find another host nest. Notably, cuckoo eggs typically hatch faster than those of the host species, allowing the young cuckoo to dispose of the host's eggs and monopolize the food supplied by the unwitting host [105]. The behavioral rules of the cuckoo birds, as translated into the CSA, can be summarized as follows:

Each cuckoo randomly selects a nest in which to lay its egg.

The nests that successfully retain cuckoo eggs, escaping detection and eviction by the host species, are carried forward to the next generation.

The probability of a host bird discovering an alien egg is denoted by $P \in[ 0,1]$, and the total number of available host eggs or nests within the search space remains constant.

The CSA primarily employs a random walk strategy for nest searching, with Levy flight [103] being the most commonly used method due to its efficiency in exploring the search space. In the context of path planning problems, the nests and eggs within the CSA framework can be metaphorically viewed as solutions, where host eggs in a nest represent current solutions and a cuckoo egg symbolizes a new, potentially superior solution $x^{t+1}$. The objective is to replace less effective solutions with more viable ones (represented by the cuckoo’s egg).

where, $i_{\text {i }}$ represents the $i$-th particle, $t$ stands for the iteration cycle, $\alpha>0$ is the step size, and $\oplus$ denotes entrywise multiplication. Step lengths of Levy flight are distributed according to this probability.

where, $L$ represents step size length and $\gamma$ denotes the variance. $\mathrm{P}, \gamma$, and $\alpha$ are are critical to the algorithm's performance and require careful tuning to enhance solution quality. One of the advantages of the cuckoo search algorithm is its minimal need for parameter fine-tuning, coupled with its ability to handle multi-modal objective functions effectively. The implementation of the Cuckoo Search Algorithm is further elucidated in a pseudocode format, as illustrated in Table 12.

The implementation of the CSA spans a wide array of fields, demonstrating its versatility and effectiveness. This includes applications in vehicle routing [106], [107], neural networks [108], scheduling [109], [110], medical fields [111], [112], cloud computing [113], and notably in robotics, particularly in the navigation of smart vehicles. Table 13 showcases a range of hybrid approaches combining Cuckoo Search with other methods to address path planning challenges. In the realm of multi-robot collaboration and navigation within densely obstacle-laden maps, Sahu et al. [114] introduced a Modified Cuckoo Search as a novel solution. This adaptation of the CSA was specifically designed to enhance collaborative strategies and navigation efficiency in complex environments. A comparative study by Ab Wahab et al. [23] assessed the performance of the cuckoo search against other metaheuristic algorithms and traditional path planning methods across various scenarios. The study highlighted CSA's strengths and potential areas for integration with other techniques. To address the dual goals of minimizing computational costs and maximizing efficiency in mobile robot path planning, Garip et al. [115] proposed a hybrid algorithm that combines the principles of cuckoo search with firefly and particle swarm optimization. This hybrid approach aimed to leverage the strengths of each method to produce a more robust and efficient path planning solution. In the context of quantum computing, Kundra et al. [92] utilized cuckoo search to prevent premature convergence in the proposed quantum firefly algorithm. This application underscores CSA's utility in enhancing the stability and performance of other advanced algorithms. Additionally, to optimize robot paths in environments with dynamic obstacles, Kumar et al. [116] implemented a Modified Cuckoo Search algorithm. This version of CSA was tailored to process obstacle distance and heading angle data from robot sensors, enabling more adaptive and responsive path planning in changing conditions.

The WOA, introduced by Mirjalili and Lewis [122], is an innovative algorithm that emulates the bubble-net hunting behavior of humpback whales [123]. These whales, known for their social nature, often forage in groups, preying primarily on krill and small fish located near the water's surface. A notable aspect of their hunting technique involves diving approximately 12 meters deep and then engaging in a unique strategy to encircle their prey. This involves creating a ring of bubbles as they spiral upward towards the surface, effectively trapping the prey. This hunting method, particularly the encircling maneuver and the spiral bubble-net movement, has been translated into a mathematical model for the WOA. The algorithm draws inspiration from these distinct whale behaviors to devise a search and optimization strategy. The spiral path and bubble-net formation are key elements that have been abstracted and applied in the algorithm to simulate the whale's approach to localize and encircle the prey effectively. The mathematical representation of these behaviors enables the WOA to efficiently explore and exploit the search space in various optimization problems.

(1) Encircling prey

In the WOA, the behavior of a humpback whale encircling its prey is a key mechanism. When a whale identifies the location of its prey, it begins to encircle it. In the context of WOA, this is modeled by assuming that the best current solution in the search space is akin to the whale closest to the target prey. Consequently, other search agents (whales) in the algorithm adjust their positions relative to this best agent, simulating the encircling behavior. This behavior is represented mathematically in the following equations:

where, $A$ and $C$ are coefficients, $t$ denotes current iteration, $X^*$ is the best whale position, $X$ is the current whale position, $a$ is a decreasing constant that linearly reduces from 2 to 0 over the course of iterations and is given by $a=2-\frac{2 t}{M}$ (M: maximum number of iteration), $r \in[ 0,1]$ is a random value.

(2) Spiral bubble-net manoeuvre (Exploitation phase)

As the value of $a$ decreases, the radius of encircling the prey diminishes. With $A$ being a random value within the range $[-a, a]$, search agents can discern the relationship between their current position and the optimal position when $A$ is reduced to the interval $[-1,1]$. Additionally, during the spiral movement phase, the position of the whale relative to the prey is updated. The distance $D^{\prime}$ between the $i$-th whale and the prey (which represents the best solution obtained so far) is calculated accordingly:

where, $b$ is a constant that defines the shape of the logarithmic spiral, and $l$ is again a random value in the range [-1, 1]. The spiral movement is an integral part of the whale's hunting strategy, where it combines the encircling maneuver with a simultaneous inward spiral motion towards the prey. In the WOA, the whale's position is updated based on a probability of 50% to either continue encircling the prey or to engage in the spiral movement. This probabilistic approach enables the algorithm to balance between exploration and exploitation, effectively mimicking the hunting behavior of humpback whales. The decision between the two behaviors is governed by the following equation:

(3) Searching for prey (Exploration phase)

In the exploration phase of the WOA, a whale updates its position based on a randomly selected agent, rather than the current best agent. This phase is crucial for global search within the solution space. When $|A|<1$, the algorithm switches to exploration mode. In this case, given $X_{\text {rand }}$ as the position of a random agent, the updated position of a whale is determined using the following equations:

The pseudocode detailing the WOA is illustrated in Table 14. This algorithm has been widely applied across various research domains. It has been utilized for image segmentation [124], in the validation of welded Al/Cu bimetal sheets [125], for intelligent facial emotion recognition [126], to enhance power system stabilizers [127], and in task scheduling for microprocessor systems [128].

In robotics, WOA has been instrumental in planning the joint trajectory of robotic arms [129], enhancing robotic manufacturing processes [130], planning navigation of unmanned vehicles [131], aiding in multiple robot space exploration [132], [133], and optimizing deep neural networks [134]. Table 15 presents an overview of various studies where WOA has been implemented in smart vehicle navigation.

Proposed by Mirjalili et al. [142], GWO is an algorithm inspired by the social hierarchy and hunting techniques of grey wolves. Grey wolves are apex predators that typically live in packs of 5 to 12 members, each adhering to a strict social structure as depicted in Figure 9.

In this hierarchy, the alphas ($\alpha$)—a male and a female—serve as the leaders. Positioned at the top, they represent the fittest solution, and their directives are followed by the rest of the pack. The beta ($\beta$) wolves, ranked second, are considered the primary candidates for alpha status. Below them are the delta ($\delta$) wolves, including scouts, sentinels, elders, hunters, and caretakers, who preside over the omega ($\omega$) wolves, often viewed as the scapegoats of the pack. Grey wolves hunt collaboratively, starting with tracking, chasing, and approaching their prey. They encircle, pursue, and harass the prey until it weakens, then launch an attack. This hunting behavior is mathematically modeled in GWO, where the alpha, beta, and delta wolves correspond to the best, second-best, and third-best solutions, respectively, while the remaining solutions are considered omega wolves. The model encompasses several phases:

(1) Encircling the prey:

where, $\vec{A}$ and $\vec{C}$ represent coefficient vectors, $t$ is the present iteration, $\overrightarrow{X_P}$ is prey's position, $\vec{X}$ is the grey wolf position, $\overrightarrow{r_1}$ and $\overrightarrow{r_2}$ are random vectors within $[ 0,1]$, and $\vec{a}$ decreases linearly from 2 to 0 in the course of iterations.

(2) Hunting:

Alpha, beta, and delta wolves update their positions first, assuming better knowledge of the prey's location:

(3) Attacking the prey (Exploitation):

The mathematical representation of a prey attack in the GWO is characterized by the gradual decrease of $a$ from 2 to 0 over the iterations. The attack phase is initiated when the value of $|A|<1$, with $\vec{A}$ being a random value within the range of $[-2 \vec{a}, 2 \vec{a}]$.

(4) Searching for prey (Exploration)

When the value of $|\boldsymbol{A}|>\mathbf{1}$ in the GWO, the wolves are prompted to explore for more suitable prey. This exploration phase is influenced by the parameter $\overrightarrow{\boldsymbol{C}}$, which is a random value within the range $[ 0,2]$. The role of $C$ is to introduce stochasticity into the behavior of the grey wolves, either emphasizing $(\mathrm{C}>1)$ or deemphasizing $(\mathrm{C}<1)$ their predatory attack. This mechanism allows for a balanced exploration of the search space, mimicking the adaptive hunting behavior of grey wolves in the wild. The pseudocode detailing the GWO process is provided in Table 16.

GWO has been applied to solve optimization problems in a diverse range of fields. In medicine, it has been used for various optimization tasks [143], [144]. In manufacturing, it has been employed for operation sequencing [145]. The algorithm has also been adapted for use in unmanned aerial vehicle navigation [146], multi-agent systems [147], and robotics. For insights into the variety of GWO applications specifically in smart vehicle navigation, one can refer to Table 17. Gul et al. [148] proposed a hybrid algorithm combining PSO with GWO. This hybrid PSO-GWO algorithm was designed to improve path length and ensure smoother trajectories for mobile robots. Furthermore, a mutation operator was introduced to refine the trajectory generated by the PSO-GWO algorithm (Figure 10) [149]. To address the challenge of local minima in GWO, Dong et al. [150] suggested a modified position update mechanism specifically tailored for robot path planning. This modification aimed to enhance the algorithm's ability to navigate complex environments more effectively. In addition, Kumar et al. [151] developed a Variable Weight GWO, aimed at increasing speed and reducing the distance of planned routes for mobile robots. This variant of GWO adjusts the algorithm's parameters dynamically to optimize performance in real-time navigation tasks.

The MVO is an innovative population-based algorithm inspired by the multi-verse theory in physics, which posits the existence of multiple universes interacting within a multi-verse [153]. This algorithm incorporates three key cosmological concepts: white holes, black holes, and wormholes [154], [155]. In astrophysics, the Big Bang, considered the origin of the universe, is likened to a white hole [156], a concept representing regions emitting energy and matter. Conversely, black holes are known for their intense gravitational force, which attracts and absorbs matter, including light beams [157]. Wormholes are theorized as space-time passages that link different parts of a universe or even connect separate universes. The concept of universe expansion, driven by the inflation rate or eternal inflation [158], is also integrated into this model.

In MVO, these astronomical phenomena are mathematically modeled to facilitate exploration (white holes), exploitation (wormholes), and local search (black holes) in the search space. Each 'universe' in MVO represents a potential solution, with the objects within a universe analogous to variables of that solution. The fitness value of a solution is equated to its inflation rate. Universes in MVO adhere to the following principles:

(1) High inflation rate leads to a high chance of having a white hole.

(2) Low inflation rate leads to a low chance of having a black hole.

(3) High inflation rate universes are likely to pass objects through white holes.

(4) Lower inflation rate universes have a tendency to get objects through black holes.

(5) Regardless of inflation rate, objects in all universes can move randomly towards an optimal universe via wormholes.

Assuming that $U$ is a set of universes, where $n$ is the number of possible solutions (universes) and d represents the number of parameters or variables:

then each parameter can be represented as below:

$x_i^j$ is the $j$-th parameter of the $i$-th universe. $N I(U i)$ indicates the normalized inflation rate of the i-th universe. $U i$ is the $i$-th universe. $r 1$ is a random value in $[ 0,1].\quad x_k^j$ denotes the $j$-th variable of $k$-th universe chosen by a roulette wheel selection mechanism. Roulette wheel, which depends on normalized inflation rate, selects a universe and determines white holes for it. Through this mechanism, exploration is done. For exploitation, each universe is assumed to have wormholes connecting it to the best universe, facilitating the exchange of objects (parameters). The update for each parameter is thus given by:

where, $X_j$ represents the $j$-th parameter of the best universe formed so far, TDR (Travelling Distance Rate) and WEP (Wormhole Existence Probability) are coefficients, $l b_j$ and $u b_j$ denote the lower and upper bounds of the $j$-th parameter respectively, $x_i^j$ represents the $j$-th parameter of the $i$-th universe and $r$2, $r$3, $r$4 are random values in $[ 0,1]$. The formulas for the coefficients are as follows:

where, $\min$ and $\max$ are the minimum and maximum respectively, $l$ tells the current iteration and $L$ is the maximum iterations.

where, $p$ denotes the exploitation accuracy over the iterations, with higher values leading to more accurate exploitation/local search. The Multi-Verse Optimizer algorithm is detailed in the pseudocode shown in Table 18.

The MVO has been successfully implemented in a variety of domains to address complex optimization problems. Its applications range from project scheduling [159] to enhancing kernel extreme learning machines for medical diagnosis [160], modeling solar radiation [161], and solving economic dispatch problems in power systems [162]. In the field of robotics, MVO has demonstrated its versatility and effectiveness. It has been used for path planning in three-dimensional search spaces [163], tuning PID controllers [164], [165], planning the navigation of quadrotors [166], and devising routes for mobile robots [167]. However, the application of MVO in the navigation of smart vehicles is relatively nascent, with only a handful of researchers exploring its potential in this area, as detailed in Table 19.

The BA, inspired by the echolocation behavior of microbats, was developed by Yang [168]. Microbats emit short, loud bursts of sound at frequencies ranging from 25 kHz to 150 kHz and listen to the echoes bouncing back from nearby objects. This echolocation ability enables them to pinpoint the location of objects. Typically, the frequency of pulse emission and the loudness of the sound increase during prey search and decrease upon prey discovery. The BA is formulated based on idealized rules derived from this echolocation behavior:

(1) Bats estimate distance based on the echo of their sounds and can differentiate prey from other objects.

(2) Bats move randomly with a velocity $v_i$ towards a prey at position $x_i$, emitting sounds at a frequency $f_{\min }$, with wavelength $\lambda$ and loudness $A_0$.

(3) The loudness is assumed to be between a large positive value and its minimum value is defined as $A_{\min }$.

For the $\mathrm{BA}$, the frequency which is assumed to be within $\left[ 0, f_{\max }\right]$, the new velocity and position are defined below.

where, $x_*$ represents the current global best solution from all $n$ bats and $\beta$ is a vector within $[ 0,1]$. The loudness $(A)$, starts as any positive number, typically within the range $[ 1,2]$, and is then updated by a constant $\alpha \in[ 0,1]$ as shown in Eq. (36). $A=0$ when a solution is found. The rate of pulse emission $\boldsymbol{r}_i^0 \in[ 0,1]$ is controlled by a constant $\gamma$, which can be the same as $\alpha$.

For local search, new solutions for each bat are generated using a random walk strategy, once a solution is selected from the current best ones.

where, $\epsilon \in[-1,1]$ denotes a random number in $[-1,1]$ and $A^t$ represents average loudness of all bats at time $t$. The implementation of the Bat Algorithm is depicted in Table 20.

The implementation of the BA in the domain of mobile robot planning and navigation has yielded impressive results, as evidenced by numerous studies in the field. Table 21 provides an overview of various research efforts that have proposed enhancements to the BA, detailing the variables considered in each study. Among these advancements, Ajeil et al. [169] introduced a Modified Frequency Bat Algorithm (MFB) specifically designed to optimize the shortest path finding from a start to an end point, compared to the standard Bat Algorithm. This novel algorithm integrates obstacle detection and avoidance techniques, utilizing sensor data to dynamically plan new paths in response to moving obstacles. The algorithm's performance was evaluated through simulations conducted in a grid mat environment. The results demonstrated that the MFB outperformed the standard BA in terms of efficiency and effectiveness in pathfinding, particularly in environments with dynamic obstacles.

The TS [171] is a method of optimization that utilizes constraint-based techniques to avoid local minima in a search space. It incorporates flexible memory cycles to intensify and diversify local search patterns, thereby facilitating the discovery of optimal solutions. During the exploration process, Tabu Search meticulously tracks information about both the current solution and those previously explored [172]. The algorithm operates by employing neighborhood search methods to progress from a current solution x to a feasible solution x'within the neighborhood of x. This iterative process continues until a predetermined stopping criterion is met. One of the key features of TS is its use of memory structures to record visited solutions, preventing the algorithm from getting trapped in local minima and encouraging the exploration of unvisited areas in the search space [173]. The memory structures, also known as the tabu list, contain a set of recently visited solutions that are temporarily banned from reconsideration, typically for n iterations (where n, the tabu tenure, specifies the length of the list). The procedure for implementing this algorithm is outlined in Table 22.

The application of the TS in mobile robot navigation is still relatively underexplored. However, some studies, as indicated in Table 23, have developed new hybrids that enhance the basic algorithm's efficiency in path planning. Xing et al. [174] introduced a novel TS tailored for routing multiple AGVs in warehouse settings. Châari et al. [175] developed a TS-based system model for global path planning on grid maps. Kumar et al. [176] modified the TS method for navigating mobile robots in complex environments. Khaksar et al. [177] integrated TS rules into a fuzzy controller designed to address online navigation challenges. Panda et al. [178] proposed a hybrid algorithm combining TS and PSO to optimize pathfinding for AMRs.

An important aspect to consider when evaluating the metaheuristic algorithms discussed in this work is their performance on various benchmark functions. Benchmark tests, comprising mathematical functions, are instrumental in assessing the algorithms' ability to find solutions in a given dimension d that lead to global optima [182]. These benchmark functions, as cataloged in Table 24, can be categorized into unimodal, multimodal, or combinatory types, which blend unimodal and multimodal characteristics. Unimodal functions are designed to lead to a single optimum solution, whereas multimodal functions yield multiple optimum solutions.

The significance of metaheuristic algorithms in research, particularly in addressing complex real-world problems, is underscored by several advantages noted by Gholizadeh and Barati [183]. Their high efficiency and flexibility are key attributes that make these algorithms increasingly valuable in solving complex challenges. Additionally, the popularity and impact of a metaheuristic algorithm can often be gauged by the number of citations it receives in academic literature. Table 25 provides a ranking of the algorithms utilized in this study based on their citation count.

Selecting the appropriate algorithm for path planning in the application of smart vehicles is a critical decision. The choice of algorithm significantly depends on the specific requirements of the smart vehicle's mission. For instance, the algorithmic needs for rescue missions and urgent tasks differ markedly from those required for surveillance or logistics operations. A key consideration in this decision-making process is the balance between exploration and exploitation, which are inherent trade-offs in optimization problems. Exploration entails an efficient search of the solution space, aiming to circumvent local optima in pursuit of global solutions. While this process is thorough, it often results in slower convergence speeds. On the other hand, exploitation focuses on rapidly converging to a solution, which enhances the speed but raises the risk of becoming trapped in local optima. Therefore, when choosing an algorithm for path planning in a particular context, it's crucial to weigh these factors: convergence speed and the ability to identify global optima. The chosen algorithm should align with the specific objectives of the task at hand, whether it requires rapid response times or a more comprehensive search of the solution space.

In the realm of computational time and path optimization for smart vehicle applications, various metaheuristic algorithms exhibit distinct strengths. A hybrid CSA, for instance, has been shown to achieve optimal paths more rapidly than both PSO and GA [187]. PSO, on the other hand, outperforms the BA in terms of convergence when tuning omnidirectional mobile robots [188], while a hybrid PSO variant provides shorter paths in less time compared to modified BA and ABC [189].

CSA has been proven to outperform BA in finding an optimal path [121]. When it comes to covering the search space effectively, a multi-objective GWO demonstrates superior performance over multi-objective PSO and GA [190]. ACO outshines GA in obtaining optimal paths [191], and a hybrid ACO-PSO algorithm yields more optimal robot paths than ACO alone [192]. Moreover, ABC is noted for achieving shorter paths than PSO, as evidenced by simulation results [88]. These findings underscore the importance of selecting appropriate algorithms for specific tasks in smart vehicle applications, as outlined in Table 26, where the best-fitted algorithms for various industrial activities such as logistics, material handling, and surveillance are detailed.

The simulation of metaheuristic algorithms is carried out on various platforms, each offering unique mathematical and graphical functionalities. While some platforms provide a basic graphical representation of simulation outputs, others, like Gazebo-ROS, offer a more immersive experience with 3D animated environments for visualizing simulated outcomes. Among the most popular choices for researchers is MATLAB, known for its comprehensive inbuilt functions that greatly facilitate the programming of metaheuristic algorithms. However, some researchers prefer custom-built solutions, creating their own simulation platforms using fundamental programming languages such as C and C++ [175], [178]. Table 27 presents a compilation of the languages and simulation platforms commonly employed in this field of research. Additionally, a quantitative comparison of some of these simulators has been conducted by Farley et al. [193], providing insights into their respective capabilities and suitability for different types of simulations.

This study provides a comprehensive review of various metaheuristic algorithms and their hybrids, as developed by researchers to address path planning and navigation challenges in smart vehicles. The classification of these algorithms is primarily into two categories: population-based (encompassing evolutionary, swarm intelligence, and nature-inspired algorithms) and trajectory-based algorithms. A detailed description of each algorithm is provided, followed by reviews of recent articles spanning the last 13 years (2010 - 2023), with a majority of the studies concentrated between 2017 and 2023. Key parameters considered in this review include the type of vehicle (single or multiple robots), obstacle nature (static or dynamic), map type (topological, geometrical, or grid map), and the simulation platforms used for analysis.

The analysis also focuses on computational time and the efficiency of these algorithms in finding the shortest optimum path. Various tasks performed by smart vehicles are enumerated, highlighting the diverse applications. A notable observation is that navigation for smart vehicles remains an ongoing challenge, particularly in optimizing path length and reducing travel time. Researchers have made significant improvements and updates to these algorithms to address observed anomalies [118], [150]. A prominent trend is the development of hybrids between different algorithms, either to fine-tune parameters [136] or to combine advantages for enhanced robustness [119]. Path smoothing has been a crucial consideration in some studies, with techniques like cubic polynomials [85], [91], Bezier curves [78], [181], B-spline curves [55], and Cubic Ferguson splines [88] being used to generate smooth paths.

While most reviewed studies focused on static environments, there is a growing need to explore the navigation of smart vehicles in dynamic settings, considering moving obstacles and human interactions. One case study demonstrates the potential of using object detection sensors and refining data through neural networks with finely tuned weights for path planning in dynamic environments [167]. Additionally, combining reinforcement learning with metaheuristic algorithms could offer novel solutions for path planning challenges. For instance, incorporating reinforcement learning agents to balance exploration and exploitation in population-based metaheuristic algorithms could significantly enhance navigation path planning.