Research on Path Planning for Intelligent Mobile Robots Based on Improved A* Algorithm

Intelligent mobile robots have garnered extensive research interest in recent years and have been progressively deployed across a diverse array of domains, including logistics, healthcare, service, and inspection. Path planning constitutes a cornerstone of research in intelligent mobile robotics. Effective path planning is essential for these robots to perform tasks autonomously, tailored to the specific requirements of various application scenarios. Contemporary research on path planning primarily encompasses local and global path planning. Local path planning involves utilizing various technologies and tools to perceive environmental information in real-time within unknown or dynamically changing settings. It focuses on dynamically planning effective trajectories from the start to the end point, with principal algorithms including the Dynamic Window Approach (DWA) and the Artificial Potential Field (APF) algorithm [1,2]. Ref. [3] introduced the dynamic weight coefficients based on Q-learning for DWA (DQDWA) to overcome the evaluation function to select inefficient paths or even resulting in collisions. Zhu et al. proposed an improved route plan guided APF method by balancing the attractive and repulsive forces, resolving the irrational and swaying of CA strategy, and extending the applicability of the COLREGS [4]. Ref. [5] proposed a combination of an improved A* algorithm and dynamic window method fusion algorithm, and the fusion algorithm can evade moving obstacles and unknown static obstacles in different map environments in real time along the global optimal path. Kozhubaev et al. proposed the A* algorithm in combination with the artificial potential field method to make the mobile robot’s path planning efficient and enhance its dynamic obstacle avoidance capability [6]. The process of global path planning involves identifying a set of waypoints from the start to the end point based on known environmental information and creating one or more viable paths. The primary algorithms utilized are biomimetic algorithms and classical algorithms. Notable biomimetic algorithms include ant colony optimization, particle swarm optimization, and genetic algorithms [7]. While classical algorithms widely used include Dijkstra’s algorithm and the A* algorithm [8]. The A* algorithm, which is based on heuristic search, has become a crucial research tool for path planning among these algorithms. The algorithm combines the breadth-first search with the greedy-first search. The A* algorithm has been widely used in Robot navigation, character movement in game development, path selection in driverless cars, and logistics and transport optimization, etc. due to its excellent planning capabilities and efficient scalability. In robot navigation, A algorithms help robots find the shortest path from the starting point to the goal in complex environments, avoiding obstacles. In game development, A is commonly used to calculate the best route for intelligent character movement and enemy pursuit. Driverless cars use A* to plan safe paths in real time, taking into account traffic rules and obstacles. In logistics, it is used to optimize routes for goods distribution to improve efficiency and reduce costs. Research efforts are currently focused on improving the universality and robustness of the A* algorithm by optimizing the evaluation function, modifying the search neighbor, and integrating other algorithms. Ref. [9] improved the evaluation function by assigning dynamic weights to the traversed nodes and then proposed a new CCWA* algorithm that speeds up the path search process and decreases planning time. Ref. [10] developed a risk model for obstacles and refined the evaluation function to mitigate safety issues related to the A* algorithm. Ref. [11] introduced the IDA* algorithm used for which designed to escape from ‘dead zones’ and enhance path security by optimizing both the cost function and the search strategy. Liu et al. proposed an improved A* algorithm that employs a bidirectional search strategy and an optimized evaluation function to increase path planning efficiency, reduce inflection points and crossing nodes [12]. Gasparetto et al. proposed a hybrid algorithm used for vessal, which combined A* with an artificial potential field, to address the issue of local trapping in A* and enhance pathfinding search efficiency [13]. Wang et al. proposed a path planning strategy used for mobile robots that integrated the A* algorithm with a greedy algorithm, which not only reduced path length to some scale but also enhanced robustness [14].

However, the above studies have not holistically addressed the performance of the A* algorithm with respect to searching efficiency, robustness, and security. Consequently, this study proposes an improved A* algorithm that integrates considerations of search efficiency, robustness, and security, to ensure optimal performance in diverse scenarios through a reasonable design. Overall, the improvement of the A* algorithm can lead to more efficient, intelligent and reliable path planning and optimization for mobile robots. Thus, the robot can avoid obstacles in the environment more accurately, leading to smarter and more flexible mobility. The contributions of this study are as follows:

The improved A* algorithm proposed in this paper is applicable to the operational tasks of inspection robots in different environments, and at the same time, compared to existing algorithms, the improved A* algorithm improves the efficiency and accuracy of the path search with good applicability and scalability, and better management of resources, reduced memory usage and computational requirements.

The remainder of this paper is organized as follows: In Section 2, the environment map construction for path planning is established, and the expansion and regularization of map are presented. Then, in Section 3, principles of preliminary A* algorithm are described. In Section 4, an improved A* algorithm for the shortest distance path between any two goal positions and the computation time optimization are described and detailed. In Section 5, the experiments are designed and compared to further verify the effectiveness of the proposed approach. Finally, the conclusion and perspectives are given in Section 6.

