Chauffeuring a crashed robot
An active robot must find a crashed robot inside a disk and carry it, at reduced speed, to one of \(e\) exits on the boundary.
Problem statement and measuresexpand
A unit disk has \(e\ge1\) exits at unknown points of its boundary. An active robot starts at the centre and moves at speed \(v\); a crashed robot lies at an unknown point inside the disk. The active robot must find it and carry it, at speed \(v'<v\), to an exit; it learns the exits' positions once it reaches the boundary. Ratio is the competitive ratio of the evacuation time (the time until every robot has reached an exit) against the optimum.
Measures: Competitive ratio, evacuation time divided by the optimal time.
One exit
verifiedCompetitive ratio at most 5 with one exit.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Exits: one exit
- Exactly one exit.
- Communication: face-to-face
- Face-to-face: two robots exchange information only when they are at the same point at the same time.
- Faults: Byzantine
- Up to \(f\) robots may lie: stay silent when they find the target, or claim to have found it where it is not.
- Speeds: distinct speeds
- Each robot \(i\) has its own maximum speed \(v_i\), known to all.
- Randomness: deterministic
- Trajectories are fixed functions of the information received.
What is known
Results, in order of publication
Open questions
None recorded for this variant.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.