General Information

---

Project Description

Graph-Based Multi-Robot Path Planning (MRPP) has been thoroughly studied, particularly on grid settings, where sub-1.5 time-optimal algorithms have been developed and run in polynomial time using Rubik Tables as an abstraction for efficient sorting in dense settings. However, adding a corner following constraint (CFC) highly constricts motion in dense settings, particularly when there are Theta(m + n) or Theta(1) empty spots in an m x n grid. As such, there is still a gap between the required Omega(m + n) makespan lower bound and the known O(mn) makespan upper bound, and so we seek to tighten this gap.

---

Weekly Log

Week 1:

This week, I met with Professor Yu to discuss the project and goals for the summer. I read a paper on efficient O(1)-time optimal Multi-Robot Path Planning Algorithms in the grid setting, taking advantage of the Rubik Table abstraction for efficient sorting expounded on in another paper also by Yu. I read another paper that added an additional corner following constraint that prevents any clear analysis that may lend itself towards Rubik Table results, learning about the gap in the lower and upper bounds on makespan in dense settings, which is the focus of my project. I put together a presentation and started thinking about ways to approach the problem.

---

Week 2:

At the start of the week, I gave an initial presentation (link) outlining my project and goals for the summer. Soon after, I had a series of possible ideas that could use Rubik Tables to reduce the makespan efficiently. Much of the week was spent attempting to develop out these ideas to see if they would work at all, and I met with my mentor twice to discuss them. So far, the strategy seems promising.

---

Week 3:

This week, I attended the Graph Algorithms Workshop, and so I didn't make any direct progress on my project, although it did give me some more ideas about different general approaches. Many of the talks were difficult to follow since I couldn't verify many of the statements made (besides them being fairly fast), but the high level ideas were novel and well-motivated, thus outlining how research involves a fair amount of exploration with wishful thinking, giving me concrete ideas about how I should work on my own project.

---

Week 4:

Getting back into my project, I began writing up and formalizing the rough sketches I had made two weeks ago. The ideas I had for Theta(1) empty spots worked more or less, although it had parity issues that didn't allow for easy generalization. After working on the Theta(m+n) case, I figured out a simpler way to make it work, retroactively improving the algorithm for the Theta(1) case. I wrote up the algorithm and key proof ideas but didn't explicitly write out all the details yet.

---

Week 5:

Professor Yu gave me more questions to think about, in particular, the NP-hardness of grid MRPP with the CFC. I began reading some more papers about the intractability of related robotics problems. In addition, to refamiliarize myself with reductions, I read over some of the elementary NP-hard problems, watched a few of Demaine's videos on NP-hardness, and practiced doing several reductions. In particular, I found the idea of decomposing a problem into its constituent parts and designing corresponding gadgets in the other problem to simulate an instance of the first to be novel and useful in making sense of why a problem really reduces to another one.

---

Week 6:

I spent the week trying to show that grid MRPP with the CFC and with one empty tile was NP-hard. I had multiple ideas for how to approach the problem, but it seems hard to analyze how a solution to the problem (smallest makespan) would be forced to move in a way that I would need to simulate another problem. The current lower bound that I am using is the same as in the (n^2 - 1)-puzzle (Manhattan distance sum), which does not capture the restriction that the empty tile can only jump to another element in the same row or column. I have attempted to search for a better lower bound capturing this idea but haven't found any so far that enables a better analysis. In the meantime, it seems that having an arbitrary number of missing tiles makes the problem substantially more like a MRPP problem, and so I have a rough sketch of a series of gadgets that could demonstrate NP-hardness for that case.

---

Week 7:

It's not so clear how to get a foothold in single escort MRPP with the CFC (SnPUZ - synchronous nPUZ, which refers to the (n^2 - 1)-puzzle), and so instead I focus on a slightly more general problem that uses only black and white tiles (BSnPUZ). I spent the week iteratively refining the hardness reduction, and hopefully it goes through. We also had a field trip to IBM, and it was cool to see how one could do math/TCS research in industry.

---

Week 8:

This is the week of final presentations, and so besides preparing for that (link), I had to formalize the hardness proofs I had for general MRPP with CFC and BSnPUZ. In doing so, I stumbled upon multiple issues, breaking the reduction, but with some tweaking, it seems that (at least for now) the proof for both goes through. I will need to spot check them more closely for the final write-up due next week.

---

Week 9:

The entire week was spent on the write-up, which involved rewriting several of the informal proofs I had written regarding the MRPP with CFC algorithms as well as tweaking some of the logic and presentation of the proofs in the hardness reductions. I also had to look through the literature related to the hardness results I had in order to write the introduction and discussion, which prompted me to fill in a few more hardness results, e.g. the hardness of BSnPUZ and PSnPUZ when there are a constant number of escorts. It's a pity that the program is coming to a close, but it has been a great opportunity to meet other students and researchers in TCS and an instructive experience in seeing what independent research is like in this area.

---

Acknowledgements

I am grateful to Jingjin Yu for his mentorship and support. This work was carried out while I was a participant in the 2023 DIMACS REU program at Rutgers University, supported by NSF HDR TRIPODS award CCF-1934924.