Over the weekend, I’d realized that I actually didn’t completely understand the rotational sweep algorithm. As it turns out, this isn’t a very well-documented algorithm, and all existing descriptions are slightly hard to follow in the same place (an edge-ordering requirement, where it’s a bit unclear what we’re sorting by). My mentor was similarly confused about the algorithm. I spent some time with him trying to parse it and get my implementation to work (by testing different edge-orderings). At about 10 PM on Monday night, we hadn’t gotten very far. At this point, I decided it might be a good idea to write a different algorithm for the visibility determination. Although its asymptotic complexity was worse than the rotational-sweep, it was a lot easier to implement. Sometimes, as my mentor paraphrased Donald Knuth, “early optimization is the death of productivity.” It can be better to have decent solution and work up from there, rather than taking thrice the time to get the best solution immediately.

In our meeting on Tuesday, Prof. Hauser clarified the description of the rotational-sweep algorithm to all of us and we discussed how the visibility graph would fit into finding the overall path. Having completed this step, I moved onto the next part: finding points in the free space that could be used to disinfect surfaces in the room. The disinfection robot does its job by radiating UV light on touch surfaces. When ultraviolet light is administered to a surface in large enough doses, it’s capable of killing or inactivating microbes lying on it. For each type of microbe, there is a certain amount of disinfection fluence of UV light required on a surface to guarantee some percentage of the microbe being completely inactivated. Therefore, when setting up this problem, we need to make sure that our solution promises to get each surface that desired amount. But that’s not all we want; we’d like to find such a solution that does this quickly. So, we’d like to find the solution that minimizes our total dwell-time – here, that means the time spent by the robot stationary as it emits light from different vantage points in the room – while ensuring that all surfaces receive the prescribed radiation dose for disinfection. This is a problem that can be solved using linear programming.

NOTE: Linear programming is a technique used for optimizing a certain value subject to some defined constraints. Say we have some number of variables, and would like to optimize a value that can be represented as a linear function of said variables. However, these variables themselves cannot take all possible values; a set of assigned values to all variables is feasible if and only if some set of constraints is also satisfied. If these constraints can all also be represented using linear expressions of all the variables, then we have a linear program. There are algorithms that allow us to systematically solve linear programs in polynomial time, with respect to the number of variables and number of constraints we have. This makes formulating linear programs very desirable! If we are able to write an optimization problem as a linear program formulation, then we can always solve for the optimal value pretty quickly.

In our problem, we’d like to minimize the total dwell-time (which is the sum of all dwell-times at all points that are potential vantage points) while maintaining that each surface (in two dimensions, a surface is just an edge) receives the dose of radiation it needs. So, if we are able to represent the amount of flux received by an edge in terms of the dwell-times of each potential vantage point, then we should be able to represent the constraints linearly, and there is indeed a linear formulation of the problem.

We use the visibility graph algorithm for each potential vantage point to determine if it’s able to irradiate a surface (aka edge) or not. If so, we can use the edge’s distance from the vantage point, as well as the angle subtended by the edge, to determine the flux per unit length per unit time received by that edge. It’s a somewhat involved expression, but it is linear in terms of the time spent at that vantage point. This means the total flux received by an edge is a linear function of the dwell-time variables, and now we have a linear program we can solve quickly. This week, I spent most of time formulating and coding up this linear program.

This Wednesday, we had the first ‘Lunch and Learn’ research presentation as part of the UIUC REU program. It was about how to go about research. I enjoyed the presentation and though the professors made some interesting points, although I think there could have been some greater depth to their talking points. For example, they recommended reading academic papers, but didn’t talk very much about how to find good papers, and how to effectively read papers. Perhaps they’ll discuss this later or I can discuss it specifically with some people.

This week, we also had a kickoff meeting for the COVID-19 robot business research. Prof. Hauser’s lab is invested in actually making these disinfection robots eventually and making them available to the public. This is a larger venture that includes people with different backgrounds focusing on different aspects of the project. Prof. Hauser’s lab is in charge of the path-planning aspect in this venture, so I (along with my mentor) was invited to the meeting as our research is going to be used here. Again, it surprised me that the work I was doing could potentially soon be having tangible consequences in the world, and I’m excited to do as good of a job as I can to accomplish this.