3.2.1. Distance condition

The first type of environmental information is the distance from the current search node to the goal point. A distance switching threshold $D_{\textit{switch}}$ is first defined as follows:

(6) \begin{equation} h(n)\leq D_{\textit{switch}} \end{equation}

By comparing the distance from node $n$ to the goal point $G$ with $D_{\textit{switch}}$ , HANSA* determines whether the search has entered the approach region. When Eq. (6) holds, the algorithm switches from the 16-neighborhood exploration mode to the 5-neighborhood search mode. This switching strategy reduces unnecessary neighbor evaluations near the goal and provides more refined local expansion in the final approximation stage. The threshold $D_{\textit{switch}}$ characterizes the approach range in the grid-based search process, and its value is determined through the parameter sensitivity analysis in Section 4.1.1.

It is worth noting that $D_{\textit{switch}}$ serves as a search parameter during the path planning phase, rather than a triggering condition for the path execution phase. This condition is evaluated for the current search node during the node expansion process and does not directly depend on the robot’s maximum physical velocity. Velocity constraints primarily influence trajectory tracking and motion control following the generation of the global path.

3.2.2. Density condition

The second type of environmental information is the local obstacle density around the current node. HANSA* introduces the local obstacle density metric $\rho (n)$ to evaluate the complexity of the surrounding environment and determine whether the search should switch from the 16-neighborhood exploration mode to the more conservative 5-neighborhood search mode.

To calculate the local obstacle density around the current node, a local density evaluation window is defined on the current occupancy grid map. This window should cover the main local area that may be involved in the current neighborhood expansion, thereby reflecting the obstacle distribution around the candidate nodes. In the 16-neighborhood exploration stage of HANSA*, the minimum complete local region covered around the current node is a 5 × 5 grid area. If a 3 × 3 window is used, it can only cover the one-layer search range of the conventional 8-neighborhood and cannot sufficiently reflect the obstacle distribution around candidate nodes in the 16-neighborhood. If a larger window is used, obstacle information outside the current expansion range would be included, causing the local density estimate to be affected by more distant obstacles. This would weaken its relevance to the current neighborhood-switching decision and introduce additional computational cost. Therefore, HANSA* adopts a 5 × 5 window as the local density evaluation window. It should be noted that this 5 × 5 window is not intended to represent the full sensing range of the LiDAR. Instead, it evaluates the local obstacle distribution relevant to the current neighborhood expansion based on the obstacle information available in the current occupancy grid map. When the sensor detection range is longer, more distant obstacles can be observed and updated in the map earlier. When the sensor detection range is shorter or when obstacles appear suddenly, the corresponding obstacle information is included in the statistics of $N_{obs}$ within the local window only after it has been observed by the sensor and updated in the occupancy grid map.

Accordingly, the obtained $\rho (n)$ describes the updated local obstacle distribution in the current occupancy grid map, rather than the distribution of all potential obstacles within the full sensing range of the sensor. Let $N_{obs}$ denote the number of obstacle cells within the 5 × 5 local density evaluation window centered at the current node $n$ , and let $N_{\textit{total}}=25$ denote the total number of cells in this window. The local obstacle density is defined as follows:

(7) \begin{equation} \rho (n)=\frac{N_{obs}}{N_{\textit{total}}} \end{equation}

Where $\rho (n)\in [0,1]$ . A larger value of $\rho (n)$ indicates a denser obstacle distribution around the current node and a more complex local environment. HANSA* compares $\rho (n)$ with the density threshold $\rho _{\textit{dense}}$ . When $\rho (n)\gt \rho _{\textit{dense}}$ , the area around the current node is considered relatively cluttered, and the algorithm switches to the 5-neighborhood search mode to improve planning safety and accuracy. Otherwise, the algorithm continues to use the 16-neighborhood search mode to maintain efficient planning. In this article, $\rho _{\textit{dense}}$ is used as the local density switching threshold, and its value is determined through parameter sensitivity analysis.

3.3.1. Exploration phase

The 16–neighborhood doubles the number of expanded neighbors compared to the 8–neighborhood, increasing computational overhead. To improve search efficiency, HANSA* uses the following dynamic hybrid heuristic. For a current node $n$ and the goal node $G$ , let their coordinates be $(x_{n},y_{n})$ and $(x_{G},y_{G})$ , respectively. Define the Euclidean distance between them as $P_{1}$ and the octile distance as $P_{2}$ :

