The beachcombers' problem: walking and searching with mobile robots

DOI10.1016/J.TCS.2015.09.011zbMATH Open1332.68256arXiv1304.7693OpenAlexW2491829515MaRDI QIDQ896140FDOQ896140

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)

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.

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

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

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)

Cites Work

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

Cited In (1)

• 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)