PhD Seminar: Path Planning for Persistent Monitoring in Possibly Adversarial EnvironmentsExport this event to calendar

Thursday, April 18, 2019 — 2:00 PM EDT

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.

Location 
EIT
Room 3151-3153
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2019 (194)
    1. December (1)
    2. November (1)
    3. October (1)
    4. September (1)
    5. August (26)
    6. July (40)
    7. June (24)
    8. May (23)
    9. April (35)
    10. March (25)
    11. February (9)
    12. January (10)
  2. 2018 (150)
    1. December (13)
    2. November (25)
    3. October (12)
    4. September (13)
    5. August (7)
    6. July (23)
    7. June (9)
    8. May (6)
    9. April (9)
    10. March (16)
    11. February (10)
    12. January (7)
  3. 2017 (212)
  4. 2016 (242)
  5. 2015 (242)
  6. 2014 (268)
  7. 2013 (192)
  8. 2012 (31)