Environmental modeling aims to convert real-world environmental information into a computer-processable mathematical model, which facilitate effective path planning. Common methods of environmental modeling include the grid method, the topology method, and the geometric feature extraction method [15]. The grid method divides the environment or workspace into uniform grids, which represent a specific area and categorize as a free grid or an obstacle grid based on the presence of obstacles. The topology method does not directly depict the geometric features of the environment, but instead constructs the environmental topology (nodes and boundaries) to convey environmental information, which omit specific environmental details. The geometric feature extraction method conveys environmental information by identifying and extracting geometric features such as points, lines, and surfaces. Among these methods, the grid method is straightforward, convenient, and intuitive for modeling, which is extensively utilized in path planning contexts. Grid maps are important in practical applications. It divides geographical areas into regular grids, and each grid cell can contain detailed geographical or environmental data. This approach makes the analysis of complex areas more intuitive and systematic, and is widely used in urban planning, environmental monitoring and resource management. In robotics, it helps robots understand their surroundings and facilitates path planning and obstacle detection by partitioning space into grids. In games, grid maps are used for character movement and collision detection to enhance the gaming experience. In addition, grid maps are used to analyze land use and resource management in urban planning and geographic information systems (GIS). IRobot’s Roomba series of sweeping robots use grid maps for room navigation, identifying obstacles and planning sweeping paths. Waymo’s driverless cars rely on grid maps for real-time environmental awareness, identifying roads, traffic signals and pedestrians to ensure safe driving. PrecisionHawk, which uses grid maps to analyze farmland and help farmers optimize crop cultivation and resource use. In this method, environmental information is simplified into binary matrices of 0 and 1, where 0 denotes a free grid and 1 denotes an obstacle grid [11]. The mathematical model of an (m × n) grid map is illustrated in Equation (1): where R represents the mathematical model of a m-row by n-column grid map, r_ij represents the grid cell at the i-th. row and j-th. column, which i ∈ [0, m) and j ∈ [0, n). The value of r_ij is 0 or 1, that 0 indicates a free grid and 1 represents an obstacle grid. When m = 9, n = 9, and the side length of each square grid is 1, the grid map represented by R is a 9 × 9 square grid map, as illustrated in Figure 1. On this map, white grids represent free spaces and black grids denote obstacles.

A linear index is introduced for the grid map to enhance the accessibility and processing of grid data and improve pathfinding efficiency. Elements from the 0–1 two-dimensional matrix are mapped into a one-dimensional array in a specific sequence, which reduce memory usage and accelerate access speed. This paper adopts a row-major order principle, which elements of the grid map are mapped into a one-dimensional array starting from the first row and column, proceeding left to right and bottom to top. The linear index begins at 0, and the corresponding calculation formula is provided in Equation (2). This method allows for the rapid location of any element within the grid map without requiring knowledge of its specific row and column positions, as illustrated in Figure 2. where index (r_ij) is the linear index of the i-th row and j-th column grid. Because obstacles in real-world environments typically have irregular shapes, the path planning algorithm can be simplified and enhance the computational efficiency by converting these irregular shapes, as illustrated in Figure 3, into regular shapes which are more manageable and computationally tractable. Additionally, grid expansion can be implemented to enhance safety margins. This paper proposes converting each grid cell occupied by an irregularly shaped obstacle into an obstacle grid in its entirety. Even if only a small portion of the grid cell is occupied, the entire cell is designated as an obstacle grid, as illustrated in Figure 4. This approach ensures effective prevention of potential collisions between the robot and obstacles during operation.

In the context of grid maps, the concepts of grid and node are closely related, with a grid typically representing a node. The attributes of the grid dictate the node’s accessibility, while the node’s connectivity influences the direction and extent of the path planning algorithm. Thus, the grid and node exhibit a one-to-one correspondence, marked by interdependence and inseparability. Within the grid map, the robot is restricted to movement within the node areas designated as free grids, and entry into node areas marked as obstacle grids is prohibited. This paper stipulates that path planning computations are based on the coordinates of each grid’s center position. However, since robot movement in this study is not confined to the cardinal directions (up, down, left, and right), there may be instances where the planned path intersects the vertices of the square grids, as illustrated in scenarios a and b in Figure 5. This paper regularizes and expands irregularly shaped obstacles within the grid map. Consequently, scene (a) represents a scenario where the robot can traverse normally without collision, whereas scene (b) indicates a planned path that intersects obstacles. This latter scenario must be avoided in subsequent path planning to ensure effective navigation.

The A* search algorithm is a highly effective heuristic method commonly employed in robotic path planning. It integrates the features of breadth-first search with greedy-first search, which assesses the merits and demerits of various paths through an evaluation function, thereby enhancing search efficiency. The preliminary A* Algorithm operates on the principle of continuously managing two lists: the openList, which contains pending nodes, and the closedList, which includes processed nodes. Nodes with the lowest evaluated function value are cyclically transferred from the openList to the closedList until the target node is located. If the openList is depleted or the target node remains unfounded, the search is deemed unsuccessful [14]. The evaluation function for the A* algorithm is illustrated in Equation (3): where g(n) represents the cumulative cost function of the path from the start node to the current node n, h(n) represents the heuristic function estimating the cost of the optimal path from the current node n to the target node, and f(n) is the integrated cost function. This function must be continually evaluated to select the next optimal node and minimize the total cost. In extreme cases where the heuristic function h(n) is significantly smaller than g(n) or even zero, the evaluation function f(n) is predominantly determined by g(n). Consequently, the A* algorithm progressively approximates Dijkstra’s algorithm, which result in a path search that involves traversing more nodes. Increasing node traversal leads to reduce search efficiency; but it generally still ensures the identification of the optimal path. Conversely, when the heuristic function h(n) greatly exceeds g(n), the evaluation function f(n) is primarily influenced by h(n). In this scenario, the A* search effectively transforms into a best-first search, which leads to faster search efficiency, however the paths found may not be optimal. This illustrates that the choice of heuristic function h(n) significantly impacts algorithm performance, because different heuristics can yield varied search outcomes. There are three most commonly utilized distance metrics in heuristic functions, which include Manhattan distance, Euclidean distance, and diagonal distance, as illustrated in Figure 6.

The Manhattan distance, within the conventional Cartesian coordinate system, is defined as the sum of the absolute differences between the x-coordinates and y-coordinates of the current node and the target node [15]. This metric, detailed in Equation (4), signifies that movement occurs exclusively along horizontal or vertical axes, disregarding any diagonal displacement.

The Euclidean distance represents the straight-line distance between the current node and the target node, as defined in Equation (5) [16]. However, in grid-based maps, where movement is restricted to horizontal and vertical directions along the grid, the Euclidean distance is usually not the best choice.

The Diagonal distance represents the maximum number of steps required to move from the current node to the target node in any direction [17], including diagonals. Its formal expression is provided in Equation (6). where, g.x, g.y represents the horizontal and vertical coordinates of the target node, and n.x, n.y represents the horizontal and vertical coordinates of the current node. The Manhattan distance directly quantifies the minimum number of steps which are required to traverse from one point to another within grid maps. As a result, Manhattan distance makes it both intuitive and effective for grid-based environments. Compared with the Euclidean distance and Diagonal distance, the computation of the Manhattan distance involves only addition and absolute value operation, excluding square root calculations. This results in greater efficiency and adaptability. This study evaluates the three distance metrics within a grid map of size 50 × 50 and an obstacle density of approximately 35%, as illustrated in Figure 7. The circles in Figure 7 represent the search points. The experimental results, presented in Table 1, demonstrate that the Manhattan distance results in fewer traversal nodes compared with the Euclidean distance and Diagonal distance, in order to enhance search efficiency. Consequently, the Manhattan distance is adopted as the heuristic function for distance in this paper.

To assess the efficacy of the improved A* algorithm, simulations and comparative experiments were conducted using grid maps of three distinct sizes: 25 × 25, 50 × 50, and 80 × 80. These experiments compared the performance of the traditional A* algorithm with the improved A* algorithm. In Figure 12, Figure 13, Figure 14, Figure 15 and Figure 16, the x-axis starts at 0 from left to right, and the maximum value is the number of grids on the x-axis of the grid map, and the y-axis starts at 0 from bottom to top, and the maximum value is the number of grids on the y-axis of the grid map. The green grid represents the starting point and the blue grid represents the end point.

This study focuses on intelligent mobile robots, specifically addressing the limitations of traditional A* pathfinding algorithms, such as excessive node traversal, low search efficiency, and poor adaptability across diverse environments. To overcome these challenges, an improved A* algorithm is proposed for the path planning of intelligent mobile robots. Comparative experiments conducted across various grid map sizes demonstrate that this improved A* algorithm exhibits superior effectiveness and robustness. The key improvements introduced in the A* algorithm in this study are primarily as follows:

When compared to the traditional A* algorithm, the improved A* algorithm proposed in this study demonstrates notable improvements in search time, although the impact on node traversal and performance across various grid sizes is less consistent. Future research will focus on further optimizing this improved A* algorithm to improve performance in terms of both search efficiency and node traversal. The improved algorithm proposed in this paper still lacks in terms of path length and number of traversal points, despite the large improvement in time. In future work, we will improve our proposed A* algorithm with novel criteria to reduce searching nodes, accelerate the search process and optimize the calculation time. Additionally, the current study does not address dynamic obstacles in real-world applications. We may apply the path planning method with the Dynamic Windows Algorithm and emphasize real-time path planning to augment the practical applicability of the method.