Generating approximative minimum length paths in 3D for UAVs
- 1 June 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2012 IEEE Intelligent Vehicles Symposium
- p. 229-233
- https://doi.org/10.1109/ivs.2012.6232120
Abstract
We consider the challenge of planning a minimum length path from an initial position to a final position for a rotorcraft. The path is found in a 3-dimensional Euclidean space containing a geometric obstacle. We base our approach on visibility graphs which have been used extensively for roadmap based path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straightforward, unless a visibility graph is generated that, when searched, will only provide an approximate minimum length path. Our approach generates such a visibility graph that is composed by an obstacle graph and two supporting graphs. The obstacle graph is generated by approximating a mesh around the configuration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by finding the supporting lines between the initial or final position and the mesh. An approximation to the optimal path can subsequently be found using an existing graph search algorithm. The presented approach is suitable for fully known environments with a single truly 3-dimensional (not merely "raised" 2-dimensional) obstacle. An example for generating a nearly minimum length path for a small-scale helicopter operating near a building is shown.Keywords
This publication has 10 references indexed in Scilit:
- Minkowski Sums of Monotone and General Simple PolygonsDiscrete & Computational Geometry, 2005
- Spherical averages and applications to spherical splines and interpolationACM Transactions on Graphics, 2001
- Computational Geometry in CPublished by Cambridge University Press (CUP) ,1998
- Fast, Minimum Storage Ray-Triangle IntersectionJournal of Graphics Tools, 1997
- Generation of configuration space obstacles: the case of a moving sphereIEEE Journal on Robotics and Automation, 1988
- New lower bound techniques for robot motion planning problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Spatial Planning: A Configuration Space ApproachIEEE Transactions on Computers, 1983
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968
- A note on two problems in connexion with graphsNumerische Mathematik, 1959