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)