Greedy localization

We show that finding localization plans with optimal worst-case execution time for localization tasks with short-range sensors in discretized domains is NP-hard, even within a logarithmic factor. This strongly suggests that finding and executing localization plans with optimal or even near-optimal worst-case execution time cannot be done in polynomial time. Greedy localization methods interleave planning and execution and keep the amount of planning performed between moves small. We analyze one such greedy localization method, the delayed planning architecture, and show that it can find and execute localization plans in polynomial time and thus substantially reduce the sum of planning and execution time compared to localization methods that find localization plans with optimal or near-optimal execution time. We also characterize how suboptimal the execution time of its localization plans can be. These results provide a first step towards analyzing other greedy localization methods.

Authors

• Craig A. Tovey
• Sven Koenig

Keywords

• Search methods
• Robot sensing systems
• Mobile robots
• Polynomials
• Contracts
• Orbital robotics
• Educational institutions
• Delay effects
• Uncertainty
• US Government
• NSF Award
• Local Method
• Time Task
• Localization Task
• Sum Of Time
• Planning Time
• Worst-case Time
• Logarithmic Factor
• Current Position
• Set Of Covariates
• State Machine
• Position In Space
• Mobile Robot
• Problem Instances
• Planning Methods
• Sensor Noise
• Task Domain
• Solid Theoretical Foundation
• Set Cover Problem