Freeze Tag

The Problem

Imagine a swarm of robots on the plane, such that all but one robot are "asleep" or in stand-by mode.
To awaken a robot, a currently active robot must go to its location on the plane.
Once a sleeping robot is awakened, it may assist in waking other sleeping robots.
Our presentation deck including a more in-depth problem statement can be found here.

The Objective

Assuming general position principle, awaken every robot in the swarm in the shortest possible period of time.
The general case of the Freeze Tag Problem is NP-hard.

Our Solutions

All of the code for our implemented solutions can be found in our git repository at https://github.com/ibanner56/freeze_tag. The code is currently unlicensed, so feel free to do whatever with it.

The Algorithms

While we initially set out to find an efficient solution to the problem, we quickly realized that we were not about to prove P=NP and instead decided to modify our problem statement. Instead we would design and implement several polynomial-time algorithms to approximate the optimal solution. The following are the different algorithms we worked on and their theoretical time complexities:

Algorithm	Theoretical Complexity	Avg. Runtime N = 5	N = 10	N = 100	N = 1000
Lexicographic Brute Force	n!	5 msec	52 msec	> 60000 msec	> 60000 msec
Prim's MST	n^2 * log(n)	17 msec	24 msec	28 msec	716 msec
Greedy by Closest	n^2 * log(n)^2	3 msec	5 msec	23.4 msec	128.8 msec
Alternating Greedy	n^2 * log(n)^2	5 msec	6 msec	22.4 msec	346.4 msec

All runtimes were calculated by averaging several runtimes on an HP Satellite laptop with an Intel i7 family quad-core 2.2GHz processor. The following is a plot of the above runtimes:

Lexicographic Brute Force

This brute force algorithm worked by generating each ordering of points in lexicographic order using an algorithm provided by Dr. Roxanne Canosa. Each lexicographic ordering was treated similarly to a heap in that for any point in the ordering at index k, its two child nodes in the traversal were at 2*k + 1 and 2*k + 2. From this it's simple enough to calculate the distances from each node to its child nodes and compare it to other orderings.

Prim's MST

This algorithm used an augmented version of Prim's algorithm to calculate a minimum spanning tree of the set of nodes. The modification to the algorithm is that no node in the mst can have more than two children (representing the two robots at that location). Other than that it works the same as Prim's, calculating edge weights based on nodes already in the mst and adding the lowest weight edge to the mst at each iteration.

Greedy By Closest

Each awake robot is sent to the closest sleeping robot at the time that it is awoken or the time it has reached another robot.
Robots are considered awake when a robot is in transit to wake it, rather than when it is reached, to avoid scheduling conflicts.

Alternating Greedy

This one is the same as the Greedy By Closest implementation, but rather than going to the closest two points one of the robots goes to the closest, while the other goes to the robot furthest from that location.

Analysis

As we expected, the brute force solution stops being usable after n exceeds 14 or 15. Since the algorithm has to generate every possible ordering of sites, after n=15 the computation time exceeds what we considered to be reasonable.
The other algorithms all ran within expected time complexities, though the algorithm that produced the best output varied from sample set to sample set.