(8) \begin{align} P_{1}&=\sqrt{\left(x_{n}-x_{G}\right)^{2}+\left(y_{n}-y_{G}\right)^{2}} \end{align}

(9) \begin{align} P_{2}&=\max\!\left(\left| x_{n}-x_{G}\right| ,\left| y_{n}-y_{G}\right| \right)+\big(\sqrt{2}-1\big)\cdot \min\left(\left| x_{n}-x_{G}\right| ,\left| y_{n}-y_{G}\right| \right) \end{align}

Let $d_{1}$ be the Euclidean distance from the current node n to the goal, and let $d_{2}$ be the Euclidean distance from the start node to the goal. The normalized search progress $\gamma \in \left(0\right.,\left.1\right]$ is given by:

(10) \begin{align} \gamma =\begin{cases} \dfrac{d_{1}}{d_{2}} & \mathrm{if}\,d_{1}\lt d_{2}\\ 1 & \text{otherwise} \end{cases} \end{align}

With these components, the dynamic hybrid heuristic function $h_{1}(n)$ blends $P_{1}$ and $P_{2}$ using the weight $\gamma$ , and the total cost $f(n)$ remains the sum of the actual cost $g(n)$ and the heuristic:

(11) \begin{align} h_{1}(n)&=(1-\gamma )\cdot P_{1}+\gamma \cdot P_{2} \\[-8pt]\nonumber\end{align}

(12) \begin{align} f(n)&=g(n)+h_{1}(n) \end{align}

When the current node $n$ is far from the goal, $d_{1}\approx d_{2}$ and thus $\gamma \approx 1$ ; the heuristic relies mainly on the octile distance $P_{2}$ , which promotes fast exploration in open areas. As the search approaches the goal, $d_{1}$ decreases, causing $\gamma$ to gradually approach 0. The heuristic then converges to the Euclidean distance $P_{1}$ . This dynamic transformation mechanism enhances the greedy behavior of HANSA*, enabling it to converge faster in open regions. The novel dynamic hybrid heuristic is designed to complement the 16-neighborhood search, improving both path quality and computational efficiency.

3.3.2. Approach phase

When the search enters the approach phase, HANSA* switches to a 5-neighborhood and scales the heuristic with a dynamic weighting factor $q(n)$ to balance computational efficiency and planning accuracy. This factor maintains the goal-directed nature of the search while improving planning accuracy and search efficiency.

In this phase, HANSA* continues to use $\gamma$ to represent the search progress, which describes the relative distance between the current node and the target point. The variable $\rho (n)$ denotes the local obstacle density around the current node $n$ . In addition, $\mu$ represents the relative angle between the candidate expansion direction and the target direction. When $\mu =0$ , the expansion direction is aligned with the target direction; as $\mu$ increases, the candidate direction deviates further from the target direction. Therefore, the dynamic weighting factor and the heuristic function in the approach phase are defined as follows:

(13) \begin{align} q(n)&=1+\rho (n)\cdot \gamma \cdot \left(\frac{1-\cos(\mu )}{2}\right) \end{align}

(14) \begin{align} h_{2}(n)&=q(n)\cdot P_{1} \\[-8pt]\nonumber\end{align}

(15) \begin{align}f(n)&=g(n)+h_{2}(n) \end{align}

Here, $1-\cos \mu$ is used to describe the deviation of the candidate expansion direction from the target direction. If $\cos \mu$ is used directly, negative values may be introduced. Moreover, $\cos \mu$ reaches its maximum value when the candidate expansion direction is aligned with the target direction. Since a larger $q(n)$ indicates a higher heuristic cost, directly using $\cos \mu$ would increase the cost of expanding toward the target direction. Therefore, $1-\cos \mu$ is adopted to convert directional consistency into directional deviation, and the term is further divided by 2 to normalize the directional deviation to the range [0,1].

The multiplicative structure of $q(n)$ combines three normalized factors, corresponding to search progress, local obstacle density, and directional deviation, respectively. This design forms a hybrid heuristic adjustment mechanism. Only when the current node still requires strong goal guidance, the local obstacle density is high, and the candidate expansion direction deviates significantly from the target direction, does the product of the three factors increase noticeably, thereby strengthening the penalty for unfavorable expansion directions. Conversely, when the local environment is relatively open, the candidate expansion direction is close to the target direction, or the current node is already near the target region, a small value in any factor suppresses the increase in the weighting factor and prevents the heuristic function from being excessively amplified by a single condition. Compared with an additive structure, the multiplicative structure prevents any individual factor from directly dominating the change in the weighting factor. As a result, heuristic enhancement occurs only when multiple unfavorable conditions appear simultaneously, making it more suitable for the approach phase.

