Algorithm

General Approach

We want to find an optimal path for the robot, minimizing time while guaranteeing that every point in the room is disinfected.

Simplifications:
This is difficult, so we make the simplifying assumption that the robot has infinite speed. In other words, we assume that the robot can teleport between different locations, waiting at each location for some amount of time required to disinfect the room. In practice, the time the robot spends traveling is negligible in comparison to the total time it takes to disinfect the room, so this simplification is reasonable. Further, we search for a discrete approximation to the optimal solution: a set of points p_1, p_2, ... and waiting times t_1, t_2, ... such that if the robot waits at each p_i for t_i seconds, the entire room is disinfected. We then compute a TSP tour through these points to get a path.

Criteria for Disinfection:
Irradiance is energy received per unit time per unit area. Suppose the light source has a power (ie. energy per time) of P. The irradiance onto a point r in the room from a light source location g, at an angle alpha to the surface normal is irradiance(r, g) = P * cos(alpha) * 1/(4pi * dist(r, g)^2). If there is not line of sight between r and g, irradiance(r, g) = 0.

We want to guarantee that the total energy per unit area at each point in the room (in other words, the sum of irradiance at each stopping location multiplied by the time spent at that location) is greater than some threshold.

Core Idea: Linear Programming:
We have two regions as an inpput: the "room region" (a closed polygon, every point of which must be disinfected) and the "guard region" (a closed polygon describing the points the robot can travel to). We discretize the problem by sampling points from these two regions based on an epsilon-grid. We have a set of points R = {r_1, r_2, ..., r_n} from the room and a set G = {g_1, g_2, ..., g_m} from the guard region. We want to find times t_1, t_2, ..., t_m that minimize the sum of times, subject to the constraint that \sum irradiance(r, g_i) * t_i is greater than some threshold for every point r in the room.

If we apply this constraint only to the sampled room points r \in R, we can precompute the constants irradiance(r_j, g_i). We are left with a linear program with O(\epsilon^4) constraints. [TODO: I don't this this is completely correct because it should also depend on the size of the room]

This approach forms the basis of the solution. However, the naive LP setup only guarantees that finitely many points in the room (ie, those in R) are disinfected. To guarantee that the rest of the room is covered, the algorithm can be adapted in numerous ways.

Modifications

1. "Branch-and-Bound Scaling" Modification

A natural approach is to take the solution provided by the LP approach, find the point (not necessarily in R) that receives the least energy, and scale up all the waiting times by the factor needed to disinfect this minimum-energy point. A (branch-and-bound approach)[https://stanford.edu/class/ee364b/lectures/bb_notes.pdf] can be used to find the minimum energy point.

[TODO: Add details. Also, what's the word for energy per unit area? I think this is really a "minimum energy-per-unit-area" point...]

2. "Worst Cast Scenario" Modification

The method described may sometimes increase the runtime significantly, so we propose an alternative.

The constraint that \sum irradiance(r, g_i) * t_i is greater than a threshold guarantees that point r is disinfected. We can modify this constraint slightly so that it instead guarantees that an epsilon region around r is disinfected. Specifically, when calculating the irradiance between (r, g):

1. "Strong visibility": irradiance(r, g) = 0 if g cannot see every point in the neighborhood around r
2. "Strong distance": dist(r, g) is treated as the furthest distance between g and any point in the neighborhood around r
3. "Strong angle": alpha is treated as the smallest angle between g and any point in the neighborhood around r

[TODO: Discuss how good an approximation this is. In convex rooms: 1 + epsilon. In nonconvex rooms: convergence and possibly 3 + epsilon? These bounds probably also apply to branch-and-bound method]

3. Etc.

Combinations of these two modifications are also possible. For example, one might use strong visibility, then use branch-and-bound to scale up the solution instead of using strong distance/angle. In fact, the "Worse Case Scenario" modification described may wait longer than necessary to disinfect each point in the room - one could use branch-and-bound to scale down such a solution. See Results for a discussion of how these two heuristics perform.