%%% ====================================================================
%%% 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 = dec,
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 = jan,
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},
note = {{A}vailable at \url{http://arxiv.org/abs/cs/0701077}},
pdf = {http://arxiv.org/pdf/cs/0701077v3},
}
@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 = aug,
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 = aug,
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 = mar,
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 = jun,
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},
keywords = {visibility coverage, multi-agent deployment, distributed, art
gallery},
note = {{A}vailable at \url{http://arxiv.org/abs/1008.4990}},
pdf = {http://arxiv.org/pdf/1008.4990v4},
month = aug,
year = 2010,
}
@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 = feb,
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.},
keywords = {visibility, sensor network, searchlight scheduling, motion
planning},
doi = {10.1142/S0218195911003573},
}
@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 = feb,
funding = {N00014-07-1-0721, IIS-0904501},
keywords = {visibility coverage, multi-agent deployment, distributed, art
gallery},
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},
}
@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 = oct,
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 = jun,
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 ﬁnd a path for the vehicle such that each target is visited at least once
by the vehicle: the path satisﬁes 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 ﬁnd 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},
}