Since all three factors are normalized to the range [0,1], $q(n)$ is bounded within [Reference Qin, Shao, Wang, Yu, Jiang and Cao1,Reference Orozco-Rosas, Montiel-Ross and Movilla-Terriza2]. This indicates that the adjustment of the heuristic function by $q(n)$ is bounded. Combined with the 5-neighborhood search mode, this bounded dynamic weighting strategy enhances the local guidance capability of HANSA* in the approach phase and helps generate safer and more refined paths in obstacle-dense regions. It should be noted that $q(n)$ is designed as a bounded heuristic adjustment factor for improving practical search guidance, rather than as a strict optimality-preserving or formally convergence-proven weighting scheme.

3.5.1. Space complexity

Space complexity refers to the amount of memory required by an algorithm during execution. In terms of asymptotic space complexity, all four algorithms mentioned above share the same worst-case theoretical upper bound. They need to maintain open and closed sets, and their space consumption is linearly related to the total number of traversable grid cells $N$ in the environment, resulting in a space complexity of $O(N)$ . Dynamically Weighted A* changes the weights of the heuristic function but does not change the asymptotic space complexity. JPS effectively reduces the required memory through rule pruning during planning, also resulting in a space complexity of $O(N)$ . In the HANSA* algorithm, a hierarchical adaptive mechanism is introduced, allowing nodes to have different neighborhood state identifiers at different search stages. However, this only adds a constant-level memory overhead of $O(1)$ for each node’s flag bits. Consequently, the space complexity of HANSA* remains strictly $O(N)$ , consistent with the other three algorithms, confirming that it uses memory efficiently in the planning task without causing additional asymptotic memory burden.

3.5.2. Time complexity

All four algorithms use priority queues to implement their open sets. In A*, the node with the lowest cost is repeatedly extracted from the open set, its neighbors are evaluated, and newly generated nodes are inserted back into the queue. The time complexity of each of these steps is $O(\log N)$ , where N is the total number of valid grid cells in the state space. The heuristic cost calculation for neighboring nodes typically requires constant time $O(1)$ , therefore, the time complexity for a single node expansion is $O(\!\log N)$ . In the worst case, where the algorithm needs to traverse all unobstructed grid cells, after N expansions, the overall time complexity of A* is:

(16) \begin{equation} T_{A\ast }=O(\!\log N)\times N=O({N\log N}) \end{equation}

The Dynamically Weighted A* modifies the weights of the heuristic function. When expanding nodes, Dynamically Weighted A* needs to calculate the dynamic weight coefficients in real-time and multiply them by the heuristic cost, maintaining a time complexity of $O(\log N)$ . The additional weight calculation step involves only local arithmetic operations, requiring $O(1)$ time. Therefore, the total time complexity of Dynamically Weighted A* is:

(17) \begin{equation} T_{DW-A^{\ast} }=N\times \left(O(\log N)+O(1)\right)=O({N\log N}) \end{equation}

The JPS significantly reduces the number of expansions required to connect the start and end points through pruning. However, JPS may need to traverse a large number of nodes in complex maps, which does not change the worst-case asymptotic time complexity. Its worst-case time complexity remains $O(N\log N)$ .

