This problem investigates waking up a collection of sleeping robots spread out over a 2D plane. All but one of the robots are initially asleep and the awake robot attempts to wake up all of the robots by moving to their locations and activating their power switch. Once a robot has been awakened it can help wake up the other robots. The goal is to find a schedule that permits the robots to be awakened in the minimum amount of time.
This web page is a visualization of four such algorithms for awakening schedule creation. Click one of the algorithm buttons below and then click play to watch the swarm awaken.
In Order Algorithm. This algorithm uses the ID numbers of the robots in order; i.e., sends robot 0 to awaken robot 1 then 0 awakens 2 and 1 awakens 3. When any robot is awakened or reaches its target it claims the robot with the next sequential unclaimed ID number.
Greedy Claim Algorithm. The Greedy algorithms make locally optimal decisions. In this case when a robot is awakened or needs a new target it claims the nearest unclaimed sleeping robot and goes to awaken it.
Greedy Delayed Target Choice. The Greedy claim algorithm doesn't consider that one robot may in face be able to reach a target before another robot before the latter robot claims it. The Delayed Target Choice algorithm lets each awake robot accumulate movement tokens until it has enough to reach the closest sleeping target. Only then does it add this target to the awakening schedule.
Constant Factor Algorithm. The constant-factor approximation algorithm developed by Arkin et al. boasts a an O(1)-approximation to the optimal wake-up schedule time. This algorithm divides the space around each robot into pie shaped sectors and the robot visits only the closest robot in each sector in order of increasing distance from its starting position. This visualization uses eight sectors and follows the Greedy Delayed Target Choice model to resolve conflicts when two robots which to awaken the same target.