Two-layer path planning framework for WMRs in dynamic environments: Optimized ant colony algorithm and dynamic window approach

Abstract

This paper proposes a two-layer path planning method for wheeled mobile robots (WMRs), where an improved ant colony optimization (ACO) and optimized dynamic window approach (DWA) algorithms are used, at the global and local layer, respectively. This method allows WMRs to plan a high-quality path under complex dynamic scenarios, while costing less traveling time and energy consumption. At the level of global path planning, a modified ACO algorithm is presented which incorporates a path duplicate counter, a new heuristic function and path smoothing operation to enhance the feasibility and robustness of global path planning. At the level of local path planning, based on DWA, an optimization method composed by energy evaluation and dynamic obstacle avoidance evaluation sub-function is proposed to save the energy cost, while enhancing the ability of WMRs to avoid moving obstacles. This study aims to enhance the efficiency and effectiveness of path planning for WMRs using a combination of ACO and DWA algorithms, such that the proposed algorithm can be applied to multi-obstacle environment to execute dynamic objects avoidance. Finally, a multi-blockage environment involved with dynamic obstacles are simulated to verify the proposed path planning method.

Keywords

Ant colony optimization (ACO)dynamic window approach (DWA)wheeled mobile robot dynamic obstacle avoidance path planning

Introduction

In recent decades, path planning has become crucial in robotics. It ensures safe navigation, optimizes robot operations, and supports task execution. In addition, it improves adaptability and facilitates coordination among robotic systems (Deng et al., 2021; Fareh et al., 2020; Sanchez-Ibanez et al., 2021; Zhang et al., 2022). The path planning of wheeled mobile robots (WMRs) involves determining the optimal path for the robot from the starting point to the target location while avoiding obstacles and considering various constraints. In order for WMRs to autonomously navigate in dynamic and uncertain environments, effective path planning algorithms play a crucial role (Gasparetto et al., 2015; Karur et al., 2021; Li et al., 2019; Madridano et al., 2021). Path planning for WMRs typically involves two components: global planning and local obstacle avoidance. Global planning involves determining a high-level path from the starting node to the goal, while local obstacle avoidance focuses on navigating around obstacles in the immediate vicinity of the robot to ensure safe and efficient movement.

In evaluating path planning algorithms for dynamic environments, each offers distinct advantages and challenges. A* algorithm, while optimal for static environments due to its efficient shortest path finding, struggles in dynamic settings due to its inability to adapt without complete re-computation. Rapidly exploring random trees (RRTs) excel in high-dimensional space exploration but often yield non-optimal paths that are not smooth. Genetic algorithms (GAs) provide robust solutions across complex scenarios but require significant computational resources and are sensitive to parameter settings, often converging to local optima. Ant colony optimization (ACO), known for its adaptability to dynamic changes through continuous pheromone updates, sometimes suffers from slow convergence in complex environments. Meta-heuristic algorithms such as ACO have been applied in various fields like robotics and transportation. ACO is proposed by Dorigo et al. (1996) in the 1990s, which is based on the concept of ants depositing pheromone trails to communicate and navigate (Blum, 2005; Gul et al., 2022; Hou et al., 2022; Miao et al., 2021; Morin et al., 2023). In recent years, scholars are implementing different approaches, dedicated to improve the effectiveness of ACO. For example, in the field of public transportation and travel sector, Che and Chen (2023) used an improved ACO with a Dijkstra least square method for personalized travel route planning in the tourism industry. Similarly, Zidi et al. (2006) presented ACO for the time scheduling of public transport traffic. Meanwhile, in the field of path planning, ACO demonstrates the process that ants explore the graph by randomly selecting paths and leaving pheromone trails. The pheromones deposited by ants guide other ants to follow more favorable paths, over iterations, the paths with higher pheromone concentration become more attractive, leading to the discovery of optimal or near-optimal paths (Dorigo and Stützle, 2019). However, as the number of ants and iterations increase, the algorithm’s computational complexity grows, making it inefficient for large-scale problems. To improve the path finding efficiency, Wang et al. (2023b) proposed a Monte Carlo–based improved ACO that uses a sigmoid function and a feedback adjustment factor. In addition, Dosad (2023) introduced a hybrid algorithm that combines ACO with particle swarm optimization to enhance convergence speed and avoid local extremum and deadlock. Nonetheless, ACO relies on pheromone deposition and communication between ants, and depending on the initial pheromone distribution and parameters, it may converge to sub-optimal paths instead of the globally optimal ones. Addressing this problem, Wang et al. (2023a) proposed an improved ACO for obstacle avoidance of robot manipulators, which includes adding an obstacle environment to the heuristic function and using the worst ant colony to avoid local optimal solutions. In addition, aiming at the shortcomings of ACO in the complex environment, such as being easy to fall into local optimum and difficult to guarantee real-time path planning of robots, Castillo et al. (2015) explored a new fuzzy approach for diversity control in ACO. Besides, Zhang et al. (2021) and Amar and Jasim (2021) introduced hybrid meta-heuristic approach for robot path planning in dynamic environment, and three approaches for determining the optimal pathway of a robot in a dynamic environment were proposed. To further improve the path planning of WMRs in complex dynamic environments, Yang et al. (2022) proposed an enhanced hybrid algorithm by considering the excellent search capability of ACO for global paths and the advantages of DWA for local obstacle avoidance. Similar work can be found from Ahmmed et al. (2008). However, few articles considered both the computing performance and the global tendency improvements of ACO at the same time. Another limitation of ACO is that ACO is not inherently designed to handle dynamic environments where obstacles or conditions change frequently. It lacks real-time adaptability, which can lead to sub-optimal or infeasible paths in such scenarios. This paper is devoted to addressing the problems above, making ACO able to apply to various path planning problems.

