1. Introduction
In recent years, the rapid growth of the artificial intelligence field has led to extensive applications of mobile robots in various areas, including transportation, rescue operations, military applications, and agriculture [
1,
2,
3]. In mobile robot research, a core topic is path planning. Essentially, a robot must autonomously devise a safe, collision-free route from its starting point to its destination, considering the known environment. An efficient path-planning algorithm, characterized by quick optimization, concise routes, and strong obstacle avoidance, not only boosts a mobile robot’s task efficiency but also guarantees safe navigation [
4,
5,
6].
Mobile robot path planning can be classified into global path planning, relying on pre-existing knowledge, and local path planning, utilizing sensor-derived information, depending on the comprehension of environmental data [
7]. Global path planning involves charting an optimal path for a mobile robot in a completely known environment. Predominantly, traditional algorithms for global path planning encompass Dijkstra [
8], the A* algorithm [
9], and rapidly exploring random trees (RRTs) [
10]. Local path planning, also known as dynamic path planning, places a stronger emphasis on the real-time dynamic information of the robot’s current environment [
11]. It utilizes sensors to perform real-time detection of the surroundings, enabling the robot to achieve dynamic obstacle avoidance. Local path planning algorithms primarily include the dynamic window approach (DWA) [
12], artificial potential field (APF) [
13], and the time elastic band (TEB) [
14]. Drawing inspiration from nature, a surge in intelligent optimization algorithms has emerged for robot path planning. Notable ones include the genetic algorithm (GA) [
4], ant colony optimization (ACO) [
15], particle swarm optimization (PSO) [
16], grey wolf optimization (GWO) [
17], and the artificial bee colony algorithm (ABC) [
18]. Numerous scholars have conducted extensive research to improve and optimize the aforementioned algorithms, thereby enhancing their performance. Zheng et al. [
19] utilized the actual shortest distance traversed by ants to update heuristic information and introduced reward and penalty rules to optimize the local pheromone update strategy, thus enhancing the convergence speed and optimal solution capability of the ant colony algorithm. Raj et al. [
20] addressed the issue of autonomous mobile robots collecting information in unknown areas with energy constraints and time-sensitive preferences. They proposed an intelligent PSO technique, which determines fitness values by simplifying optimization tasks and improves the velocity update formula for each particle. This effectively optimizes the energy consumption and time constraints of mobile robot navigation. Dong et al. [
21] utilized three improvement strategies to balance the global and local search capabilities of the GWO. This approach mitigates the algorithm’s slow convergence and vulnerability to local optima issues to some extent. Eshtehardian et al. [
22] proposed a method that combines RRT* and B-spline optimization to smooth the paths generated by the RRT* algorithm. They also incorporated some optimization functions into the RRT* algorithm and provided correction methods, validating the effectiveness of the algorithm in the Webots simulation environment. Zhang et al. [
23] proposed a path-planning approach that combines ant colony algorithms with the A* shortest-path search algorithm. They optimized the heuristic function, enabling the method to swiftly and effectively obtain an optimal path.
Drawing inspiration from the collective intelligence, foraging, and anti-predator behaviors of sparrows, Xue et al. [
24] introduced a novel swarm intelligence optimization algorithm in 2020, termed the sparrow search algorithm (SSA). By simulating the foraging behavior of sparrow populations, this algorithm optimizes the exploration and exploitation capabilities of the search space to some extent. It showcases robust competitiveness concerning both convergence speed and stability when compared to alternative algorithms. However, during the later stages of the algorithm’s search for global optima, issues such as reduced population diversity, insufficient local exploration, and vulnerability to local optima arise [
25]. Liu et al. [
26] achieved a balance between the exploitation and exploration capabilities of the SSA using adaptive weight factors. They utilized the Cauchy Gaussian mechanism to enhance SSA’s ability to break free from stagnation, thereby verifying the superiority of this enhancement strategy. Zhou et al. [
27] proposed the incorporation of genetic algorithm crossover and mutation principles to enhance the convergence capability of the algorithm. Khedr et al. [
28] proposed a vehicle clustering algorithm that combines the GA and SSA to address the vehicle clustering problem in the Internet of Vehicles. This algorithm integrates the advantages of weight-based and mobility-based clustering methods, employing a fitness function that considers mobility metrics on clustering distance. This design results in superior performance in terms of cluster count and average cluster lifespan compared to the current state-of-the-art algorithms. Zhang et al. [
29] employed a linear path strategy in conjunction with neighborhood search strategies to enhance the fitness value of the global optimal individuals. They utilized an improved position update function to accelerate convergence speed and elevate the quality of planned paths. Geng et al. [
30] improved the development and exploration capabilities of the SSA by introducing an adaptive weight-balancing algorithm. They also employed an adaptive spiral search method to enhance the performance of the SSA, resulting in improved stability and convergence accuracy of the algorithm. Khaleel [
31] combined the SSA with differential evolution (DE), fully utilizing the advantages of these two heuristic algorithms. This integration improved the efficiency of job scheduling on a heterogeneous cloud computing platform, reducing system response time and energy consumption and effectively enhancing resource utilization.
The above research optimized the algorithm in terms of efficiency, computational complexity, energy efficiency, etc. The use of various optimization strategies and the fusion of multiple algorithms have certain reference significance for subsequent research, improving the performance of the algorithm to a certain extent and enhancing the efficiency and safety of path planning. Although the aforementioned studies on the SSA somewhat improved the algorithm’s performance, there is still room for optimization and improvement. Moreover, the current research on the SSA predominantly focuses on algorithmic theory and the ability to solve objective functions. Research applying the SSA to the field of robot path planning remains relatively limited, and there is a scarcity of studies investigating the algorithm’s applicability to dynamic path-planning challenges in complex environments for robots. Considering that mobile robots predominantly operate in dynamic work environments, the efficient planning of a globally optimal path while ensuring dynamic obstacle avoidance holds research significance and practical value. Through analyzing previous research, it is known that global path-planning algorithms can easily obtain the optimal path, but they cannot avoid unknown static and dynamic obstacles that may appear during the planning process. Local path-planning algorithms can navigate obstacles encountered during travel, but they are prone to falling into local optima [
32,
33].
Building on prior research, this paper addresses the challenges of mobile robot path planning and dynamic obstacle avoidance by proposing an integrated approach that combines the improved SSA with the DWA for path planning. Initially, addressing concerns arising during the iterative process of the basic SSA, such as insufficient population diversity, inadequate local exploration, slowed convergence speed, and poor ability to escape local optima, a multi-strategy optimization approach is integrated to enhance algorithm performance. This gives rise to the multi-strategy improved sparrow search algorithm (MISSA), facilitating the attainment of a globally optimal path. Subsequently, within the DWA, an adaptive velocity adjustment strategy is incorporated to enhance safety during the motion process. Furthermore, the evaluation function of the DWA is optimized and adjusted to improve its dynamic obstacle avoidance capability. Finally, the integration of the aforementioned two algorithms involves using the globally significant waypoints generated by the improved SSA as local subgoals within the DWA. This facilitates localized dynamic path planning through the application of the DWA. By ensuring that the globally planned path remains optimal, this integrated approach achieves dynamic obstacle avoidance for unknown obstacles, thereby yielding a smooth path for real-time obstacle avoidance and enhancing the overall efficiency of robot movement.
The remaining sections of this paper are organized as follows:
Section 2 introduces the basic SSA and the SSA with multiple strategy improvements.
Section 3 discusses the improved DWA and the MISSA-DWA fusion algorithm of dynamic path planning.
Section 4 analyzes simulation and experimental results, confirming the superiority of the improved algorithm and the effectiveness of the fusion algorithm through comparative experiments. Finally,
Section 5 gives the conclusion and outlines the next steps in the research plan.
4. Simulation and Experimental Results Analysis
4.1. Environment Modeling
Environment modeling is a crucial step in robot path planning. Common methods for environmental modeling include grid-based methods, topological methods, and visibility graph methods [
44]. This study adopts a grid-based approach for environmental representation. In the grid map, grid cells are binarized according to Equation (32) to establish the grid map. A value of 0 represents free traversable space, while 1 denotes obstacles. An illustrative grid map example is depicted in
Figure 5, where the workspace is divided into white and black grid cells. Here, black grid cells symbolize obstacle regions that are inaccessible to the robot, while white grid cells represent areas traversable by the robot. Therefore, the task of charting paths for mobile robots within complex environments transforms into the objective of determining the most efficient route from the starting point to the destination, utilizing a grid map model under defined constraints [
45,
46].
4.2. Simulation Experimental Environment
To guarantee the integrity and comparability of our experimental results, all simulation experiments adhered to uniform configurations. A grid-based approach was employed to construct grid maps for the simulation experiments. The computer processor used was an AMD R7-6800H with a clock frequency of 3.20 GHz, the operating system was Windows 11 (64-bit), and the system had 16 GB of memory. MATLAB R2022b served as the simulation platform.
4.3. Simulation Comparative Experiment of MISSA Global Path Planning
To validate the superior performance of the MISSA, this paper juxtaposes it with the conventional ACO, improved ant colony optimization (IACO), and SSA by performing simulations on two grid maps with distinct complexities. Simulation analysis is conducted on 20 × 20 grid maps of varying complexities. Crucially, to authenticate the algorithm’s efficiency, parameter configurations for both the SSA and the MISSA are kept uniform.
Table 1 delineates the parameter specifications for both the sparrow search and ant colony optimization algorithms.
4.3.1. Environment Model 1
In environment model 1, obstacles were sparsely distributed and simulations were executed on a 20 × 20 grid map within MATLAB.
Figure 6 visually represents the path-planning outcomes of ACO, IACO, SSA, and MISSA. To minimize the impact of random variables, each algorithm underwent 50 repetitive simulation trials. The comparative performance evaluation of these four algorithms is encapsulated in
Table 2.
Simulation outcomes reveal that all four algorithms are adept at devising collision-free global paths. Analyzing path length, total rotation angle, and runtime from 50 simulation trials, the MISSA emerged superior in path efficiency, charting the shortest path of 27.1290 m. This trims the shortest path lengths determined by the ACO, IACO, and SSA by 3.60%, 2.79%, and 4.28%, respectively. Its average path lengths also undercut theirs by 8.76%, 7.09%, and 15.31%, respectively. In rotation metrics, MISSA exhibited commendable precision. It slashed the minimal total rotation angle relative to paths from ACO, IACO, and SSA by 88.71%, 61.90%, and 77.98%, respectively. Similarly, the average rotation angles were curtailed by 91.68%, 66.99%, and 80.60%. When clocking runtime, MISSA proved to be more time-efficient. Its minimal runtime surpassed ACO, IACO, and SSA by shrinking durations by 21.45%, 88.92%, and 13.54%, respectively. Likewise, average runtimes dwindled by 47.48%, 88.39%, and 41.84% compared to the other algorithms.
4.3.2. Environment Model 2
To bolster the assertion of the enhanced algorithm’s supremacy, more complex obstacles are added to the grid map for simulation experiments.
Figure 7 distinctly displays the path optimization outcomes for ACO, IACO, SSA, and MISSA. After conducting 50 iterative experiments,
Table 3 provides a comprehensive performance comparison of these four algorithms.
From the simulation results of the four algorithms, the MISSA’s planned path stands out as the shortest, measuring at 34.3719 m. This is a reduction of 9.24%, 6.15%, and 4.98% compared to the shortest paths from the ACO, IACO, and SSA, respectively. In terms of average path lengths, the MISSA outperforms with a reduction of 19.55%, 9.81%, and 11.92% relative to the aforementioned algorithms. Regarding rotation angles, the MISSA’s minimal total rotation angle is 57.75%, 35.96%, and 20.86% less than the ACO, IACO, and SSA paths, respectively. The average rotation angles also show marked improvement, declining by 77.19%, 69.17%, and 57.79% for the respective algorithms. In runtime efficiency, the MISSA demonstrates significant prowess. Its fastest runtime is shorter by 69.77%, 82.71%, and 20.70% compared to the ACO, IACO, and SSA. The average runtimes also see notable reductions of 71.03%, 86.53%, and 33.23% compared to the trio of algorithms.
From the aforementioned experimental results, it is evident that the MISSA introduced in this study is adept at crafting globally optimal paths across diverse grid map complexities. The generated global path consistently outperforms the other three benchmarked algorithms, excelling in metrics like path length, total rotation angle, and runtime. Beyond its superior path optimization prowess, the MISSA also showcases remarkable stability and the ability to produce smooth paths.
4.4. Analysis of Random Obstacle Avoidance in the Fusion Algorithm
In a grid map of the same environment, four sets of simulation experiments were designed to validate the integrated algorithm. The path planning was conducted using both the MISSA and the combined MISSA-DWA method. The starting and ending grids were marked as “S” and “G”, respectively. Various quantities of random obstacles, represented as blue rectangles, were added to the grid map. The parameters for the DWA are set as follows: the maximum linear velocity is 1 , the maximum linear acceleration is 0.3 , the maximum angular velocity is 30 , the maximum angular acceleration is 50 , the velocity resolution is 0.01 , the angular velocity resolution is 1.0 , the time resolution is 0.1 s, and the prediction period is 3.0 s. The parameters for the evaluation function are set as , , , , and .
Figure 8 displays the simulation outcomes for random obstacle avoidance. The path plotted by the MISSA is illustrated in red, whereas the blue pathway symbolizes the path designed using the MISSA-DWA fusion method. From these simulations, it becomes evident that in the absence of random obstacles, both algorithms can achieve optimal paths. However, when confronted with random obstacles, the MISSA, relying solely on global map data, fails to recognize and subsequently avoid these obstructions. Conversely, the MISSA-DWA approach seamlessly integrates real-time obstacle evasion for sporadic barriers while ensuring path fluidity. As the quantity of random obstacles rises, the designed route consistently demonstrates its efficacy in bypassing impediments and securing a successful arrival at the intended destination. In essence, the introduced hybrid methodology proficiently negotiates random obstacles within grid maps, delivering a streamlined route that closely mirrors the globally optimal trajectory. Pertinent performance metrics for random obstacle sidestep**, utilizing the fusion algorithm, are detailed in
Table 4.
4.5. Dynamic Path Planning with the Fusion Algorithm
In an effort to robustly assess the obstacle evasion capabilities of the MISSA-DWA fusion algorithm within dynamic environments, simulations were executed across four types of environmental models on a 50 × 50 grid map. A certain number of dynamic obstacles and random unknown obstacles are introduced into the experimental environment. “S” and “G” identify the starting and ending grid cells, respectively. The green cursor reflects the robot’s directional sensing. Dynamic obstacles are illustrated as pink orbs, with their origins and movement paths depicted by light pink dots and dashed lines. Blue rectangles represent unpredictable obstructions. The trajectory crafted by the MISSA is denoted in red, while the fusion algorithm’s real-time navigation is rendered in blue, emphasizing the fusion algorithm’s agility in swiftly adapting to dynamic changes.
From
Figure 9a, it is evident that the robot follows the path prescribed by the MISSA until it encounters the first unknown obstacle. Upon detecting this unknown static obstacle and assessing the robot’s relative position and motion status in relation to it, there is a foreseen risk of a collision along the original trajectory. Consequently, the fusion algorithm is activated to engage in local obstacle avoidance, effectively circumventing the unknown obstacle. Subsequently, the robot recalibrates its route to converge with the optimal path generated by the MISSA. As illustrated in
Figure 9b, the robot detects a dynamic obstacle at that location and, foreseeing a potential side collision, employs a local obstacle avoidance strategy after determining the dynamic obstacle’s movement direction. Through four instances of real-time obstacle avoidance scenarios involving both unknown static and dynamic obstacles, the robot successfully reaches the target point, as evidenced in
Figure 9c.
In
Figure 9, it is evident that the robot, commencing its journey from the initial point, consistently demonstrates the ability to promptly and accurately employ appropriate obstacle avoidance strategies when confronted with lateral and frontal collisions involving random unknown obstacles and dynamic obstacles along the global path. This capability enables the robot to discern a smooth and secure path, ultimately achieving the anticipated outcome of algorithm fusion.
To further substantiate the efficacy of the proposed fusion algorithm, a series of dynamic path-planning simulations were executed under diverse scenarios. The paths generated by the fusion algorithm were juxtaposed with the globally planned paths determined by the MISSA to ascertain the dynamic obstacle avoidance performance outlined in this paper. The simulation results encompassing three distinct complexity levels of environments are illustrated in
Figure 10.
Summarizing the simulation results across the four environments, it can be inferred that in environments containing both unknown static and dynamic obstacles, the enhanced MISSA’s planning process, which does not rely on dynamic grid information, generates paths consistent with those in static environments. As a consequence, it lacks real-time dynamic obstacle avoidance capabilities, rendering it incapable of maneuvering around dynamic obstacles. In contrast, the proposed MISSA-DWA algorithm, coupled with the improved DWA algorithm, demonstrates the ability to perform real-time local dynamic path planning based on the global path. It successfully navigates around newly introduced unknown static and dynamic obstacles, crafting smooth paths that strike a balance between global optimality and effective obstacle avoidance. The algorithm adapts seamlessly to complex dynamic obstacle environments, thereby enhancing the operational efficiency of the robot.
4.6. Experimental Validation
To further assess the effectiveness of the algorithm in real-world applications, practical robot path-planning experiments were conducted in an actual environment. The current study utilized the Songling Robot SCOUT2.0 robot chassis, equipped with a Velodyne 16-line LiDAR sensor and integrated with the ROS system on the host computer. The host computer facilitated control over the robot and its sensors, enabling the collection of environmental data. The Gmap**-SLAM algorithm was employed to generate a two-dimensional grid map of the experimental surroundings. The resulting grid map was saved in image format, with white areas denoting explored and unoccupied regions, black areas indicating detected obstacles, and gray areas representing inflated obstacle boundaries. Subsequently, the MISSA and MISSA-DWA fusion algorithms were validated within the constructed grid map.
The experiments in a real-world environment are divided into static and dynamic components. In the static path-planning experiment, the first step involves constructing the environmental map and launching the Rviz platform. Subsequently, the robot’s initial and destination points are specified, and the MISSA-DWA fusion algorithm is invoked to facilitate global path planning for the robot, guiding it from the starting point to the target point within a static environment. The robot adheres to the planned path as it progresses toward the destination. The experimental procedure, as depicted in
Figure 11 and
Figure 12, illustrates that the mobile robot departs from its initial position and adeptly navigates around all static obstacles throughout the entire movement process. Eventually, the robot safely arrives at the target point by following the globally optimal path. The feedback of robot control parameters during the experiment is shown in
Figure 13.
To assess the robot’s capability to avoid dynamic obstacles during its movement, a small mobile robot was introduced as a dynamic obstacle in the experimental environment, as depicted in
Figure 14. The experimental procedure, as illustrated in
Figure 14 and
Figure 15, demonstrates that after the robot plans its global path and embarks on its journey, the dynamic obstacle robot is activated and positioned onto the pre-planned global path. As the dynamic obstacle enters the detection range of the local path-planning algorithm, the robot promptly identifies and responds, utilizing the fusion algorithm for local dynamic obstacle avoidance. This enables successful avoidance of the dynamic obstacle, as depicted in
Figure 15a,c. Subsequently, the robot continues its movement toward the planned global optimal path and ultimately reaches the target point. The experimental results in
Figure 14 and
Figure 15 illustrate that the proposed fusion algorithm ensures smooth motion paths while effectively evading dynamic obstacles in the environment, thereby validating the algorithm’s effectiveness. The feedback of robot control parameters during the experiment is shown in
Figure 16.
To further validate the proposed algorithm and its effectiveness, experiments were conducted in a more complex map environment. Additional randomly shaped static obstacles and dynamic obstacles were introduced into the experimental environment. In the more complex conditions, as shown in
Figure 17 and
Figure 18, two blue benches and a barrel were added as new random static obstacles, and a small mobile robot served as a dynamic obstacle. The experimental results demonstrate that the mobile robot can still plan its path reasonably based on the algorithm and navigate around static and dynamic obstacles effectively, ensuring the robot reaches the target point safely. This further validates the effectiveness of the algorithm. The feedback of robot control parameters during the experiment is shown in
Figure 19.