During the search process, HANSA* switches between the 16-neighborhood and 5-neighborhood expansion modes according to the distance condition and the local density condition. Since different node expansions involve different numbers of neighboring candidates, the numbers of nodes expanded using the 16-neighborhood and 5-neighborhood modes are denoted as $N_{16}$ and $N_{5}$ , respectively. The total number of neighbor evaluations during the search process can then be expressed as $B=16N_{16}+5N_{5}$ , where $B$ denotes the total number of neighbor evaluations in the entire search process. For each node expansion, extracting the current minimum-cost node from the priority queue requires $O(\!\log N)$ time. For each evaluated neighbor, cost updating, heuristic computation, and insertion or update operations in the Open list require at most $O(\!\log N)$ time. Therefore, the time complexity of the search expansion stage of HANSA* can be expressed as $T_{\textit{search}}=O(B\log N)$ . Since the total number of expanded nodes during the search process does not exceed the total number of nodes $N$ in the grid map, we have $N_{16}+N_{5} \lt N$ . Furthermore, $B=16N_{16}+5N_{5}\lt 16(N_{16}+N_{5}) \lt 16N$ . Accordingly, in the worst case, the asymptotic time complexity of the search expansion stage of HANSA* remains $T_{\textit{search}}=O(N\log N)$ . When more nodes are expanded using the 5-neighborhood mode, the effective branching factor of HANSA* is reduced compared with a fixed 16-neighborhood expansion strategy, thereby decreasing the actual number of neighbor evaluations. In addition, HANSA* includes a two-stage path optimization process. Let $L$ denote the total number of grid cells traversed during all line-of-sight checks, and let $P$ denote the number of path points processed during B-spline smoothing. The time complexity of the path optimization stage can be expressed as $T_{opt}=O(L)+O(P)$ . The overall time complexity of HANSA* can be expressed as:

(19) \begin{equation} T_{\textit{HANSA}^{\ast} }=O(B\log N)+O(L)+O(P) \end{equation}

Here, $O(Blog\, N)$ represents the computational cost of the search expansion stage, $O(L)$ represents the cumulative cost of line-of-sight checks, and $O(P)$ represents the computational cost of B-spline smoothing.

3.5.3. Performance discussion and trade-offs

As will be demonstrated in Section 4.2, aggressive algorithms such as JPS or Weighted A* may require fewer expansion nodes and have slightly shorter runtimes than HANSA*. JPS prunes large portions of the search space, while Weighted A* relies on a highly greedy heuristic. However, the paths they generate are often not optimal, frequently contain hazardous sharp corners, and have inadequate obstacle clearance. In contrast, HANSA* employs adaptive mechanisms to improve overall path quality. While the 16-neighborhood evaluation and two-stage optimization add some computational overhead, they effectively reduce redundant waypoints and sharp corners. For an omnidirectional robot, avoiding a sharp corner reduces unnecessary deceleration and improves chassis stability. Ultimately, HANSA* achieves both higher path quality and shorter path length at the cost of only a marginal increase in runtime.

4.1.1. Distance threshold analysis

The distance switching threshold $D_{\textit{switch}}$ determines when HANSA* enters the approach phase and switches to the 5-neighborhood search mode. Since maps with different sizes have different search distance scales, $D_{\textit{switch}}$ is evaluated as a percentage of the map dimension in this sensitivity analysis. To analyze the influence of this parameter on planning performance, the threshold ratio was varied from 10% to 30% on 30 × 30, 60 × 60, 100 × 100 maps, while the density threshold was fixed at $\rho _{\textit{dense}}=0.3$ . Each parameter setting was repeated 100 times, and the average planning time and expanded nodes were used as the main evaluation metrics.

Figure 6(a)–(c) show the sensitivity analysis results under the three map sizes. As the distance switching threshold ratio increases from 10% to 20%, both the average planning time and the number of expanded nodes decrease. When the threshold ratio further increases from 20% to 30%, these two metrics increase again. This trend is consistent across the 30 × 30, 60 × 60, 100 × 100 maps. Among the tested settings, the 20% threshold ratio achieves the lowest average planning time and the fewest expanded nodes in all three maps.

Figure 6.

Parameter sensitivity analysis of the distance switching threshold $\mathrm{D}_{\text{switch}}$ under different map sizes: (a) $30 \times 30$ map; (b) $60 \times 60$ map; (c) $100 \times 100$ map.

Figure 6. Long description

