# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph  
[PERSON]  
1 Department of Engineering, University of Campania [PERSON], 81031 Aversa (CE), Italy; [EMAIL_ADDRESS] (L.B. ); [EMAIL_ADDRESS] (M.M. ); [EMAIL_ADDRESS] (I.N.) [PERSON]  
2 Department of Science and Technology, University of Naples Parthenope, 80143 Naples, Italy 2  
including graph based paths. Graphs are widely used in trajectory optimization thanks to their capability of discretizing and modeling the continuum by means of a certain number of nodes and arcs: probabilistic roadmaps [15; 16], Voronoi diagrams [17; 18; 19; 20], cell decomposition [21; 22; 23; 24; 25], and polynomial and spline parameterizations [26; 27; 28] are examples of methods based on graphs. The Visibility Graph (VG) [29; 30; 31] can be a very effective approach in the case of polygonal obstacles. Several approaches based on VGs have been developed to reduce the computational burden, as the Reduced Visibility Graph (RVG) [32; 33; 34] and the Essential Visibility Graph (EVG) [35; 36; 34]. Other popular techniques in path planning make use of potential fields for both offline nominal trajectory optimization [37; 38] and online collision avoidance [39; 40; 41]. More sophisticated approaches are specifically aircraft oriented, integrating flight dynamics constraints into the problem [42; 43; 44]. Trajectory optimization with constraints can be also based on nature inspired optimization techniques [45], but they are usually too burdensome to be implemented in real-time applications. The available approaches for conflict resolution can be grouped into three different categories. Prescribed methods [46; 47; 48] are based on rules and protocols, and they are very effective in the case of integration in a preexisting airspace, but hardly capable of facing unexpected conditions. Optimization based methods [49; 50; 51; 52; 53; 54; 55] inherit several techniques from offline path planning and obstacle avoidance. Optimization makes these methods more versatile, but it increases the computational burden; for this reason, they are difficult to implement in real-time applications. Potential field based techniques [56; 57; 58; 59; 60; 61] are based on the concept of considering aircraft as charged particles repelled by any other vehicle or obstacle. While the computational burden of these approaches are very low, sometimes they can result in non-feasible paths and possible deadlocks, limiting the capability to make optimal decisions independently. In the literature [62; 63], some works exist that try to solve the problem of escaping from deadlocks and local minimums. In order to optimize flight paths in real-time collision avoidance problems, in the presence of other aircraft or newly detected obstacles, this paper deals with the design of a reactive distributed guidance system. The proposed algorithm considers independent aircraft, sharing information only about position, speed, and direction within their communication/sensor range. One of the original contributions of this work is the use of the Essential Visibility Graph (EVG). While the EVG was previously described in [34; 36], in this paper, a complete proof of the optimality of the resulting path under some assumptions is presented. The EVG concept is extended in the presence of unknown or newly detected obstacles in both static and dynamic scenarios.