Back to Search
Start Over
Linear Search by a Pair of Distinct-Speed Robots
- Source :
- Algorithmica, Algorithmica, Springer Verlag, 2019, 81 (1), pp.317-342. ⟨10.1007/s00453-018-0447-0⟩, Springer US, Structural Information and Communication Complexity 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 19-21, 2016, Revised Selected Papers, 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), Jul 2016, Helsinki, Finland. pp.195-211, ⟨10.1007/978-3-319-48314-6_13⟩, Structural Information and Communication Complexity ISBN: 9783319483139, SIROCCO
- Publication Year :
- 2019
- Publisher :
- HAL CCSD, 2019.
-
Abstract
- Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{17}+4\approx 8.123$$\end{document}17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.
- Subjects :
- Engineering
General Computer Science
Computer science
different speeds
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
Bang-bang robot
linear search
01 natural sciences
Article
Computer Science::Robotics
Position (vector)
mobile robots
0202 electrical engineering, electronic engineering, information engineering
Cartesian coordinate robot
Point (geometry)
Computer vision
[INFO]Computer Science [cs]
Online algorithm
Simulation
Linear search
021103 operations research
business.industry
Applied Mathematics
Mobile robot
Computer Science Applications
010201 computation theory & mathematics
group search
Moment (physics)
Line (geometry)
Robot
020201 artificial intelligence & image processing
Artificial intelligence
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
business
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-319-48313-9
- ISSN :
- 01784617 and 14320541
- ISBNs :
- 9783319483139
- Database :
- OpenAIRE
- Journal :
- Algorithmica, Algorithmica, Springer Verlag, 2019, 81 (1), pp.317-342. ⟨10.1007/s00453-018-0447-0⟩, Springer US, Structural Information and Communication Complexity 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 19-21, 2016, Revised Selected Papers, 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), Jul 2016, Helsinki, Finland. pp.195-211, ⟨10.1007/978-3-319-48314-6_13⟩, Structural Information and Communication Complexity ISBN: 9783319483139, SIROCCO
- Accession number :
- edsair.doi.dedup.....b62afd8d3305e4d11dec7475c72464e0