Robots Evacuating a Unit Disk

X

X

X

X

X

X

X

X

Algorithm Steps:

Steps:
1. The robots go to the perimeter at the same angle.
2. They travel opposite directions once they reach the perimeter. e.g, If Robot 1 goes clockwise, Robot 2 goes counter-clockwise.
3. The robots move along the perimeter until one of them finds the exit, in which case they will intercept the other's path (in the case of Face-To-Face communication). The robot which finds the exit will calculate a path (chord) across the circle s.t. the distance of its chord is equal to the arc that the other would have travelled along the perimeter in the time it takes to cross the chord.
4. The robots meet at the end of the point of interception and travel directly back to the exit.

R1 intercepting R2 after finding the exit.

Algorithm referenced in:
Jurek Czyzowicz et al. (2014). Evacuating Robots via Unknown Exit in a Disk. Proceedings of DISC 2014, LNCS 8784, pp. 122–136, 2014
Jurek Czyzowicz et al. (2015). Evacuating Robots From a Disk Using Face-To-Face Communication. Proceedings of CIAC, 2015 p. 140-152, 2015.

X

Algorithm Steps:

This algorithm takes two arguments, B(X, Φ); X being the arc length travelled before taking a detourThe robot will go away from the perimeter at an angle Φ, and travel toward and stop at the vertical axis of origin. If it has not been intercepted or notified about the exit at the point, it will return to the perimeter., and Φ being the angle to take the detour at. This algorithms shares the same first three steps as algorithm A.

Steps (Algorithm B):
1. The robots follow the same trajectory as they would in Algorithm A, for a certain amount of time X.
2. If the robots have travelled the distance X without being notified of the exit, they initiate the detour phase at angle Φ relative to the tangent to the circle at that point.
3. If, after the detour phase the exit has not been found, the robots continue moving around the perimeter and follow the normal interception methods.

Both robots take a detour at angle Φ after searching for distance X.

This method takes advantage of the detour phase to provide a slightly faster evacuation time in the event that the exit is found quickly. The robot which finds the exit will travel less distance to intercept the other if it is currently in its detour phase, thus lowering the overall time. The only time which this does not apply is for a smaller set of exit positions, which are observed after the detour phase.

Algorithm referenced in:
Jurek Czyzowicz et al. (2014). Evacuating Robots via Unknown Exit in a Disk. Proceedings of DISC 2014, LNCS 8784, pp. 122–136, 2014
Jurek Czyzowicz et al. (2015). Evacuating Robots From a Disk Using Face-To-Face Communication. Proceedings of CIAC, 2015 p. 140-152, 2015.

X

Algorithm Steps:

This algorithm takes three arguments, C(X, Φ, λ); X being the arc length travelled before taking a triangular detourThe robot will go away from the perimeter at an angle Φ for time λ, and then travel DIRECTLY toward and stop at the vertical axis of origin. If it has not been intercepted or notified about the exit at the point, it will return to the perimeter using the shortest path back to the point it came from., Φ being the angle to take the detour at, and λ being the time for at which the robot starts to travel directly to the central axis from its detour. This algorithm shares the same first three steps as Algorithm A.

Steps (Algorithm C):
1. The robots follow the same trajectory as they would in Algorithm A, for a certain amount of time X.
2. If the robots have travelled the distance X without being notified of the exit, they initiate the triangular detour phaseThe robot will go away from the perimeter at an angle Φ for time λ, and then travel DIRECTLY toward and stop at the vertical axis of origin. If it has not been intercepted or notified about the exit at the point, it will return to the perimeter using the shortest path back to the point it came from. at angle Φ, for time λ.
3. If, after the triangular detour phase the exit has not been found, the robots continue moving around the perimeter and follow the normal interception methods.

Both robots take a detour at angle Φ after searching for distance X, follow it for λ seconds, then go directly toward the center.

This method takes advantage of the triangular detour phase to provide a slightly faster evacuation time in the event that the exit is found quickly. The robot which finds the exit will travel less distance to intercept the other if it is currently in its detour phase, thus lowering the overall time. The only time which this does not apply is for a smaller set of exit positions, which are observed after the detour phase.

Algorithm referenced in:
Jurek Czyzowicz et al. (2014). Evacuating Robots via Unknown Exit in a Disk. Proceedings of DISC 2014, LNCS 8784, pp. 122–136, 2014
Jurek Czyzowicz et al. (2015). Evacuating Robots From a Disk Using Face-To-Face Communication. Proceedings of CIAC, 2015 p. 140-152, 2015.

X

Algorithm Steps:

This algorithm takes two arguments, Q(α, β): α being this arc length that the priority robot will take until it makes a small detour, β being the angle (α + β) on the unit disk that the priority robot travels to, creating a chord. After this, the priority robot will travel in the opposite direction, back towards the point where it originally made the detour.

