Transcript TZ.soda07.pps

Deterministic Rendezvous,
Treasure Hunts
and
Strongly Universal Exploration Sequences
Amnon Ta-Shma
Uri Zwick
Tel Aviv University
The Rendezvous problem
Two robots are activated, at different
times and in different locations, in an
unknown environment
Should both follow deterministic
sequences of instructions
The instructions should guarantee that the two
robots meet in a polynomial number of steps,
after the activation of the second robot
The unknown environment
An undirected (cubic) graph.
Graph and its size uknown to robots
2
Vertices are undistinguishable
Exits are numbers.
No consistently assumed
2
No pebbles allowed
Robots meet when they are in the
same vertex at the same time
Robots move synchronously
1
2
3
1
Instructions – memoryless model
Each robot gets a
sequence
σ = σ1 σ2 σ3…  {0,1,2,3}*.
In the i-th step,
if σi=0, stay in place,
otherwise, take exit no. σi.
1
2
2
2
3
1
2
2
σ = 3202…
Instructions – backtracking model
When a robot enters a vertex,
it learns the number of the
edge used to enter the vertex.
Action taken may now
depend on entrance labels
In particular,
backtracking is possible
1
2
2
2
3
1
2
2
σ = 3202…
ρ = 122…
Parameters
n – size of the environment
l – length (in bits) of smaller label
τ – difference in activation time
Results
Dessmark, Fraigniaud, Pelc (2003)
Dessmark, Fraigniaud, Kowalski, Pelc (2006)
Rendezvous after O*(n5(τl)1/2+n10l) steps
Kowalski, Malinowski (2006)
Rendezvous after O*(n15+l3) steps
when backtracking allowed
Our result
Rendezvous after O*(n5l) steps
Additional results
The previous results guarantee a rendezvous
after a polynomial number of steps.
But, we do not know how to compute
these steps in polynomial time…
We give the first polynomial steps
and polynomial time solution in the
backtracking model
Symmetry breaking
If the two robots are identical,
no deterministic solution
is possible
To break the symmetry, the
robots are assigned distinct
labels L1 and L2.
1
1
2
1
2
2
1
1
2
2
In this talk we assume that
the labels are 0 and 1.
2
1
Randomized rendezvous
If randomization is allowed,
then achieving a rendezvous is easy:
Each robot simply performs a random walk.
Expected number of steps before the two
robots meet is O(n3)
Coppersmith, Tetali, Winkler (1993)
Alternatively, one of the robots performs a
random walk while the other stays put.
Universal Traversal Sequences (UTS)
A sequence σ  {1,2,3}* is a UTS for (cubic)
graphs of size n if for every connected (cubic) graph
of size at most n, every labeling and every starting
point, the walk defined by σ covers the graph.
Aleliunas, Karp, Lipton, Lovasz, Rackoff (1979)
A random sequence of length O(d2n3log n) is,
with high probability, a UTS for d-regular
graphs of size n.
No efficient construction known!
A natural solution That doesn’t quite work…
Robot 0 stays put
Robot 1 executes U1U2U4…U2k…
where Un is a UTS for graphs of size n
Fails as robot 0 may be activated when
robot 1 is executing Uk, where k >> n.
Robot 0 activated
Strongly Universal Traversal
Sequences (SUTS)
An infinite sequence σ  {1,2,3}ω is a SUTS for
(cubic) graphs with cover time p(n), if for any n≥1,
any contiguous subsequence of σ of length p(n) is a
UTS for (cubic) graphs of size n.
Main open problem: Do SUTS exist?
Treasure hunt
The version of the rendezvous problem
in which one of the robots is static.
Treasure may be activated after the seeking robot.
In the memoryless model,
equivalent to the existence of SUTS.
We obtain an efficient solution when
backtrackings are allowed.
Solution of rendezvous problem
A robot with label
uses the sequence:
The k-th block of robot 1:
Run U2k twice, then stay put for 2u2k steps.
Stay put for u2k steps between any two steps above.
Theorem: The two robots meet after O(|Un|4) steps,
where n is the size of the environment.
A more complicated solution guarantees
a meeting after O*(|Un|) steps,
where Un are the best UTS currently known
Universal Exploration Sequences (UES)
Instructions are now
interpreted as offsets
UES are analogous to UTS
Theorem: (Reingold ’05)
UESs (of polynomial length)
can be constructed in
polynomial time.
1
2
2
3
2
3
1
1
3
2
2
σ = 1202…
Strongly Universal Exploration
Sequences (SUES)
Suppose that Un=u1u2…un is a UES for
graphs of size nα, for 0<α<1.
Suppose that U2i is a prefix of U2j for i<j.
Theorem: Sn is a SUES
Open problems
Strongly Universal Traversal Sequences ???
Efficient construction of
Universal Traversal Sequences
???
Solution of rendezvous problem
A robot with label
uses the sequence:
0
0