Search in geometric domains
Robots with unit speed move continuously in a known domain (a line, rays, a disk, a polygon) to find a target or an exit whose position is unknown.
The measure is worst-case time: for search on unbounded domains, the competitive ratio (time divided by the distance to the target); for evacuation of a bounded domain, the time until the last robot reaches the exit. The questions are exact constants, the price of weaker communication, and the price of faults.
Robots start together (at the origin of a line or rays, or at the centre of a disk or polygon) and move with at most unit speed. A target (or exit) lies at an unknown point; a robot recognises it only when it reaches it. Robots know the domain. In search the task ends when the first robot reaches the target; in evacuation it ends when the last robot reaches the exit. Robots exchange information either only when they meet (face-to-face) or instantly at any distance (wireless); some models allow one-way communication.
How the axes work. As in the other models, level 0 assumes nothing and higher levels are stronger assumptions.
How the assumptions fit together
From the cow path to evacuation
Bellman posed the linear search problem in 1963 and Beck studied it in 1964, with the target placed according to a known probability distribution Bellman 1963 Beck 1964 (as reported by Czyzowicz et al. 2021). Baeza-Yates, Culberson and Rawlins recast it as searching an unbounded domain where each probe costs "proportional to the distance of the next probe position relative to our current position": doubling the turning point (their linear spiral search) finds a point at distance \(d\) within \(9d\) steps, and no algorithm does better up to lower-order terms Baeza-Yates et al. 1993. Kao, Reif and Tate call it the cow-path problem Kao et al. 1996. Group search sends several robots, and evacuation, posed for a disk by Czyzowicz et al. at DISC 2014, ends only when the last robot reaches the exit Czyzowicz et al. 2014. Their trade-off is between "spreading sufficiently the robots so that they can find the exit point fast in parallel" and "not to spread them too far" Czyzowicz et al. 2014. Czyzowicz, Georgiou and Kranakis survey this line of work Czyzowicz et al. 2019.
Communication
Once several robots search, what they can tell each other changes the answer. The first evacuation paper already compared robots that talk only when they meet with robots that broadcast at any distance, and showed "a clear separation between the local and the wireless communication models" Czyzowicz et al. 2014. Later work considered asymmetric senders and receivers, whose evacuation time on the disk lies strictly between the two Czyzowicz et al. 2021 Georgiou et al. 2022. Communication is therefore the first axis of the model.
Unreliable and unequal robots
Two further axes describe how the robots differ from the ideal. Faults: Czyzowicz et al. introduced crash-faulty searchers that fail to report the target Czyzowicz et al. 2016 (as reported by Kupavskii & Welzl 2018) and studied Byzantine searchers that may also lie Czyzowicz et al. 2021. Since a lower bound for crash faults is also a lower bound for Byzantine faults, the two form a scale Kupavskii & Welzl 2018. Speeds: patrolling Czyzowicz et al. 2011 and two-robot search on the line Chrobak et al. 2015 Bampas et al. 2019 gave the robots different maximum speeds, and it turned out that a slow robot can help or be useless depending on the speed ratio Bampas et al. 2019.
Randomness and the problem axes
Randomness is the fourth axis: Kao, Reif and Tate showed that a randomized cow, whose expected distance is compared with the distance to a goal fixed in advance, does "almost twice as good as is possible with a deterministic algorithm" Kao et al. 1996. Everything else differs from problem to problem and is kept on the problems as their own axes: the domain (line, \(m\) rays, disk, polygons, a fence), the number of robots, what counts as success (first arrival, last arrival, the queen's arrival, fetching a treasure), and how many exits there are.
Notation
Symbols of this model; the notation page has every model and the general conventions.
| Symbol | Meaning | Papers write | Used in |
|---|---|---|---|
| \(k\) | number of robots | \(n\) | whole model |
| \(f\) | maximum number of faulty robots (crash or Byzantine) | whole model | |
| \(m\) | number of rays sharing an endpoint | whole model | |
| \(e\) | number of exits on the boundary | Chauffeuring a crashed robot | |
| \(d\) | distance from the origin to the target on a line or on rays | whole model | |
| \(x\) | position of the target on the line | whole model | |
| \(R\) | radius of the disk (results are usually stated for \(R=1\)) | whole model | |
| \(v,\ v_i\) | speeds of robots (robot \(i\) moves at speed at most \(v_i\)) | \(s\), \(s_i\) | whole model |
| \(\alpha\) | known arc distance along the boundary (between two exits, or between the treasure and the exit) | \(d\) | whole model |
| \(r\) | communication range of wireless robots | whole model | |
| \(\ell\) | length of the fence (segment or circle) | Patrolling | |
| \(L\) | known distance between the starting points of two robots | Evacuation | |
| \(p\) | index of an \(\ell_p\) norm | Evacuation | |
| \(w\) | weight of the second robot's arrival time in weighted group search | Evacuation | |
| \(\sigma\) | number of servants in priority evacuation (the queen and \(\sigma\) servants, \(k=\sigma+1\) robots) | \(n\) | Evacuation |
Assumption axes
Each axis below says where the assumption comes from and why the community studies it. Every axis is a scale. Level 0 assumes nothing; each higher level is a stronger assumption, which makes a problem easier. Values on the same level are alternatives that do not imply each other. An algorithm designed for weaker assumptions works under stronger ones; a lower bound proved under stronger assumptions holds under weaker ones.
Communication
Czyzowicz et al. defined evacuation from the disk in two communication models, "non-wireless (or local)", where robots exchange information only at the same point at the same moment, and wireless, where a broadcast "is instantly acquired by other robots, independently of their current positions" Czyzowicz et al. 2014. Their bounds for two and three robots, and for large \(k\), showed "a clear separation between the local and the wireless communication models" Czyzowicz et al. 2014. The earliest paper in this atlas with mixed abilities is by Czyzowicz et al.: senders transmit wirelessly but receive only face-to-face, and receivers do the opposite; such robots could be cheaper to build, or could be fully wireless robots whose sender or receiver module has failed Czyzowicz et al. 2021. For two robots on the disk, Georgiou, Giachoudis and Kranakis showed that the sender/receiver evacuation time lies strictly between the face-to-face and wireless times Georgiou et al. 2022. Not every setting separates the levels: for two robots of very different speeds on the line, "wireless communication offers no advantage over communication by meeting" Bampas et al. 2019.
Formal definitions
- 0face-to-face
- Face-to-face: two robots exchange information only when they are at the same point at the same time.
- 1sender/receiver
- Sender/receiver: one robot can only transmit and the other only receive, instantly at any distance.
- 2wireless
- Wireless: every robot can send messages to every other robot instantly at any distance.
Faults
Fault-tolerant group search began on the line in 2016. Czyzowicz, Kranakis, Krizanc, Narayanan and Opatrny introduced crash-type faults, robots that "fail to report the target although visiting its location" Czyzowicz et al. 2016 (as described by Kupavskii & Welzl 2018). At ISAAC 2016 Czyzowicz et al. studied Byzantine robots, which "can fail to report the target even after reaching it, or ... make malicious claims about having found the target", so that search ends only when the reliable robots have "sufficient verification" Czyzowicz et al. 2021. Because a lower bound for crash faults is also a lower bound for Byzantine faults, the two levels form a scale Kupavskii & Welzl 2018. Unreliable robots had appeared a year earlier in patrolling: at ISAAC 2015 Czyzowicz et al. studied patrollers that "fail to comply with their patrolling duties", so that only visits by reliable robots count Czyzowicz et al. 2017. The faults were later carried over to evacuation from the disk Czyzowicz et al. 2017. Georgiou, Giachoudis and Kranakis note that "fault tolerant group search has been considered less extensively mainly due to the complexity of the resulting optimization problem" Georgiou et al. 2022.
Formal definitions
- 0Byzantine
- Up to \(f\) robots may lie: stay silent when they find the target, or claim to have found it where it is not.
- 1crash faults
- Up to \(f\) robots may fail to detect or to report the target when they pass over it.
- 2no faults
- Every robot detects and reports the target.
Speeds
In the classical problems all searchers move at unit speed Baeza-Yates et al. 1993 Czyzowicz et al. 2014. Czyzowicz, Gąsieniec, Kosowski and Kranakis studied patrolling of a segment and a circle by agents with distinct maximum speeds at ESA 2011 and conjectured that simple partition strategies are optimal Czyzowicz et al. 2011. The conjecture was later disproved Kawamura & Kobayashi 2015 (as summarised by Kawamura & Soejima 2020). For search, Chrobak et al. solved two-robot evacuation on the line when the slower robot has at least a third of the faster one's speed Chrobak et al. 2015, and Bampas et al. covered every speed ratio Bampas et al. 2019. Czyzowicz et al. motivate such variants by noting that "it is quite natural to consider collaborative tasks in which the participant robots have different capabilities" Czyzowicz et al. 2018; disk evacuation with two speeds followed Lamprou et al. 2020.
Formal definitions
- 0distinct speeds
- Each robot \(i\) has its own maximum speed \(v_i\), known to all.
- 1equal speeds
- All robots move at most at unit speed.
Randomness
Bellman and Beck posed linear search with a target drawn from a known distribution and the expected time as the measure Bellman 1963 Beck 1964 (as reported by Czyzowicz et al. 2021). In the competitive formulation the target is adversarial, and every deterministic strategy has ratio at least 9 (Theorem 2.1 of Baeza-Yates et al. 1993). Kao, Reif and Tate gave the first randomized algorithm for the cow-path problem on several paths, SmartCow, which picks a random permutation of the paths and a random initial distance; for every goal at distance \(d\) fixed in advance its expected distance is at most \(c\,d + O(1)\), with \(c \approx 4.5911\) on the line, and they proved this optimal on the line Kao et al. 1996. They note that Gal had given many of these results earlier in a game-theoretic setting Kao et al. 1996. Randomization thus improves the ratio on the line by about half, which is why the catalogue keeps it as an axis. Most of the group-search and evacuation literature in this atlas is deterministic.
Formal definitions
- 0deterministic
- Trajectories are fixed functions of the information received.
- 1randomized
- Trajectories may depend on random choices; the measure is the expected competitive ratio against an oblivious adversary.
Problems in this model
Problem familySearch, evacuation and patrolling
Find a target, or get every robot out through an exit, at an unknown point of a known continuous domain. Evacuation builds on linear search (the cow-path problem).