License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06421.5
URN: urn:nbn:de:0030-drops-8687
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/868/
Go to the corresponding Portal

Eubeler, Andrea ; Fleischer, Rudolf ; Kamphans, Tom ; Klein, Rolf ; Langetepe, Elmar ; Trippen, Gerhard

Competitive Online Searching for a Ray in the Plane

pdf-format:
06421.LangetepeElmar.Paper.868.pdf (0.2 MB)

Abstract

We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the flashlight. In order to pick it up, the searcher moves to the origin of the light beam. We compare the length of the path of the searcher to the shortest path to the goal.

First, we give a search strategy for a special case of the ray search---the window shopper problem---,
where the ray we are looking for is perpendicular to a known ray. Our strategy achieves a competitive factor of $1.059ldots$, which is optimal. Then, we consider rays in arbitrary position in the plane. We present an online strategy that achieves a factor of $22.513ldots$, and give a lower bound of $2pi,e=17.079ldots$.





BibTeX - Entry

@InProceedings{eubeler_et_al:DagSemProc.06421.5,
  author =	{Eubeler, Andrea and Fleischer, Rudolf and Kamphans, Tom and Klein, Rolf and Langetepe, Elmar and Trippen, Gerhard},
  title =	{{Competitive Online Searching for a Ray in the Plane}},
  booktitle =	{Robot Navigation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/868},
  URN =		{urn:nbn:de:0030-drops-8687},
  doi =		{10.4230/DagSemProc.06421.5},
  annote =	{Keywords: Online motion planning, competitive analysis, ray search}
}

Keywords: Online motion planning, competitive analysis, ray search
Collection: 06421 - Robot Navigation
Issue Date: 2007
Date of publication: 07.02.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI