Research

We study the problem of capturing an Omnidirectional Evader in convex environments using a Differential Drive Robot (DDR). The DDR wins the game if at any time instant it captures (collides with) the evader. The evader wins if it can avoid capture forever. Both players are unit disks with the same maximum (bounded) speed, but the DDR can only change its motion direction at a bounded rate. We show that despite this limitation, the DDR can capture the evader.

[Video1] [Video2]

Capturing an Omnidirectional Evader in Convex Environments using a Differential Drive Robot [PDF]

U. Ruiz and V. Isler

IEEE Robotics and Automation Letters, 1(2):1007-1013, 2016.

This paper addresses a differential pursuit/evasion game. The players are an omnidirectional agent (OA) and a differential drive robot (DDR). They move in an obstacle free environment, the DDR is faster than the OA but it can only change its motion direction up to a bounded rate. First, we analyze the scenario in which, the OA has as objective to capture a differential drive robot (DDR) in minimum time and the DDR wants to retard the capture as long as possible. We present the time optimal motion primitives of the players to achieve their goals. Later, combining the results obtained in this paper and the ones in Ruiz et al. (2013), we allow the agents to change the roles, namely, the DDR is allowed to play as the pursuer and the OA is allowed to play as the evader. This later analysis allows one to establish which is the winner role for each agent, based only on the initial position of the players and their maximum speed.

[Video1] [Video2]

A differential pursuit/evasion game of capture between an omnidirectional agent and a differential drive robot, and their winning roles [PDF]

U. Ruiz and V. Isler

To appear in International Journal of Control, 2016.

We consider the problem of capturing an omnidirectional evader using a differential drive robot in an obstacle-free environment. At the beginning of this game, the evader is at a distance L > l (the capture distance) from the pursuer. The goal of the evader is to keep the pursuer farther than this capture distance for as long as possible. The goal of the pursuer is to capture the evader as soon as possible. In this work, we make the following contributions. We present closed-form representations of the motion primitives and time-optimal strategies for each player; these strategies are in Nash equilibrium, meaning that any unilateral deviation of each player from these strategies does not provide to such player benefit toward the goal of winning the game. We propose a partition of the playing space into mutually disjoint regions where the strategies of the players are well established. This partition is represented as a graph, which exhibits properties that guarantee global optimality. We also analyze the decision problem of the game and we present the conditions defining the winner.

[Video1] [Video2]

Time-Optimal Motion Strategies for Capturing an Omnidirectional Evader using a Differential Drive Robot [PDF]

U. Ruiz, R. Murrieta-Cid and J.L. Marroquin,

IEEE Transactions on Robotics, 29(5): 1180-1196, 2013.

A Homicidal Differential Drive Robot [PDF]

U. Ruiz and R. Murrieta-Cid

Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Saint Paul MN, USA, ICRA 2012.

In this paper, we address the pursuit-evasion problem of tracking an Omnidirectional Agent (OA) at a bounded variable distance using a Differential Drive Robot (DDR), in an Euclidean plane without obstacles. We assume that both players have bounded speeds, and that the DDR is faster than the evader, but due to its nonholonomic constraints it cannot change its motion direction instantaneously. Only a purely kinematic problem is considered, and any effect due to dynamic constraints (e.g., acceleration bounds) is neglected. We provide a criterion for partitioning the configuration space of the problem into two regions, so that in one of them the DDR is able to control the system, in the sense that, by applying a specific strategy (also provided), the DDR can achieve any inter-agent distance (within an error bound), regardless of the actions taken by the OA. Particular applications of these results include the capture of the OA by the DDR and maintaining surveillance of the OA at a bounded variable distance

[Video1] [Video2]

Tracking an Omnidirectional Evader with a Differential Drive Robot at Bounded Variable Distance [PDF]

U. Ruiz, J.L. Marroquin and R. Murrieta-Cid.

International Journal of Applied Mathematics and Computer Science, 24(2): 371-385, 2014.

We consider the surveillance problem of tracking a moving evader by a nonholonomic mobile pursuer. We deal specifically with the situation in which the only constraint on the evader's velocity is a bound on speed (i.e., the evader is able to move omnidirectionally), and the pursuer is a nonholonomic, differential drive system having bounded speed. We formulate our problem as a game. Given the evader's maximum speed, we determine a lower bound for the required pursuer speed to track the evader. This bound allows us to determine at the beginning of the game whether or not the pursuer can follow the evader based on the initial system configuration. We then develop the system model, and obtain optimal motion strategies for both players, which allow us to establish the long term solution for the game. We present an implementation of the system model, and motion strategies, and also present simulation results of the pursuit-evasion game.

[Video1] [Video2]

Tracking an Omnidirectional Evader with a Differential Drive Robot [PDF]

R. Murrieta-Cid, U. Ruiz, J.L. Marroquin, J.-P. Laumond and S. Hutchinson

Journal Autonomous Robot, special issue on Search and Pursuit/Evasion with Mobile Robots, Vol 31, No. 4, pages 345-366, 2011.