An official website of the United States government
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
Roadmap for Visibility-based Target Tracking: Iterative Construction and Motion Strategy
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
- Award ID(s):
- 1816343
- PAR ID:
- 10351063
- Date Published:
- Journal Name:
- International Conference on Intelligent Robots and Systems
- Page Range / eLocation ID:
- 4732 to 4737
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We designed an observer-aware method for creating navigation paths that simultaneously indicate a robot’s goal while attempting to remain in view for a particular observer. Prior art in legible motion does not account for the limited field of view of observers, which can lead to wasted communication efforts that are unobserved by the intended audience. Our observer-aware legibility algorithm directly models the locations and perspectives of observers, and places legible movements where they can be easily seen. To explore the effectiveness of this technique, we performed a 300-person online user study. Users viewed first-person videos of restaurant scenes with robot waiters moving along paths optimized for different observer perspectives, along with a baseline path that did not take into account any observer’s field of view. Participants were asked to report their estimate of how likely it was the robot was heading to their table versus the other goal table as it moved along each path. We found that for observers with incomplete views of the restaurant, observer-aware legibility is effective at increasing the period of time for which observers correctly infer the goal of the robot. Non-targeted observers have lower performance on paths created for other observers than themselves, which is the natural drawback of personalizing legible motion to a particular observer. We also find that an observer’s relationship to the environment (e.g. what is in their field of view) has more influence on their inferences than the observer’s relative position to the targeted observer, and discuss how this implies knowledge of the environment is required in order to effectively plan for multiple observers at once.more » « less
-
null (Ed.)We develop a new framework for designing online policies given access to an oracle providing statistical information about an off-line benchmark. Having access to such prediction oracles enables simple and natural Bayesian selection policies and raises the question as to how these policies perform in different settings. Our work makes two important contributions toward this question: First, we develop a general technique we call compensated coupling, which can be used to derive bounds on the expected regret (i.e., additive loss with respect to a benchmark) for any online policy and off-line benchmark. Second, using this technique, we show that a natural greedy policy, which we call the Bayes selector, has constant expected regret (i.e., independent of the number of arrivals and resource levels) for a large class of problems we refer to as “online allocation with finite types,” which includes widely studied online packing and online matching problems. Our results generalize and simplify several existing results for online packing and online matching and suggest a promising pathway for obtaining oracle-driven policies for other online decision-making settings. This paper was accepted by George Shanthikumar, big data analytics.more » « less
-
This paper considers the single source shortest path (SSSP) problem, which is the key for many applications such as navigation, mapping, routing, and social networking. Existing SSSP algorithms are designed mostly for shared-memory systems. Nevertheless, with the prevalence of diverse smart devices like drones, there is a growing interest in deploying SSSP algorithms over distributed computing systems so that they can run efficiently onboard of smart devices via Mobile Ad Hoc Computing or at the network edges via Mobile Edge Computing. In this paper, we introduce a communication-efficient ∆-stepping algorithm for distributed computing systems. The proposed algorithm is featured by 1) a message coordination architecture for reducing message exchanges between workers, 2) a pruning technique for reducing redundant computations, and 3) an aggregation technique for further reducing message exchanges when communication delay is significant. Theoretical analyses and experimental studies on real-world graph datasets demonstrate the promising performance of proposed algorithm.more » « less
-
Random mobility models (RMMs) capture the statistical movement characteristics of mobile agents and play an important role in the evaluation and design of mobile wireless networks. Particularly, RMMs are used to model the movement of unmanned aerial vehicles (UAVs) as the platforms for airborne communication networks. In many RMMs, the movement characteristics are captured as stochastic processes constructed using two types of independent random variables. The first type describes the movement characteristics for each maneuver and the second type describes how often the maneuvers are switched. We develop a generic method to estimate RMMs that are composed of these two types of random variables. Specifically, we formulate the dynamics of movement characteristics generated by the two types of random variables as a special Jump Markov System and develop an estimation method based on the Expectation–Maximization principle. Both off-line and on-line variants of the method are developed. We apply the estimation method to the Smooth–Turn RMM developed for fixed-wing UAVs. The simulation study validates the performance of the proposed estimation method. We further conduct a UAV experimental study and apply the estimation methods to real UAV trajectories.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/IROS51168.2021.9636581
