Generating Approximative Minimum Length Paths in 3D for UAVs

Flemming Schøler, Anders la Cour-Harbo, Morten Bisgaard

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

13 Citations (Scopus)
101 Downloads (Pure)

Abstract

We consider the challenge of planning a minimum length path from an initial position to a desired 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 path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straight-forward, unless a visibility graph is generated that, when searched, will only provide an approximative 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 conguration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by nding the supporting lines between the initial or desired 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. A example for generating a path for a small-scale helicopter operating near a building is shown.
Original languageEnglish
Title of host publicationIntelligent Vehicles Symposium (IV), 2012 IEEE
Number of pages5
PublisherIEEE Press
Publication date2012
Pages229-233
ISBN (Print)978-1-4673-2119-8
DOIs
Publication statusPublished - 2012
Event2012 IEEE Intelligent Vehicles Symposium (IV) - Madrid, Spain
Duration: 3 Jun 20127 Jun 2012

Conference

Conference2012 IEEE Intelligent Vehicles Symposium (IV)
CountrySpain
CityMadrid
Period03/06/201207/06/2012
SeriesI E E E Intelligent Vehicles Symposium
ISSN1931-0587

Fingerprint

Unmanned aerial vehicles (UAV)
Visibility
Motion planning
Helicopters
Planning

Keywords

  • Trajectory generation
  • obstacle avoidance
  • UAS

Cite this

Schøler, F., la Cour-Harbo, A., & Bisgaard, M. (2012). Generating Approximative Minimum Length Paths in 3D for UAVs. In Intelligent Vehicles Symposium (IV), 2012 IEEE (pp. 229-233). IEEE Press. I E E E Intelligent Vehicles Symposium https://doi.org/10.1109/IVS.2012.6232120
Schøler, Flemming ; la Cour-Harbo, Anders ; Bisgaard, Morten. / Generating Approximative Minimum Length Paths in 3D for UAVs. Intelligent Vehicles Symposium (IV), 2012 IEEE. IEEE Press, 2012. pp. 229-233 (I E E E Intelligent Vehicles Symposium).
@inproceedings{514f8111bc2749cfbe3928580740eeab,
title = "Generating Approximative Minimum Length Paths in 3D for UAVs",
abstract = "We consider the challenge of planning a minimum length path from an initial position to a desired 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 path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straight-forward, unless a visibility graph is generated that, when searched, will only provide an approximative 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 conguration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by nding the supporting lines between the initial or desired 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. A example for generating a path for a small-scale helicopter operating near a building is shown.",
keywords = "Trajectory generation, obstacle avoidance, UAS",
author = "Flemming Sch{\o}ler and {la Cour-Harbo}, Anders and Morten Bisgaard",
year = "2012",
doi = "10.1109/IVS.2012.6232120",
language = "English",
isbn = "978-1-4673-2119-8",
series = "I E E E Intelligent Vehicles Symposium",
publisher = "IEEE Press",
pages = "229--233",
booktitle = "Intelligent Vehicles Symposium (IV), 2012 IEEE",

}

Schøler, F, la Cour-Harbo, A & Bisgaard, M 2012, Generating Approximative Minimum Length Paths in 3D for UAVs. in Intelligent Vehicles Symposium (IV), 2012 IEEE. IEEE Press, I E E E Intelligent Vehicles Symposium, pp. 229-233, 2012 IEEE Intelligent Vehicles Symposium (IV), Madrid, Spain, 03/06/2012. https://doi.org/10.1109/IVS.2012.6232120

Generating Approximative Minimum Length Paths in 3D for UAVs. / Schøler, Flemming; la Cour-Harbo, Anders; Bisgaard, Morten.

Intelligent Vehicles Symposium (IV), 2012 IEEE. IEEE Press, 2012. p. 229-233 (I E E E Intelligent Vehicles Symposium).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Generating Approximative Minimum Length Paths in 3D for UAVs

AU - Schøler, Flemming

AU - la Cour-Harbo, Anders

AU - Bisgaard, Morten

PY - 2012

Y1 - 2012

N2 - We consider the challenge of planning a minimum length path from an initial position to a desired 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 path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straight-forward, unless a visibility graph is generated that, when searched, will only provide an approximative 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 conguration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by nding the supporting lines between the initial or desired 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. A example for generating a path for a small-scale helicopter operating near a building is shown.

AB - We consider the challenge of planning a minimum length path from an initial position to a desired 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 path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straight-forward, unless a visibility graph is generated that, when searched, will only provide an approximative 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 conguration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by nding the supporting lines between the initial or desired 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. A example for generating a path for a small-scale helicopter operating near a building is shown.

KW - Trajectory generation

KW - obstacle avoidance

KW - UAS

UR - http://www.scopus.com/inward/record.url?scp=84865022662&partnerID=8YFLogxK

U2 - 10.1109/IVS.2012.6232120

DO - 10.1109/IVS.2012.6232120

M3 - Article in proceeding

SN - 978-1-4673-2119-8

T3 - I E E E Intelligent Vehicles Symposium

SP - 229

EP - 233

BT - Intelligent Vehicles Symposium (IV), 2012 IEEE

PB - IEEE Press

ER -

Schøler F, la Cour-Harbo A, Bisgaard M. Generating Approximative Minimum Length Paths in 3D for UAVs. In Intelligent Vehicles Symposium (IV), 2012 IEEE. IEEE Press. 2012. p. 229-233. (I E E E Intelligent Vehicles Symposium). https://doi.org/10.1109/IVS.2012.6232120