# Multi-Task Agent Hybrid Control in Sparse Maps and Complex Environmental Conditions
## 2 Path Planning Algorithms Under Sparse Map Conditions
### Traditional A* Algorithm  
The traditional A* algorithm employs the following evaluation function [16]:  
\[f(n)=g(n)+h(n) \tag{1}\]  
In the traditional A* algorithm, \(g(n)\) represents the actual cost of the optimal path from the start point to the current node \(n\), \(h(n)\) represents the estimated cost of the optimal path from the current node \(n\) to the destination, and \(f(n)\) represents the actual cost of the optimal path from the start point to the destination via the current node \(n\). Clearly, \(f(n)\) is not known a priori. During each iteration of the algorithm, an estimate of \(f(n)\), denoted as \(\hat{f}(n)\), is used as the evaluation function, which can be obtained by adding together the estimates \(\hat{g}(n)\) and \(\hat{h}(n)\) of \(g(n)\) and \(h(n)\), respectively. The A* algorithm can evaluate all accessible necessary search positions in the state space to determine the next node to move to and then continue the search from this node until the destination is reached. Compared to the Dijkstra algorithm, its time complexity is reduced from \(O(N^{2})\) to \(O(N\log N)\), significantly improving the efficiency of the path planning algorithm.  
Figure 1: Compares path planning outcomes in the same 500 \(\times\) 500-resolution lunar surface map, showing the difference between an 8-directional movement intelligent agent using the traditional binary A* algorithm (**left**) and an A* pathfinding algorithm that considers the elevation differences in three-dimensional space (**right**).  
The choice of the heuristic function \(h(n)\) is crucial for the A* algorithm: the smaller \(h(n)\) is, the more inclined the algorithm is to expand more nodes in search of the optimal path, but the slower the search speed. When \(h(n)\) is reduced to zero, the A* algorithm becomes the Dijkstra algorithm. The larger \(h(n)\) is, the more the algorithm tends to find a path with the fastest search speed, but it cannot guarantee that the path found is the optimal one. When the value of \(h(n)\) far exceeds \(g(n)\), the A* algorithm becomes the Breadth-First Search (BFS) algorithm. In a two-dimensional map where movement is possible in eight directions, Manhattan or Euclidean distances are commonly used as the heuristic function, with the cost function calculated in the same manner of distance calculation:  
\[g(n)_{\text{M}}=\sum_{j=1}^{k}\Biggl{(}\sum_{i=x,y}\left|i_{p_{j}}-i_{p_{j-1}} \right|+(\sqrt{2}-2)\cdot\prod_{i=x,y}\left|i_{p_{j}}-i_{p_{j-1}}\right|\Biggr{)} \tag{2}\]  
\[h(n)_{\text{M}}=\sum_{i=x,y}\left|i_{T}-i_{n}\right|+(\sqrt{2}-2)\cdot\prod_{i =x,y}\left|i_{T}-i_{n}\right| \tag{3}\]  
\[g(n)_{\text{E}}=\sum_{j=1}^{k}\sqrt{\sum_{i=x,y}\left(i_{p_{j}}-i_{p_{j-1}} \right)^{2}} \tag{4}\]  
\[h(n)_{\text{E}}=\sqrt{\sum_{i=x,y}\left(i_{T}-i_{n}\right)^{2}} \tag{5}\]  
where \(T\) is the target point, and \(p_{0}\), \(p_{1},\ldots,p_{k}\) are the nodes that are actually passed through in the path from the start point to the current node, with \(p_{0}\) being the starting point and \(p_{k}\) being the current node \(n\). In an isotropic three-dimensional space, the agent has the capability to move in 26 directions, including 6 basic directions along the three orthogonal axes, 12 edge diagonal directions, and 8 vertex diagonal directions. In this case, the heuristic function and the cost function are typically as follows:  
\[g(n)_{\text{M}}=\sum_{j=1}^{k}\Biggl{(}\sum_{i=x,y,z}\left|i_{p_{j}}-i_{p_{j-1} }\right|+(\sqrt{2}-2)\cdot\left(\sum_{i=x,y,z}\left|i_{p_{j}}-i_{p_{j-1}} \right|-1\right)^{2}+(5-4\sqrt{2}+\sqrt{3})\cdot\prod_{i=x,y,z}\left|i_{T}-i_{ n}\right|\Biggr{)} \tag{6}\]  
\[h(n)_{\text{M}}=\sum_{i=x,y,z}\left|i_{T}-i_{n}\right|+(\sqrt{2}-2)\cdot \left(\sum_{i=x,y,z}\left|i_{T}-i_{n}\right|-1\right)^{2}+(5-4\sqrt{2}+\sqrt{ 3})\cdot\prod_{i=x,y,z}\left|i_{T}-i_{n}\right| \tag{7}\]  
\[g(n)_{\text{E}}=\sum_{j=1}^{k}\sqrt{\sum_{i=x,y,z}\left(i_{p_{j}}-i_{p_{j-1}} \right)^{2}} \tag{8}\]  
\[h(n)_{\text{E}}=\sqrt{\sum_{i=x,y}\left(i_{T}-i_{n}\right)^{2}} \tag{9}\]