Mobility Matters
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 measurescollapse
OStart: two robots at the centre, exit unknownTogether to the boundary, then along itOne robot crashes; the other picks it upFinal: carried to the exit at speed v' = v/2
Chauffeuring: an active robot must find a crashed robot inside a unit disk and carry it, at a lower speed \(v' < v\), to an exit on the boundary Pattanayak et al. 2019. The animation runs the simplest algorithm in the setting of the arXiv version: two robots walk together from the centre to the boundary and along it; when one crashes (at time \(w\)), the other picks it up on the spot and carries it along the same route at speed \(v' = v/2\) (red) until it finds the exit, within time \(w + (1 + 2\pi - w)/v'\).

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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

A rescue robot in a round room must carry a broken robot to a door; carrying it slows the rescuer down. In chauffeuring the room is a unit disk, the points at distance at most 1 from its centre; the edge of the room is the boundary, the circle of radius 1; and the doors are one or more exits at unknown points of the boundary. The rescuer is the active robot: it starts at the centre and moves at speed \(v\). The broken robot is a crashed robot, one that has stopped moving and communicating; it lies somewhere inside the disk. The active robot must carry the crashed robot to an exit, that is, move together with it, at the slower speed \(v' < v\). Performance is the competitive ratio: the evacuation time (the time until every robot has reached an exit) divided by the best time possible if everything were known. The catalogue's bounds for this formulation (competitive ratio at most \(4 + 2\pi\) for any number of exits) were supplied by the catalogue owner and have not been checked against a published text; the ideas below come from the setting of the arXiv version of Pattanayak et al. 2019, where two robots start together at the centre, one exit is hidden on the boundary, and one robot may crash at some time \(w\).

1AlgorithmMove together, so nobody is far from the crash One exit → Pattanayak et al. 2019

Take speed \(v = 1\); carrying a robot one unit of distance takes time \(1/v'\).

  1. Both robots walk together from the centre to the boundary.
  2. They walk together along the boundary until they find the exit, then leave.
  3. If one crashes on the way, the other picks it up on the spot and continues the same route, carrying it at speed \(v'\).
Why it works and what it costs. Without a crash the robots reach the boundary in time 1 and walk at most the whole boundary, of length \(2\pi\), so they leave by time \(1 + 2\pi\). If one crashes at time \(w\), the rest of the route, of length at most \(1 + 2\pi - w\), is walked at the slow speed, so the time is at most \(w + (1 + 2\pi - w)/v'\) Pattanayak et al. 2019. It does not use the second robot to search elsewhere; Pattanayak et al. 2019 give better algorithms in which the robots search in opposite directions, as in two-robot evacuation.

Why it matters. It is the baseline every chauffeuring algorithm must beat, and it shows the trade-off: staying together makes a crash cheap but makes the search slow.

2Lower boundExplore the whole boundary and carry from the centre One exit → Pattanayak et al. 2019

Let one robot crash immediately, at the centre. The active robot alone must search the boundary, and the adversary, an opponent who chooses the exit position, keeps the exit at a point the active robot has not yet visited, so it must walk the whole boundary, of length \(2\pi\). In addition, the crashed robot has to be carried at least the radius, from the centre to the boundary, which takes time at least \(1/v'\).

Why it holds. Carrying from the centre to the boundary and walking around the boundary are separate stretches of time, so every algorithm needs at least \(2\pi + 1/v'\) in this case Pattanayak et al. 2019 (Theorem 1 there, which writes the slowdown as a factor). Compared with the fault-free optimum \(1 + 2\pi/3 + \sqrt3 \approx 4.826\) Czyzowicz et al. 2014, a crash can cost a lot.

Why it matters. It isolates the two unavoidable costs, searching alone and carrying slowly, that every chauffeuring bound balances.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Competitive ratio
\(e\) exits standard
A constant competitive ratio, at most \(4+2\pi \approx 10.28\), for any number of exits.
unknown \(4+2\pi\) vs —
One exit
Competitive ratio at most 5 with one exit.
unknown \(5\) vs —
Two exits
Competitive ratio at most 6.6 with two exits.
unknown \(6.6\) vs —

What the community started looking at

Chauffeuring asked how the cost of evacuation changes when a robot must be carried rather than merely informed, and how the number of exits affects the competitive ratio Pattanayak et al. 2019.

Variant of Evacuation

Evacuation where one robot has crashed inside the disk: the active robot must first find it, then carry it, more slowly, to an exit.

All settings

The assumption tree (3 settings, 0 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Competitive ratio); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Exits › Communication › Faults › Speeds › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Exits

0\(e \ge 1\) exits1one exit1two exits

Pattanayak, Ramesh and Mandal introduced chauffeuring at ALGOSENSORS 2019: a crashed robot "stops moving and sending messages altogether", and instead of abandoning it the non-faulty robot carries it to the exit at a reduced speed Pattanayak et al. 2019. That paper has two robots, wireless communication and a single exit on the boundary of the disk Pattanayak et al. 2019. Two exits at unknown boundary points come from the two-exit evacuation problem of Pattanayak et al. Pattanayak et al. 2018. The catalogue's statement with \(e \ge 1\) exits, and its bounds for one, two and any number of exits, were supplied by the catalogue owner; they have not been checked against a published text.

Formal definitions
0\(e\) exits
\(e\ge1\) exits at unknown boundary points.
1one exit
Exactly one exit.
1two exits
Exactly two exits.

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