Advanced Graph Search Algorithms for Path Planning of Flight Vehicles
Luca De, Giorgio Guglieri · InTech eBooks · 2012
Path planning is one of the most important tasks for mission definition and management of manned flight vehicles and it is crucial for Unmanned Aerial Vehicles (UAVs) that have autonomous flight capabilities.This task involves mission constraints, vehicle's characteristics and mission environment that must be combined in order to comply with the mission requirements.Nevertheless, to implement an effective path planning strategy, a deep analysis of various contributing elements is needed.Mission tasks, required payload and surveillance systems drive the aircraft selection, but its characteristics strongly influence the path.As an example, quad-rotors have hovering capabilities.This feature permits to relax turning constraints on the path (which represents a crucial problem for fixed-wing vehicles).The type of mission defines the environment for planning actions, the path constraints (mountains, hills, valleys, …) and the required optimization process.The need for off-line or real-time re-planning may also substantially revise the path planning strategy for the selected type of missions.Finally, the computational performances of the Remote Control Station (RCS), where the mission management system is generally running, can influence the algorithm selection and design, as time constraints can be a serious operational issue.This chapter aims to cover three main topics: Describe the most important algorithms developed for path planning of flying vehicles in order to compare them and depict their merits and drawbacks. Focus on graph search algorithms in order to define their main characteristics and provide a complete overview of the most important methods developed. Present a new graph search algorithm (called Kinematic A*) that has been developed on the base of the well-known A* algorithm and aims to fill the relation gap between the path planned with classical graph search solutions and the aircraft kinematic constraints.The chapter is structured as follow: General description of the most important path planning algorithms: Introduction to first approaches to path planning: manual path planning and Dubins curves.Also some simple applications developed by this research group are presented.www.intechopen.comRecent Advances in Aircraft Technology 158 General description of probabilistic and graph search algorithms. General description of potential field and model predictive algorithms. Introduction to some generic optimization algorithms. Study on graph search algorithms: General description of commonality and differences between methods composing this family.Basic algorithm structure identification and introduction to the general features of these methods. First graph search solutions focusing on the A* algorithm. Introduction to dynamic-graph search and to the principal developed methods. "Any heading" algorithms description focusing on Theta*. Brief comparison between Theta* and A* on paths planned with the tools developed by this research group, focusing on the main improvements introduced with Theta*. Kinematic A*: State space definition: in order to implement Kinematic A*, redefinition of the state space is needed. Kinematic model description: the system of differential equation modelling the aircraft kinematic behaviour. Introduction of wind in the kinematic model in order to take into account this disturbance on the path. Formulation of the optimization problem solved with the graph search approach. Constraints definition identifying the set of states evaluated to find the optimal path. Algorithm description. Results presentation in order to identify new algorithm merits and drawbacks: Algorithm test on a square map collecting four obstacles placed close to the four corners.A* path comparison with the Kinematic A* one planned with and without wind. Algorithm test on a square map with one obstacle obstructing the path.This test is made to verify the algorithm search performances. Conclusion and future work description. How to referenceIn order to correctly reference this scholarly work, feel