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. 2021a). 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. 2019d.
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. 2021d 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 detect the target Czyzowicz et al. 2019c and studied Byzantine searchers that may also lie Czyzowicz et al. 2021a. Since a lower bound for crash faults is also a lower bound for Byzantine faults, the two form a scale Kupavskii & Welzl 2021. Speeds: patrolling Czyzowicz et al. 2011 and two-robot search on the line Chrobak et al. 2015 Bampas et al. 2019b 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. 2019b.
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, on rays or in the plane) | 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 |
| \(u\) | speed of a moving target, which moves at constant speed toward or away from the origin | \(v\); Coleman et al. 2026a write \(u\) for the evasiveness \(1/(1-u)\) | Linear search (cow path), Search for a moving target |
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. 2021d. 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. 2019b.
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: a faulty robot follows its trajectory and "is indistinguishable from a reliable robot, except that a faulty robot does not detect the target while visiting its location" Czyzowicz et al. 2019c. 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. 2021a. Because a lower bound for crash faults is also a lower bound for Byzantine faults, the two levels form a scale Kupavskii & Welzl 2021. 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. 2017e. The faults were later carried over to evacuation from the disk Czyzowicz et al. 2017c. 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 robots with distinct maximum speeds at ESA 2011, and proved the proportional partition strategy optimal on a segment for two robots Czyzowicz et al. 2011. Kawamura and Kobayashi report that Czyzowicz et al. conjectured it optimal for every number of robots, and disproved this with six robots Kawamura & Kobayashi 2015; see also 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. 2019b. 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. 2020b; 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. 2021a). 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).
Linear search (cow path)
Papers
102 papers are cited in this model, listed under each problem that cites them, oldest first. Filter the references by this model →
Linear search (cow path) 21 papers
- Bellman 1963 An Optimal Search cited in text
- Beck 1964 On the linear search problem posed the problem
- Baeza-Yates et al. 1993 Searching in the Plane current best, lower bound
- Kao et al. 1996 Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem current best, lower bound
- Czyzowicz et al. 2015a The Beachcombers' Problem: Walking and searching with mobile robots further reading
- Chrobak et al. 2015 Group Search on the Line introductory result
- Bampas et al. 2019b Linear Search by a Pair of Distinct-Speed Robots current best, lower bound
- Czyzowicz et al. 2019c Search on a Line with Faulty Robots current best
- Czyzowicz et al. 2021a Search on a line by Byzantine robots current best
- Angelopoulos & Panagiotou 2017 preprint Optimal strategies for weighted ray search further reading
- Brandt et al. 2020b Wireless evacuation on m rays with k searchers cited in text
- Czyzowicz et al. 2017d Linear Search with Terrain-Dependent Speeds further reading
- Kupavskii & Welzl 2021 Lower bounds for searching robots, some faulty lower bound
- Jawhar 2020 Bike Assisted Linear Search and Evacuation further reading
- Sun et al. 2020 Better Upper Bounds for Searching on a Line with Byzantine Robots cited in text
- Czyzowicz et al. 2021d Group Evacuation on a Line by Agents with Different Communication Abilities cited in text
- Czyzowicz et al. 2021e Search and evacuation with a near majority of faulty agents cited in text
- Jawhar & Kranakis 2021 Robot Evacuation on a Line Assisted by a Bike cited in text
- Bansal et al. 2023 A nearly tight lower bound for the d-dimensional cow-path problem further reading
- Coleman & Morales-Ponce 2025 Linear Search with Probabilistic Detection and Variable Speeds further reading
- Ma & Yin 2026 preprint On the Cyclic Assumption of the Cow-Path Search Algorithm lower bound
Evacuation 64 papers
- Baeza-Yates & Schott 1995 Parallel searching in the plane introductory result
- Fekete et al. 2010 Evacuation of Rectilinear Polygons further reading
- Xu & Qin 2013 Strategies of Groups Evacuation from a Convex Region in the Plane further reading
- Czyzowicz et al. 2014 Evacuating Robots via Unknown Exit in a Disk posed the problem, introductory result, current best, lower bound
- Wei et al. 2014 On-Line Strategies for Evacuating from a Convex Region in the Plane further reading
- Chrobak et al. 2015 Group Search on the Line current best, lower bound
- Czyzowicz et al. 2015c Wireless Autonomous Robot Evacuation from Equilateral Triangles and Squares introductory result, current best, lower bound
- Czyzowicz et al. 2020d Evacuating Robots from a Disk Using Face-to-Face Communication other result, lower bound
- Jiang et al. 2015 An On-Line Strategy of Groups Evacuation from a Convex Region in the Plane further reading
- Liu et al. 2015 Online Strategies for Evacuating from a Convex Region by Groups in the Plane further reading
- Bampas et al. 2019b Linear Search by a Pair of Distinct-Speed Robots current best, lower bound
- Borowiecki et al. 2025 Discrete evacuation in graphs with multiple exits further reading
- Czyzowicz et al. 2018a Evacuating two robots from multiple unknown exits in a circle cited in text
- Georgiou et al. 2017 Searching with Advice: Robot Fence-Jumping further reading
- Georgiou et al. 2019 Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models current best, lower bound
- Georgiou et al. 2021 Treasure evacuation with one robot on a disk cited in text
- Lamprou et al. 2020 Fast two-robot disk evacuation with wireless communication current best, lower bound
- Wei et al. 2016 Evacuating from an Unknown Affected Area further reading
- WEI et al. 2016 Competitive Strategies for Evacuating from an Unknown Affected Area cited in text
- Brandt et al. 2017 Collaboration Without Communication: Evacuating Two Robots from a Disk other result
- Brandt et al. 2020b Wireless evacuation on m rays with k searchers current best, lower bound
- Chuangpishit et al. 2020b Evacuating equilateral triangles and squares in the face-to-face model current best, lower bound
- Czyzowicz et al. 2017c Evacuation from a Disc in the Presence of a Faulty Robot current best, lower bound
- Kupavskii & Welzl 2021 Lower bounds for searching robots, some faulty lower bound
- Li & Xu 2017 Online Strategies for Evacuating from a Convex Region in the Plane further reading
- Pattanayak et al. 2018 Evacuating Two Robots from Two Unknown Exits on the Perimeter of a Disk with Wireless Communication current best, lower bound
- Chuangpishit et al. 2018b Average Case - Worst Case Tradeoffs for Evacuating 2 Robots from the Disk in the Face-to-Face Model cited in text
- Chuangpishit et al. 2020a A Multi-Objective Optimization Problem on Evacuating 2 Robots from the Disk in the Face-to-Face Model; Trade-Offs between Worst-Case and Average-Case Analysis further reading
- Czyzowicz et al. 2020a Priority evacuation from a disk: the case of \(n = 1, 2, 3\) introductory result, current best, lower bound
- Czyzowicz et al. 2020b Priority evacuation from a disk: the case of \(n \ge 4\) current best, lower bound
- Acharjee et al. 2019 Lower Bounds for Shoreline Searching With 2 or More Robots cited in text
- Bagheri et al. 2019 Evacuation of Equilateral Triangles by Mobile Agents of Limited Communication Range current best
- Czyzowicz et al. 2019a Energy Consumption of Group Search on a Line cited in text
- Czyzowicz et al. 2019d Group Search and Evacuation further reading
- Czyzowicz et al. 2019e Group search of the plane with faulty robots further reading
- Czyzowicz et al. 2021f Time-energy tradeoffs for evacuation by two robots in the wireless model further reading
- Disser & Schmitt 2019 Evacuating Two Robots from a Disk: A Second Cut current best
- Georgiou et al. 2023b Optimal circle search despite the presence of faulty robots current best, lower bound
- Dobrev et al. 2020b Improved Lower Bounds for Shoreline Search further reading
- Georgiou & Lucier 2023 Weighted group search on a line & implications to the priority evacuation problem current best, lower bound
- Nakamura et al. 2021 Evacuation from various types of finite two-dimensional square grid fields by a metamorphic robotic system further reading
- Pattanayak et al. 2020a Collaborative Evacuation of Mobile Robots further reading
- Coleman et al. 2021 Message Delivery in the Plane by Robots with Different Speeds further reading
- Czyzowicz et al. 2021d Group Evacuation on a Line by Agents with Different Communication Abilities current best, lower bound
- Czyzowicz et al. 2021e Search and evacuation with a near majority of faulty agents current best
- Devillez et al. 2021 Two-Agent Tree Evacuation cited in text
- Georgiou et al. 2023a Evacuating from \(\ell_p\) unit disks in the wireless model cited in text
- Jawhar & Kranakis 2021 Robot Evacuation on a Line Assisted by a Bike further reading
- Leonardos et al. 2023 Byzantine fault tolerant symmetric-persistent circle evacuation introductory result, current best
- Coleman et al. 2023 Delivery to Safety with Two Cooperating Robots further reading
- Georgiou et al. 2022 Evacuation from a Disk for Robots with Asymmetric Communication current best, lower bound
- Georgiou & Jang 2026 Triangle evacuation of 2 agents in the wireless model & the power of choosing a starting point current best, lower bound
- Liu et al. 2022 Online Algorithm for Evacuating Crashed Faulty Robots from A Square further reading
- Behrouz et al. 2025 Byzantine fault-tolerant protocols for (n,f)-evacuation from a circle current best
- Georgiou et al. 2024 Overcoming probabilistic faults in disoriented linear search cited in text
- Jawhar & Kranakis 2025a Bike-assisted evacuation of robots on a line with asymmetric S/R communication cited in text
- Conley & Georgiou 2025 Multi-agent Disk Inspection further reading
- Georgiou et al. 2025b Multi-agent Search-Type Problems on Polygons cited in text
- Georgiou & Wang 2025 Weighted group search on the disk & improved lower bounds for priority evacuation current best, lower bound
- Kranakis 2024 Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search further reading
- Georgiou et al. 2025c preprint Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents further reading
- Georgiou 2026 Optimal Average Disk-Inspection via Fermat’s Principle further reading
- Coleman et al. 2026b preprint Search and Rescue on the Plane further reading
- Kaminski et al. 2026 preprint Going in Circles: Collaborative Multi-Robot Treasure Hunting cited in text
Patrolling 15 papers
- Czyzowicz et al. 2011 Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds posed the problem, introductory result, lower bound
- Kawamura & Kobayashi 2015 Fence patrolling by mobile agents with distinct speeds other result, lower bound
- Dumitrescu et al. 2014 On Fence Patrolling by Mobile Agents current best, other result
- Kawamura & Soejima 2020 Simple strategies versus optimal schedules in multi-agent patrolling other result
- Czyzowicz et al. 2017e When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots current best, lower bound
- Chuangpishit et al. 2018a Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits further reading
- Das et al. 2019c Patrolling on Dynamic Ring Networks further reading
- Haeupler et al. 2019 Optimal Strategies for Patrolling Fences current best, lower bound
- Morales-Ponce 2022 Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots further reading
- Afshani et al. 2021 Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency further reading
- Oshrat et al. 2020 Adversarial Fence Patrolling: Non-Uniform Policies for Asymmetric Environments further reading
- Amir et al. 2023 preprint Patrolling Grids with a Bit of Memory further reading
- Coleman & Morales-Ponce 2023 The Snow Plow Problem: Perpetual Maintenance by Mobile Agents on the Line further reading
- Georgiou et al. 2025a The Fagnano Triangle Patrolling Problem further reading
- Chen et al. 2024 Improved Approximation Algorithms for Patrol-Scheduling with Min-Max Latency Using Multiclass Minimum Spanning Forests further reading
Chauffeuring a crashed robot 3 papers
- Czyzowicz et al. 2014 Evacuating Robots via Unknown Exit in a Disk cited in text
- Pattanayak et al. 2018 Evacuating Two Robots from Two Unknown Exits on the Perimeter of a Disk with Wireless Communication cited in text
- Pattanayak et al. 2019a Chauffeuring a Crashed Robot from a Disk posed the problem, current best
Search with segment visibility 4 papers
- Baeza-Yates et al. 1993 Searching in the Plane cited in text
- Acharjee et al. 2019 Lower Bounds for Shoreline Searching With 2 or More Robots cited in text
- Dobrev et al. 2020b Improved Lower Bounds for Shoreline Search cited in text
- Kranakis 2026 preprint Searching the Plane in the Segment Visibility Model posed the problem, current best, lower bound
Search for a moving target 10 papers
- Alpern & Gal 2003 The Theory of Search Games and Rendezvous posed the problem, current best, lower bound
- Chrobak et al. 2015 Group Search on the Line cited in text
- Czyzowicz et al. 2020f Searching for a non-adversarial, uncooperative agent on a cycle further reading
- Czyzowicz et al. 2021d Group Evacuation on a Line by Agents with Different Communication Abilities lower bound
- Coleman et al. 2022 Line Search for an Oblivious Moving Target introductory result, current best, lower bound
- Coleman et al. 2026a The power of knowledge in linear search for an escaping target current best, lower bound
- Kranakis 2024 Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search further reading
- Jawhar & Kranakis 2025b Linear Search for Capturing an Oblivious Mobile Target in the Sender/Receiver Model current best, lower bound
- Jawhar & Kranakis 2026b Linear Search for Capturing a Moving Target by Two Robots in the F2F Model current best, lower bound
- Jawhar & Kranakis 2026a preprint Capturing a Moving Target on Star Graphs by Two Communicating Mobile Agents current best, lower bound