Steps (Algorithm Priority 1):
1. The robots go out to the perimeter at the same angle.
2. The Helper will travel clockwise around the circle until it finds the exit and notifies the priority of its location.
3. The priority will travel counter-clockwise for time α, at which point it will make its detour.
4. The priority will travel to the angle (α + β).
5. The priority will travel clockwise until the exit is found.

Algorithm referenced in:
Jurek Czyzowicz et al (2018). God Save the Queen. In Proceedings of FUN, pp. 16:1–16:20.

X

Algorithm Steps:

This algorithm takes two arguments, Q(α, ρ): α being the angle the priority robot will travel before moving directly across the disk to point ρ, which is the y-value of the point K(α/2, ρ). This is the point where the priority will diverge and travel toward the angle -α/2 on the disk. We will denote the Helpers in this algorithm as S1 and S2, and the priority as P.

Steps (Algorithm Priority 2):
1. S1 and P will go out to the perimeter at angle (π - α). S2 will go out to the perimeter at angle π.
2. S1 travels clockwise until it finds the exit. S2 travels counter-clockwise until ti finds the exit.
3. The priority P will travel counter-clockwise for time α, at which point it will make its detour.
4. The priority will travel to the point K(α/2 + ρ) on the interior of the disk.
5. The priority will then travel to angle (2π - α/2) on the perimeter and wait until the exit is found.

Algorithm referenced in:
Jurek Czyzowicz et al (2018). God Save the Queen. In FUN, pp. 16:1–16:20.

X

Algorithm Steps:

Steps (Algorithm 2 Priority + 1 Helper): In this algorithm, we designate two of the robots as priority, and only one as the Helper. The algorithm terminates when at least one of the priority robots finds the exit. The algorithm takes one argument, Q(α). α is the angle at which one Helper and one priority will travel toward the perimeter. We will denote the Helper as S, and the two priority robots as P1 and P2. 14*pi/9 - 2*sqrt(3)/3
1. The robots S and P1 will travel to the perimeter at angle α.This is usually an angle located between (π, 3π/2) P2 will travel to the perimeter at angle 0.
2. P1 travels counter-clockwise until it finds the exit. P2 travels counter-clockwise until it finds the exit. Finally, S travels clockwise until it finds the exit.

We can show that this algorithm has an upper bound of 3.55 time units for angle α = 14π/9 - 2√3/3. The two worst-cases for the exit location in this algorithm are: 2π - θ for some very small θ, or π - ((6√3 - 2)/9).

1Q1S1Q X

Algorithm Steps:

Coming soon.

Algorithm referenced in:
Jurek Czyzowicz et al (2018). God Save the Queen. In Proceedings of FUN, pp. 16:1–16:20.

Q1S4 X

Algorithm Steps:

Steps (Algorithm 1 Priority + 4 Helper):
1. 2 Helpers will travel to the wall at angle 0. They will each travel 1.309 radians around the perimeter in opposite directions toward angle pi and search until the starting point of the next helpers.
2. 2 Helpers will travel to the wall at 1.309 radians and 4.974 radians respectively, and travel in opposite directions toward angle pi and search until the exit is found.
3. The Priority will wait at the center (0,0) for 1 + pi/2 time.
4. After the Priority has waited, it will travel to the perimeter at angle pi. It then waits at that point (-pi, 0) until the exit is found.

Algorithm referenced in:
Jurek Czyzowicz et al (2018). Priority Evacuation from a Disk Using Mobile Robots. Proceedings of SIROCCO, pages 392-407, 2018.

1Q8S X

Algorithm Steps:

Steps (Algorithm 1 Priority + 4 Helper):
1. 2 Helpers will travel to the wall at angle 0. They will each travel pi/3 radians around the perimeter in opposite directions toward angle pi and search until the starting point of the next helpers.
2. 2 Helpers will travel to the wall at pi/3 radians and 5pi/3 radians respectively, and travel in opposite directions toward angle pi and search until the starting point of the next helpers.
3. 2 Helpers will travel to the wall at pi/2 radians and 3pi/2 radians respectively, and travel in opposite directions toward angle pi and search until the starting point of the next helpers.
4. 2 Helpers will travel to the wall at 2pi/3 radians and 4pi/3 radians respectively, and travel in opposite directions toward angle pi and search until the starting point of the next helpers.
5. The Priority will wait at the center (0,0) for 1 + pi/2 time.
6. After the Priority has waited, it will travel to the perimeter at angle pi. It then waits at that point (-pi, 0) until the exit is found.

Algorithm referenced in:
Jurek Czyzowicz et al (2018). Priority Evacuation from a Disk Using Mobile Robots. Proceedings of SIROCCO, pages 392-407, 2018.