Approximate 3D Euclidean Shortest Paths for Unmanned Aircraft in Urban Environments

This paper introduces a fast algorithm that finds collision-free 3D paths for unmanned aircraft in urban environments. These environments are represented by a three-dimensional scenario in which obstacles are vertical polyhedra. This algorithm uses a method to reduce the number of obstacles taken in...

Full description

Saved in:
Bibliographic Details
Published in:Journal of intelligent & robotic systems 2017-02, Vol.85 (2), p.353-368
Main Authors: Frontera, Guillermo, Martín, David J., Besada, Juan A., Gu, Da-Wei
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Control
Electrical Engineering
Engineering
Mathematical models
Mechanical Engineering
Mechatronics
Obstacles
Polyhedrons
Robotics
Run time (computers)
Shortest-path problems
Unmanned aircraft
Urban environments
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper introduces a fast algorithm that finds collision-free 3D paths for unmanned aircraft in urban environments. These environments are represented by a three-dimensional scenario in which obstacles are vertical polyhedra. This algorithm uses a method to reduce the number of obstacles taken into account in the path finding process. This method is combined with an algorithm that computes approximate Euclidean shortest paths, which has been adapted to suit this kind of scenarios. Instead of focusing on reducing the asymptotic worst-case running time of the algorithm in unrealistic cases, this approach aims to reduce the computation time in a more practical situation. Experimental cases are provided comparing our approach to existing methods in the literature, showing it is very competitive both in terms of speed and solution quality.
ISSN:0921-0296
1573-0409
DOI:10.1007/s10846-016-0409-1