Multirobot deployment, coordination and tracking strategies: A computational-geometric approach

Abstract

<p>This dissertation addresses three novel problems in the visual-based target tracking field using a team of mobile observers/guards. In all the problems, there is a mobile and unpredictable target/intruder inside a closed and polygonal environment. A team of observers must maintain the target inside the field of view of at least one observer all the time. We explore the coordination and motion strategies that the observers require to achieve their objective when they are constrained to move along fixed paths in the environment. This work lays some ground on the target tracking field when the observers have limited motion capabilities, so it builds a bridge between typical pursuit-evasion games where the observer can move freely in the environment, and area coverage in robotics with static sensors. In the first problem, a team of diagonal guards is deployed inside the polygon to provide mobile coverage. In the first problem, we formulate the target tracking task as a multi-robot task allocation (MRTA) problem. Leveraging on guard deployment strategies in art gallery problems for mobile coverage, we show that the problem of finding the minimum speed of guards to persistently track a single mobile intruder is NP-hard. Next, for a given maximum speed of the intruder and the guards, we propose a technique to partition the polygon, and compute a feasible allocation of guards to the partitions. We prove the correctness of the proposed algorithm, and show its completeness for a specific class of inputs. We extend the proposed techniques to address guard deployment and allocation strategies for non-simple polygons and multiple intruders. Additionally, a hybrid automaton is designed to model the problem with a single intruder, and sufficient conditions are presented for the team of diagonal guards to guarantee persistent surveillance.</p> <p>In the second problem, 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</p> <p>either static guards can be placed or they can serve as an endpoint of the segment on which mobile guards move. Finally, we present a strategy to activate/deactivate static guards based on the speed of the intruder. For the third problem, we consider the case of a single guard and a single intruder. The guard can move along a more complex trajectory and its responsible of persistently tracking the intruder. The concept of a p-route is introduced, which is the fixed path of the mobile observer. Next, we address the problem of minimizing the speed required by the observer to guarantee persistent tracking along a given p-route, which is proven to be at most three times the optimal speed. We propose a metric for tracking to estimate a sufficient speed for the observer given the geometry of the environment. A reactive motion strategy for the observer is presented. Moreover, we show that the problem of finding the p-route on which the observer requires minimum speed is computationally intractable. Finally, an iterative technique is proposed to modify an initial p-route to get a new path where the minimum speed required for persistent tracking is minimized.</p>