Candidate: Ahmad Bilal Asghar
Title: Path Planning for Persistent Monitoring in Possibly Adversarial Environments
Date: April 18, 2019
Time: 2:00 PM
Place: EIT 3151-3153
Supervisor(s): Smith, Stephen L.
Abstract:
We consider two robot patrolling problems for persistent monitoring of an environment. The areas to be monitored are represented as vertices of a weighted graph. The events that are to be monitored at each vertex appear there for a certain amount of time. We first consider a multi robot problem, where to avoid missing detection of such events, there is a constraint on the maximum time spent by the robots between visits to each vertex, called the latency, and the objective is to find the minimum number of robots that can satisfy these latency constraints. The decision version of this problem is known to be PSPACE-complete. We present a O(log p) approximation algorithm for this problem where p is the ratio of the maximum and the minimum latency constraints.
For the single robot case, the latency constraints may not be satisfied, and adversarial events can observe the patrolling path of the robot and use the information gained by observation to avoid being detected by the patrolling robot. We also consider this problem of finding stochastic patrolling strategies in such adversarial environments by posing the problem as a multi-stage two player game and characterizing the expected payoffs for the players. We propose a local search algorithm to find patrolling policies in such scenarios.