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.
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.
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.
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:
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.
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.
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.
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.
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.