%%% ==================================================================== %%% BibTeX-file{ %%% author = "Karl J. Obermeyer", %%% filename = "kjobermeyer.bib", %%% url = "http://karlobermeyer.github.io/publications/kjobermeyer.bib", %%% email = "karl.obermeyer at gmail.com", %%% codetable = "ISO/ASCII", %%% docstring = "This file contains the bibliography of Karl J. Obermeyer.", %%% } %%% ==================================================================== @InProceedings{KJO-AG-FB:2007, author = {K. J. Obermeyer and A. Ganguli and F. Bullo}, title = {Asynchronous distributed searchlight scheduling}, booktitle = {{IEEE} Conf.\ on Decision and Control}, address = {New Orleans, LA, USA}, year = 2007, month = 12, pages = {4863-4868}, funding = {DARPA/AFOSR-MURI-F49620-02-1-0325, NSF-CMS-0626457}, abstract = {This paper develops and compares two simple asynchronous distributed searchlight scheduling algorithms for multiple robotic agents in nonconvex polygonal environments. A searchlight is a ray emitted by a robot which cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which can move continuously with unbounded speed. The objective of the proposed algorithms is for the agents to coordinate the slewing (rotation about a point) of their searchlights in a distributed manner, i.e., using only local sensing and limited communication, such that any target will necessarily be detected in finite time. The first algorithm we develop, called the DOWSS (Distributed One Way Sweep Strategy), is a distributed version of a known algorithm described originally in 1990 by Sugihara et al, but it can be very slow in clearing the entire environment because only one searchlight may slew at a time. In an effort to reduce the time to clear the environment, we develop a second algorithm, called the PTSS (Parallel Tree Sweep Strategy), in which searchlights sweep in parallel if guards are placed according to an environment partition belonging to a class we call PTSS partitions. Finally, we discuss how to possibly extend DOWSS and PTSS for environments with holes, and for coordinated search by mobile guards.}, keywords = {visibility, sensor network, searchlight scheduling, distributed motion planning} } @Misc{KJO-AG-FB:2007-arxiv, author = {K. J. Obermeyer and A. Ganguli and F. Bullo}, title = {Asynchronous Distributed Searchlight Scheduling}, year = 2007, month = 1, abstract = {This paper develops and compares two simple asynchronous distributed searchlight scheduling algorithms for multiple robotic agents in nonconvex polygonal environments. A searchlight is a ray emitted by a robot which cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which can move continuously with unbounded speed. The objective of the proposed algorithms is for the agents to coordinate the slewing (rotation about a point) of their searchlights in a distributed manner, i.e., using only local sensing and limited communication, such that any target will necessarily be detected in finite time. The first algorithm we develop, called the DOWSS (Distributed One Way Sweep Strategy), is a distributed version of a known algorithm described originally in 1990 by Sugihara et al, but it can be very slow in clearing the entire environment because only one searchlight may slew at a time. In an effort to reduce the time to clear the environment, we develop a second algorithm, called the PTSS (Parallel Tree Sweep Strategy), in which searchlights sweep in parallel if guards are placed according to an environment partition belonging to a class we call PTSS partitions. Finally, we discuss how to possibly extend DOWSS and PTSS for environments with holes, and for coordinated search by mobile guards.}, note = {{A}vailable at \url{http://arxiv.org/abs/cs/0701077}}, pdf = {http://arxiv.org/pdf/cs/0701077v3}, keywords = {visibility, sensor network, searchlight scheduling, distributed motion planning} } @Misc{KJO:2008-VisiLibity1, author = {K. J. Obermeyer and Contributors}, title = {{VisiLibity}: A {C}++ Library for Visibility Computations in Planar Polygonal Environments}, howpublished = {\url{http://www.VisiLibity.org}}, year = 2008, note = {v1}, funding = {NSF-CMS-0626457, ARO-MURI-W911NF-05-1-0219}, keywords = {visibility, software, computational geometry, library} } @InProceedings{KJO:2009, author = {K. J. Obermeyer}, title = {Path Planning for a {UAV} Performing Reconnaissance of Static Ground Targets in Terrain}, booktitle = {{AIAA} Conf.\ on Guidance, Navigation and Control}, year = 2009, month = 8, address = {Chicago, IL, USA}, abstract = {In this article we consider a path planning problem for a single fixed-wing aircraft performing an ISR (Intelligence Surveillance Reconnaissance) mission using EO (Electro- Optical) camera(s). We give a mathematical formulation of the general aircraft visual reconnaissance problem for static ground targets in terrain and show that, under simplifying assumptions, it can be reduced to a variant of the Traveling Salesman Problem which we call the PVDTSP (Polygon-Visiting Dubins Traveling Salesman Problem). We design a genetic algorithm to solve the PVDTSP and validate it in a Monte Carlo numerical study. For fixed computation time, the genetic algorithm produces reconnaissance tours on average nearly half the length (and thus can be flown in half the time) of those delivered by a random search. The modular design of the genetic algorithm allows it to easily be extended to handle realistic assumptions such as wind and airspace constraints.}, keywords = {path planning, reconnaissance, uav, genetic algorithm} } @InProceedings{KJO-PO-SD:2010a, author = {K. J. Obermeyer and P. Oberlin and S. Darbha}, title = {Sampling-Based Roadmap Methods for a Visual Reconnaissance {UAV}}, booktitle = {{AIAA} Conf.\ on Guidance, Navigation and Control}, address = {Toronto, ON, Canada}, year = 2010, month = 8, abstract = {This article considers a path planning problem for a single fixed- wing aircraft performing a reconnaissance mission using EO (Electro-Optical) camera(s). A mathematical formulation of the general aircraft visual reconnaissance problem for static ground targets in terrain is given and it is shown, under simplifying assumptions, that it can be reduced to what we call the PVDTSP (Polygon-Visiting Dubins Traveling Salesman Problem), a variation of the famous TSP (Traveling Salesman Problem). Two algorithms are developed to solve the PVDTSP. They fall into the class of algorithms known as sampling-based roadmap methods because they operate by sampling a finite set of points from a continuous state space in order to reduce a continuous motion planning problem to planning on a finite discrete graph. The first method is resolution complete, which means it provably converges to a nonisolated global optimum as the number of samples grows. The second method achieves slightly shorter computation times by using approximate dynamic programming, but consequently is only guaranteed to converge to a nonisolated global optimum modulo target order. Numerical experiments indicate that, for up to about 20 targets, both methods deliver good solutions suitably quickly for online purposes. Additionally, both algorithms allow trade-off of computation time for solution quality and are shown extensible to handle wind, airspace constraints, any vehicle dynamics, and open-path (vs. closed-tour) problems.}, keywords = {path planning, reconnaissance, uav, sampling-based roadmap method} } @Article{KJO-PO-SD:2010b, author = {K. J. Obermeyer and P. Oberlin and S. Darbha}, title = {Sampling-Based Path Planning for a Visual Reconnaissance {UAV}}, journal = {{AIAA} Journal of Guidance, Control, and Dynamics}, year = 2012, volume = 35, number = 2, pages = {619-631}, month = 3, abstract = {This article considers a path planning problem for a single fixed- wing aircraft performing a reconnaissance mission using one or more electro- optical cameras. The aircraft visual reconnaissance problem for static ground targets in terrain is formulated as a \emph{PVDTSP (Polygon-Visiting Dubins Traveling Salesman Problem)}, a variation of the famous Traveling Salesman Problem. Two algorithms for solving the PVDTSP are developed. They fall into the class of algorithms known as \emph{sampling-based roadmap methods} because they operate by sampling a finite set of points from a continuous state space in order to reduce a continuous motion planning problem to planning on a finite discrete graph called a roadmap. Under certain technical assumptions, the algorithms are \emph{resolution complete}, which means the solution returned provably converges to a global optimum as the number of samples grows. The first algorithm is resolution complete under slightly milder assumptions, but the second algorithm achieves faster computation times by a novel roadmap construction. Numerical experiments indicate that, for up to about 20 targets, both algorithms deliver very good solutions suitably quickly for online purposes. Additionally, the algorithms allow trade-off of computation time for solution quality and are shown to be highly extensible.}, keywords = {path planning, reconnaissance, uav, sampling-based roadmap method} } @PhdThesis{KJO:2010-phd, author = {K. J. Obermeyer}, title = {Visibility Problems for Sensor Networks and Unmanned Air Vehicles}, school = {Mechanical Engineering Department, University of California at Santa Barbara}, year = 2010, month = 6, abstract = {This dissertation presents novel motion coordination, planning, and control algorithms to solve {\emph{visibility~problems}} for mobile sensor networks and UAVs (Unmanned Air Vehicles). These are problems where an autonomous system must move in such a way that it achieves or maintains line of sight of some object(s) of interest in a nonconvex environment. More specifically, we address variations of the following three problems: (1) How should a group of camera-equipped robotic agents deploy into an environment in order to achieve full visibility of that environment, (2) how can the rotations of security cameras be coordinated to ensure an intruder is caught on video, and (3) what path should a UAV follow in order to photograph a set of suspicious vehicles in a city as quickly as possible? We find answers to these questions using a unique blend of tools from the research domains of computational geometry, combinatorics, robot motion planning, and control theory.}, keywords = {visibility, motion planning, sensor network, uav} } @Misc{KJO-AG-FB:2010-arxiv, author = {K. J. Obermeyer and A. Ganguli and F. Bullo}, title = {Multi-Agent Deployment for Visibility Coverage in Polygonal Environments with Holes}, note = {{A}vailable at \url{http://arxiv.org/abs/1008.4990}}, pdf = {http://arxiv.org/pdf/1008.4990v4}, month = 8, year = 2010, keywords = {visibility coverage, multi-agent deployment, distributed, art gallery} } @Article{KJO-AG-FB:2011a, author = {K. J. Obermeyer and A. Ganguli and F. Bullo}, title = {A Complete Algorithm for Searchlight Scheduling}, journal = {International Journal of Computational Geometry \& Applications}, year = 2011, month = 2, volume = 21, number = 1, pages = {101-130}, funding = {DARPA/AFOSR-MURI-F49620-02-1-0325, NSF-CMS-0626457}, abstract = {This article develops an algorithm for a group of guards statically positioned in a non-convex polygonal environment with holes. Each guard possesses a single searchlight, a ray sensor which can rotate about the guard’s position but cannot penetrate the bound- ary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which move arbitrarily fast. The objective of the proposed algorithm is to compute a schedule to rotate a set of searchlights in such a way that any target in an environment will necessarily be detected in finite time. This is known as the Searchlight Scheduling Problem and was described originally in 1990 by Sugihara et al. We take an approach known as exact cell decomposition in the mo- tion planning literature. The algorithm operates by decomposing the searchlights’ joint configuration space and the environment, and then by constructing a so-called informa- tion graph. Searching the information graph for a path between desired states yields a search schedule. We also introduce a new problem called the φ-Searchlight Scheduling Problem in which φ-searchlights sense not just along a ray, but over a finite field of view. We show that our results for searchlight scheduling can be directly extended for φ-searchlight scheduling. Proofs of completeness, complexity bounds, and computed examples are presented.}, doi = {10.1142/S0218195911003573}, keywords = {visibility, sensor network, searchlight scheduling, motion planning} } @Article{KJO-AG-FB:2011b, author = {K. J. Obermeyer and A. Ganguli and F. Bullo}, title = {Multi-agent deployment for visibility coverage in polygonal environments with holes}, journal = {International Journal of Robust and Nonlinear Control}, year = 2011, volume = 21, number = 12, pages = {1467-1492}, month = 2, funding = {N00014-07-1-0721, IIS-0904501}, abstract = {This article presents a distributed algorithm for a group of robotic agents with omnidirectional vision to deploy into nonconvex polygonal environments with holes. Agents begin deployment from a common point, possess no prior knowledge of the environment, and operate only under line-of-sight sensing and communication. The objective of the deployment is for the agents to achieve full visibility coverage of the environment while maintaining line-of-sight connectivity with each other. This is achieved by incrementally partitioning the environment into distinct regions, each completely visible from some agent. Proofs are given of (i) convergence, (ii) upper bounds on the time and number of agents required, and (iii) bounds on the memory and communication complexity. Simulation results and description of robust extensions are also included.}, doi = {10.1002/rnc.1700}, keywords = {visibility coverage, multi-agent deployment, distributed, art gallery} } @InProceedings{SGM-SR-SD-KJO:2012, author = {S. G. Manyam and S. Rathinam and S. Darbha and and K. J. Obermeyer}, title = {Computation of a Lower Bound for a Vehicle Routing Problem with Motion Constraints}, booktitle = {{ASME} Dynamic Systems and Control Conference}, address = {Ft. Lauderdale, FL, USA}, year = 2012, month = 10, keywords = {vehicle routing, motion planning} } @InProceedings{JA-KO-ES:2014, author = {J. Adaska and K. Obermeyer and S. Schmidt}, title = {Robust Probabilistic Conflict Prediction for Sense and Avoid}, booktitle = {American Control Conference}, address = {Portland, OR, USA}, year = 2014, month = 6, keywords = {sense and avoid, uav, nextgen airspace} } @Article{SGM-SR-SD-KJO:2015, author = {S. G. Manyam and S. Rathinam and S. Darbha and K. J. Obermeyer}, year = 2015, title = {Lower Bounds for a Vehicle Routing Problem with Motion Constraints}, journal = {International Journal of Robotics and Automation}, volume = 30, number = 3, abstract = {Given a set of targets that needs to be monitored and a vehicle, we consider a combinatorial motion planning problem where the objective is to find a path for the vehicle such that each target is visited at least once by the vehicle: the path satisfies the motion constraints of the vehicle and the length of the path is a minimum. This is an NP-hard problem, and currently, there are no algorithms that can find an optimal solution to this problem. In this paper, we model the motion of the vehicle as a Dubins car and develop a method that can provide lower bounds to the motion planning problem. Lower bounds are important because they can be used to corroborate the quality of the solutions produced by the heuristics or the approximation algorithms. We obtain a lower bound by relaxing the constraints corresponding to the angle of approach at each of the targets and then penalizing them whenever they are violated. The solution to the Lagrangian relaxation gives a lower bound, and this lower bound is maximized over the penalty variables using sub-gradient optimization. Simulation results to compare the proposed lower bound with the existing lower bounds are presented.}, keywords = {vehicle routing, motion planning} }