Abstract

Abstract: In this paper, 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.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.