Meanwhile, in terms of local path planning methods, dynamic window approach (DWA) is commonly used. DWA is proposed by Fox et al. (1997) in 1997, which aims to navigate WMRs through an environment by dynamically selecting a safe and feasible velocity command. DWA combines information about the WMRs’ current state and the surrounding obstacles to generate a safe and available path. DWA and the artificial potential field (APF) method are key techniques for local path planning, each with distinctive advantages and drawbacks that determine their effectiveness in different scenarios. DWA stands out for its real-time obstacle avoidance capabilities, making immediate adjustments based on the robot’s current state and velocity, thus excelling in dynamic environments with moving obstacles. This focus on real-time processing, though myopic, allows DWA to respond swiftly to environmental changes, which is crucial for navigating through rapidly altering conditions. On the contrary, APF’s approach, based on modeling attractive and repulsive forces, is straightforward and computationally efficient, suitable for static environments. However, APF often struggles with local minima and complex obstacle configurations, where the robot might get trapped in positions that are neither at the goal nor free from net forces. Given these characteristics, DWA was chosen over APF for this research due to its robust performance in handling real-time adjustments and dynamic obstacles more effectively. DWA’s method of evaluating all feasible movements within a specified window to optimize a function that considers safety and goal distance ensures that the robot avoids obstacles while maintaining a feasible path towards the target, aligning well with the needs of mobile robots in interactive and unpredictable settings. DWA generates a window of reachable velocities and evaluates them using an objective function to select an optimized velocity (Chang et al., 2021; Xu et al., 2023; Yang et al., 2023; Zhan et al., 2013, 2015; Zhou et al., 2023). However, DWA focuses on finding a locally optimal trajectory by considering only immediate obstacles and kinematic constraints. As a result, it may not always generate the globally optimal path. Several papers proposed improvements to tackle the problem, including hybridization with particle swarm optimization (Yang et al., 2023), parameter adaptation based on real-time obstacle information (Li et al., 2023), combination with velocity obstacle, and integration with fuzzy inference system and Kalman filter for state estimation of dynamic obstacles, and so on. Furthermore, the following articles integrated DWA with other algorithms to improve performance. For example, Jin et al. (2022) coordinated DWA with improved A* algorithm as a global planner, while Lin et al. (2022) proposed a modified DWA based on fuzzy control scheme combined with particle swarm optimization-based artificial potential field. In addition, Zhou et al. (2023) proposed an RRT* algorithm that combines the RRT* algorithm with fuzzy-based DWA to generate a global optimal path and handle the local path in real-time when obstacles are nearby. Finally, in the automotive field, Hang et al. (2023) raised a local path planning method for intelligent vehicles that incorporates the minimum turning radius constraint and the curvature retention evaluation index into DWA. Nevertheless, DWA primarily assumes static obstacles and may face challenges in adapting to dynamic obstacles that move or appear unexpectedly during the WMRs’ motion. It may not be able to generate appropriate avoidance strategies in real-time for such dynamic scenarios, potentially resulting in collisions. Besides, DWA does not explicitly optimize for factors like energy consumption or minimum time, which can be a drawback in applications that require optimal resource allocation or time-sensitive tasks. Also, DWA focuses on local obstacle avoidance and does not provide a holistic view of the entire path from starting node to goal. It lacks the ability to perform long-range planning or consider the global optimality of the chosen path.

DWA is adept at real-time decision-making in dynamic scenarios but tends to focus on local path optimality, potentially missing better global routes. Given these considerations, the combination of ACO and DWA was chosen for this study to leverage ACO’s global optimization capabilities, enhancing path diversity and adaptability, complemented by DWA’s strength in real-time, local obstacle avoidance. This hybrid approach aims to balance the exploration of optimal paths at a global level with effective real-time adjustments at a local level, making it particularly suitable for environments with dynamic and unpredictable obstacles. This choice is further justified in the manuscript through comparative analysis, highlighting how this combination better addresses the specific requirements of WMRs in complex dynamic environments. Inspired by the aforementioned paper, this study aims to propose a path planning framework that combines the improved ACO with the optimized DWA algorithm. By integrating these two algorithms, WMR is able to overcome the drawbacks of each algorithm and achieve more efficient and robust path planning. The main contributions of this paper are as follows.

At the layer of global path planning, using ACO, an approach is proposed that includes a path duplicate counter to prevent ants from getting stuck in deadlocks, and increased heuristic information to guide ants towards globally or locally optimal paths. Specifically, to optimize the generated path, triple line segment optimization and the Floyd path smoothing algorithm is raised, thus reducing sharp turnings and path length.

At the aspect of local path planning, using DWA, a method is proposed that includes setting a dynamic initial heading angle to minimize immediate turning at departure, improving the evaluation equation to prioritize paths with lower energy consumption, and introducing a dynamic obstacle avoidance evaluation sub-function to enhance WMR’s capability to avoid moving obstacles.

The rest of this paper is organized as follows. Section II describes the design of the architecture associated with ACO. The design and improvements of DWA are presented in Section III. In Section IV, the simulation scheme and the results of the simulation are presented. Section V concludes this paper.

Global path planning

Traditional ACO algorithm

ACO is a heuristic search algorithm that simulates the foraging behavior of ants. In the process of searching for food, ants leave pheromones on their path, and other ants follow the paths with more pheromones, gradually discovering the shortest path, as shown in Figure 1(a).

Figure 1.

Principle of traditional ACO: (a) searching process of ants and (b) situation of deadlock solved by path duplicate counter mechanism.

During the search process, ants probabilistically choose the next direction based on the pheromone information. After passing through a path, ants release pheromones on the path, and the concentration of pheromones is also updated. Both the search process of ants and the updating process of pheromones have certain mathematical descriptions as follows:

τ_{ij} \leftarrow (1 - ρ) \cdot τ_{ij} + \sum_{k = 1}^{m} Δ τ_{ij}^{k}

(1)

where $τ_{ij}$ represents the pheromone concentration on path ( $i$ , $j$ ), $ρ$ is the pheromone evaporation coefficient, $Δ τ_{ij}^{k}$ represents the amount of pheromones deposited by the $k$ th ant on path ( $i$ , $j$ ), and $m$ is the amount of ants.

The probability equation for ants to choose the next direction can be described as:

P_{ij}^{k} = \frac{{[τ_{ij} (t)]}^{α} \cdot {[η_{ij}]}^{β}}{\sum_{u \in J_{k}^{i}} {[τ_{iu} (t)]}^{α} \cdot {[η_{iu}]}^{β}}

