Home›Search in geometric domains›Search, evacuation and patrolling›Linear search (cow path)›Evacuation›Chauffeuring a crashed robot

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.

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Competitive ratio

\(e\) exits

0 open · 1 results

unknown \(4+2\pi\) vs —

One exit + one exit

0 open · 1 results

unknown \(5\) vs —

Two exits + two exits

0 open · 1 results

unknown \(6.6\) vs —

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.