Reaching a target in the plane with no information

DOI10.1016/J.IPL.2018.04.006MaRDI QIDQ1799599zbMATH OpenOpenAlexWikidataFDO

Authors Andrzej Pelc

Publication date 19 October 2018

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.07145

zbMATH Keywords

Euclidean planeexplorationlowest costmobile agentspeed

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: A mobile agent has to reach a target in the Euclidean plane. Both the agent and the target are modeled as points. In the beginning, the agent is at distance at most $D>0$ from the target. Reaching the target means that the agent gets at a {em sensing distance} at most $r>0$ from it. The agent has a measure of length and a compass. We consider two scenarios: in the {em static} scenario the target is inert, and in the {em dynamic} scenario it may move arbitrarily at any (possibly varying) speed bounded by $v$. The agent has no information about the parameters of the problem, in particular it does not know $D$, $r$ or $v$. The goal is to reach the target at lowest possible cost, measured by the total length of the trajectory of the agent. Our main result is establishing the minimum cost (up to multiplicative constants) of reaching the target under both scenarios, and providing the optimal algorithm for the agent. For the static scenario the minimum cost is $Theta((logD+logfrac1r)D^2/r)$, and for the dynamic scenario it is $Theta((logM+logfrac1r)M^2/r)$, where $M=max(D,v)$. Under the latter scenario, the speed of the agent in our algorithm grows exponentially with time, and we prove that for an agent whose speed grows only polynomially with time, this cost is impossible to achieve.

Recommendations

• Deterministic treasure hunt in the plane with angular hints
• Deterministic Polynomial Approach in the Plane
• Deterministic polynomial approach in the plane
• Navigation Without Perception of Coordinates and Distances
• Searching in the plane

Cites work

• Competitive complexity of mobile robot on-line motion planning problems
• Competitive Online Approximation of the Optimal Search Ratio
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• scientific article; zbMATH DE number 6297684 (Why is no real title available?)
• On the two-dimensional cow search problem
• Searching for an axis-parallel shoreline
• Searching in the plane
• The game of cops and robbers on graphs
• The theory of search games and rendezvous.

Cited in

(7)

• Advice complexity of treasure hunt in geometric terrains
• Deterministic treasure hunt in the plane with angular hints
• Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs
• Impact of knowledge on the cost of treasure hunt in trees
• Treasure hunt in graph using pebbles
• Symmetry breaking in the plane. Rendezvous by robots with unknown attributes
• Almost-optimal deterministic treasure hunt in arbitrary graphs

This page was built for publication: Reaching a target in the plane with no information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1799599)