skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Path planning with Incremental Roadmap Update for Visibility-based Target Tracking
In this paper, we address the visibility-based target tracking problem in which a mobile observer moving along a p-route, which we define as a fixed path for target tracking, tries to keep a mobile target in its field-of-view. By drawing a connection to the watchman's route problem, we find a set of conditions that must be satisfied by the p-route. Then we propose a metric for tracking to estimate a sufficient speed for the observer given the geometry of the environment. We show that the problem of finding the p-route on which the observer requires minimum speed is computationally intractable. We present a technique to find a p-route on which the observer needs at most twice the minimum speed to track the intruder and a reactive motion strategy for the observer.  more » « less
Award ID(s):
1816343
PAR ID:
10176386
Author(s) / Creator(s):
;
Date Published:
Journal Name:
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Page Range / eLocation ID:
1159 to 1164
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Bodlaender, Hans L (Ed.)
    Given a geometric domain P, visibility-based search problems seek routes for one or more mobile agents ("watchmen") to move within P in order to be able to see a portion (or all) of P, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within P according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of P. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain P in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of P (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon P we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains P (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in P to guarantee some specified probability of detection of a static target within P, randomly distributed in P according to a given prior distribution. 
    more » « less
  2. ; ; (, International Conference on Intelligent Robots and Systems)
    We consider the problem of generating a fixed path for a mobile observer in a polygonal environment that can maintain a line-of-sight with an unpredictable target. In contrast to purely off-line or on-line techniques, we propose a hierarchical tracking strategy in which an off-line path generation technique based on a RRT is coupled with an online feedback-control technique to generate trajectories for the mobile observer. 
    more » « less
  3. ; ; (, AIAA SciTech Forum)
    We consider the problem of trajectory planning for optimal relative orbit determination in the cislunar environment. The recent interest in cislunar space has created a need to develop autonomous tracking technologies that can maintain situational awareness of this dynamically complex regime. Optical sensors provide an ideal observation platform because of their low cost and versatility in tracking both cooperative and non-cooperative space objects. The estimation performance of an optical observer can be significantly enhanced through manuevering. This work develops a trajectory planning tool, compatible with low-thrust propulsion, for tracking one or multiple targets operating in proximity to the observer. We formulate an objective function that is a convex combination of the mutual information between target states and measurements, and the low-thrust control effort. The subsequent optimal control problem is solved via direct collocation using the successive convexification algorithm, which, we argue, is well suited for a potential onboard trajectory planning application. We demonstrate the tool for several relevant scenarios with one and multiple targets operating around periodic orbits in the circular restricted three-body problem. A sequential estimator's performance is evaluated using the Cramer-Rao lower bound and, compared to a purely passive observer, we show that optimizing the observer's trajectory can decrease this bound by up to several orders of magnitude within a planning window. This investigation provides an initial proof-of-concept to future onboard planning technologies for relative tracking in the cislunar domain. 
    more » « less
  4. ; ; ; (, ACM Transactions on Internet of Things)
    We present the design, implementation, and experimental evaluation of ASTRO, a modular end-to-end system for distributed sensing missions with autonomous networked drones. We introduce the fundamental system architecture features that enable agnostic sensing missions on top of the ASTRO drones. We demonstrate the key principles of ASTRO by using on-board software-defined radios to find and track a mobile radio target. We show how simple distributed on-board machine learning methods can be used to find and track a mobile target, even if all drones lose contact with a ground control. Also, we show that ASTRO is able to find the target even if it is hiding under a three-ton concrete slab, representing a highly irregular propagation environment. Our findings reveal that, despite no prior training and noisy sensory measurements, ASTRO drones are able to learn the propagation environment in the scale of seconds and localize a target with a mean accuracy of 8 m. Moreover, ASTRO drones are able to track the target with relatively constant error over time, even as it moves at a speed close to the maximum drone speed. 
    more » « less
  5. ; (, International conference on robotics and automation)
    In this work, we address a visbility-based target tracking problem in a polygonal environment in which a group of mobile observers try to maintain a line-of-sight with a mobile intruder. We build a bridge between data mining and visibility-based tracking using a novel tiling scheme for the polygon. First, we propose a tracking strategy for a team of guards located on the tiles to dynamically track an intruder when complete coverage of the polygon cannot be ensured. Next, we propose a novel variant of the Voronoi Diagram to construct navigation strategies for a team of co-located guards to track an intruder from any initial position in the environment. We present empirical analysis to illustrate the efficacy of the proposed tiling scheme. Simulations and testbed demonstrations are present in a video attachment. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email