# High-Efficiency Navigation of Nonholonomic Mobile Robots Based on Improved Hybrid A* Algorithm
## 1 Introduction  
With the development of artificial intelligent and automation technologies, mobile robots with self-navigation capabilities are gradually replacing conventional machines such as manually operated vehicles. However, the working areas and traffic conditions for autonomous mobile robots could be complex, e.g., in the central business district. To work efficiently in these environments, an autonomous robot should have three functions [1]: (1) global planning capability under different working conditions, which enables the robot to plan a feasible global path efficiently according to the local surroundings; (2) tracking and controlling capability to ensure high precision in the movement based on the path planning; and (3) rapid response to environmental constraints and planning of new feasible paths in a time when the local environments are changed due to the passing-by vehicles or pedestrians [2]. The planning of the path can be divided into global path planning and local path planning. Global path planning is designing the route of the robot in a fully perceived environment. It is the process of constructing a two-dimensional or three-dimensional map of the known environment with specific constraints [3] and target information [4]. For the global path planning, two classical searching methods are often used to detect the positions and areas of obstacles: (1) searching algorithms based on random samplings, such as the probabilistic road-map (PRM) [5], rapidly exploring random tree (RRT) method [6],and RRT algorithm based on convolutional neural network (CNN) [7]; and (2) graph search-based algorithms, such as the Dijkstra [8] and extended Dijkstra algorithms [9]. The Dijkstra algorithm is characterized by its ability to guarantee that the obtained path will be the shortest. However, it needs to scan all the nodes in the map, and the number of nodes is generally immense. This results in a significant increase in computation and a potential decrease in solution rate, while also consuming significant memory space. To increase the scanning/searching efficiency, A* algorithm was proposed by using a heuristic function as the search-guided approach [10; 11]. The mathematical principle of the A* algorithm is presented in Equation (1). To determine the priority of the next node \(f\)(n) in the scanning/searching process, two cost functions, \(g(n)\) and \(h(n)\), are used in the equation: \(g(n)\) represents the cost from the current node to the start node of the path, and \(h(n)\) represents the estimated cost from the next node to the end node of the path. \[f(n)=g(n)+h(n) \tag{1}\]  
Based on the A* algorithm, some improved algorithms were developed recently. For example, [PERSON] and [PERSON] developed the jump point search (JPS) algorithm [12] by storing nodes in the open list to improve search efficiency. [PERSON] et al. proposed self-adaptive learning particle swarm optimization (PSO) with different learning strategies [13] to improve the search capability of PSO. With the development of nonholonomically constrained robots, path planning becomes more and more important for robots, such as the Ackermann mobile robot chassis. However, the A* algorithm is not effective in planning path for nonholonomically constrained mobile platforms. When planning the paths for such robots, post-processing and smooth optimization processes are required before the application of the paths because such robots are only feasible to paths that satisfy their kinematic constraints, and they are not capable of tracking all the continuous paths. As shown in Figure 1, the Ackermann robots cannot traverse angles greater than 90\({}^{\circ}\) (such as the red robot in Figure 1a) in a limited range when confronting such obstacles (the blue grid) in real-world scenarios. Therefore, flexible path planning should be used to avoid potential collisions (Figure 1b). In addition to the global path planning, local path planning is also critical when the working environment keeps changing dynamically.