Three line graphs depict the parameter sensitivity analysis of the distance switching threshold under different map sizes. Panel A: A line graph shows the relationship between the distance switching threshold ratio and the average planning time and expanded nodes for map size 1. The x-axis represents the distance switching threshold ratio ranging from 0.10 to 0.30. The left y-axis represents the average planning time in seconds, and the right y-axis represents the expanded nodes. The blue line with square markers indicates the average planning time, while the red dashed line with circle markers indicates the expanded nodes. The graph shows a U-shaped trend for both metrics, with the lowest values around a threshold ratio of 0.20. Panel B: A line graph shows the relationship between the distance switching threshold ratio and the average planning time and expanded nodes for map size 2. The x-axis represents the distance switching threshold ratio ranging from 0.10 to 0.30. The left y-axis represents the average planning time in seconds, and the right y-axis represents the expanded nodes. The blue line with square markers indicates the average planning time, while the red dashed line with circle markers indicates the expanded nodes. The graph shows a U-shaped trend for both metrics, with the lowest values around a threshold ratio of 0.20. Panel C: A line graph shows the relationship between the distance switching threshold ratio and the average planning time and expanded nodes for map size 3. The x-axis represents the distance switching threshold ratio ranging from 0.10 to 0.30. The left y-axis represents the average planning time in seconds, and the right y-axis represents the expanded nodes. The blue line with square markers indicates the average planning time, while the red dashed line with circle markers indicates the expanded nodes. The graph shows a U-shaped trend for both metrics, with the lowest values around a threshold ratio of 0.20.

This result can be explained by the role of $D_{\textit{switch}}$ in controlling the transition to the approach phase. When the threshold ratio is too small, HANSA* enters the approach phase too late, and the 16-neighborhood exploration mode is retained for a longer distance near the goal. This increases redundant neighbor evaluations and leads to more expanded nodes. In contrast, when the threshold ratio is too large, the algorithm switches to the 5-neighborhood search mode too early. Although this reduces the local branching factor, it also restricts the expansion directions prematurely and may reduce the flexibility of the search. Therefore, a threshold ratio of 20% provides a suitable balance between global exploration and local refinement. Based on this analysis, $D_{\textit{switch}}$ is set to 20% of the map dimension in the following experiments.

4.1.2. Density threshold sensitivity analysis

Grid resolution affects the statistics of obstacle cells within the local evaluation window, while map size changes the overall search scale and the obstacle distribution encountered by the planner. Based on these two aspects, this section conducts a parameter sensitivity analysis of the local density switching threshold $\rho _{\textit{dense}}$ . Maps with different sizes are first used to evaluate the performance of $\rho _{\textit{dense}}$ under different search scales. Then, the same 100 m × 100 m physical environment is discretized into grid maps with different resolutions to analyze the stability of $\rho _{\textit{dense}}$ under different map resolutions.

When $\rho _{\textit{dense}}$ is set to 0.3, HANSA* can switch to the 5-neighborhood search in relatively dense regions while retaining the 16-neighborhood search in open regions. As shown in Figure 7, this threshold results in a path length and planning time of 91.158 m and 14.81 ms in the 60 × 60 map and 140.391 m and 15.9 ms in the 100 × 100 map, respectively. These results indicate that $\rho _{\textit{dense}}=0.3$ performs well in both planning time and path length under the tested map settings. When $\rho _{\textit{dense}}\geq 0.4$ , the condition for switching to the 5-neighborhood becomes harder to satisfy. As a result, some relatively dense regions may still be expanded using the 16-neighborhood search, which can increase ineffective node expansion and lead to longer paths, as observed in the 30 × 30 and 100 × 100 maps. When $\rho _{\textit{dense}}\leq 0.2$ , HANSA* tends to switch to the 5-neighborhood too early. Although this makes the search more conservative, the reduced expansion directions may increase both the path length and the number of expanded nodes.

Figure 7.

Parameter sensitivity analysis of the obstacle density threshold ( ${\unicode[Arial]{x03C1}} _{\text{dense}}$ ) in a complex cluttered environment: (a) $30 \times 30$ map; (b) $60 \times 60$ map; (c) $100 \times 100$ map.

Figure 8(a)–(c) present the results of the sensitivity analysis for $\rho _{\textit{dense}}$ across different grid resolutions. In this study, a single 100 m × 100 m physical environment was discretized into grid maps with resolutions of 0.5 m, 1.0 m, and 2.0 m, respectively. The results indicate that, across all three resolutions, a value of $\rho _{\textit{dense}}=0.3$ consistently demonstrated stable performance with respect to both planning time and path length. At a resolution of 0.5m, the number of grid cells in the map increased significantly, thereby expanding the search space and correspondingly increasing the planning time; however, the geometric form of the path could be represented with greater fidelity. Conversely, at a resolution of 2.0 m, the search space was reduced and planning time was shortened; yet, this coarser grid representation potentially resulted in an increase in the actual physical path length. Taken together, $\rho _{\textit{dense}}=0.3$ exhibited superior overall performance across the grid resolutions tested in this study and was subsequently selected as the density switching threshold for the experiments that followed.