(2)

where $P_{ij}^{k}$ represents the probability that ant $k$ at position $i$ chooses path ( $i$ , $j$ ) when making a decision, $τ_{ij} (t)$ represents the pheromone concentration on path ( $i$ , $j$ ) at the current time, $η_{ij}$ represents the heuristic factor on that path, $α$ , $β$ are parameters that represent the importance of the pheromone and heuristic factors, $u$ represents the collection of paths chosen by all ants, and $J_{k}^{i}$ represents the set of paths that the $k$ -th ant can choose from while at position $i$ .

The heuristic factor $η_{ij}$ can be described as:

η_{ij} = \frac{1}{d_{ij}}

(3)

where $d_{ij}$ represents the distance of path ( $i$ , $j$ ).

However, traditional ACO algorithms often suffer from slow convergence and the tendency to get trapped in local optima, particularly in complex environments. The improved ACO method proposed in this paper addresses these weaknesses by incorporating a path duplicate counter and an enhanced heuristic function, which significantly reduce the likelihood of premature convergence and improve the global search capability. The results in this paper demonstrate faster convergence and more optimal path selection, which are critical in dynamic environments where real-time adjustments are necessary.

ACO modification and improvements

Path duplicate counter

In ACO, a duplicate path counter is introduced to avoid ants getting stuck in loops or repeatedly visiting the same path. It is achieved by limiting the number of times ants choose previously traveled paths. In implementation, a counter $φ$ can be set for each path, and when an ant chooses that path, the counter $φ$ increases by 1. When $φ$ reaches a predefined threshold $φ_{\max}$ , the path is considered not able to pass, thus the ant no longer chooses that path.

In the grid map, the planned path is stored in the array in the form of a two-dimensional point matrix. As shown in Figure 1(b), $P_{0} (x_{0}, y_{0}), P_{1} (x_{1}, y_{1}), P_{2} (x_{2}, y_{2}), P_{3} (x_{3}, y_{3})$ indicate the path node selected after optimization. $\vec{P_{0} P_{1}}, \vec{P_{1} P_{2}}, \vec{P_{2} P_{3}}$ represents the path that avoids deadlocks. The pseudo-code for path duplicate counter is shown in Algorithm 1.

Algorithm 1 Path duplicate counter
Require: $path = \sum_{i = 1}^{n} (x_{i}, y_{i})$
%The set of predecessor path nodes.
Ensure: $pat h_{optimized} = \sum_{i = 1}^{n} (x_{i}, y_{i})$
%The set of optimized path nodes.
$isPathEqual$ = true
if $numel (path) > 1$ then
for i = 1:(numel( $path$ )-1) do
if numel( $pat h_{optimized}$ ) == numel( $path$ {i , m}) then
if sum( $pat h_{optimized}$ == $path$ {i,m})==numel( $pat h_{optimized}$ ) then
$isPathEqual$ = false
end if
end if
end for
end if
if $i s P a t h E q u a l$ = true then
$pat h_{optimized} \leftarrow path$
else
$φ = φ + 1$
if $φ > φ_{\max}$ then
Sample again from the previous turning point
$pat h_{optimized} \leftarrow New Sample$
end if
end if

By introducing the duplicate counter, ants can be prevented from continuing stuck in deadlocks by repeatedly selecting the same path. Also, it effectively speeds up convergence speed.

Increase heuristic information

To expedite the ant’s search speed and increase path diversity, a local search mechanism is introduced. This can be achieved by allowing ants, when selecting paths, to ignore the pheromone concentration with a certain probability and instead randomly explore other paths, as shown in Figure 2(a). This helps prevent ants from getting trapped in local optima and promotes global exploration. The implementation steps are as follows:

Step 1 Set a control parameter $ζ \in (0, 1)$ , representing the probability for each ant to perform local search when selecting a path.

Step 2 When an ant reaches a location and is ready to choose the next one, determine the next step’s selection method based on the local search probability. Moreover, a control parameter of $ζ$ is introduced, which means ants have a chance of ignoring pheromone concentration and exploring other paths randomly.

Step 3 If a randomly generated probability $G \in (0, 1)$ is less than the local search probability $ζ$ , the ant will perform a local search. In this case, the ant selects an unexplored adjacent location randomly as the next step. This helps prevent ants from getting stuck in paths with high pheromone concentration and increases path diversity.

Step 4 If $G$ is greater than the local search probability $ζ$ , the ant will choose the next location in the traditional way, based on the pheromone concentration.

Figure 2.

ACO improvements: (a) increased heuristic information and local search mechanism and (b) path smoothing process and its effect.

In conclusion, the probability equation for ants to choose the next target $j$ at time $t$ can be represented as follows:

