Local exploration: Online algorithms and a probabilistic framework

Volkan Isler, Sampath Kannan, Kostas Daniilidis

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations


Mapping an environment with an imaging sensor becomes very challenging if the environment to be mapped is unknown and has to be explored. Exploration involves the planning of views so that the entire environment is covered. The majority of implemented mapping systems use a heuristic planning while theoretical approaches regard only the traveled distance as cost. However, practical range acquisition systems spend a considerable amount of time for acquisition. In this paper, we address the problem of minimizing the cost of looking around a corner, involving the time spent in traveling as well as the time spent for reconstruction. Such a local exploration can be used as a subroutine for global algorithms. We prove competitive ratios for two online algorithms. Then, we provide two representations of local exploration as a Markov Decision Process and apply a known policy iteration algorithm. Simulation results show that for some distributions the probabilistic approach outperforms deterministic strategies.

Original languageEnglish (US)
Pages (from-to)1913-1920
Number of pages8
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - Dec 9 2003
Event2003 IEEE International Conference on Robotics and Automation - Taipei, Taiwan, Province of China
Duration: Sep 14 2003Sep 19 2003


Dive into the research topics of 'Local exploration: Online algorithms and a probabilistic framework'. Together they form a unique fingerprint.

Cite this