Chauffeuring a crashed robot: e exits

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.

no assumptions

\(e\) exits

standard settingverified

Competitive ratio: unknown

A constant competitive ratio, at most \(4+2\pi \approx 10.28\), for any number of exits.

Assumed (added on the last edge are outlined)

nothing

Not assumed

Exits\(e \ge 1\) exitsCommunicationface-to-face: robots exchange information only when they meetFaultsup to \(f\) Byzantine robots (may lie or stay silent)Speedsrobots may have different maximum speedsRandomnessdeterministic

Formal definitions of this setting

Exits: \(e\) exits: \(e\ge1\) exits at unknown boundary points.
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

Competitive ratio · evacuation time divided by the optimal time

unknown

No lower bound recorded.

lower boundnone known

introductory—

current best

\(4+2\pi\)

Pattanayak et al. 2019

Results, in order of publication

Pattanayak et al. 2019 current best

Competitive ratio \(4+2\pi\)

Introductory and current best.

Open questions

None recorded for this variant.

Notes

Results supplied by the catalogue owner (a co-author).

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.