On-Line Navigation, WS 2012/13, Prof. Rolf Klein
%%%%%%%%%
Overview%%
%%%%%%%%%
Navigation Algorithms and Lower Bounds
==========================
---------------------
Touch Sensor, No Vision
---------------------
(A) Correct, but no performance guarantee
all algorithms of type "search"
*Shannon mouse
escapes from labyrinth in grid environment (walls between grid cells)
- no memory
- can mark each cell with 1 of 4 symbols; read/write
*Pledge algorithm
escapes from polygonal polygon
- no memory, except
- angle counter; reset, add/subtract turning angle
*Goal finder
finds target point t starting from point s amidst polygonal
obstacles in the plane, by generating a word
leading to t from s and every obstacle vertex
- compass pointing to t
- notices when t is reached
- memory plus computation (Turing machine)
@ Definition: Competitive strategy
(B) Correct + performance guarantee
(B1) type "explore"
*DFS
explores arbitrary cellular environment
on closed tour from given start cell
- Turing machine
Performance: visits each cell twice ==> 2-competitive
Lower bound: no other strategy achieves smaller bound
*SmartDFS
explores simple cellular environment (=no holes!)
on closed tour from given start cell
- Turing machine
Performance: #steps <= #cells + 1/2 #edges - 3
4/3 - competitive
Lower bound: 7/6
* Tethered Graph Exploration (piecemeal is related)
starts from s, visits all edges/vertices of given graph
of known radius r, and returns
unit length edges
- recognizes vertices and adjacent edges (instead of touch sensor)
- Turing machine
- attached to s by cable of fixed length (1+alpha)*r
Performance: C (#edges + #vertices/alpha) steps
8 + 16/alpha - competitive
Generalizations possible (weighted edges, radius unknown)
(B2)
type "search"
*BUG 1
finds target point t starting from s in polygonal environment
- knows coordinates of t and current position
- Turing machine
Performance: path length <= |st| + 3/2*sum of perimeters of obstacles
intersecting circle of radius |st| around t
Lower bound: max (|st| + sum of perimeters of above obstacles - delta, any given K)
*BUG2 (similar)
Performance: |st| + sum of n_i/2 * perimeter of obstacle U_i
intersecting circle of radius |st| around t,
where n_i = #cuts of line segment st with boundary of U_i
*Doubling
finds target point t in unknown position on two halflines meeting in
start point s
- precise distance measurement
- Turing machine
Performance: 9-competitive; optimal among deterministic strategies
Can be generalized to m-way search: 2*m^m/(m-1)^(m-1) +1
(*Hyperbolic Dove Tailing
finds endpoint of one of m lists of unknown length
- recognizes last element of list (instead of touch sensor)
- re-visiting previous list position (even in different list) : free of charge
- advancing list position: 1 step
- Turing machine
Performance: If set of list lengths l_i known in descending order:
#steps <= min i*l_i =: omega (optimal)
If list length unknown: #steps <= C*omega*ln(min(omega,m)) )
*Searching for a line at known location, n units away, amidst rectangular obstacles
of hight/width >=1
- Turing machine
- precise length measurement
Performance: c*sqrt(n) - competitive; optimal
simulates local vision by doubling
@ Visibility; some facts on Art Gallerie and Lower envelopes
------------
Perfect Vision
------------
All algorithms correct plus performance guarantee
(B1) type "search"
*Looking around a corner
finds extension of invisble edge, starting from the other edge
- Turing machine
- precise distance and angle measurement
Performance: 1.21218 - competitive; optimal
*CAB (searching for the nearest kernel point in a star-shaped polygon)
-Turing machine
- precise distance and angle measurement
Performance: 5.3331 - competitive
Lower bound: sqrt(2)
uses tight bound on self-approaching curves
*Searching for a point in a street
finds an s-to-t path in a simple polygon with vertices s and t
whose s-to-t boundary chains are mutually weekly visible (=street)
-Turing machine
- precise distance and angle measurement
Performance: sqrt(2) - competitive; optimal
In general simple polygons, no constant competitive factor can be
achieved, but:
@Definition Optimal Search Path/ Search Competitive
*PolyExplore+Doubling
- Turing-machine
- precise distance and angle measurement
Performance: 213-search-competitive
(B2) type "explore"
*PolyExplore
explores an unknown simple polygon on a tour through
given boundary point s.
Path length compared with length of optimum watchman path.
- Turing-machine
- precise distance and angle measurement
Performance: 18 sqrt(2) + 1 = 26,5 - competitive
uses tight upper bound on relative angle hull
(Lower bound: 1.2825)
*Exploring a scene with n rectangular obstacles
- Turing machine
- precise distance and angle measurement
Lower bound: c*sqrt(n)*length of optimum watchman tour
k-Server Problem
===========
move one of k servers to request position in
metric space; minimize total path length
*General k-server problem
- shortest paths to request positions known
- no charge for serving, only for moving
(Performance: 2k-1 - competitive)
Lower bound: k- competitive
*DoubleCoverage (moves k servers on the line)
Performance: k - competitive; optimal
*SlackCoverage (moves two servers in the plane)
Performance: 3 - competitive
Game Theory
=========
@ Finite Two-Person Zero-Sum Games without Random Moves
*If complete information: White or Black have winning strategy,
or both can enforce impasse
Minimax principle holds; value exists
*With incomplete information: Using mixed strategies
(= distributions on pure strategies) ensures that
Minimax principle holds; value exists
Example related to on-line navigation: Merels (MÃ¼hle)
Both players can enforce impasse
Paradigms applied
============
Doubling
Dovetailing
Randomization (game theory)
Analytical methods used
===============
linear recursions (door in wall)
differential equations (looking around corner, shopping arcade)
structural geometric properties (angle hull, self-approaching curves)
potential function method (Double Coverage, Slack Coverage)