The beachcombers' problem: walking and searching with mobile robots

DOI10.1016/J.TCS.2015.09.011MaRDI QIDQ896140zbMATH OpenOpenAlexFDO

Authors Jurek Czyzowicz, Leszek Gąsieniec, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmmobile robotsschedulesearchingoffline algorithmtwo-speed robots

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Agent technology and artificial intelligence (68T42) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We introduce and study a new problem concerning the exploration of a geometric domain by mobile robots. Consider a line segment $[0,I]$ and a set of $n$ mobile robots $r_1,r_2,\mathrm{...},r_n$ placed at one of its endpoints. Each robot has a {em searching speed} $s_i$ and a {em walking speed} $w_i$, where $s_i<w_i$. We assume that each robot is aware of the number of robots of the collection and their corresponding speeds. At each time moment a robot $r_i$ either walks along a portion of the segment not exceeding its walking speed $w_i$ or searches a portion of the segment with the speed not exceeding $s_i$. A search of segment $[0,I]$ is completed at the time when each of its points have been searched by at least one of the $n$ robots. We want to develop {em mobility schedules} (algorithms) for the robots which complete the search of the segment as fast as possible. More exactly we want to maximize the {em speed} of the mobility schedule (equal to the ratio of the segment length versus the time of the completion of the schedule). We analyze first the offline scenario when the robots know the length of the segment that is to be searched. We give an algorithm producing a mobility schedule for arbitrary walking and searching speeds and prove its optimality. Then we propose an online algorithm, when the robots do not know in advance the actual length of the segment to be searched. The speed $S$ of such algorithm is defined as $S=in{f}_{I_L}S(I_L)$ where $S(I_L)$ denotes the speed of searching of segment $I_L=[0,L]$. We prove that the proposed online algorithm is 2-competitive. The competitive ratio is shown to be better in the case when the robots' walking speeds are all the same.

Recommendations

• The beachcombers' problem: walking and searching with mobile robots
• Beachcombing on strips and islands
• The beachcombers' problem: walking and searching from an inner point of a line
• Linear search by a pair of distinct-speed robots
• Linear search by a pair of distinct-speed robots

Cites work

• scientific article; zbMATH DE number 4110447 (Why is no real title available?)
• An annotated bibliography on guaranteed graph searching
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Collaborative search on the plane without communication
• Competitive Algorithms for Layered Graph Traversal
• Competitive Online Approximation of the Optimal Search Ratio
• Exploring Unknown Environments
• Exploring an unknown graph
• Fast collaborative graph exploration
• How to learn an unknown environment. I
• Map construction of unknown graphs by multiple agents
• Multi-target ray searching problems
• Network exploration by silent and oblivious robots
• On the linear search problem
• On utilizing speed in networks of mobile agents
• Online algorithms: a survey
• Online graph exploration algorithms for cycles and trees by multiple searchers
• Online searching with turn cost
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• Shortest paths without a map
• The beachcombers' problem: walking and searching with mobile robots
• The theory of search games and rendezvous.
• Theory of optimal search
• Worst-case optimal exploration of terrains with obstacles

Cited in

(6)

• Linear search by a pair of distinct-speed robots
• The beachcombers' problem: walking and searching from an inner point of a line
• Lower bounds for shoreline searching with 2 or more robots
• The beachcombers' problem: walking and searching with mobile robots
• Linear search by a pair of distinct-speed robots
• Beachcombing on strips and islands

This page was built for publication: The beachcombers' problem: walking and searching with mobile robots

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