Transcript The Cat and The Mouse -- The Case of Mobile Sensors and Targets

Game-Theoretic Analysis of Mobile
Network Coverage
David K.Y. Yau
Outline






Introduction
Mobility models
Cats’ strategies
Mouse’s strategies
Experimental results
Conclusion
Motivation – Why Mobile?
 The mouse
 Evade detection
 Nature of “mission”
 The cat
 Improved coverage with fewer sensors
 Robustness against contingencies
Problem Formulation
 Two player game—cats and mouse






Closed rectangular area
Cats try to shorten detection time
Mouse tries to lengthen detection time
Both move at constant speed
Both have finite sensing range
Ends when mouse is within cat’s sensing range
Mobility Model
 Four-tuple <N, M, T, R>
 N: network area
 M: accessibility constraints
-- the “map”
 T: trip selection
 R: route selection
 Random waypoint model is a special case
 Null accessibility constraints
 Uniform random trip selection
 Cartesian straight line route selection
The Sensing Range
 Cats’ sensing range  Rc
 Mouse’s sensing range  Rm
 Blind mouse
 Rm < Rc
 Caught before evasion
 Seeing mouse
 Rm > Rc
 Active evasion possible
Cats’ Strategies
 Uniform scan
 Bouncing
 Random waypoint model
Mouse Strategy
 Blind
 Hide at safe haven
 Assume cats’ presence statistics is known
 Seeing
 Cats presence  Run
 Maximize the minimum distance to all cats
 Cats absence
 Bouncing
 Random waypoint model
 Static  Don’t move
The Presence Matrix – ∏
 Probability of a cat presence at an area
 Divide network area into m × n cells
 ∏i,j = Probability of one or more cats
present in cell (i, j)
Best Blind Mouse Play
 Find an optimal path to move to a safest cell
 Detection time is maximized along the path
 ∏i,j is lowest at the safest cell (usually)
 Dynamic programming
 Greedy does not always work
Comparison with Local Greedy Strategy
0.0003
0.0300
Greedy
0.0003
0.0300
Dynamic Programming
Optimal Escape Path Formulation
 Using ∏, computes
 Ej[Tstay] = Expected detection time if staying at cell i
 Ej[Tmove(k)] = Expected detection time if moving to cell k
 Cell k is a neighboring cell of i
 Make decision—stay or move
 Maximize expected detection time
 Optimal escape path = sequence of movement until
stay is chosen
 How to compute the expected detection time?
Compute Expected Detection Time
 Initialize Ej[Tdetect] as Ej[Tstay]
 Insert all the cells into max-heap
 i := Extract-max
 Update Ej[Tdetect] for each neighbor cell k of i
 Ek[Tdetect] := max(Ek[Tdetect], Ei[Tmove(k)])
 Heapify
 Repeat until heap becomes empty
Example Optimal Paths
0.0000
0.0374
Vm = 10 m/s
0.0000
0.0374
Vm = 15 m/s
Blind Mouse Strategies Compared
Expected
Detection Time
DP
Mouse
RWP
Strategies
Stay
Cat Strategies
Scan
Bouncing
RWP
1083.26
628.66
2823.26
415.31
442.23
271.73
511.50
305.03
226.13
Vc = 10 m/s, Vm = 10 m/s, Rc = 25 m, Rm = 0 m
Other Options for Cats
 Increase sensing range
Rc (m)
Tdetect (s)
1
15136
5
3056
15
948
25
585
50
271
20
1253
40
640
80
245
160
130
2
278
10
45
50
6
100
2
 Increase speed
Vc (m/s)
Tdetect (s)
10
2618
 Increase quantity
Nc
Tdetect (s)
1
573
Best Seeing Mouse Play
 Find and move at the optimum direction
 Minimum distance to all cats is maximized
 Distance between cat and mouse
 d(β, t) = ║C(t) – M(β, t)║
 Minimum distance moving at direction β
 d*(β) = min t ≥ 0 { d(β, t) }
 Optimal escape direction
 β * = argmax d*(β)
Strategies When Cat Absence




Bouncing
Centric
Random waypoint model
Static  Don’t move
Seeing Mouse Strategies Compared
Expected
Detection Time
Mouse
Strategies
Cat Strategies
Bouncing
RWP
Bouncing
149.53
1455.28
Centric
340.85
1092.29
Static
92.39
899.07
Stay
10.23
21.99
Vc = 10 m/s, Vm = 10 m/s, Rc = 5 m, Rm = 10 m
Result Explained
 Why Bouncing is better for cats?
 All area are equally likely to be visited (approx.)
 Uniform presence matrix (approx.)
 Safe haven eliminated
 Why Centric is better for mouse?
 More choices of direction
Presence Matrices
Random Waypoint Model
Bouncing
Where The Mouse Were Caught?
0.0
1543.2
Detection
Time (s)
Other Options—Sensing Range
Other Options—Speed
Other Options—Quantity
Conclusions
 Detect intelligent mobile target using mobile sensor
 Mobile sensors increase robustness
 Strategies to evade detection without full knowledge of cat
movement
 Movement model is important
 Presence matrix determine the coverage performance
 Bouncing movement is better than random waypoint model
 Stochastic movement prevent movement prediction
 Optimal escape direction helps seeing mouse
 Dynamic programming algorithm helps blind mouse
 Effects of sensing range, speed and number of cats are
quantified
Future Work
 Radioactive, chemical plume detection
 Explosion
 Dispersion
 Mobile target detection with presence of obstacle
 Model for sensor reliability, interference, etc.
 Quantification of sensing uncertainty
Question…