Figure 8.

Parameter sensitivity analysis of the obstacle density threshold ( ${\unicode[Arial]{x03C1}} _{\text{dense}}$ ) in a complex cluttered environment: (a) $0.5$ m; (b) $1.0$ m; (c) $2.0$ m.

Figure 8. Long description

Three line graphs depict the parameter sensitivity analysis of the obstacle density threshold in a complex cluttered environment. Panel A: A line graph shows the planning time and path distance for different obstacle density thresholds. The x-axis represents the obstacle density threshold, and the y-axes represent planning time in milliseconds and path distance in meters. The blue line indicates planning time, while the red line indicates path distance. Panel B: Another line graph displays similar data for a different obstacle density threshold. The axes and color scheme are the same as in Panel A. Panel C: The third line graph follows the same format, showing planning time and path distance for yet another obstacle density threshold. Each panel illustrates how planning time and path distance vary with changes in the obstacle density threshold.

4.6.1. Experiments in static environments

In the static real-world experiment, the occupancy grid map of the indoor environment was first constructed by the mobile robot using Gmapping. Based on the generated map, the same start point and target point were specified for all algorithms to compare their path planning performance. Figure 16 shows the mobile robot, the actual experimental environment, and the generated occupancy grid map.

Figure 17 presents the path planning results of different algorithms in the static real-world environment, and Table VII reports the corresponding comparison results. The evaluation metrics include Planning Time, Path Nodes, Corners, Min Angle, and Path Length.

Table VII.

Experimental results in real environment

Table VII Long description

A table comparing the performance of different algorithms in a static real-world environment based on various metrics. The table has 7 columns and 6 rows, including the header row. The columns are labeled as Metrics, Trad. A*, JPS, W-A*, DW-A*, Liao, Zhang, Huang, and HANSA*. The rows are labeled as Planning time (ms), Path nodes, Corners (≥45°), Min Angle (°), and Path length (m). Row 1: Planning time (ms), Trad. A*, 27.5; JPS, 28.2; W-A*, 26.3; DW-A*, 25.6; Liao, 26.7; Zhang, 25.4; Huang, 26.9; HANSA*, 25.8. Row 2: Path nodes, Trad. A*, 178; JPS, 48; W-A*, 73; DW-A*, 65; Liao, 188; Zhang, 197; Huang, 50; HANSA*, 18. Row 3: Corners (≥45°), Trad. A*, 20; JPS, 15; W-A*, 19; DW-A*, 33; Liao, 38; Zhang, 17; Huang, 5; HANSA*, 1. Row 4: Min Angle (°), Trad. A*, 45; JPS, 45; W-A*, 45; DW-A*, 45; Liao, 38; Zhang, 47; Huang, 12; HANSA*, 5. Row 5: Path length (m), Trad. A*, 9.737; JPS, 9.637; W-A*, 9.537; DW-A*, 9.544; Liao, 9.567; Zhang, 9.546; Huang, 9.242; HANSA*, 9.017.

Note: Trad. A* = Traditional A*; W-A* = Weighted A*; DW-A* = Dynamically Weighted A*. Liao, Zhang, and Huang refer to the methods proposed in Refs. [Reference Liao, Hu, Luo, Li and Qu18], [Reference Zhang, Wang and Zhou19], and [Reference Huang, Zhu and Wang20], respectively.

Figure 16.

Mobile Robot, actual experimental environment and occupancy grid map.

Figure 16. Long description

Panel A: A mobile robot equipped with sensors and cameras, positioned on a tiled floor. Panel B: An office environment with desks, chairs, and various obstacles scattered around. Panel C: An occupancy grid map representing the layout of the office environment, showing walls and obstacles as black areas and free space as white areas.

Figure 17.

Pathfinding results for various algorithms: (a) Traditional A*; (b) JPS; (c) Weighted A*; (d) Dynamically weighted A*; (e) Liao’s method; (f) Zhang’s method; (g) Huang’s method; (h) HANSA*.

Figure 17. Long description

