Enhanced Modified Voronoi Algorithm for UAV Path Planning and Obstacle Avoidance


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


This paper presents an enhanced obstacle avoidance Voronoi algorithm for path planning and trajectory generation for unmanned aerial vehicles (UAVs). The proposed algorithm produces a flyable collision-free path through a series of obstacles/threats represented by cylindrical risk zones. A generalized model of the risk zones is formulated that can cover a wide diversity of real operational situations. This updated methodology produces a more predictable path grid with reduced computational overhead with respect to the original methodology by constructing the external path segments as tangent lines encircling the outer-most threat zones in the environment. The new methodology also improves the mechanism used to divert path segments away from obstacles. The result is a ready-to-use planner that can easily be implemented on-board UAVs. A model of the West Virginia University (WVU) YF-22 research aircraft implemented within the WVU UAV Simulation Environment is used to demonstrate the functionality of the proposed algorithm. The enhanced algorithm is compared with the original methodology to illustrate path generation and computational improvements.
Copyright © 2013 Praise Worthy Prize - All rights reserved.

Keywords


Fixed-Wing; Path Planning; Road-Map; Unmanned Aerial Vehicle; Voronoi Diagram

Full Text:

PDF


References


Unmanned Systems Roadmap 2011-2036, Washington D.C.: Office of the Secretary of Defense, 2011.

P. R. Chandler, S. Rasmusen, M. Pachter, UAV Cooperative Path Planning, AIAA Guidance, Navigation, and Control Conference (2000).

T. W. McLain, R. W. Beard, Trajectory Planning for Coordinated Rendezvous of Unmanned Ar Vehicles, AIAA Guidance, Navigation, and Control Conference (2000).

T. Schouwenaars, J. How, E. Feron, Decentralized Cooperative Trajectory Planning of Multiple Aircraft with Hard Safety Guarantees, Proc. of AIAA Guidance, Navigation, and Control Conference (2004).

S. I. Higashino, T. Takebayashi, A Method for Real-Time Task Assignment and Path Planning for Multiple UAVs Considering Obstacle Avoidance, (2009) International Review of Aerospace Engineering (IREASE), 2 (4), pp. 175-184.

D. Boukraa, Y. Bestaoui, N. Azouz, Three Dimensional Trajectory Generation for an Autonomous Plane, (2008) International Review of Aerospace Engineering (IREASE), 1 (4), pp. 355-365.

R. R. Kulic, S. Bauks, D. P. Margaris, Modification of Kohonen Rule for Vehicle Path Planning, (2008) International Review of Aerospace Engineering (IREASE), 1 (2), pp. 162-171.

A. Tsourdos, B. White, M. Shanmugavel, Cooperative Path Planning of Unmanned Aerial Vehicles, first ed. (Wiley, Reston, VA, 2011).

L. E. Dubins, On Curves of Minimum Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents, American Journal of Mathematics 79 (1957), 497-516.

C. Hanson, J. Richardson, A. Girard, Path Planning of a Dubins Vehicle for Sequential Target Observation with Ranged Sensors, Proc. of the 2011 American Control Conference (2011).

Z. Said, K. Sunsaraj, Simulation of Nonholonomic Trajectory for a Car-Like Mobile Platform using Dubins Shortest Path Model, IEEE Conf. on Sustainable Utilization and Development in Eng. and Tech. (2011).

S. Jeyaraman et al, Formal Techniques for Modelling and Validation of a Co-operating UAV Team that uses Dubins Set for Path Planning, Proc. of the 2005 American Control Conf. (2005).

J. N. Wilburn, M. G. Perhinschi, B. K. Wilburn, Implementation of a 3-Dimensional Dubins-Based UAV Path Generation Algorithm, submitted to AIAA Guidance, Navigation, and Control Conference (2013).

M. Shimizu, K. Kobayashi, K. Watanabe, Clothoidal Curve-Based Path Generation for an Autonomous Mobile Robot, Proc. of the 2006 IEEE International Joint Conference (2006).

M. Kanehara et al, Path Shortening and Smoothing of Grid-Based Path Planning with Consideration of Obstacles, Proc. of the IEEE International Conference on Systems, Man, and Cybernetics (2007).

N. Montes, M. C. Nora, J. Tomero, Trajector Generation Based on Rational Bezier Curves as Clothoids, IEEE Intelligent Vehicles Symposium(2007).

J. N. Wilburn, M. G. Perhinschi, B. K. Wilburn, Implementation of Composite Clothoid Paths for Continuous Curvature Trajectory Generation for UAVs, submitted to AIAA Guidance, Navigation, and Control Conference (2013).

S. Subchan et. al., Pythagorean Hodograph (PH) Path Planning for Tracking Airborne Contaminant Using Sensor Swarms, IEEE Instrumentation and Measurement Technology Conference (2008).

