An On-Line Algorithm for Improving Performance in Navigation

Recent papers have shown optimally-competitive on-line strategies for a robot traveling from a point s to a point t in certain unknown geometric environments. We consider the question: Having gained some partial information about the scene on its first trip from s to t, can the robot improve its performance on subsequent trips it might make? This is a type of on-line problem where a strategy must exploit partial information about the future (e. g. , about obstacles that lie ahead). For scenes with axis-parallel rectangular obstacles where the Euclidean distance between s and t is n, we present a deterministic algorithm whose average trip length after t trips, k/spl les/n, is O(/spl radic/n/k) times the length of the shortest s-t path in the scene. We also show that this is the best a deterministic strategy can do. This algorithm can be thought of as performing an optimal tradeoff between search effort and the goodness of the path found. We improve this algorithm so that for every i/spl les/n, the robot's ith trip length is O(/spl radic/n/t) times the shortest s-t path length. A key idea of the paper is that a tree structure can be defined in the scene, where the nodes are portions of certain obstacles and the edges are "short" paths from a node to its children. The core of our algorithms is an on-line strategy for traversing this tree optimally. >

Authors

• Avrim Blum
• Prasad Chalasani

Keywords

• Navigation
• Layout
• Robot kinematics
• Computer science
• Euclidean distance
• Cities and towns
• Tree data structures
• Path Length
• Tree Structure
• Trip Length
• Lower Bound
• Results Of This Paper
• Shortest Path
• Total Distance
• Constant Factor
• Edge Length
• End Of Step
• Short Path
• Cost Of Procedure
• Robot Motion
• Total Steps
• Search Phase
• Tree Edges
• Robot Path
• Path Tree
• Competitive Ratio