P_{ij}^{k} (t) = {\begin{matrix} \begin{matrix} \frac{{[τ_{ij} (t)]}^{α} \cdot {[η_{ij}]}^{β}}{\sum_{u \in J_{k}^{i}} {[τ_{iu} (t)]}^{α} \cdot {[η_{iu}]}^{β}}, G \geq ζ, u \in J_{k}^{i} \\ \frac{1}{| J_{i} (t) |}, G < ζ, u \in J_{k}^{i} \\ 0, u \notin J_{k}^{i} \end{matrix} \end{matrix}

(4)

where $J_{i} (t)$ represents the set of non-obstacle target spots that the $k$ th ant can choose from while at position $i$ .

Path smoothing

When using ACO to solve optimization problems, the generated path may not be a straight line but rather a series of line segments. To further optimize this path, the technique of triple line segment optimization can be employed. Triple line segment optimization is a technique used within ACO to improve the efficiency of path planning. It is achieved by introducing additional control points at the turning points of the path, making the path smoother and avoiding sharp turns.

The algorithm involved in implementing triple line segment optimization can be described as below:

Step 1 Divide the original path into a series of line segments, each consisting of two adjacent path points.

Step 2 For each line segment, determine the turning point between the two endpoints (often the midpoint of the segment).

Step 3 Add two control points between the original endpoints of each line segment to make the path smoother. The position of these control points are the perpendicular bisector of the endpoints.

Step 4 Use cubic Bezier curve interpolation to replace each line segment of the original path with a third-order polyline. This curve will pass through the endpoints and control points to connect the path segments.

Step 5 Repeat $Steps 2 ~ 4$ until all line segments have been optimized, resulting in the final optimized path.

After this, Floyd path smoothing algorithm is introduced to further optimize the route processed by triple line segment optimization. The algorithm involved can be described as:

Step 1 For each point in the path, evaluate its smoothness by calculating the distance between its neighboring points.

Step 2 If the distance between the neighboring points around a particular point is too small, indicating a sharp turn in the path, it can be smoothed out by finding the midpoint between the two neighboring points and introducing it as a new point in the path.

Step 3 Repeat $Steps 1 ~ 2$ until all points have been smoothed.

By applying the techniques of triple line segment optimization and Floyd path smoothing algorithm, a smoother and more optimized path can be obtained that reduces sharp turns and the number of curves, thereby improving the quality and feasibility of the path, as shown in Figure 2(b).

Local path planning

Traditional DWA

Traditional DWA algorithm searches for the WMR’s control commands within the given range of velocities and accelerations, and selects the optimal command through an evaluation equation. The main advantage of the DWA algorithm is fast computation speed, making it suitable for robots that require rapid response for path planning. The basic steps of the DWA algorithm are as follows:

First, based on WMR’s current velocity, a set of possible velocities is sampled within the reach of the acceleration and rotation speed ranges, each velocity consisting of a linear velocity and an angular velocity. Base on WMR’s mechanical performance, the available speed range $V_{m} = [v, ω]^{T}$ is:

{\begin{matrix} 0 \leq v \leq v_{\max} \\ ω_{\min} \leq ω \leq ω_{\max} \end{matrix}

(5)

where ( $0$ , $v_{\max}$ ) and ( $ω_{\min}$ , $ω_{\max}$ ) represent the constraints allowed by WMR.

Besides, the velocity pairs cannot exceed WMR’s maximum linear acceleration ${\overset{\cdot}{v}}_{\max}$ and maximum angular acceleration ${\overset{\cdot}{ω}}_{\max}$ , thus the available speed range $V_{d} = [v, ω]^{T}$ is:

{\begin{matrix} v_{t} - {\overset{\cdot}{v}}_{\min} Δ t \leq v \leq v_{t} + {\overset{\cdot}{v}}_{\max} Δ t \\ ω_{t} - {\overset{\cdot}{ω}}_{\min} Δ t \leq ω \leq ω_{t} + {\overset{\cdot}{ω}}_{\max} Δ t \end{matrix}

(6)

where $({\overset{\cdot}{v}}_{\min}, {\overset{\cdot}{v}}_{\max})$ , $({\overset{\cdot}{ω}}_{\min}, {\overset{\cdot}{ω}}_{\max})$ are the constraints of WMR’s linear and angular acceleration, and $Δ t$ indicates the sampling time.

Also, there is a safety speed for WMR to avoid colliding into obstacles, thus the available speed range $V_{s} = [v, ω]^{T}$ is:

{\begin{matrix} 0 \leq v \leq \sqrt{2 {\overset{\cdot}{v}}_{\min} dist (v, ω)} \\ 0 \leq ω \leq \sqrt{2 {\overset{\cdot}{ω}}_{\min} dist (v, ω)} \end{matrix}

(7)

dist (v, ω) = \sqrt{{(x_{t} - x_{obs})}^{2} + {(y_{t} - y_{obs})}^{2}}

(8)

where $dist (v, ω)$ represents the Euclidean distance between the position of WMR $(x_{t}, y_{t})$ and the nearest obstacle point $(x_{obs}, y_{obs})$ .

Ultimately, the result of WMR’s selectable speed range $V_{r}$ is:

V_{r} = [v, ω]^{T} = V_{m} \cap^{V_{d}} \cap^{V_{s}}

(9)

Last procedure is the evaluation equation. For each predicted trajectory, a corresponding evaluation value is calculated. The value is usually a weighted sum of heading angle towards the target, the distance to obstacles, and the WMR’s velocity.

First, $heading (v, ω)$ indicates WMR’s orientation degree to the target. The larger value $heading (v, ω)$ is, the closer WMR is heading towards the optimal direction, which can be described as:

heading (v, ω) = 180 - (| \arctan \frac{y_{T} - y_{t + Δ t}}{x_{T} - x_{t + Δ t}} - θ_{t + Δ t} | \cdot \frac{180}{2 π})

(10)

where $(x_{T}, y_{T})$ is the target node of DWA, and $x_{t + Δ t}, y_{t + Δ t},$ $θ_{t + Δ t}$ are the state parameters of WMR after sampling time $Δ t$ , which shares the same model as shown in equation (14).

Next, $dist (v, ω)$ shares the same definition as shown in equation (8).

Then, $vel (v, ω)$ is the velocity of WMR, which can be described as:

vel (v, ω) = | v |

(11)

Last, the evaluation equation $V_{cost}$ can be described as:

\begin{matrix} V_{cost} = σ ( & c_{1} \cdot heading (v, ω) + c_{2} \cdot dist (v, ω) + c_{3} \cdot vel (v, ω)) \end{matrix}

(12)

where $c_{1}$ , $c_{2}$ and $c_{3}$ are the coefficient weights for the three factors above, and $σ$ indicates normalization process of the evaluation equation.

Ultimately, DWA will select the velocity with the highest evaluation value $V_{r} = [v, ω]^{T}$ as the control command for the next step. This method is effective in real-time obstacle avoidance but often fails to consider energy efficiency and global path optimality. Recent works have attempted to improve DWA by integrating it with other algorithms like A* or using fuzzy logic. However, these methods still exhibit limitations in handling complex dynamic environments where rapid changes occur. Our optimized DWA addresses these issues by incorporating an energy evaluation sub-function and a dynamic obstacle avoidance evaluation, which not only enhances the WMR’s ability to avoid obstacles but also optimizes energy consumption, leading to more efficient and sustainable operations.

DWA modification and improvements

Dynamic initial heading angle

The purpose of introducing dynamic initial heading angle in DWA is to improve the feasibility and robustness of path planning by limiting WMR’s initial heading angle during navigation.

In traditional DWA, the initial pose of WMR, including its position and heading angle, affects path planning and motion control. If the initial heading angle of WMR is random or can change freely within a certain range, WMR may make unnecessary turns or even fail to reach the target location, as shown in Figure 3(a).

Figure 3.

DWA improvements: (a) dynamic initial heading angle mechanism and (b) kinematic and energy consumption evaluation model for WMR.

The method of introducing dynamic initial heading angle is to calculate the direction angle $θ_{heading}$ between WMR’s starting heading angle $θ_{0}$ at starting position $(x_{0}, y_{0})$ and the first critical node generated by ACO $(x_{c 1}, y_{c 1})$ before the DWA algorithm starts running, then control rotating WMR in place by an angle of $θ_{heading}$ , which can be described as:

θ_{heading} = \arctan \frac{y_{c 1} - y_{0}}{x_{c 1} - x_{0}}

(13)

This can effectively reduce WMR’s motion control space, making path planning more reliable and efficient, while also increasing its path planning success rate and safety.

Introduce energy evaluation

The purpose of introducing evaluation of energy consumption during motion is to make WMR more inclined to choose a path with less energy consumption. The energy evaluation equation should be defined based on the specific mobile robot system. Initially, efforts are made to measure the energy consumption of WMR at different speeds and directions, such as battery consumption and motor runtime, and so on. However, due to the WMR’s diversity of forms in real-life scenarios, a relatively universal approach for the estimation of energy consumption is selected.

The WMR model discussed in this case is assumed to be equipped with rear-wheel-drive motor and non-driven front wheels, steering controlled by differential on front wheel speeds. It is also assumed that there is no sliding friction between the wheels and the ground during motion. As is shown in Figure 3(b), $p_{t} = [x_{t}, y_{t}, θ_{t}, v_{t}, ω_{t}]^{T}$ represents WMR’s coordinate $(x_{t}, y_{t})$ , heading angle $θ_{t}$ , linear velocity $v_{t}$ , and angular velocity $ω_{t}$ at the starting point, $θ_{d}$ represents the heading angle difference between $θ_{t}$ and the designated direction of WMR, and $Δ t$ is a single control period of DWA. It is assumed the ground is level, no slipping friction between wheels and the ground.

For each velocity, assuming that the WMR moves at this velocity for a sampling time $Δ t$ , a predicted trajectory is obtained. The motion model $p_{t + Δ t} = [x_{t + Δ t}, y_{t + Δ t}, θ_{t + Δ t},$ $v_{t + Δ t}, ω_{t + Δ t}]^{T}$ for WMR performing motion within $Δ t$ is:

p_{t + Δ t} = [\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} x_{t} \\ y_{t} \\ θ_{t} \\ v_{t} \\ ω_{t} \end{matrix}] [\begin{matrix} Δ t \cos θ_{t} & 0 \\ Δ t \sin θ_{t} & 0 \\ 0 & Δ t \\ 1 & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} v_{t + Δ t} \\ ω_{t + Δ t} \end{matrix}]

(14)

If the WMR’s wheelbase $L$ and wheel radius $r$ is already known, the relationship between WMR’s linear velocity $v$ and angular velocity $ω$ is as follows:

[\begin{matrix} v_{x} \\ v_{y} \end{matrix}] = \frac{r}{L} [\begin{matrix} L / 2 & L / 2 \\ - 1 & 1 \end{matrix}] [\begin{matrix} ω_{x} \\ ω_{y} \end{matrix}]

(15)

The energy loss when the motor does work on the external environment can be represented as:

E_{motor} (v, ω) = (1 - η_{robot}) P \frac{S_{P_{1} P_{2}}}{(v_{t} + v_{t + Δ t}) / 2}

(16)

where $η_{robot}$ represents motor efficiency, $P$ serves as power of motor, $S_{P_{1} P_{2}}$ is the distance of motion between nodes $P_{1}$ and $P_{2}$ , which can be accessed by the motor’s control unit, while $v_{t}$ , $v_{t + Δ t}$ are the linear velocity at nodes $P_{1}$ and $P_{2}$ , respectively.

The energy expended to overcome tire rolling resistance can be represented as:

E_{friction} = μ m_{robot} g S_{P_{1} P_{2}}

(17)

where $μ$ represents coefficient of rolling friction, $m_{robot}$ serves as WMR’s weight and $g$ is gravitational acceleration.

The energy consumption during speed change and during turning can be represented as:

E_{kinetic} (v, ω) = \frac{1}{2} m_{robot} (| v_{P_{2}}^{2} - v_{P_{1}}^{2} |) + \frac{1}{2} I (| ω_{P_{2}}^{2} - ω_{P_{1}}^{2} |)

(18)

where $I$ represents moment of inertia, $ω$ serves as WMR’s angular velocity during turning.

Combine the energy evaluation equations (16)–(18), WMR’s total energy consumption during the movement process can be represented as:

ener (v, ω) = E_{motor} (v, ω) + E_{friction} + E_{kinetic} (v, ω)

(19)

Ultimately, energy consumption evaluation $ener (v, ω)$ can be incorporated into DWA’s evaluation equation $V_{cost}$ , which can be described as:

\begin{matrix} V_{cost} = σ (c_{1} \cdot heading (v, ω) + c_{2} \cdot dist (v, ω) + c_{3} \cdot vel (v, ω) \\ + c_{4} \cdot ener (v, ω)) \end{matrix}

(20)

By introducing the energy evaluation equation, energy consumption of WMR during the path planning process can be considered, thereby reducing the actual energy cost during operation. Besides, it makes the planned paths more flexible and efficient, allowing WMR to operate for a longer time under the same task requirements, thus enhancing system efficiency.

Enhance dynamic obstacle avoidance

As discussed above, DWA will select the velocity with the highest evaluation value as the control command for the next step. However, in DWA algorithm, collision detection is a critical part, especially in environments with dynamic obstacles, thus WMR needs to detect and avoid collisions in real-time to ensure safe traveling.

Traditional DWA may encounter situations when dealing with dynamic obstacles where there is a risk of collision due to a failure to timely obtain obstacle information or the need for parallel motion to avoid dynamic obstacles. To address this, sensors are required to detect obstacles and continuously update their positions, as shown in Figure 4. Thus introduce a dynamic obstacle avoidance evaluation sub-function.

Figure 4.

Procedure of WMR assessing and avoiding moving obstacles during motion.

By comparing the current position $P_{obs 1}$ with the previous position $P_{obs 0}$ , it is easy to identify if there is a difference in positions to address dynamic obstacles. Then use the following equation to determine the distance traveled $S_{obs}$ and the heading angle $θ_{obs}$ of the dynamic obstacles within sample time period $Δ t$ and predict their positions at time $(t + Δ t)$ , as shown in equations (21) and (22).

S_{obs} = \sqrt{{(x_{obs 0 + Δ t} - x_{obs 0})}^{2} + {(y_{obs 0 + Δ t} - y_{obs 0})}^{2}}

(21)

θ_{obs} = \arctan \frac{y_{obs 0 + Δ t} - y_{obs 0}}{x_{obs 0 + Δ t} - x_{obs 0}}

(22)

where $(x_{obs}, y_{obs})$ stand for coordinates of the obstacle.

At the same time, the evaluation sub-function will evaluate if there is a collision risk or parallel motion between the optimal planning position at each time step and the predicted position of the obstacle. According to equation (14), it can be described as:

{\begin{matrix} x_{obs 0 + n Δ t} = x_{obs 0} + n S_{obs} \cos θ_{obs}, n = 2, 3, . . . \\ y_{obs 0 + n Δ t} = y_{obs 0} + n S_{obs} \sin θ_{obs}, n = 2, 3, . . . \end{matrix}

(23)

where $n$ represents the number of sampling intervals $Δ t$ that have elapsed.

Next, the dynamic obstacle avoidance evaluation sub-function $S_{d}$ can be defined as:

{\begin{matrix} S_{d} = \max (0, 1 - \frac{d - d_{safe}}{d_{safe}}) \\ d = \sqrt{{(x_{t} - x_{obs 0 + n Δ t})}^{2} + {(y_{t} - y_{obs 0 + n Δ t})}^{2}}, n = 2, 3 ? - \\ d_{safe} = d_{\min} + L / 2 \end{matrix}

(24)

where $d$ is a more accurate prediction of the distance between the robot and the obstacles, and $d_{safe}$ is the overall safety distance, which combines safety distance $d_{\min}$ and half of robot wheelbase $L / 2$ .

When the distance $d$ between robot and obstacle is less than $d_{safe}$ , the evaluation score decreases. When there will be a collision, the velocity corresponding to the trajectory will be marked as $S_{d} = 0$ , which means WMR is required to maintain a certain distance away from the obstacle. In this way, the velocity with a collision risk will be automatically excluded when selecting the optimal velocity. Thus enhance the ability of mobile robots to avoid moving obstacles.

The proposed sub-function is fundamentally reliant on sensor data for accurate obstacle detection and position estimation. While this approach is effective, it does pose certain challenges, particularly related to sensor noise and limited sensing range. Sensor noise can lead to inaccuracies in detecting obstacles, which might result in suboptimal path planning decisions. In addition, the limited sensing range of sensors could restrict the robot’s ability to detect and respond to obstacles in a timely manner.

To mitigate these challenges, filtering techniques can be incorporated, such as Kalman filters, to smooth sensor data and reduce the impact of noise. It is also suggested to consider the integration of multiple sensors to enhance the overall sensing range, thereby improving obstacle detection robustness. Furthermore, there is a potential of using machine-learning algorithms, which can predict the trajectories of dynamic obstacles based on past movement patterns, offering a more proactive approach to obstacle avoidance. While these enhancements come with their own trade-offs, such as increased computational complexity, they provide a promising direction for overcoming the inherent limitations of sensor-based obstacle detection.

Simulation analysis

The experimental environment is MATLAB R2021a, based on Windows10 22H2 64-bit, with a six-core Intel Core i5-12400F with a clock frequency of 4.0 GHz, with 32 GB of memory. The overall path planning algorithm can be summarized as Figure 5. Initial parameters for the algorithm are set as shown in Table 1.

Figure 5.

Algorithm overall structure.

Table 1.

Initial parameters of ACO and DWA.

Parameters	Meaning	Value
$m$	Number of ants	50
$N_{\max}$	Maximum iteration count	100
$N_{\min}$	Threshold for iteration count	10
$α$	Pheromone importance factor	1.05
$β$	Heuristic importance factor	7
$ρ$	Phero. evaporation coefficient	0.1
$Q$	Phero. increase coefficient	1
$τ_{\min}$	Lower limit of phero. concentration	0.1
$τ_{\max}$	Upper limit of phero. concentration	0.9
$ζ$	Control parameter for searching	0.1
$φ_{\max}$	Path duplicate counter	5
$m_{robot}$	Mass of robot	$35$ kg
$μ$	Rolling friction coefficient	0.02
$η_{motor}$	Motor efficiency	0.95
${\overset{\cdot}{v}}_{\max}$	Maximum linear acceleration	$1 m / s^{2}$
${\overset{\cdot}{ω}}_{\max}$	Maximum angular acceleration	$1 rad / s^{2}$
$v$	Linear velocity	$[0, 0.5] m / s$
$ω$	Angular velocity	$[- 1, 1] rad / s$
$L$	Wheelbase of robot	$0.5$ m
$d_{\min}$	Safety distance	$0.3$ m
$Δ t$	Resolution of time	$0.1$ s
$c_{1}$	Heading angle weight factor	0.1
$c_{2}$	Obstacle distance weight factor	0.4
$c_{3}$	Velocity weight factor	0.2
$c_{4}$	Energy cost weight factor	0.2

Modified ACO improvements verification

To validate the effectiveness of the proposed algorithm, a static grid map resembling a warehouse environment is created, selecting the starting and target point to perform global path planning. Comparison results are illustrated in Figure 6(a) and Table 2.

Figure 6.

ACO planned path comparison: (a) path smoothing, (b) deadlock avoidance under trap map scenario and (c) comparison of convergence speed.

Table 2.

Path length and turning angle of Figure 6(a).

Algorithm	Path length (m)	Robot turning angle(rad)
Traditional ACO	42.21	36.13
Triple line segment	36.79	11.76
Floyd	35.91	9.28

First, comparing to traditional ACO, route processed by triple line segment reduces the path length by 12.84%, reduces turning angle by 67.45%. Furthermore, route processed by Floyd path smoothing further reduces the path length by 2.39%, reduces turning angle by 21.09%.

Second, a trap map is set to validate the algorithm’s deadlock resistance. As shown in Figure 6(b), “S” is the starting node and “T” is the target node. The algorithm combined with a path duplicate counter which limited the number of path repetitions $φ \leq 5$ , is able to effectively enhance the global tendency of path searching.

Meanwhile, the average convergence speed of the algorithm is calculated, as shown in Figure 6(c). In the map shown in Figure 6(a), traditional ACO takes 72 iterations for the algorithm to converge to minimum path length, while improved ACO proposed by Shao et al. (2021) takes 23 iterations. In contrast, algorithm proposed in this paper takes 11 iterations to generate the shortest path without falling into local optima, reducing convergence speed up to 52.17%. Studies have introduced hybrid algorithms combining ACO with other techniques like PSO or Dijkstra’s algorithm to improve performance. However, these approaches often increase computational complexity and may still struggle with real-time obstacle avoidance in highly dynamic scenarios. In contrast, method proposed in this paper not only simplifies the computational process by integrating DWA at the local planning level but also enhances real-time performance. This dual-layer approach provides a more balanced solution, offering both global path optimality and local adaptability.

Modified DWA improvements verification

Initial parameters for the algorithm are set as shown in Table 1. First, under static scene M1 and M2 shown in Figure 7(a), with the introduction of dynamic initial heading angle, WMR moving in the early stages occupy smaller movement spaces and have stronger navigation abilities in narrow environments. Besides, by combining energy cost evaluation equation $ener (v, ω)$ into evaluation equation $V_{cost}$ , the amount of energy consumed during movement is also lower.

Figure 7.

DWA planned path comparison: (a) static scene M1 and M2, (b) Vertical crossing scene S1 and (c) approaching scene S2.

As shown in Figure 7(a) and Table 3, in simple static map M1, the overall path length has been shortened by 9.77%, costing 9.54% less time and 9.05% less energy consumption. In the rather complicated static map M2, the overall path length has been shortened by 1.38%, costing 5.19% less time, and 4.22% less energy consumption. Improved DWA proposed in this paper shows better performance in path tracking and energy consumption.

Table 3.

Path length, time and energy cost.

Map	Algorithm	Length(m)	Time(s)	Energy(J)
M1	Traditional DWA	28.76	58.93	2867.6
	Improved DWA	25.95	53.31	2608.1
M2	Traditional DWA	66.43	142.33	7968.5
	Improved DWA	65.51	134.94	7632.1

Second, under dynamic conditions, scenarios S1 and S2 are designed to verify the performance of WMR to avoid moving obstacles. As shown in Figure 7(b), scene S1 $vertical crossing$ simulates the scenario where the robot’s forward path intersects vertically with the path of obstacle in a warehousing-like environment. The obstacle is shown as yellow-colored box which is crossing the intersection in the middle. Besides, an unknown static obstacle is set in the way of WMR’s route, which is not considered by ACO, is represented with a gray-colored box down below the intersection.

Conclusion can be drawn from Figure 7(b) that DWA introduced with dynamic obstacle avoidance evaluation sub-function $S_{d}$ performs better in terms of passing through obstacle paths. Orientation angle during WMR’s motion is shown in Figure 7(b). Due to successful prediction of the future trajectory of the moving obstacle, the turning process of DWA with $S_{d}$ is smoother.

Last, scene S2 $approaching$ is designed as shown in Figure 7(c). It simulates the scenario that the obstacle approaching the robot rapidly from the front. Under the situation, DWA with $S_{d}$ is able to avoid quickly approaching obstacles, while traditional DWA makes WMR too close to obstacle. Besides, as shown in Figure 7(c), improved DWA can make the turning process smoother, a same situation as in scene S1. By addressing the specific weaknesses of these existing methods, such as slow convergence in ACO, high computational complexity in hybrid approaches, and limited adaptability in DWA, this paper demonstrated through simulations that the proposed method achieves better performance in terms of path quality, computational efficiency, and adaptability to dynamic environments. The results show that the approach offers a more comprehensive and effective solution for path planning for WMRs.

Conclusion

In this paper, a two-layer WMR path planning method is proposed, by combining improved ACO and optimized DWA algorithms at the global level and the local level, respectively. The framework aims to enhance the efficiency and effectiveness of path planning for WMRs in dynamic environments, thus overcome drawbacks and achieve efficient and robust path planning. Above all, the global path planning procedure can avoid deadlocks in trap map, increase globality of the search and accelerate the convergence speed. Meanwhile, the proposed local path planner can reduce WMR’s control space, and the design of energy evaluation equation allows WMR to tend to find a energy-saving route. Besides, introducing the dynamic obstacle avoidance evaluation sub-function will enhance WMR’s performance in dynamic scenes. Further work will focus on adaptability of the algorithm to different types of WMRs and their specific constraints, and scalability of the proposed method to handle larger and more complex environments. Meanwhile, verification of the proposed algorithm will be performed in real world, thus assess its practical applicability and performance.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Key R&D Program of China (grant no. 2023YFB4706800), the National Natural Science Foundation of China (grant nos. 52372378 and U2013601), and the State Key Laboratory of High-Performance Precision Manufacturing (grant no. ZY202414).

ORCID iD

Ming Yue

References

Ahmmed

Rana

MAA

Haque

AAMM

, et al. (2008) A multiple ant colony system for dynamic vehicle routing problem with time window. In: 2008 third international conference on convergence and hybrid information technology, Busan, Korea, 11–13 November, pp. 182–187. New York: IEEE.

Amar

Jasim

(2021) Hybrid metaheuristic approach for robot path planning in dynamic environment. Bulletin of Electrical Engineering and Informatics 10(4): 2152–2162.

Blum

(2005) Ant colony optimization: Introduction and recent trends. Physics of Life Reviews 2(4): 353–373.

Castillo

Neyoy

Soria

, et al. (2015) A new approach for dynamic fuzzy logic parameter tuning in ant colony optimization and its application in fuzzy control of a mobile robot. Applied Soft Computing 28: 150–159.

Chang

Shan

Jiang

, et al. (2021) Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment. Autonomous Robots 45: 51–76.

Che

Chen

(2023) Tourism planning path based on ant colony optimization algorithm. In: 2023 5th international conference on communications, information system and computer engineering (CISCE), Guangzhou, China, 14–16 April, pp. 363–366. New York: IEEE.

Deng

Zhao

, et al. (2021) Multi-obstacle path planning and optimization for mobile robot. Expert Systems with Applications 183: 115445.

Dorigo

Maniezzo

Colorni

(1996) Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 26(1): 29–41.

Dorigo

Stützle

(2019) Ant colony optimization: Overview and recent advances. Cham: Springer.

10.

Dosad

(2023) Mobile robot path planning based on hybrid ant colony optimization. Journal of Intelligent and Fuzzy Systems 45: 2611–2623.

11.

Fareh

Baziyad

Rahman

, et al. (2020) Investigating reduced path planning strategy for differential wheeled mobile robot. Robotica 38(2): 235–255.

12.

Fox

Burgard

Thrun

(1997) The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine 4(1): 23–33.

13.

Gasparetto

Boscariol

Lanzutti

, et al. (2015) Path planning and trajectory planning algorithms: A general overview. In: Carbone

Gomez-Bravo

(eds) Motion and Operation Planning of Robotic Systems: Background and Practical Approaches. Cham: Springer, pp. 3–27.

14.

Gul

Mir

Alarabiat

, et al. (2022) Implementation of bio-inspired hybrid algorithm with mutation operator for robotic path planning. Journal of Parallel and Distributed Computing 169: 171–184.

15.

Hang

Yan

, et al. (2023) Research on local path planning of intelligent vehicle based on improved dynamic window approach. In: Third international conference on artificial intelligence and computer engineering (ICAICE 2022), Dalian, China, 11–13 November 2022, pp. 1326–1334. SPIE.

16.

Hou

Xiong

Wang

, et al. (2022) Enhanced ant colony algorithm with communication mechanism for mobile robot path planning. Robotics and Autonomous Systems 148: 103949.

17.

Jin

Yue

, et al. (2022) An improved target-oriented path planning algorithm for wheeled mobile robots. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 236(22): 11081–11093.

18.

Karur

Sharma

Dharmatti

, et al. (2021) A survey of path planning algorithms for mobile robots. Vehicles 3(3): 448–468.

19.

Cui

Yan

, et al. (2019) Long-term adaptive informative path planning for scalar field monitoring using cross-entropy optimization. Science China Information Sciences 62: 1–3.

20.

Zhao

Chen

, et al. (2023) A robot path planning method based on improved genetic algorithm and improved dynamic window approach. Sustainability 15(5): 4656.

21.

Lin

Yue

Chen

, et al. (2022) Path planning of mobile robot with PSO-based APF and fuzzy-based DWA subject to moving obstacles. Transactions of the Institute of Measurement and Control 44(1): 121–132.

22.

Madridano

Al-Kaff

Martín

, et al. (2021) Trajectory planning for multi-robot systems: Methods and applications. Expert Systems with Applications 173: 114660.

23.

Miao

Chen

Yan

, et al. (2021) Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering 156: 107230.

24.

Morin

Abi-Zeid

Quimper

(2023) Ant colony optimization for path planning in search and rescue operations. European Journal of Operational Research 305(1): 53–63.

25.

Sanchez-Ibanez

Perez-del Pulgar

García-Cerezo

(2021) Path planning for autonomous mobile robots: A review. Sensors 21(23): 7898.

26.

Shao

, et al. (2021) Mobile robot path planning based on improved ant colony fusion dynamic window approach. In: 2021 IEEE international conference on mechatronics and automation (ICMA), Takamatsu, Japan, 8–11 August, pp. 1100–1105. New York: IEEE.

27.

Wang

Cao

, et al. (2023a) Obstacle avoidance path planning of 7-DOF redundant manipulator based on improved ant colony optimization. Recent Patents on Mechanical Engineering 16(3): 177–187.

28.

Wang

, et al. (2023b) Monte Carlo-based improved ant colony optimization for path planning of welding robot. Journal of King Saud University-Computer and Information Sciences 35: 101603.

29.

Zhang

, et al. (2023) A local path planning algorithm based on improved dynamic window approach. Journal of Intelligent & Fuzzy Systems 45: 4917–4933.

30.

Yang

, et al. (2022) An effective dynamic path planning approach for mobile robots based on ant colony fusion dynamic windows. Machines 10(1): 50.

31.

Yang

Zhang

, et al. (2023) Mobile robot path planning based on improved particle swarm optimization and improved dynamic window approach. Journal of Robotics 2023: 1–16.

32.

Zhan

Guan

, et al. (2013) Tracking performance limitation of multi-channel networked systems. Control Theory and Applications 30(4): 503–507.

33.

Zhan

Jiang

, et al. (2015) Optimal performance of networked control systems under the packet dropouts and channel noise. ISA Transactions 58: 214–221.

34.

Zhang

Jin

Gao

, et al. (2021) A multi-goal global dynamic path planning method for indoor mobile robot. In: 2021 3rd international symposium on robotics & intelligent manufacturing technology (ISRIMT), Changzhou, China, 24–26 September, pp. 97–103. New York: IEEE.

35.

Zhang

Zhan

, et al. (2022) A new hybrid algorithm for path planning of mobile robot. The Journal of Supercomputing 78(3): 4158–4181.

36.

Zhou

Chen

, et al. (2023) RRT*-fuzzy dynamic window approach (RRT*-FDWA) for collision-free path planning. Applied Sciences 13(9): 5234.

37.

Zidi

Maouche

Hammadi

(2006) Ant colony with dynamic local search for the time scheduling of transport networks. International Journal of Computers Communications & Control 1(4): 110–125.