H. Bruyninckx, D. Reynaerts, Path Planning for Mobile and Hyper-Redundant Robots Using Pythagorean Hodograph Curves, IEEE International Conference on Advanced Robotics (1997).

S. Lim, H. Bang, UAV Guidance Laws to Arrival at Desired Position and Time for Desired Direction, IEEE International Conference on Control, Automation, and Systems (2011).

H. Kaluder, M. Brezak, I. Petrovic, A Visibility Graph Based Method for Path Planning in Dynamic Environments, Proc. of the 34th International Convention MIPRO (2011).

B. Gao et al, Constructing Visibility Graph and Planning Optimal Path for Inspection of 2D Workspace, IEEE International Conference on Intelligent Computing and Intelligent Systems (2009).

F. Lingelbach, Path Planning Using Probabilistic Cell Decomposition, IEEE International Conference on Robotics and Automation (IEEE).

T. Arney, An Efficient Solution to Autonomous Path Planning by Approximate Cell Decomposition, Third International Conference on Information and Automation for Sustainabilty (2007).

O. M. Hammouri, M. M. Matalgah, Voronoi Path Planning Technique for Recovering Communication in UAVs, IEEE International Conference on Computer Systems and Applications (2008).

F. Benavides et al, Real Path Planning Based on Genetic Algorithm and Voronoi Diagrams, IEEE Latin American Robotics Symposium and IEEE Columbian Conference on Automation and Industry Applications (2011).

P. Bhattachara, M. L. Gavrilova, Roadmap-Based Path Planning Using the Voronoi Diagram for a Clearance-Based Shortest Path, IEEE Robotics and Automation Magazine 15 (2008), 38-47.

P. Bhattachara, M. L. Gavrilova, Voronoi Diagram in Optimal Path Planning, 4th International Symposium on Voronoi Diagrams in Science and Engineering (2007).

Y. J. Ho, J. S. Liu, Collision-Free Curvature-Bounded Smooth Path Planning Using Composite Bezier Cure Based on Voronoi Diagram, IEEE International Symposium on Computational Intelligence in Robotics and Automation (2009).

L. Liu, S. Zhang, Voronoi Diagram and GIS-Based 3D Path Planning, 17th International Conference on Geoinformatics (2009).

M. C. Novy, D. R. Jacques, M. Pachter, Air Vehicle Optimal Trajectories Between Two Radars, Proc. of the 2002 American Control Conference (2002).

G. Bo et al, A Method of Constructing Complete Graph for Multiple Objects Path Planning in Complex Environment, IEEE International Conference on Information and Automation (2009).

J. N. Wilburn, M. G. Perhinschi, B. K. Wilburn, O. Karas, Development of a Modified Voronoi Algorithm for UAV Path Planning and Obstacle Avoidance, AIAA Guidance, Navigation, and Control Conference (2012).

K. B. Judd, Trajectory Planning Strategies for Unmanned Air Vehicles, M. S. thesis, Dept. of Mech. Eng., Brigham Young Univ., Provo, UT, 2001.

M. G. Perhinschi et al, Development of a Simulation Environment for Autonomous Flight Control Algorithms, Proc. of the AIAA Modeling and Simulation Technologies Conference (2011).

C. Olson, Introduction to FlightGear, [online] flightgear.org.

O. Karas, UAV Simulation Environment for Autonomous Flight Control Algorithms, M.S. thesis, Dept. of Mechanical and Aerospace Eng., West Virginia Univ., Morgantown, WV, 2012.

M. R. Napolitano, Development of Formation Flight Control Algorithms Using 3 YF-22 Flying Models, AFOSR Project Report, Morgantown, WV, April 2005.

T. Jordan et al, Development of a Dynamically Scaled Generic Transport Model Testbed for Flight Research Experiments, NASA Langley Research Center, Hampton, VA.

United States Navy Fact File: RQ-2A Pioneer Unmanned Aerial Vehicle (UAV), America's Navy, (2009) [online] http://www.navy.mil/navydata/fact_display.asp?cid=1100&tid=2100&ct=1.

Unmanned Aircraft Systems, Navmar Applied Sciences Corporation, [online] http://www.nasc.com/ps-uas.php.

OX Unmanned Aerial Vehicle (UAV), CLMax Engineering, [online] clmaxengineering.com.

H. T. Moncayo et al, Analysis of Fault Tolerant Performance of UAV L1 Adaptive Control Laws, submitted to AIAA Guidance, Navigation, and Control Conference (2013).

H. T. Moncayo et al, UAV Adaptive Control Laws Using Non-Linear Dynamic Inversion Augmented with an Immunity-based Mechanism, Proc. of AIAA Guidance, Navigation, and Control Conference (2012).

H. T. Moncayo et al, Extended Non-Linear Dynamic Inversion Control Laws for Unmanned Air Vehicles, Proc. of AIAA Guidance, Navigation, and Control Conference (2012).

Wilburn B., algorithm comparison paper submitted to IJIUS.


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize