Transcript How to Lighten the Heavy Tails of Sequential Decoding

Impact of Structure on Complexity
Carla Gomes
[email protected]
Bart Selman
[email protected]
Cornell University
Intelligent Information Systems Institute
Kickoff Meeting
AFOSR MURI
May 2001
Outline
• I - Overview of our approach
• II - Structure vs. complexity – results on a abstract domain
• III - Examples of Application Domains
• IV - Conclusions
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
Part I
Structure vs. Complexity
Quasigroup Completion Problem
(QCP)
Given a matrix with a partial assignment of colors
(32%colors in this case), can it be completed so
that each color occurs exactly once in each row /
column (latin square or quasigroup)?
Example:
32% preassignment
Structural features of instances provide
insights into their hardness namely:
– Phase transition phenomena
– Backbone
– Inherent structure and balance
Are all the Quasigroup Instances
(of same size) Equally Difficult?
Time performance:
150
1820
165
What is the fundamental difference between instances?
Are all the Quasigroup Instances
Equally Difficult?
Time performance:
150
Fraction of preassignment:
1820
165
35%
40%
50%
Median Runtime (log scale)
Complexity of Quasigroup
Completion
Critically constrained area
Underconstrained
area
20%
Overconstrained area
42%
50%
Fraction of pre-assignment
Complexity
Graph
Phase
Transition
Fraction of unsolvable cases
Phase transition
from almost all solvable
to almost all unsolvable
Almost all solvable
area
Almost all unsolvable
area
Fraction of pre-assignment
Quasigroup Patterns and Problems
Hardness
Hardness is also controlled by structure of
constraints, not just percentage of holes
Rectangular Pattern
Aligned Pattern
Tractable
Balanced Pattern
Very hard
Bandwidth
Bandwidth: permute rows and columns of QCP to minimize
the width of the diagonal band that covers all the holes.
Fact: can solve QCP in time exponential in bandwidth
swap
Random vs Balanced
Random
Balanced
After Permuting
Random
bandwidth = 2
Balanced
bandwidth = 4
Structure vs. Computational Cost
Computational
cost
Balanced QCP
QCP
Aligned/ Rectangular
QCP
% of holes
Balancing makes the instances very hard - it increases bandwith!
Backbone
Backbone is the shared structure of all the
solutions to a given instance.
This instance has
4 solutions:
Backbone
Total number of backbone variables: 2
Phase Transition in the Backbone
(only satisfiable instances)
• We have observed a transition in the
backbone from a phase where the size of
the backbone is around 0% to a phase with
backbone of size close to 100%.
• The phase transition in the backbone is
sudden and it coincides with the hardest
problem instances.
(Achlioptas, Gomes, Kautz, Selman 00, Monasson et al. 99)
New Phase Transition in Backbone
% of Backbone
% Backbone
Sudden phase transition in Backbone
Computational
cost
Fraction of preassigned cells
Why correlation between backbone and
problem hardness?
• Small backbone is associated with lots of solutions,
widely distributed in the search space, therefore it is
easy for the algorithm to find a solution;
• Backbone close to 1 - the solutions are tightly
clustered, all the constraints “vote” to push the
search into that direction;
• Partial Backbone - may be an indication that
solutions are in different clusters that are widely
distributed, with different clauses pushing the search
in different directions.
Structural Features
The understanding of the structural
properties that characterize problem
instances such as phase transitions,
backbone, balance, and bandwith
provides new insights into the practical
complexity of computational tasks.
Examples of Application
Domains
Fiber Optic Networks
• Wavelength Division Multiplexing (WDM)
is the most promising technology for the
next generation of wide-area backbone
networks.
• WDM networks use the large bandwidth
available in optical fibers by partitioning
it into several channels, each at a different
wavelength.
Fiber Optic Networks
Nodes
connect point to point
fiber optic links
Fiber Optic Networks
Nodes
connect point to point
fiber optic links
Each fiber optic link supports a
large number of wavelengths
Nodes are capable of photonic switching
--dynamic wavelength routing -which involves the setting of the wavelengths.
Routing in Fiber Optic Networks
preassigned channels
Input Ports
1
Output Ports
1
2
2
3
3
4
4
Routing Node
How can we achieve conflict-free routing in each node of the network?
Dynamic wavelength routing is a NP-hard problem.
QCP Example Use: Routers in
Fiber Optic Networks
Dynamic wavelength routing in Fiber Optic Networks can be
directly mapped into the Quasigroup Completion Problem.
•each channel cannot be repeated in the same input port
(row constraints);
• each channel cannot be repeated in the same output
port (column constraints);
1
2
3
4
Output ports
Output Port
1
2
3
4
Input ports
Input Port
CONFLICT FREE
LATIN ROUTER
(Barry and Humblet 93, Cheung et al. 90, Green 92, Kumar et al. 99)
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
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 edges
sensors
targets
possible solution
Complexity and Phase
Transition Phenomena of
Sensor Domain
IISI, Cornell University
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
Average Case complexity
and Phase Transition
Phenomena
IISI, Cornell University
Phase Transition w.r.t.
Communication Level:
Probability( all targets tracked )
Experiments with a random 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 level
Communication edge probability p
IISI, Cornell University
Phase Transition w.r.t.
Radar Detection Range
Probability( all targets tracked )
Experiments with a random 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
Normalized Radar Range R
Distributed Model
IISI, Cornell University
Distributed CSP Model
• In a distributed CSP (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 interagent constraints
IISI, Cornell University
DCSP Model
• We can represent the sensor tracking
problem as DCSP using dual
representations:
– One with each sensor as a distinct agent
– One with a distinct tracker agent for each
target
Sensor Agents
• Binary variables associated with each target
• 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
Target Tracker Agents
• Binary variables associated with each sensor
• Intra-agent constraints :
– Each target must be tracked by 3 communicating
sensors to which it is visible
• Inter-agent constraints:
– A sensor can only track one target
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
Implicit versus Explicit
Constraints
•
Explicit constraint:
(correspond to the explicit domain
constraints)
– no two targets can be tracked by same sensor (e.g. t2, t3 cannot
share s4 and t1, t3 cannot share s9)
– three sensors are required to track a target (e.g. s1,s3,s9 for t1)
•
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 Costs 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
Conclusions and
Research Directions
Future directions
• Study structural issues and inpact on
complexity, as they occur in the
distributed environments e.g.:
– effect of balancing;
– backbone (insights into critical resources);
– refinement of phase transition notions
considering additional parameters;
DCSP Model
• With the DCSP model, we plan to study
both per-node computational costs as well
as inter-node communication costs
• We are in the process of applying known
DCSP algorithms to study issues
concerning complexity and scalability
Summary
• We have made considerable progress in our
understanding of the nature of hard computational
problems - structure matters!
• We have harnessed a variety of mechanisms with proven
impact on time-critical problem solving.
• A rich spectrum of applications taking advantage of
these new methods are on the horizon in planning,
scheduling and many other areas.
• Future focus on Dynamic Distributed models
The End