Transcript A Graph Model for Studying the Complexity of the ANTs problem

Wireless Distributed Sensor
Tracking: Computation and
Communication
Bart Selman, Carla Gomes, Scott Kirkpatrick,
Ramon Bejar, Bhaskar Krishnamachari,
Johannes Schneider
Intelligent Information Systems Institute, Cornell
University & Hebrew University
Autonomous Negotiating Teams
Principal Investigators' Meeting, Oct. 19, 2001
Outline
Overview of our approach
Ants - Challenge Problem (Sensor Domain)




Graph Models
Results on average case complexity
Distributed CSP model
Phase Transitions --- 3D view (communication
vs. complexity vs. overall performance)
Conclusions and Future Work
Overview of Approach
Overall theme --- exploit impact of structure
on computational complexity

Identification of domain structural features






tractable vs. intractable subclasses
phase transition phenomena
backbone
balancedness
…
Goal:
 Use findings in both the design and operation of
distributed platform
 Principled controlled hardness aware systems
IISI, Cornell University
ANTs Challenge Problem
Multiple doppler radar sensors track moving
targets
Energy limited sensors
Communication
constraints
Distributed
environment
Dynamic problem
IISI, Cornell University
Domain Models
Start with a simple graph model
Successively refine the model in stages to
approximate the real situation:




Static weakly-constrained model
Static constraint satisfaction model with
communication constraints
Static distributed constraint satisfaction model
Dynamic distributed constraint satisfaction model
Goal: Identify and isolate the sources of
combinatorial complexity
IISI, Cornell University
Initial Assumptions
Each sensor can only track one target
at a time
3 sensors are required to track a target
IISI, Cornell University
Initial Graph Model
Bipartite graph G = (S U T, E)
S is the set of sensor nodes, T the set
of target nodes, E the edges indicating
which targets are visible to a given
sensor
Decision Problem: Can each target be
tracked by three sensors?
IISI, Cornell University
Initial Graph Model
Target visibility
Sensor
nodes
Graph Representation
Target
nodes
IISI, Cornell University
Initial Graph Model
The initial model presented is a bipartite
graph, and this problem can be solved using
a maximum flow algorithm in polynomial time
Results incorporated into framework
developed by Milind Tambe’s group at ISI,
USC
Joint work in progress
Sensor
Target
nodes
nodes
Sensor Communication
Constraints
IISI, Cornell University
initial model
+ communication edges
Possible solution
In the graph model, we now have additional edges between
sensor nodes
IISI, Cornell University
Constrained Graph Model
communication links
sensors
targets
possible solution
Complexity and Phase
Transition Phenomena
IISI, Cornell University
Worst-Case Complexity
Decision Problem: Can each target be
tracked by three sensors which can
communicate together ?
We have shown that this constraint
satisfaction problem (CSP) is NPcomplete, by reduction from the
problem of partitioning a graph into
isomorphic subgraphs
What about averagecase complexity?
IISI, Cornell University
Description of Experiments
Create
communication
graph
based
on
range
Combine
Create
Create
Place
Start
visibility
sensors
visibility
the
with
communication
square
and
graph
graph
targets
area
based
based
with
randomly
and
on
on visibility
radar
unit
radar
sides
in
range
range
area
graphs
RRC
sensor
target
C
R
IISI, Cornell University
Description of Experiments
Determine if all targets can be tracked
by three communicating sensors
sensor
target
Limit cases
IISI, Cornell University
Phase Transition w.r.t.
Communication Range:
Probability( all targets tracked )
Experiments with a configuration of 9 sensors and 3
targets such that there is a communication channel
between two sensors with probability p
Insights into the design
and operation of sensor
networks w.r.t.
communication range
Communication edge probability p
Special case:
all targets are
visible to all
sensors
IISI, Cornell University
Phase Transition w.r.t.
Radar Detection Range
Probability( all targets tracked )
Experiments with a configuration of 9 sensors and 3
targets such that each sensor is able to detect targets
within a range R
Insights into the design
and operation of sensor
networks w.r.t.
radar detection range
Special case:
all nodes can
communicate
Normalized Radar Range R
Communication vs. Radar Range
vs. Performance
The full picture
IISI, Cornell University
Communication vs. Radar Range vs. Performance
Radar range R: from 0 (no target is covered) to 1 (all targets covered)
Comm. range C: from 0 (no sensors communicates) to 1 (all sensors comm.)
Probability of tracking all targets
5 targets, 15 sensors
5 targets, 17 sensors
IISI, Cornell University
Distributed Computational Model
In a Distributed Constraint Satisfaction
Problem (DCSP), variables and constraints
are distributed among multiple agents. It
consists of:



A set of agents 1, 2, … n
A set of CSPs P1, P2, … Pn , one for each agent
There are intra-agent constraints and inter-agent
constraints
IISI, Cornell University
DCSP Models
We can represent the sensor tracking
problem as a DCSP using dual
representations:


One with each sensor as a distinct agent
One with a distinct tracker agent for each
target
IISI, Cornell University
DCSP Models
With the DCSP models, we study both
per-node computational costs as well as
inter-node communication costs
DCSP algorithms: DIBT (Hamadi et al.)
and ABT (Yokoo et al.)
IISI, Cornell University
Target Tracker Agents
Intra-agent constraints :

Each target must be tracked by 3 communicating
sensors to which it is visible
Inter-agent constraints:

No common sensors between targets
s1
s2
s3
s4
s5
s6
s7
s8
s9
t1
1 0
1
x
x
x
x
x
1
t2
x
x
x
1
1
1
x
x
x
t3
x
x
x
1
x
x
1
1
0
IISI, Cornell University
Sensor Agents
Intra-agent constraints :

Sensor must track at most 1 visible target
Inter-agent constraints:

3 communicating sensors should track each target
t1
t2
t3
t4
s1
x
0
x
1
s2
x
x
x
1
s3
x
x
x
1
s4
1 0
x
0
Inter-agent
constraints => All
sensors seeing a target
must know which sensors
are tracking the target
IISI, Cornell University
Comparison of the two models
Model
Sensor-centered Target-centered
Agents
Vars for intra constraints
Vars for inter constraints
Intra-agent constraints
Inter-agent constraints
Sensors
Targets
Targets
Only one target
3 comm. sensors
Targets
Sensors
-3 comm. sensors
Only one target
Sensor-centered: To check the inter-agent constraints,
sensors must maintain one variable for every target they
can track, that indicates which 3 sensors are tracking it
Target-centered: Does not need additional variables for
the inter-agent constraints
IISI, Cornell University
Communication vs. Radar Range
vs. Computation
Computational Complexity: total
computation cost for all agents
Communication Complexity: total
number of messages sent by all agents
Communication range / Sensor (radar) range
provides 3rd dimension.
These measures can vary for the same
problem when using different DCSP models
Average Complexity
Probability of Tracking
(target-centered)
Mean computational cost
X
• 5 targets and 17 sensors
IISI, Cornell University
104
Average Complexity
Probability of Tracking
(target-centered)
Mean communication cost
1000
• 5 targets and 17 sensors
IISI, Cornell University
Implicit versus Explicit
Constraints
IISI, Cornell University
Agent ordering can
make a difference !
Explicit constraint: no two targets can be tracked
by same sensor (e.g. t2, t3 cannot share s4 and t1,
t3 cannot share s9)
Implicit constraint: due to a chain of explicit
constraints: (e.g. implicit constraint between s4 for t2
and s9 for t1 )
s1
s2
s3
s4
s5
s6
s7
s8
s9
t1
1 0
1
x
x
x
x
x
1
t2
x
x
x
1
1
1
x
x
x
t3
x
x
x
1
x
x
1
1
0
Communication Cost for Implicit
Constraints
Explicit constraints can be resolved by direct
communication between agents
Resolving Implicit constraints may require
long communication paths through multiple
agents  scalability problems
s1
s2
s3
s4
s5
s6
s7
s8
s9
t1
1 0
1
x
x
x
x
x
1
t2
x
x
x
1
1
1
x
x
x
t3
x
x
x
1
x
x
1
1
0
Future Work
IISI, Cornell University
Structure
Further study structural issues as they
occur in the Sensor domain e.g.:



effect of balancing
backbone (insights into critical resources)
refinement of phase transition notions
considering additional parameters
(concepts introduced in previous PI meeting)
IISI, Cornell University
Dynamic DCSP Model
Further refinement of the model:
incorporate target mobility
The graph topology changes with time
What are the complexity issues when
online distributed algorithms are
used?
IISI, Cornell University
Purely Local Computation Models
We are also exploring local computation
methods for target tracking.
(I.e. communication cannot be used
for global computation.)
We are drawing on an analogy to
physical models.
(energy function minimization approach)
Summary
IISI, Cornell University
Summary
Introduced graph-based models capturing
the ANTs challenge domain
Results on the tradeoffs between:
Computation, Communication, Radar range,
and Performance.
Results enable a more principled and
efficient design of distributed sensor networks.
Extensions:


additional structural issues for the sensor domain
complexity issues in distributed and dynamic settings
Collaborations / Interactions
ISI: Analytic Tools to Evaluate Negotiation
Difficulty

Design and evaluation of SAT encodings for
CAMERA’s scheduling task.
ISI: DYNAMITE

Formal complexity analysis DCSP model (e.g.,
characterization of tractable subclasses).
UMASS: Scalable RT Negotiating Toolkit

Analysis of complexity of negotiation protocols.
IISI, Cornell University
The End