# A High-Fidelity Energy Efficient Path Planner for Unmanned Airships
## 4 Cost Wavefront Expansion Planner  
The optimal flight trajectory is defined to be the one that reaches the goal position within the desired time while consuming the minimum amount of energy and avoiding obstacles at a sufficiently safe distance.  
The cost wavefront propagation is a simple yet efficient method for generating optimal paths in autonomous robot applications in unknown environments [41]. This approach starts from the robots's current position and expands anisotropically outward toward the goal position while minimizing a cost function. The cost function is the sum of all trajectory objectives multiplied by the mission weights that are dependent on the mission objective priority and selected by the user _a priori_. The cost function is then searched using a multi-resolution Dijkstra algorithm. This approach produces a trajectory that is complete and resolution optimal [2].  
The cost function, \(\mathbb{C}\), proposed for the trajectory planning of unmanned airships is given by,  
\[\mathbb{C}\left(n,n^{\prime}\right)=W_{t}\cdot\mathbb{C}_{t}\left(n,n^{\prime }\right)+W_{e}\cdot\mathbb{C}_{e}\left(n,n^{\prime}\right)+W_{a}\cdot\mathbb{ C}_{a}\left(n,n^{\prime}\right) \tag{1}\]  
with the user-selectable weight, \(W\), given by:  
\[W_{t}+W_{e}+W_{a}=1 \tag{2}\]  
for any two nodes \(n\) and \(n^{\prime}\) where the subscripts \(t\), \(e\) and \(a\) denote the time, energy and avoidance objectives, respectively. In (1), the three objective cost functions are mapped onto a common scale of zero to one with the exception of \(\mathbb{C}_{a}\), which equals \(\infty\) at the obstacle boundary.  
The selection of resolution and scope is critical since the Dijkstra search algorithm is only resolution optimal and has a proven computational complexity of \(O\left(N\log N\right)\), where \(N\) is the number of nodes in the grid [2]. If the resolution is too large, the planner will generalize obstacles and will over-simplify the wind vector field. If the resolution is too small, planning becomes more computationally expensive. One approach to reduce computation time is to apply sub-optimality bounds through the inclusion of an inflated heuristic (a multiplier greater than one that penalizes new path branches) [42]. It can be shown that the confidence level on the environmental information, such as wind, decreases as the distance from the vehicle increases [43]. The optimal trajectory segments close to the goal node may change due to variations in temporal environmental information (such as wind and flight patterns of other aircraft). Thus, the value of determining the optimal trajectory segments near the goal node is diminished. Two types of methods can be imposed to mitigate this uncertainty. The first is the use a  
Figure 4: Platform used in the simulations (middle), camera, GPS and inertial navigation system (left), hybrid power plant (lower left) and auxiliary electric propulsion (lower middle) [38].  
multi-resolution grid, employing a fine resolution in the immediate vicinity of the UAV, and a coarse resolution approaching the goal node. This approach is similar to the action space map decomposition approach outlined in [44]. Since both fine and coarse resolutions follow the same procedure, this paper focuses on the short-range, fine resolution grid. Using this method, the sub-optimality condition can be effectively controlled by adapting the spatial range and gradient of resolution changes to maximize optimality within the computational constraints. The second method, which could also be applied during the implementation stage, is temporal re-planning which is similar to the three re-planning triggers outlined in [45].