Sequential pursuit of multiple targets under external disturbances via Zermelo–Voronoi diagrams

Abstract

We address the problem of pursuit between a collection of targets and a team of pursuers distributed in the plane subject to an environmental disturbance (e.g., wind, sea current). The objective of the pursuers is to intercept the moving targets which, however, are not affected by the presence of the flow field. We first solve the multiple-pursuers/single-target problem by assigning only one pursuer to chase the target at every instant of time, based on a Voronoi-like partition of the plane. During the pursuit, the pursuer assignment changes dynamically based on this partition. We then present an algorithm to efficiently update this Voronoi-like partition on-line. The results are then extended to the multiple-pursuers/multiple-targets case. Simulations are included to illustrate the theoretical results.

Introduction

Consider a scenario where a group of helicopters or small UAVs fly in the presence of a wind field and try to capture a group of vehicles moving on the ground, or a team of small marine or underwater vehicles attempting to intercept a ship which is large enough so that the sea currents do not significantly affect its motion. Given such a group of pursuers, we want to find a pursuit strategy to intercept the target(s) in minimum time. Problems of this nature fall under the general class of group pursuit. These are difficult problems to solve, in general (Blagodatskikh, 2008, Blagodatskikh, 2009, Pittsyk and Chikrii, 1982). Their solution is also based on the information the pursuers and the targets/evaders have about each other, resulting in either cooperative or non-cooperative strategies (Bakolas and Tsiotras, 2012, Devillers and Golin, 1993, Krasovskiǐ and Krasovskiǐ, 1994, Pashkov and Terekhov, 1987, Vidal et al., 2002, Yeung and Petrosjan, 2006). In order to solve such problems, in this work we propose to use a sequential pursuit strategy (Bakolas & Tsiotras, 2012). By sequential (or relay) pursuit we mean that for each target, only one pursuer is assigned to chase this target at every instant of time. In addition to simplifying significantly the group pursuit problem, a relay pursuit strategy may be desirable in cases where the power or energy/fuel consumption of the agents is an important consideration, when the agents also play a dual role, both as pursuers as well as guardians protecting a certain area, or in order to account for possible deceptive strategies of an intelligent opponent.

For the multiple-pursuers/single-target problem, in contrast to most existing similar problem formulations in the literature (Bakolas and Tsiotras, 2012, Ibragimov et al., 2012, Jang and Tomlin, 2005, Khaidarov, 1984, Pshenichnyi, 1976), where the effect of the environment is not taken into consideration, in our problem setup (only) the pursuers are affected by known exogenous environmental conditions (e.g., the winds or currents). As with all pursuit games, the solution of this problem depends on the knowledge each pursuer has about the current and future position of the target. In this paper it will be assumed that each pursuer has a stroboscopic view of each target position. That is, each pursuer knows the current position of the target but it knows neither its velocity nor its future position. Our objective is to find the optimal assignment to determine which pursuer to go after which target at each instant of time so as to reduce, or minimize, the overall capture time. No assumptions about the target strategy are explicitly imposed a priori, other than the target moves with maximum speed, the value of which is known to all pursuers.

Our solution strategy is based on a dynamic assignment of the pursuers, by which the “best” pursuer to go after the target is selected according to a Voronoi-like partition of the plane, called the Zermelo–Voronoi partition, or the Zermelo–Voronoi Diagram (ZVD) (Bakolas & Tsiotras, 2010). The major difficulty in this setting arises from the fact that, owing to the presence of the wind field, a point in the plane can be close to a pursuer in terms of Euclidean distance, but it may not be close in terms of minimum-time to intercept. As a result, standard Voronoi partitions for this problem may lead to erroneous conclusions.

The ZVD is based on time-to-intercept as the relevant distance metric, instead of the Euclidean metric used in the standard Voronoi diagram. Such Voronoi-like diagrams have been previously introduced in Bakolas and Tsiotras, 2010, Bakolas and Tsiotras, 2012, Bakolas and Tsiotras, 2013. For instance, in Bakolas (2014) the author constructs a Voronoi-like partition in a spatiotemporal flow field by taking the proximity metric as the time required for each vehicle to reach an arbitrary point using a line-of-sight (LOS) control law. Furthermore, as it is shown later on, the use of the so-called Zermelo Navigation Law (Eqs.  (6)–(7) below) leads to a better solution (in terms of capture time) than one that uses a classical LOS control law.

Voronoi-like diagrams have been used in the past to solve group pursuit problems in the plane (Bakolas and Tsiotras, 2010, Bakolas and Tsiotras, 2012). In Bakolas and Tsiotras (2012), the authors proposed a relay pursuit problem where a group of pursuers aims at capturing a target that follows a specific evading strategy. The assignment problem is solved by dynamically assigning the pursuer whose Voronoi cell contains the target. Although our work follows closely the original work in Bakolas and Tsiotras (2012), where ZVDs were first employed to generate the pursuer assignments in an external wind field, our work differs from–and extends the results of–this work as follows: First, and contrary to Bakolas and Tsiotras (2012), we take into account the known disturbance of the environment. Furthermore, this disturbance affects only the pursuers, thus leading to asymmetric dynamics between the target and the pursuers. The asymmetry of the agents’ dynamics does not allow us to use a common reference frame to solve the problem, as was done, for example, in Bakolas and Tsiotras (2010). Second, we use a somewhat different Voronoi-like partition than the one in Bakolas and Tsiotras (2012). Owing to the fact that the target and the pursuers obey different dynamics, in our case we cannot check the condition in Bakolas and Tsiotras (2012) to update the ZVD; instead, we need to update the ZVD continuously. In the process, we propose a numerically efficient algorithm to update the ZVD on-the-fly that may be of independent interest (see Section  5). Third, we assume minimal knowledge of the target state, namely, only its instantaneous position is known to the pursuers. In Bakolas and Tsiotras (2012), on the other hand, it was assumed that the target implements a specific evading strategy, which is known to all of the pursuers.

Contributions. The major contributions of the paper are summarized below:

• We provide a new formulation for the solution of an asymmetric group pursuit problem using the recently introduced concept of Zermelo–Voronoi diagram (ZVD). The formulation leads to a decentralized solution of the original group pursuit problem by decomposing it to a sequence of simpler pursuit problems that are much easier to solve.

• We provide conditions so that the well-known Zermelo Navigation Law (ZNL) achieves capture against a maneuvering target. This key result allows us to implement the ZNL in a sequential manner against arbitrarily maneuvering targets and in the presence of unknown exogenous drift fields.

• We propose a decentralized algorithm for updating efficiently the ZVD as the pursuit evolves based on the dual of the Voronoi diagram, that is, the Delaunay Triangulation (DT) and we provide a complexity analysis for updating the DT (and hence also the ZVD). The updated ZVD is then used to provide the best assignments of the active pursuer(s).

• One of the major benefits of the proposed approach is that it scales well with the number of pursuers and the targets involved. We propose two algorithms that address multiple-pursuer/multi-target problems that make use of this nice property of the proposed ZVD decomposition.