Panel A: Traditional A* algorithm showing a path with multiple turns and some redundant node expansions. Panel B: JPS algorithm displaying a more streamlined path with fewer turns. Panel C: Weighted A* algorithm presenting a path with fewer turns and reduced redundancy. Panel D: Dynamically weighted A* algorithm showing a path with adaptive turns and reduced node expansions. Panel E: Liaos method illustrating a path with improved regularity and fewer unreasonable nodes. Panel F: Zhangs method depicting a path that avoids highly cluttered regions and reduces redundant expansions. Panel G: Huangs method showing a path with enhanced global search capability and reduced travel distance. Panel H: HANSA* algorithm displaying a path with improved overall navigation performance and adaptive search structure.

As shown in Table VII, HANSA* achieves the shortest path length of 9.017m and uses only 18 path nodes, fewer than all comparison algorithms. In terms of path smoothness, HANSA* produces only one sharp corner, while the other algorithms generate more sharp turns. These results indicate that HANSA* generates a higher-quality and smoother path. The reduction in path nodes and sharp corners further supports the effectiveness of the adaptive neighborhood switching mechanism. In the static indoor environment, HANSA* reduces redundant path points and sharp heading changes, making the generated path more suitable for execution on the mobile robot platform.

Overall, the results show that HANSA* generates a shorter and smoother path in the tested static real-world environment, with fewer path nodes and fewer sharp turns, indicating better execution-oriented path quality for the mobile robot platform.

4.6.2. Real-world replanning with unknown obstacles

We utilized SLAM to construct a static map encompassing both complex indoor environments and long, narrow corridors. During the navigation task, unknown obstacles were introduced in selected regions along the planned route to create local map changes in the real-world environment. After the obstacle information was detected and updated in the occupancy grid map, HANSA* replanned the remaining path based on the updated map. This experiment evaluates how HANSA* adapts its replanning strategy when newly detected obstacles cause local changes in the occupancy grid map. The experimental results are presented in Table VIII and Figure 18. Figure 18(a) shows the narrow corridor environment, while the complex indoor environment is similar to the static real-world environment shown in Figure 16. Figure 18(b) and (c) show the regions with unknown obstacles, and Figure 18(d) presents the replanned path after the unknown obstacles are introduced.

Table VIII.

Experimental results in an unknown environment

Table VIII Long description

A table comparing metrics for different navigation strategies. The table has five rows and six columns. The columns are labeled Trad. A*, JPS, W-A*, DW-A*, Huang, and HANSA*. The rows are labeled Replanning time (ms), Path nodes, Corners (≥45°), and Path length (m). The values in the table are as follows: Row 1: Trad. A*, 88.3; JPS, 114.2; W-A*, 35.7; DW-A*, 20.2; Huang, 57.9; HANSA*, 51.8. Row 2: Trad. A*, 455; JPS, 72; W-A*, 246; DW-A*, 182; Huang, 466; HANSA*, 315. Row 3: Trad. A*, 36; JPS, 33; W-A*, 153; DW-A*, 167; Huang, 25; HANSA*, 0. Row 4: Trad. A*, 57.982; JPS, 68.911; W-A*, 50.015; DW-A*, 51.904; Huang, 46.628; HANSA*, 42.243.

Note: Trad. A* = Traditional A*; W-A* = Weighted A*; DW-A* = Dynamically Weighted A*; Huang refers to the methods proposed in Ref. [Reference Huang, Zhu and Wang20].

Figure 18.

Replanning experiment with unknown obstacles: (a) narrow corridor environment; (b), (c) regions with unknown obstacles; (d) replanned path after unknown obstacles are introduced.

After the unknown obstacle information is updated in the occupancy grid map, the map state changes accordingly, and the algorithm replans the remaining path based on the updated map. As shown in Table VIII, HANSA* achieves the shortest path length of 42.243 m and produces no sharp corners under the Corners metric. Compared with JPS, Weighted A*, and Dynamically Weighted A*, the path generated by HANSA* avoids noticeable oscillations and large detours. Although Huang’s method also produces a relatively short path, its replanning time and number of path nodes are higher than those of HANSA*. These results indicate that HANSA* generates a higher-quality and smoother path in the tested unknown-obstacle scenario.

The improved path quality is mainly related to the two-stage path optimization mechanism and the local-density-based neighborhood switching strategy. In environments where open corridors and complex spaces alternate, HANSA* may require longer replanning time than faster heuristic methods such as Weighted A* and Dynamically Weighted A*. However, this additional computation helps reduce path length and sharp turns, improving the execution-oriented quality of the generated path for the mobile robot platform.