# A High-Fidelity Energy Efficient Path Planner for Unmanned Airships
## 1 Introduction  
Path planning algorithms can be categorized into those with differential constraints and those without. Differential constraints refer to limitations such as velocity and acceleration limits, non-holonomic motion and other higher order dynamic constraints. The inclusion of these constraints is important to promote more realistic and feasible paths [1]. [PERSON] et al. developed a comprehensive literature summary of path planning methods for unmanned aerial vehicle (UAV) guidance and defined five distinct stages in the planning process: sensor model, terrain representation, roadmap generation, graph search and trajectory generation [2]. The idealized sensor model detects and maps all critical points such as sensed obstacles, initial pose, and goal pose. The terrain representation stage divides the map into a finite search space and segments passable and impassible regions. Roadmap generation is the process of producing a graph that is then searched, with or without differential constraints, for feasible paths or the optimal path (depending on the search approach) between the start and goal poses. The optimality of the path is generally subjective and based on multiple user-defined mission objectives such as time, energy and risk. Applying a scalar-valued preference (or weighting) function to relate each objective into a global cost function is a common approach in multi-objective optimization problems [3; 4]. Finally, trajectory generation can be used to perform path smoothing and speed control. Wind is a major concern for airships and small UAVs with limited propulsion power [5]. If the strength of the local wind is larger than the maximum vehicle velocity, impassible zones are created which many planners do not account for [6]. Moreover, while many planners consider wind as a disturbance whose influence is suppressed by the vehicle's autopilot [7], the wind vector field hasthe potential to be used as a source for powering the UAV to further reduce energy consumption and travel time [8]. This has been especially important in the path planning of static soaring UAVs that use the vertical component of wind for lift, or dynamic soaring UAVs that exploit the vertical gradients in the horizontal wind [9; 10; 11; 12; 13]. Other sources of wind energy that can be exploited are horizontal shear layers [8]. For example, unperturbed wind velocity creates a boundary layer with the Earth's surface as shown in Figure 1. During path planning, it is more energy efficient to fly at lower altitudes when travelling into the wind and higher altitudes when travelling with the wind. Potential field path planning methods are uniquely suited to this problem since much of the environmental data, such as digital elevation maps (DEMs) and wind vector fields (WVFs), are already available in a discrete matrix form. The wavefront expansion algorithm is a type of path planning approach that propagates the costs for the graph and does not rely on the potential field being known _a priori_. Therefore, a navigation policy can be applied to restrict field graph connectivity during the propagation phase based on dynamic constraints such turning rate, pitching rate, velocity and acceleration bounds. This policy promotes more realistic and feasible paths and has the added benefit of reducing the search space. An example of this type of planner is presented by [PERSON] to provide feasible and the minimum-time optimal path for small UAVs in the presence of strong current fields [6]. Unfortunately, the research is performed in 2D and does not include other objectives such as fuel or risk. [PERSON] et al. presented an evolutionary algorithm-based on-line planner for multiple UAVs in 3D that includes optimization of multiple mission objectives such as path length, fuel and several flight risks, but has no mention of wind [15]. [PERSON] developed a wavefront expansion type planner with multiple objectives (distance travelled, time taken, fuel consumed) for a UAV in 3D [16].