Competitive Online Searching for a Ray in the Plane

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



PDF
Thumbnail PDF

File

DagSemProc.06421.5.pdf
  • Filesize: 236 kB
  • 19 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive Online Searching for a Ray in the Plane. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.06421.5

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$.
Keywords
  • Online motion planning
  • competitive analysis
  • ray search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail