https://doi.org/10.31449/inf.v48i10.5693 Informatica 48 (2024) 181–194 181 Improved A* Algorithm for Intelligent Navigation Path Planning Lisha Dong School of Computer and Software Engineering, Sias University Zhengzhou, Zhengzhou 450000, China E-mail: doris-lisa@126.com Keywords: intelligent navigation, LIDAR, depth camera, grid map, path planning Received: February 2, 2024 For path planning in intelligent navigation, traditional navigation maps currently fail to meet the requirements of autonomous navigation and optimal path search in terms of three-dimensional environmental features and accuracy. Therefore, the study combined multiple sensors of LIDAR and depth camera to construct a three-dimensional simulation environment map model, and the optimized A* algorithm used to improve path planning. The cost proportion factor and improved heuristic function were used to optimize the A* algorithm. Through experimental comparison before and after optimization, the shortest path and time of the A* algorithm in the 8×8 grid map before optimization were 12.89 and 0.56s, respectively. It had a shortest path and time of 28.76 and 0.28s in a grid map of 16×16, respectively. The improved A* algorithm had an optimal path and time of 12.26 and 0.34s on an 8×8 grid map, and a shortest path and time of 26.34 and 0.28s on a 16×16 grid map. These experiments confirm that the improved A* algorithm improves the search range and efficiency of path planning. This demonstrates its superiority for intelligent navigation path planning and provides technical references for environmental map construction and optimal path planning. Povzetek: Prispevek predstavi izboljšan algoritem A* za inteligentno načrtovanje poti. S kombinacijo več senzorjev, kot sta LIDAR in globinska kamera, je bil zgrajen tridimenzionalni model simulacijskega okolja. Optimizacija algoritma vključuje uporabo faktorja stroškovne sorazmernosti in izboljšano hevristično funkcijo, kar povečuje obseg iskanja in učinkovitost načrtovanja poti. Eksperimenti so potrdili, da izboljšani algoritem A* doseže krajše poti in hitrejši čas izračuna v primerjavi s standardnim algoritmom. 1 Introduction With the rapid development of artificial intelligence and network technologies, intelligent robots have been widely used in the industry. They have achieved autonomous navigation, positioning, and recognition functions in indoor environments [1-3]. In intelligent transportation, the autonomous navigation of intelligent robots has gradually penetrated into the construction of map models and three-dimensional spatial Path Planning (PP) in daily life. The most critical technology for intelligent robots to complete autonomous navigation tasks lies in path search and optimal planning capabilities [4-5]. PP includes spatial positioning, map construction, motion control, and sensor operation. Among them, motion control technology has achieved many results in indoor intelligent robots and provided great convenience for the production and life of people [6]. Sensors play an important role in the autonomous navigation function of intelligent robots. A single-sensor is usually unable to meet the diverse and complex spatial environment perception. In current research, multi-sensor fusion can improve the accuracy of environmental data, thereby improving environmental information [7]. In addition, PP is usually a node calculation from the starting point to the endpoint. The A* algorithm, genetic algorithm, and ant colony algorithm provide many obstacles avoidance measures and shortest distance search for PP. However, there are still issues such as low computational efficiency and incomplete path search. Based on this, the study combines two-dimensional LIDAR and depth camera to construct a simulated spatial environment map model. The Manhattan function and cost scaling factor are utilized to optimize the A* algorithm, thereby demonstrating the advantages of the improved A* algorithm in intelligent navigation PP. The study is conducted in five parts. Firstly, the results of the present study are elaborated. Secondly, multi-sensor fusion and improved A* algorithm are used for model construction and optimization. The following is a comparison of the PP experiments before and after the optimization of algorithm. The fourth part is a discussion of the results. The last part is a summary of the entire study. 2 Related works The key technologies of intelligent robots in motion control, object detection and tracking, and autonomous navigation are constantly being developed and improved. Environmental perception, map modeling, and PP algorithms are the research directions of intelligent robots in autonomous navigation. The PP algorithm needs to comprehensively perceive the characteristics of the surrounding environment to achieve the optimal path search in all directions. PP and sensor perception have 182 Informatica 48 (2024) 181–194 L. Dong been intensively studied by many researchers in recent years. Durakli et al. proposed using grid maps to model the environment for the mobile robots PP, and then simplifying the planning path using traditional algorithms and Bessel curves to improve the effectiveness of PP [8]. Wang et al. proposed to improve the A* algorithm using an artificial potential field and optimize the turning point of the greedy algorithm to improve the smoothness of the robot's PP and tracking problem [9]. In addition, the design of the PP algorithm added the autonomous obstacle avoidance function of the robot combined with its mobility performance. Hossain et al. proposed the use of reactive local PP algorithm for the local PP of autonomous mobile robots. And they combined the dynamic window method and the following gap method to improve obstacle avoidance ability, thereby demonstrating the efficient performance of the robot algorithm [10]. Li et al. proposed the use of forward search optimization algorithms to shorten the planning path for the search optimization and planning problem of robot global paths. Then they used a hybrid PP method based on sub-objectives to smooth the path and improve the obstacle avoidance ability of the robot's movement, thereby meeting the requirements for safe movement of the robot [11]. Ding et al. proposed the use of a social adaptive PP framework for the adaptive PP of mobile robots. And they combined non-homotopy path penalty strategies and fast exploration of random numbers to improve the computational efficiency of path generation, thus proving the superiority of the algorithm [12]. Yang et al. proposed using A* algorithm and adaptive arc optimization strategy for mobile robot PP and utilizing node jump search to reduce computational complexity, thereby improving path search efficiency and movement smoothness [13]. For the study of robot path capability in different fields or applications, model construction is carried out by combining algorithm design and attitude estimation to meet the PP needs of different aspects. Xu et al. proposed using an adaptive optimal fast exploration random number to improve the algorithm of parallel robot PP to generate obstacle avoidance paths in complex environments. This demonstrated the high efficiency and smoothness of the improved adaptive optimal fast exploration random number algorithm in robot PP [14]. Fan et al. proposed an image edge detection algorithm based on three-dimensional features for the panoramic vision recognition path control problem of intelligent robots. The visual recognition was utilized to construct three-dimensional images, thereby improving the automatic PP and control technology of robots. It indicated that this algorithm was superior to the hidden Markov algorithm and also met the obstacle avoidance requirements of intelligent robots [15]. Sergiyenko et al. proposed the use of three-dimensional optical sensor data transmission algorithms for robot group navigation and visual sensor problems. Automated three-dimensional metrology was combined to optimize the database and improve the PP capability of robots [16]. Yue et al. proposed using a multi-sensor Monte Carlo positioning algorithm for attitude estimation in navigation planning of mobile robots. And the A* algorithm was improved with a cost function to reduce running time and improve the smoothness of the mobile path [17]. Yu et al. proposed a heuristic fast exploration random number algorithm based on cylinders for the underwater robots PP. The direct greedy sampling method was combined to improve the search efficiency of the optimal solution, thereby improving the efficiency and feasibility of underwater robots PP [18]. The relevant research work summarized and compared, as shown in Table 1. Table 1: Summary of comparison of related works Reference Method Result [8] Grid maps are used to model the environment, and traditional algorithms and Bezier curves are used to streamline the PP. Improved the PP ability of mobile robots. [9] Artificial potential field improvement A* algorithm, greedy algorithm optimization turning point. Improved the smoothness of PP for hexapod robots. [10] Reactive local PP algorithms, dynamic window methods, and following gap methods. Improved obstacle avoidance ability of autonomous mobile robots. [11] Forward search optimization algorithm, a hybrid PP method based on sub-objectives. Improved the obstacle avoidance ability of the robot and met its safe movement requirements. [12] Social adaptive PP framework, non-homotopy path penalty strategy, and fast exploration of random numbers. Improved the computational efficiency of path generation. [13] A* algorithm, adaptive arc optimization strategy, and node jump. Improved the path search efficiency and movement smoothness of the robot. [14] Improved adaptive optimal fast exploration random Improved the obstacle Improved A* Algorithm for Intelligent Navigation Path Planning… Informatica 48 (2024) 181–194 183 number algorithm. avoidance ability of robots in complex environments. [15] Image edge detection algorithm based on three-dimensional features and visual recognition to construct three-dimensional images. Improved automatic PP and control technology for intelligent robots. [16] Three-dimensional optical sensor data transmission algorithm, automated three-dimensional metrology optimization database. Improved the ability of robot PP. [17] Multi-sensor Monte Carlo localization algorithm and cost function improvement A* algorithm. Improved the smoothness and operational efficiency of the mobile path. [18] Heuristic fast exploration of random number algorithms based on cylinders and direct greedy sampling method. Improved the PP ability of underwater robots. From Table 1, researchers have conducted model construction and algorithmic studies on intelligent robots in different domains. The development results have been achieved in motion trajectory and obstacle avoidance, providing feasible solutions for PP and navigation problems in practical applications. However, there is a lack of exploration and fusion of the overall map environment. Therefore, LiDAR and depth camera are combined for multi-sensor fusion to construct a simulation environment map. Then, the Manhattan function and cost scaling factor are used to optimize the A* algorithm to improve the perception of the map environment, thereby increasing the obstacle avoidance ability of the algorithm and improving the ability of intelligent navigation and PP. In summary, PP techniques are increasingly demanding in terms of intelligence and accuracy in recent research directions and application fields. The study fully utilizes the fusion of sensors to achieve simulation perception of map environments, thereby providing a technical foundation for intelligent robots to plan paths, navigate and avoid obstacles. However, the A* algorithm plays an important role in PP technology, and it is optimized using the Manhattan function and cost scaling factor to meet the skill requirements of intelligent robot navigation obstacle avoidance and PP. 3 Construction of path planning system based on improved A* algorithm Intelligent navigation systems are constructed based on the multi-dimensional map model, usually using two types of sensors: LIDAR and depth camera to detect the spatial environment. As a result, the precise environmental data for map model construction can be provided. The autonomous navigation function is a key test for building map models. PP is used to perceive and actively avoid obstacles in the environmental space, thereby achieving a fast and convenient map PP scheme and improving PP efficiency. 3.1 Construction of environmental maps for multi-sensor information fusion Due to the complexity of the environmental space, two-dimensional LIDAR is used in this research to accurately measure the distance of environmental targets and achieve intelligent navigation system technology. Depth cameras can obtain more data and algorithms in rich environments, thereby improving the simulation environment of navigation maps. The ranging tool for the two-dimensional LIDAR is the RPLIDAR-A1 Shanghai Silan Technology 360° LIDAR, which combines the triangulation method for real-time ranging of the spatial environment, as shown in Figure 1. Laser ranging core Scanning motor and transmission Interface Clockwise rotation Camera Object Focal length Distance d Figure 1: Schematic diagram of LIDAR ranging for space targets In Figure 1, the combination of LIDAR and triangulation may affect the angle, distance, and position of the camera and target, resulting in a triangle in their positions. The target object also forms a similar triangle with the camera and auxiliary points under the reflection of LIDAR. Therefore, the spatial coordinates and position information of the target object under LIDAR can be 184 Informatica 48 (2024) 181–194 L. Dong computed. The distance between the LIDAR and the target object is represented by equation (1). ( ) ( ) sin sin FC Fj ij D i C D    =    =    =   (1) In equation (1), D represents the distance between the LIDAR and the target object. F is the focal length of the camera. j is the distance between the LIDAR and the camera. The distance between the target point reflected by laser at one point of the camera and the auxiliary point of the camera is i .  represents the angle at which the laser is emitted from the LIDAR device and the target object. Because the LIDAR and camera are on the same horizontal plane, C is the vertical distance between the target object and the LIDAR or camera, and Fj C i  = . Therefore, the range technology of LIDAR for space targets has practicality, providing high accuracy and real-time positioning for environmental measurement. However, LIDAR may suffer from issues such as partial information loss and distorted scanning data when horizontally obtaining object information, leading to measurement data errors. The color information of the objects can be captured by scanning the space objects using depth cameras. The positioning technology of visual sensors can be measured and imaged in Figure 2. Reference plane Infrared laser emitter Screen Horizontal field of view 45° Vertical field of view 58° Image plane Speckle offset A B C D E F G h b Figure 2: Schematic diagram of depth camera positioning and triangulation In Figure 2, the depth value of the target object is obtained by stimulating the positions of the infrared emitter and camera, as well as the speckle pixel offset in the imaging plane when the depth camera measures the distance of occlusion in actual space. Then, the corresponding three-dimensional distance and its position are measured in the spatial environment. Two sets of similar triangles are formed with the infrared camera lens and occlusion as the center, represented by equation (2). pF ED h ED h C AB C  =    −  =   (2) In equation (2), p represents the offset distance between points G and F on the image plane. F refers to the focal length of the camera. h is the vertical distance between the camera and the plane. C represents the depth value of the measured target. The depth value of the target object can be calculated using equation (3). h AB F C AB a h p  =  +  (3) In equation (3), C represents the depth value of the measured target. p is the offset distance between points G and F on the imaging plane. The data collected by the depth camera are converted into LIDAR data format to build an intelligent navigation map, and then a simulation environment map is constructed. For data conversion, it is necessary to convert the two-dimensional pixels of the depth map into three-dimensional spatial coordinate points. The coordinate relationship between the two is represented by equation (4) using the principle of small hole image and the transformation matrix. 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 11 0 0 1 F u xx dx u yy F z v N R T v zz dy                         =     =                               (4) In equation (4), ( ) , uv is a two-dimensional pixel coordinate point. ( ) ,, x y z is a three-dimensional coordinate point of the same point. N represents the inner parameter matrix. R and T are the rotation Improved A* Algorithm for Intelligent Navigation Path Planning… Informatica 48 (2024) 181–194 185 matrix and the translation matrix, respectively. dx and dy are the row and column distances of pixels, respectively, in millimeters. Based on the horizontal and vertical field of view of the depth camera, key extraction is performed on the depth image to maintain an appropriate size. Furthermore, the angle in the depth camera is calculated using equation (5). x z   =   (5) In equation (5),  refers to the angle between a point and its projection point on the x-axis of the three-dimensional coordinate system and the line connecting the coordinate origin. If this angle is projected onto the LIDAR data, the index value of the point in the laser data is represented by equation (6). ( ) n s n     − − == − − (6) In equation (6), s represents the index value of LIDAR data   laser S . ( ) ,  is the set radar angle. n is the number of laser beams. The distance corresponding to the laser data is the distance from the projection point to the optical center of camera, represented by equation (7).   22 l laser s x z = = + (7) In equation (7), l is the vertical distance from the projection point to the camera. Finally, the shortest distance value and the two-dimensional plane laser point cloud collection data are calculated based on the laser data, represented by equation (8).   ( )   min , a jj a depth j a pp pp   =   =   (8) In equation (8), i and j represent the row and column of pixel ( ) , p  , respectively. a j p is the minimum value in column j , which is converted to the corresponding number a of the LIDAR point cloud. Finally, the sensors of LIDAR and depth camera are combined to construct an environmental map model, which deepens the perception of spatial environment and intelligent navigation information in Figure 3. Mileage meter information Depth camera information Lidar information Window extraction Depth image Pixel column Convert Pseudo laser data Count Minimum distance per column Radar information Data synchronization and fusion Gamping algorithm Fusion generation 2D grid map Figure 3: Construction process diagram of environment map for multi-sensor fusion In Figure 3, the depth camera and LIDAR can fully collect spatial environmental information to increase the environmental perception of the map. The odometer information can accurately locate the map navigation. The precise construction of intelligent navigation maps can be promoted by combining three-dimensional spatial display. Therefore, the fusion of sensors can add information and feature perception to the three-dimensional spatial environment, thereby providing comprehensive information supplementation for the construction of map models [19-20]. 3.2 Optimization of A* Algorithm for Environmental Map Path Planning PP utilizes a comprehensive environmental map model and combines optimal algorithms to achieve efficient and efficient map positioning and PP, thereby promoting the development of intelligent navigation technology. In the study, intelligent robots are used for autonomous 186 Informatica 48 (2024) 181–194 L. Dong planning of environmental maps, and the PP algorithm is selected and improved. It mainly includes the grid method, artificial potential field method, genetic algorithm, and neural network algorithm based on map environmental information and technological level. The grid method converts the information of the map environment into network units, which contains binary information of obstacle areas and free areas. Figure 4 shows the process of the specific construction. Obstacle points Target point 0 1 Start point Free Point 1 1 1 0 0 0 0 Neighborhood labeling Around nodes Heuristic Minimum value Move Figure 4: Schematic diagram of path planning grid method process In Figure 4, the grid method divides the obstacle area and the free area into binary information, combined with neighborhood labeling and function calculation. The minimum value of the function is used as the starting point for each step and gradually moves to the position of the target endpoint. The grid method is usually used for map identification using rectangular coordinate systems and numbering to distinguish path areas combined with the construction steps of environmental map information. The number method involves arranging the squares of a raster map in order of numbering from left to right and from top to bottom. Equation (9) is a representation of serial numbers in conjunction with a rectangular coordinate system. ( ) ( ) 1, int W x Mod g m m gH y nn  = −       =     (9) In equation (9), m and n are the rows and columns of the raster map, respectively. Mod and int represent taking remainder and taking integer, respectively. The information of the raster map is further path encoded using equation (10). ( ) 0 , 1 a map x y  =   (10) In equation (10), map represents the grid map, and   0 /1 aa Map map map == . a is an integer. When the evaluation is 1, ( ) , xy is a free grid, which is the passable path. When the value is 0, the grid ( ) , xy represents an obstructing grid, which is an impassable path. Finally, combined with a multi-sensor map model, the path information is transformed into raster map information to clarify the area through which the path passes, thereby achieving the intelligent navigation. The PP algorithm, also known as the A* algorithm, is used in map environments. The Dijkstra shortest path algorithm and Breadth First Search (BFS) algorithm are combined. This not only considers the shortest distance of the obstacle path, but also integrates the distance between the moving position and the target, thereby achieving the optimal implementation of PP. Therefore, the formula for the A* algorithm is represented by equation (11). ( ) ( ) ( ) f n g n h n =+ (11) In equation (11), ( ) fn represents the global proxy value of the current mobile node. ( ) gn is the actual proxy value from the starting point to the position of the mobile node. ( ) hn is the predicted value from the moving node to the target endpoint. The feature information related to the environmental map is used as a heuristic function and applied to the proxy value of the PP. The Manhattan distance function is chosen as the heuristic function, represented by equation (12). Manhattan Distance x Endx y Endy = − + − (12) In equation (12), Manhattan Distance is the sum of absolute values from the starting point to the target endpoint. ( ) , xy is the starting point coordinate. ( ) , Endx Endy is the coordinate of the target endpoint. The shortest distance between the starting point and the destination endpoint in the map environment is the Euclidean distance, represented by equation (13). ( ) ( ) 22 Euclidean distance x Endx y Endy = − + − (13) In equation (13), Euclidean distance represents Improved A* Algorithm for Intelligent Navigation Path Planning… Informatica 48 (2024) 181–194 187 the shortest straight-line distance, which is the Euclidean distance. The Manhattan distance function selected for research can reduce the computational steps for PP, thereby simplifying the number of steps in node motion. Finally, the Manhattan function formula is applied to the A* algorithm, and Figure 5 shows its specific process. Start point The smallest node Open list Current node Increase Target Node NO Traverse adjacent nodes Open list Feasible region Appear No Calculate the value of f Yes Minimum value g Count YES Update node values Open list Spare No path Output Path Figure 4: Schematic diagram of the A* algorithm for Manhattan distance calculation In Figure 5, the Manhattan distance calculation can simplify the planned path while reducing the search nodes. The starting point in the grid map is set in the list, and the minimum value is determined. Then, the moving node and the distance between this node and the target node are set. The proxy value is updated based on the information of neighboring nodes, and the nodes in the list are processed sequentially until the list is empty. Finally, the optimal result for an effective path is obtained. Therefore, the A* algorithm has real-time and accurate PP for intelligent maps and provides algorithm support for transportation fields such as intelligent navigation and autonomous driving. The map environmental information and features are becoming more refined with the complex changes in road traffic, requiring more efficient algorithms to achieve real-time updates of navigation systems. In the study, cost proportion factors and improved functions are introduced to optimize the A* algorithm to improve the PP efficiency. The cost proportion factor is represented by equation (14). * * d d  = (14) In equation (14), d represents the distance between the moving node and the target endpoint. d  is the distance between the starting point and the ending point.  is the distribution parameter of obstacles, often taken as 0.5 or 0.7 based on the distribution type of obstacles. Therefore, the cost proportion factor is introduced into the A* algorithm, represented by equation (15). ( ) ( ) ( ) ( ) ** 1 f n g n h n  = −  +  (15) In equation (15), ( ) fn represents the global proxy value of the current mobile node. ( ) gn is the actual proxy value from the starting point to the position of the mobile node. ( ) hn is the predicted value from the moving node to the target endpoint, deepening the connection with obstacle density. The improvement of the algorithm lies in the optimization of its weights, which in turn facilitates the planning of the optimal path. Therefore, it not only accurately locates obstacles in a multi-sensor fusion environment map, but also reduces the expansion coefficient to ensure the feasibility of the PP intelligent navigation system, thereby improving the accuracy of the optimal PP. 4 Experimental analysis of intelligent navigation for environmental maps using path planning optimization algorithms A simulation environment map model was constructed based on multi-sensor fusion of LIDAR and depth camera. Afterwards, the PP algorithm was applied to the constructed environmental map in the research. The PP algorithm was optimized by combining heuristic functions such as Manhattan function and cost scaling factor. Finally, a path search was performed on the A* algorithm based on the node cost to compare its optimized PP performance. Windows 10 system and grid maps of 8×8 and 16×16 was selected to set obstacle areas 188 Informatica 48 (2024) 181–194 L. Dong in the environmental map. Firstly, the A* algorithm formula was introduced into path search in Figure 6. Start point End point Mobile Node Obstacle area Global proxy value 104 110 124 90 84 110 104 90 98 84 84 78 78 78 92 72 Figure 6: Schematic diagram of A* algorithm path search In Figure 6, the path from the starting point to the destination endpoint was determined based on the global cost value of neighboring nodes around its node. The minimum value was chosen as the next moving node, and the process continues until the destination endpoint was reached. The order of each minimum node path was the optimal path. Simulation experiments were conducted on the PP of the environmental map by introducing the Manhattan function in Figure 7. (a) Accessible Manhattan Distance Planning Results (b) Manhattan Distance Planning Results with Obstacles Figure 7: Path planning results for Manhattan distance In Figure 7, the Manhattan function provided a smooth path and a concise search node for environmental maps with obstacles, resulting in faster real-time updates for intelligent navigation and optimal PP. Finally, the optimized A* algorithm was applied to two grid maps of different specifications, and path search experiments were conducted on different numbers of obstacle areas in Figure 8. (a) Path planning diagram for obstacles<20 on a grid map 8 × 8 grid map (b) Path planning diagram for obstacles>20 on a grid map 8 × 8 grid map 16×16 grid map (c) Path planning diagram for obstacles<60 on a grid map 16×16 grid map (d) Path planning diagram for obstacles>60 on a grid map Figure 8: Path planning results of grid maps of different specifications and their obstacles Improved A* Algorithm for Intelligent Navigation Path Planning… Informatica 48 (2024) 181–194 189 In Figure 8, when the starting and ending points were set as a diagonal, the diagonal at that point should be the shortest distance. However, the obstacles and their areas could affect the selection of the shortest path in practical environments, and the A* algorithm could affect the computational efficiency of path search. In different maps, the node calculation of A* algorithm could be increased and the planning efficiency could be reduced by expanding the range of path search in Table 2. Table 2: Comparison of path planning results for grid maps of different specifications Grid map and its obstacles 8×8, <20 obstacles 8×8,>20 obstacles 16×16, <60 obstacles 16×16,>60 obstacles Optimal path length 12.38 13.04 28.52 30.26 Total search length 32 38 64 68 Total length of Open list 16 32 43 48 Total length of Close list 14 12 28 26 Run time(s) 0.19s 0.26s 0.31s 0.46s From Table 2, as the area of the map and obstacles increased, the length of the optimal path chosen continuously increased, resulting in values of 12.38, 13.04, 28.52, and 30.26, respectively. In addition, the running time of path search gradually increased, to 0.19s, 0.26s, 0.31s, and 0.46s, respectively, indicating that the A* algorithm could not adapt to updating complex and diverse environmental information and features. Therefore, the improvement of the A* algorithm has become the main research direction. The improved A* algorithm reduced computation time and improved PP efficiency by introducing a cost proportion factor and combining it with a multi-sensor environment model and increasing the nodes. Afterwards, the multi-sensor environmental map model was compared with the A* algorithm and the improved A* algorithm in terms of PP in Figure 9. (a) Path Planning of Multi Sensor and A * Algorithm (b) Multi sensor and improved A * algorithm for path planning Figure 9: Comparison results of path planning between multi-sensor and A* algorithm In Figure 9 (a), the PP length of the multi-sensor and A* algorithm was longer, while in Figure 9 (b), the PP length of the multi-sensor and improved A* algorithm approached the diagonal. The comparison showed that the optimization of A* algorithm had a higher PP efficiency for complex maps. Table 3 shows the specific comparison results. 190 Informatica 48 (2024) 181–194 L. Dong Table 3: Path planning results of multiple sensors and different A* algorithms Algorithm Single sensor + A* algorithm Multi sensor + A* algorithm Multi sensor + optimized A* algorithm Traverse total nodes 68 72 93 Total length of Open list 51 46 54 Total length of Close list 22 28 32 Length 32.24 32.06 28.54 Run time(s) 0.74s 0.61s 0.32s From Table 3, the PP results of the A* algorithm with multiple sensors and optimization were good, with a path length of 28.54 and a planning time of 0.32s, respectively. This proved that the A* algorithm with cost scaling factor had the best PP effect on multi-sensor environmental maps. Afterwards, the A* algorithm and the optimized A* algorithm were improved on the Manhattan function based on A*, so a PP comparison was made between the two in Figure 10. The grid map of 8×8 is represented by A, where the number represents the number of obstacles, while B represents the grid map of 16×16. 36 32 80 73 12.89 12.89 30.54 28.76 0 10 20 30 40 50 60 70 80 90 A-30 A-60 B-120 B-240 Path nodes and length Grid map and obstacles Total number of nodes Shortest Path 0.28 0.31 0.57 0.56 0 0.1 0.2 0.3 0.4 0.5 0.6 Run time(s) Run time 38 34 86 82 12.26 12.26 27.64 26.34 0 10 20 30 40 50 60 70 80 90 A-30 A-60 B-120 B-240 Path nodes and length Grid map and obstacles Total number of nodes Shortest Path 0.28 0.29 0.57 0.34 0 0.1 0.2 0.3 0.4 0.5 0.6 Run time Run time(s) (a) Experimental results of path planning for A * algorithm (b) Experimental results of optimizing A * algorithm for path planning Figure 10: Comparison results of path planning experiments using different A* algorithms Figure 10 (a) shows the PP results of the A* algorithm in multi-sensor environment maps of different specifications. The PP effect of the 8×8 grid map was lower than that of the 16×16 grid map. As obstacles increased, the shortest path length of the 8×8 grid map was 12.89, but the time was 0.56s and 0.57s, respectively. In the 16×16 grid map, the increase of obstacles reduced the shortest path length, which was 30.54 and 28.76, respectively, and the running time was 0.31s and 0.28s, respectively. In Figure 10 (b), the changes and comparisons between the two raster maps were consistent with those before optimization, but there had been some improvements for changes of the same specification. In a 16×16 grid map, the shortest paths were 27.64 and 26.34, respectively, which were lower than the results before algorithm optimization. The running times of grid maps with 8×8 and 16×16 was 0.34s, 0.57s, 0.29s, and 0.28s, respectively, which were lower than the algorithm results before optimization, proving the superiority of the optimized A* algorithm for PP. An 8×8 grid map was used to compare the results of the two to visually demonstrate the PP capabilities of the improved A* algorithm and the standard A* algorithm, as shown in Figure 11. Improved A* Algorithm for Intelligent Navigation Path Planning… Informatica 48 (2024) 181–194 191 (a) Standard A * algorithm(b) Improved A * algorithm Figure 11: Schematic diagram of path planning for standard A* algorithm and improved A* algorithm From Figure 11, the path length of the standard A* algorithm was longer than the planned length of the improved A* algorithm, which proved the effectiveness of the improved A* algorithm in PP and met the requirements of intelligent navigation. In addition, for the execution efficiency of the algorithm, the relationship transformation of the nodes with the shortest path was needed to study, and the time and space complexity were used to represent the changes in the storage structure of the algorithm, as shown in Table 4. Table 4: Comparison results of time space complexity of algorithms Algorithm Time complexity Spatial complexity Standard A*algorithm O (n2) Ω (n2) Improved A*algorithm O ((m+n)log) Ω (n+m) According to Table 4, when calculating the shortest path in the map environment, it was transformed into a graphical structure based on the relationship between grid boundaries and nodes. Corresponding storage structures were obtained in different algorithm structures to ensure the computational efficiency of PP for a network graph with n nodes and m arcs. The improved A* algorithm had a superior storage structure and higher execution efficiency. The reduction of spatial and temporal complexity not only avoided the waste of storage space, but also improved the computational efficiency of the algorithm, thereby meeting the real-time and accurate PP ability of intelligent navigation. The fixed spatial environments should be detected and constructed in intelligent simulation map environments. However, robots needed more advanced and real-time technology to handle obstacle avoidance strategies that occur in dynamic environments for intelligent obstacle avoidance capabilities. Therefore, local planning tests were conducted on the obstacle avoidance strategy of intelligent robots in dynamic environments, as shown in Figure 12. (a) Time t1 (b) Time t2 Fixed obstacles Moving obstacles Figure 12: Path planning results in dynamic environment From Figure 12 (a), at time t1, the intelligent robot blocked the moving obstacle and adjusted the optimal route based on path search. Figure 12 (b) shows the activity of moving obstacles at time t2, which continuously changes and adjusts the robot's PP. Meanwhile, it ensured the real-time and effectiveness of the optimal PP. When a dynamic environment or obstacle appeared, the PP of intelligent robots needed to meet the real-time update of the map environment and adjust the optimal path in a timely manner. Therefore, when the improved A* algorithm improved the GIS map planning program, it not only updated the changes in the map 192 Informatica 48 (2024) 181–194 L. Dong environment in real-time, but also provided real-time feedback on road congestion, so that users could re-plan their routes. 5 Discussion Various algorithms and techniques have been used by domestic and foreign researchers to smooth paths and improve computational efficiency in the research of intelligent navigation robots in different fields. However, there is still a lack of in-depth integration in the optimization of A* algorithm functions and the simulation perception and construction of map environments. As a result, there is a lack of technical skills in the adaptive adjustment steps of the robot to navigate the environment. However, the fusion of different sensors was used to meet the environment simulation and real-time perception of the space map, which provided a technical basis for the robot to actively avoid obstacles. In addition, the Manhattan function and cost proportion factor were also used to optimize the A* algorithm, further improving the PP ability of intelligent robots and the efficiency of intelligent perception of the environment and obstacle avoidance. The PP of automatic guided vehicles in logistics factories was combined with the improved A* algorithm in response to the practical application of the improved A* algorithm. The efficiency of its path search was effectively improved. In the global PP of unmanned ships, the improved A* algorithm not only expanded the search neighborhood of nodes, but also improved the smoothness of path turning points and navigation security. The improved A* algorithm for searching the shortest path of high-rise roads improved the operational efficiency and retrieval accuracy on the basis of layering urban roads. Finally, the improved A* algorithm was combined with a mixed data structure to smooth the trajectory in the application of aircraft penetration trajectory planning, thereby making the generated trajectory flyable. Therefore, the optimization strategies and application value of A* algorithm will be continuously explored in different fields of production and life. 6 Conclusion To achieve the best PP for intelligent navigation maps, the study fused two sensors, LIDAR and depth camera, to construct an intelligent environmental map. The Manhattan function and cost scaling factor were utilized to optimize the A* algorithm, and PP experiments were conducted on different specifications of raster maps. These results confirmed that the optimal path length selected by the A* algorithm before optimization gradually increased and was 12.38, 13.04, 28.52, and 30.26, respectively, with the area expansion of map and obstacle. Its running time was 0.19s, 0.26s, 0.31s, and 0.46s, respectively. Therefore, the optimal planning path for optimizing A* algorithm and multi-sensor environmental map system was 28.54 after introducing the cost proportion factor, with a time of 0.32s. The optimal PP for an 8×8 grid map was 12.26 with a time of 0.34s after improving the Manhattan function, while the optimal path length for a 16×16 grid map was 26.34 with a minimum time of 0.28s. Therefore, the optimized A* algorithm had the best PP capability in intelligent navigation with multi-sensor environmental maps. However, the research still lacks data on PP in simulation experimental environments, as well as in-depth exploration in multidimensional and complex environmental maps. Therefore, further thinking and improvement are needed in future research. The positioning, navigation, and PP of intelligent robots are involved in different fields according to the summary of relevant works. Therefore, the research directions of autonomous vehicle, teleoperation robots and underwater environment route planning will continue to deepen with the development of science and technology in the future. More sophisticated and perfect technological progress will be made in complex environments and multidimensional spaces. Funding The research is supported by Documents from the Henan Provincial Department of Finance and the Henan Provincial Department of Education, (No.202116) and the first project on the connection between the supply and demand of employment and education of the Department of College Student Affairs of Ministry of Education, (NO. 20220102387). References [1] Y. Zhang, J. Zhao, and H. Han, “A 3D machine vision-enabled intelligent robot architecture.” Mobile Information Systems, vol. 2021, no. 3, pp. 1-11, 2021. https://doi.org/ 10.1155/2021/6617286 [2] Y. Xu, and W. Gu, “Research on the impact of embedded intelligent robots on english news dissemination.” Wireless Communications and Mobile Computing, vol. 2022, no. 1, pp. 1-14, 2022. https://doi.org/ 10.1155/2022/2127411 [3] R. Zhong, X. Liu, Y. Liu, Y. Chen, and X. Wang, “Path design and resource management for noma enhanced indoor intelligent robots.” IEEE transactions on wireless communications, vol. 21, no. 10, pp. 8007-8021, 2022. https://doi.org/ 10.1109/TWC.2021.3073692 [4] K. Anggriani, S. F. Chiou, N. I. Wu, and M. S. Hwang, "A Robust and High-Capacity Coverless Information Hiding Based on Combination Theory," Informatic, Vol. 34, No. 3, pp. 449–464, 2023. https://doi.org/10.15388/23-INFOR521 [5] K. Fujita, T. Maki, T. Matsuda, Y. Hamamatsu, and T. Sakamaki, “Parent–child‐based navigation method of multiple autonomous underwater vehicles for an underwater self‐completed survey.” Journal of Field Improved A* Algorithm for Intelligent Navigation Path Planning… Informatica 48 (2024) 181–194 193 Robotics, vol. 39, no. 2, pp. 89-106, 2022. https://doi.org/ 10.1002/rob.22038 [6] F. Xu, and H. Wang, “Soft robotics: morphology and morphology-inspired motion strategy.” IEEE/CAA Journal of, Automatica Sinica, vol. 8, no. 9, pp. 1500-1522, 2022. https://doi.org/ 10.1109/JAS.2021.1004105 [7] U. Martinez-Hernandez, U. Martinez-Hernandez, M. I. Awad, and A. A. Dehghani-Sanij, “Learning architecture for the recognition of walking and prediction of gait period using wearable sensors.” Neurocomputing, vol. 470, no. 1, pp. 1-10, 2022. https://doi.org/10.1016/j.neucom.2021.10.044 [8] Z. Durakli, and V. Nabiyev, “A new approach based on Bezier curves to solve path planning problems for mobile robots.” Journal of computational science, vol. 58, no. 2, pp. 101540.1-101540.8, 2022. https://doi.org/10.1016/j.jocs.2021.101540 [9] Z. Wang, F. Gao, Y. Zhao, Y. Yin, and L. Wang, “Improved A* algorithm and model predictive control- based path planning and tracking framework for hexapod robots.” Industrial Robot, vol. 50, no. 1, pp. 135-144, 2023. https://doi.org/10.1108/IR-01-2022-0028 [10] T. Hossain, H. Habibullah, R. Islam, and R. V. Padilla, “Local path planning for autonomous mobile robots by integrating modified dynamic ﹚ indow approach and improved follow the gap method,” Journal of Field Robotics, vol. 39, no. 4, pp. 371-386, 2021. https://doi.org/10.1016/j.comcom.2021.06.018 [11] H. Li, T. Zhao, and S. Dian, “Forward search optimization and subgoal-based hybrid path planning to shorten and smooth global path for mobile robots.” Knowledge-based systems, vol. 258, no. 12, pp. 1-10, 2022. https://doi.org/ 10.1016/j.knosys.2022.110034 [12] Z. Ding, J. Liu, W. Chi, J. Wang, G. Chen, and L. Sun, “PRTIRL Based Socially Adaptive Path Planning for Mobile Robots.” International Journal of Social Robotics, vol. 15, no. 2, pp. 129-142, 2023. https://doi.org/10.1007/s12369-022-00924-8 [13] Z. Yang, J. Li, L. Yang, H. Chen, and K. Watanabe, “A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model.” Journal of robotics, vol. 2022, no. 1, pp. 1.1-1.15, 2022. https://doi.org/ 10.1155/2022/7682201 [14] J. J. Xu, and K. S. Park, “Kinematic performance-based path planning for cable-driven parallel robots using modified adaptive RRT*.” Microsystem Technologies, vol. 28, no. 10, pp. 2325-2336, 2022. https://doi.org/ 10.1007/s00542-022-05319-3 [15] L. K. Fan, X. C. Li, C. S. Guo, and B. S. Jia, “Path control of panoramic visual recognition for intelligent robots based-edge computing,” Computer Communications, vol. 178, no. 10, pp. 64-73, 2021. https://doi.org/10.1016/j.comcom.2021.06.018 [16] O. Y. Sergiyenko, and V. V. Tyrsa, “3D optical machine vision sensors with intelligent data management for robotic swarm navigation improvement.” IEEE sensors journal, vol. 21, no. 10, pp. 11262-11274, 2021. https://doi.org/ 10.1109/JSEN.2020.3007856 [17] G. F. Yue, M. Zhang, C. Shen, and X. H. Guan, “Bi-directional smooth A-star algorithm for navigation planning of mobile robots.” SCIENTIA SINICA Technologica, vol. 51, no. 4, pp. 459-468, https://doi.org/ 10.1360/SST-2020-0186 [18] F. Yu, H. Shang, Q. Zhu, H. Zhang, and Y. Chen, “An efficient RRT-based motion planning algorithm for autonomous underwater vehicles under cylindrical sampling constraints.” Autonomous robots, vol. 47, no. 3, pp. 281-297, 2023. https://doi.org/ 10.1007/s10514-023-10083-y [19] B. Mahmut Can, O. Murat, and Ü. Mehmet, "Circular Pythagorean Fuzzy Sets and Applications to Multi-Criteria Decision Making," Informatic, vol. 34, no. 4, pp. 713-742, 2023. https://doi.org/10.15388/23-INFOR529 [20] G. Fernando, C. Ismael, R. Moisés, and P. Mario, "A Data Quality Model for Master Data Repositories," Informatic, Vol. 34, No. 4, pp. 795-824, 2023. https://doi.org/10.15388/23-INFOR534 194 Informatica 48 (2024) 181–194 L. Dong