Sampling-Based Path Planning for a Visual Reconnaissance Unmanned Air Vehicle
Journal of Guidance Control and DynamicsPublished 1 March 2012
Karl J. Obermeyer, Paul Oberlin, Swaroop Darbha
Citations81
SJR quartileQ1
SJR score1.22
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Nomenclature jAj means cardinality of a set A A, A, @A = interior, closure, and boundary of a sets A, respectively, and C = cost of an aircraft reconnaissance tour, m d x;x0 = length of shortest aircraft path from state x to state x0, m nsamples = actual number of samples to build a roadmap, and rmin = Dubins aircraft minimum turn radius.
Abstract
Nomenclature jAj = cardinality of a set A A , A, @A = interior, closure, and boundary of a set A, respectively C = cost of an aircraft reconnaissance tour , m d x;x0 = length of shortest aircraft path from state x to state x0, m nsamples = actual number of samples to build a roadmap nsamples = estimated number of samples to build a roadmap rmin = Dubins aircraft minimum turn radius R = s-dimensional Euclidean space S = circle parameterized by angle radians ranging from 0 to 2 SE(2) = special Euclidean group R S T = set fT 1; T 2; . . . ; T ng of n targets to be photographed by aircraft V T i = visibility region of ith target Va = Dubins aircraft airspeed X = aircraft state space x = aircraft state vector x; y = Dubins aircraft Earth-fixed Cartesian coordinates, m = parameter controls ratio of translational vs rotational density of roadmap = Dubins aircraft azimuth angle, rad 2 = set of all subsets of a set A
Keywords
Computer ScienceEngineering
Robot Motion Planning
5,423 Citations1991Jean‐Claude Latombe
Planning Algorithms
4,194 Citations2006Steven M. LaValle
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Journal of the American Statistical AssociationRandom Number Generation and Quasi-Monte Carlo Methods.
2,959 Citations1993Bruce Jay Collings, Harald Niederreiter
Medical Entomology and ZoologyPrinciples of Robot Motion: Theory, Algorithms, and Implementations
2,060 Citations2005Howie Choset, Jean‐Claude Latombe
This text reflects the great advances that have taken place in the last ten years in robotics, including sensor-based planning, probabalistic planning, localization and mapping, and motion planning for dynamic and nonholonomic systems.
Choice Reviews OnlineThe Traveling salesman problem: a computational study
1,767 Citations2007
Open Library features a library with books from the Internet Archive and lists them in the open library and gives you access to over 1 million free e-Books and the ability to search using subject, title and author.
European Journal of Operational ResearchAn effective implementation of the Lin–Kernighan traveling salesman heuristic
1,553 Citations2000Keld Helsgaun
An implementation of the Lin–Kernighan heuristic, one of the most successful methods for generating optimal or near-optimal solutions for the symmetric traveling salesman problem (TSP), is described.
Combinatorial optimizationThe Traveling Salesman Problem and Its Variations
1,374 Citations2006Gregory Gutin, Abraham P. Punnen
This paper presents Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP, a model for solving the Asymmetric Traveling Salesman Problem, and some examples of how this model was applied to the Geometric TSP.
Computers in PhysicsComputational Geometry in C
1,207 Citations1995Joseph O’Rourke, A. John Mallinckrodt
The basic techniques used in computational geometry are all covered: polygon triangualtions, convex hulls, Voronoi diagrams, arrangements, geometric searching, and motion planning.
Theoretical Computer ScienceThe Euclidean travelling salesman problem is NP-complete
775 Citations1977Christos H. Papadimitriou
Aircraft trajectory planning with collision avoidance using mixed integer linear programming
766 Citations2002Arthur Richards, Jonathan P. How
Incremental Sampling-based Algorithms for Optimal Motion Planning
667 Citations2010Sertaç Karaman, Emilio Frazzoli
A new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path returned by RRG converges to the optimum almost surely, and a tree version of RRG is introduced, called RRT∗, which preserves the asymptotic optimality ofRRG while maintaining a tree structure like RRT.
EMS Press eBooksOn the solution of traveling salesman problems
334 Citations1998Vašek Chvátal, William J. Cook +2 more
A breakthrough came when Dantzig, Fulkerson, and Johnson (1954) published a description of a method for solving the TSP and illustrated the power of this method by solving an instance with 49 cities, an impressive size at that time.
SIAM Journal on ComputingAn Optimal Algorithm for Euclidean Shortest Paths in the Plane
319 Citations1999John Hershberger, Subhash Suri
The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time.
2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601)An overview of emerging results in cooperative UAV control
274 Citations2004Allison Ryan, Marco Zennaro +3 more
Research topics in cooperative UAV control include efficient computer vision for real-time navigation and networked computing and communication strategies for distributed control, as well as traditional aircraft-related topics such as collision avoidance and formation flight.
IEEE Transactions on RoboticsMotion planning for multitarget surveillance with mobile sensor agents
271 Citations2005Zhijun Tang, Ümi̇t Özgüner
A gradient-approximation algorithm is proposed to generate a suboptimal loop path for a mobile agent to traverse a sequence of target points in the multi-MSA-multitarget case and a cooperative online motion-planning approach is developed.
IEEE Transactions on Automatic ControlTraveling Salesperson Problems for the Dubins Vehicle
252 Citations2008Ketan Savla, Emilio Frazzoli +1 more
This paper studies minimum-time motion planning and routing problems for the Dubins vehicle, i.e., a nonholonomic vehicle that is constrained to move along planar paths of bounded curvature, without reversing direction, and proposes a novel stabilizing algorithm.
INFOR Information Systems and Operational ResearchAn Efficient Transformation Of The Generalized Traveling Salesman Problem
250 Citations1993Charles E. Noon, James C. Bean
This paper shows how to efficiently transform a GTSP into a standard asymmetric Traveling Salesman Problem (TSP) over the same number of nodes and allows certain routing problems which involve discrete alternatives to be modeled using the TSP framework.
Journal of Intelligent & Robotic SystemsShortest paths of bounded curvature in the plane
235 Citations1994Jean‐Daniel Boissonnat, Andr� C�r�zo +1 more
Given two oriented points in the plane, the authors determine and compute the shortest paths of bounded curvature joining them and propose a solution based on the minimum principle of Pontryagin.
IEEE Transactions on Automation Science and EngineeringA Resource Allocation Algorithm for Multivehicle Systems With Nonholonomic Constraints
196 Citations2007Sivakumar Rathinam, Raja Sengupta +1 more
This paper addresses the constraint that captures the inability of a fixed wing aircraft to turn at any arbitrary yaw rate and gives an algorithm to solve this problem by combining ideas from the traveling salesman problem and the path planning literature.
Journal of AlgorithmsApproximation algorithms for TSP with neighborhoods in the plane
191 Citations2003Adrian Dumitrescu, Joseph S. B. Mitchell
New approximation results for the TSPN are presented, including a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and a PTAS for the important special case of disjoint unit disk neighborhoods.
UAV cooperative control
178 Citations2001Phillip Chandler, Meir Pachter +1 more
This paper addresses the development of cooperative rendezvous and cooperative target classification agents in a hierarchical distributed control system for unmanned aerospace vehicles and minimizes team exposure from Individual coordination functions while satisfying stringent timing constraints.
Journal of Guidance Control and DynamicsMinimum-Time Path Planning for Unmanned Aerial Vehicles in Steady Uniform Winds
161 Citations2009Laszlo Techy, Craig A. Woolsey
The paper's primary contribution is a simple analytical solution for a subset of candidate extremal paths: those for which an initial maximum-rate turn is followed by a straight segment and then a second maximum- rate turn in the same direction as the first.
Shortest path synthesis for Dubins non-holonomic robot
156 Citations2002Xuan-Nam Bui, J. D. Boissonnat +2 more
This work calculates the partition of the configuration space R/sup 2//spl times/S/sup 1/ of a car-like robot, only moving forwards, with respect to the type of the length optimal paths, and gives new optimality conditions on these paths.
AIAA Guidance, Navigation, and Control Conference and ExhibitOptimal path planning in a constant wind with a bounded turning rate
137 Citations2005T Mcgee, Stephen C. Spry +1 more
A method for generating the optimal path from an initial position and orientation to a flnal position and and orientation in the two-dimensional plane for an aircraft with a bounded turning radius in the presence of a constant wind is presented.
Dynamic network flow optimization models for air vehicle resource allocation
135 Citations2001Kendall E. Nygard, Phillip Chandler +1 more
A weapon system consisting of a swarm of air vehicles whose mission is to search for, classify, attack, and perform battle damage assessment, is considered, and the periodic reapplication of the centralized optimization algorithm yields the benefit of cooperative feedback control.
MILP and NLP Techniques for centralized trajectory planning of multiple unmanned air vehicles
111 Citations2006Francesco Borrelli, Dharmashankar Subramanian +2 more
The main objective of this paper is to open the route to the use of MILP solutions (based on simple linear UAV models) in order to initialize NLP solvers which allow the use to enforce flyability constraints on more detailed Uav models at any desired level of detail.
Journal of AlgorithmsTSP with neighborhoods of varying size
110 Citations2005Mark de Berg, Joachim Gudmundsson +4 more
Task allocation for wide area search munitions
87 Citations2002Corey Schumacher, Phillip Chandler +1 more
Memory of previous task assignments is included in the task benefit calculations to reduce churning due to frequent reassignments and a network flow optimization model is used to develop a linear program for optimal resource allocation.
Proceedings of the ... American Control Conference/Proceedings of the American Control ConferenceMicro UAV Path Planning for Reconnaissance in Wind
82 Citations2007Nicola Ceccarelli, John J. Enright +3 more
Simulations are provided in the presence of randomly perturbed wind, based on the Air Force Research Laboratory equipment and the high fidelity simulator MultiUAV2.
AIAA Guidance, Navigation, and Control ConferencePath Planning for a UAV Performing Reconnaissance of Static Ground Targets in Terrain
81 Citations2009Karl J. Obermeyer
A genetic algorithm is designed to solve the general aircraft visual reconnaissance problem for static ground targets in terrain and shown that, under simplifying assumptions, it can be reduced to a variant of the Traveling Salesman Probem which is called the PVDTSP (Polygon-Visiting Dubins Traveling salesman Problem).
A graph-based approach to multi-robot rendezvous for recharging in persistent tasks
72 Citations2013Neil Mathew, Stephen L. Smith +1 more
It is shown that while the optimal solution is not computationally feasible for large problem sizes, it is possible to graphically transform the single charging robot problem to a Traveling Salesman Problem, for which existing heuristic and approximation algorithms can be applied.
Journal of Guidance Control and DynamicsPath-Planning with Avoidance Using Nonlinear Branch-and-Bound Optimization
69 Citations2009Alison Eele, Arthur Richards
A novel method for finding optimal trajectories for a vehicle constrained to avoid fixed obstacles that provides globally optimal solutions while retaining the full nonlinear dynamics model and a significant improvement on mixed-integer linear programming solve times is described.
Journal of Guidance Control and DynamicsTour Planning for an Unmanned Air Vehicle Under Wind Conditions
59 Citations2007Rachelle L. McNeely, Ram Iyer +1 more
This paper considers the problem of constructing minimum time trajectories for a Dubins vehicle in the presence of a time varying wind vector field, and proposes an algorithm for obtaining the minimum-time solution for an UAV and proves its convergence.
eScholarship (California Digital Library)Resource Allocation Algorithm for Multi-Vehicle Systems with Non holnomic Constraints
54 Citations2005Sivakumar Rathinam, Raja Sengupta +1 more
The curvature-constrained traveling salesman problem for high point densities
51 Citations2007Jérôme Le Ny, Emilio Frazzoli +1 more
It is shown that any algorithm that computes a tour for the Dubins' vehicle following an ordering of points optimal for the Euclidean TSP cannot have an approximation ratio better than Omega(n), where n is the number of points.
PolyPublie (École Polytechnique de Montréal)An approximation algorithm for the curvature-constrained traveling salesman problem
42 Citations2005Jérôme Le Ny, Éric Féron
Systematic surveillance for UAVs: A feedforward iterative learning control approach
30 Citations2013Kira Barton, Derek Kingston
The proposed framework has the potential to significantly decrease the resources required for surveillance-based applications and leverages a region-based tracking requirement to minimize overall distance traveled, while guaranteeing convergence within the required tracking zone.
Combinatorial optimizationApproximation Algorithms for Geometric TSP
20 Citations2006Sanjeev Arora
There is no known polynomial-time algorithm that, given integers a1,a2,..., an, C, can decide if \( \sum\nolimits_i {\sqrt {a_i } \leqslant C} \) .