An official website of the United States government
This work explores a variation of the art gallery problem in which a team of static and mobile guards track a mobile intruder with unknown maximum speed. We consider the special case when the mobile guards are restricted to move along the diagonals of a polygonal environment. First, we present an algorithm to identify candidate vertices in a polygon at which either static guards can be placed or they can serve as an endpoint of the segment on which mobile guards move. Next, we present a technique to partition the environment based on the triangulation of the environment, and allocate guards to each partition to track the intruder. The allocation strategy leads to a classification of the mobile guards based on their task and coordination requirements. Finally, we present a strategy to activate/deactivate static guards based on the speed of the intruder. Simulation results are presented to validate the efficacy of the proposed techniques.
more »
« less
Relay Pursuit for Multirobot Target Tracking on Tile Graphs
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
- Award ID(s):
- 1816343
- PAR ID:
- 10442343
- Date Published:
- Journal Name:
- International conference on robotics and automation
- Page Range / eLocation ID:
- 7691 to 7698
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
We study the problem of reducing the amount of communication in a distributed target tracking problem. We focus on the scenario where a team of robots are allowed to move on the boundary of the environment. Their goal is to seek a formation so as to best track a target moving in the interior of the environment. The robots are capable of measuring distances to the target. Decentralized control strategies have been proposed in the past that guarantee that the robots asymptotically converge to the optimal formation. However, existing methods require that the robots exchange information with their neighbors at all time steps. Instead, we focus on reducing the amount of communication among robots. We propose a self-triggered communication strategy that decides when a particular robot should seek up-to-date information from its neighbors and when it is safe to operate with possibly outdated information from the neighbor. We prove that this strategy converges to an optimal formation. We compare the two approaches (constant communication and self-triggered communication) through simulations of tracking stationary and mobile targets.more » « less
-
Utilizing millimeter-wave (mmWave) frequencies for wireless communication in mobile systems is challenging since it requires continuous tracking of the beam direction. Recently, beam tracking techniques based on channel sparsity and/or Kalman filter-based techniques were proposed where the solutions use assumptions regarding the environment and device mobility that may not hold in practical scenarios. In this paper, we explore a machine learning-based approach to track the angle of arrival (AoA) for specific paths in realistic scenarios. In particular, we use a recurrent neural network (R-NN) structure with a modified cost function to track the AoA. We propose methods to train the network in sequential data, and study the performance of our proposed solution in comparison to an extended Kalman filter based solution in a realistic mmWave scenario based on stochastic channel model from the QuaDRiGa framework. Results show that our proposed solution outperforms an extended Kalman filter-based method by reducing the AoA outage probability, and thus reducing the need for frequent beam search.more » « less
-
Mulzer, Wolfgang; Phillips, Jeff M (Ed.)We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICRA48891.2023.10161532
