2016 · 62 citations · 15 references
ComputingComputer ScienceRobotics EngineeringAerial RoboticsPath PlanningRobot KinematicsObstacle AvoidanceRobot Motion PlanningShortest Path AlgorithmsTrajectory GenerationTrajectory OptimizationVisibility GraphsPath OptimizationPolynomial-time AlgorithmsRobot Path PlanningRobotic Path PlanningShortest Path PlanningShortest Path ProblemsTrajectory PlanningVehicle Path Planning
We present a two step path planning algorithm for unmanned aerial vehicles (UAVs) with kinematic constraints in the presence of polygonal obstacles. We use a visibility graph representation for the environment and a Dubins vehicle approximation to model UAV kinematics. A modified Dijkstra's shortest path algorithm is developed as first step of our approach to plan paths for a UAV. The algorithm in step one takes polynomial time in the number of obstacle vertices in the visibility graph. The second step performs a reverse search on the graph to find feasible paths and uses results of the first step as priors to speed up the search. We present simulation results to substantiate the claims.
15
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Scott A. Bortoff · 2000 · 341 citations
Engineering, Aerospace Engineering, Mechanical Engineering +17
Time-optimal paths for a Dubins airplane
Hamidreza Chitsaz, Steven M. LaValle · 2007 · 249 citations