Every Tuesday morning, I meet with a sub-group of Prof. Hauser’s lab, to discuss weekly progress. This sub-group is called the ‘Planning and Control’ group, made of people involved in the modules of path-planning and perception of the disinfection robot. The undergrad interns are supposed to present what we’ve done over the week during this meeting. So, Mondays are usually a checkpoint for me to really think about what I did over the last week and how to present that work concisely and clearly. This week, I’ll need to talk about testing the different TSP solvers, so I need to collect the detailed experimental results completely and do formal comparisons.

I spent time over the weekend generating random example graph distance matrices to test and running the different TSP solvers on these examples. At the large graph sizes (~ 5000 nodes), most of the solvers took an incredibly long time to run, so this was a long process. After getting these results, I got some graphical results plotting runtime against solution tour length for all of the solvers, and also got some box plots and histograms to show a good visual comparison.

During the meeting, I talked about these results, and it seemed pretty acceptable to everyone. In terms of next steps, this meant I would be moving onto other parts of the path-planning algorithm. Prof. Hauser suggested I read about some common multi-path planning algorithms to strengthen my background, such as Probabilistic Road Maps and Rapidly Exploring Random trees. He also recommended a few papers that detail multi-goal planning algorithms and inspection path algorithms which are closely related to our own algorithm. So, I spent more time this week learning theory again, which I really liked.

This week also marked the official kickoff of the Urbana-Champaign summer REU program. The program wants to make sure students get as much out of the research experience as we can. During the introductory meeting, they mentioned that every week would have a research-related presentation led by UIUC professors, ranging from topics like networking in academia to how to prepare competitive graduate school applications. It was nice to meet everyone else in the program, albeit through a camera. I imagine there would be more events and meeting opportunities with an in-person REU, but a pandemic requires certain adjustments. I hope to learn more during the weekly presentations.

I spent the latter part of the week working on the next step of the overall path-planning algorithm. Although real rooms are obviously three-dimensional, we simplified to 2D for our first algorithm and tests. There is a simple two dimensional path-planning algorithm that involves finding visibility graphs for points in free space.

NOTE: This algorithm assumes that you have a polygonal representation of your space. That is, you have an X-Y plane, and polygons described by Euclidean coordinates represent the “obstacles” in your space. Everything outside of these polygons represent your free space. Let’s say we’re trying to find a path between any pair of points A and B in free space. Something that’s useful to know is which obstacle vertices are directly visible – meaning a straight line from one point to the other passes entirely through free space, and doesn’t go through any polygons – from A and from B. This can help find an optimal path from A to B with a few more steps. However, just this first step is the one useful to our own work.

There are (as one may expect) multiple known algorithms to calculate visibility graphs. The one we want to use is the rotational sweep algorithm because it has the best big O time. Now, there are existing implementations of the entire rotational sweep algorithm to find complete visibility graphs, but for our purposes we wanted only a subgraph of the entire visibility graph and it would be more efficient to calculate just the subgraph as it tends to be much smaller. So, I spent time understanding the algorithm completely and started implementing our specific version of it myself.