Student: | Polina Kochetova |
---|---|
School: | Rutgers University, New Brunswick |
Majors: | Computer Science and Mathematics |
E-mail: | pk506@scarletmail.rutgers.edu |
Project: | Minimum Active Buffers in Object Rearrangement |
In the problem of object rearrangement, we have n items in an initial configuration and we want to move them to certain goal positions. In particular, we are considering the case where each item has its own respective goals and the objects may be initially positioned atop each other's goals. It has been shown how by considering the items' relationships as a dependency graph where each item is a vertex and there is an directed edge (u,v) if and only if v's initial position intersects u's goal. Finding the minimum amount of items that need to be moved to temporary locations, or buffers, in order to move all objects to their goals is then shown to be equivalent to finding a minimum feedback vertex set for this dependency graph, as the collisions which are unsolvable without buffers are cycles. The goal of this project was to look at the related problem of the minimum number of active buffers required. In other words, the minimum amount of items that need to be simultaneously stored in temporary locations in order to resolve the graph.
In the Rubik Table Problem, one has an nxn table filled with unique items. The objective is to start with some initial arrangement, and find a sequence of modifications that leads to some ideal arrangement. A potential application of this is stack rearrangement, where you have n stacks with d items each and a buffer stack, and you want to move all the items from their initial stacks to their designated stacks. The goal of this project is to find and work with additional applications of this problem, such as what occurs when rather than removing items from stacks, you work with rotations, or you otherwise modify the problem.
This week, we had introductions to all our fellow undergrads in the program, as well as a virtual coffee house and our own social events to get to know each other better. In relation to the project, I read Mario Szegedy and Jingjin Yu's paper "On Rearrangement of Items Stored in Stacks" in order to familiarize myself with the Rubik's Table Problem and their proof of its running time's bounds. Additionally, Professor Yu and I had a meeting to discuss the current trajectory for the project.
We kicked off this week with project presentations to our mentors and fellow participants, mine centered around the proof of the Rubik's Table Problem from the paper I read during Week 1. After this, I continued to work on my understanding of the problem, and realized a few misconceptions I'd previously possessed. Then I began reading the Stack Exchange answer he sent me regarding solving a variation of the Rubik's problem with rotation, and I came to understand that this relied upon Group Theory, which I have unfortunately not studied. As a result, I am looking into Abstract Algebra while Professor Yu considers a different direction for me to take.
This week the goal was to focus on trying to implement a method for resolving a tabletop rearrangement from "High-Quality Tabletop Rearrangement with Overhand Grasps." This work began with me reading through more of the paper in an attempt to understand what was happening, but was relatively quickly sidetracked by my quest to understand and implement Johnson's algorithm for finding all the cycles in the graph (which I thought was necessary for the original algorithm). This involved quite a bit of both reading through the paper published about the algorithm, as well as more struggles with Python.
At the start of the week, I finished my code. However, upon finally implementing Johnson's accursed cycle finding algorithm, I found that my new task was to pursue an understanding of the minimum simultaneous problem through the lens of integer programming. However, the first step of this was actually understanding how to consider things through such a perspective. Of course I realized this not through logic, but rather simply plunging myself into the first paper recommended by Professor Yu. There might be people who can just hit the ground running. I am not one of them.
Thus, armed with a friend's recommendations, I set out to learn more about integer programming. A couple of days, a few lecture notes, and a video lecture later, I felt comfortable enough with the concept to attempt to return to "The orienteering problem: A survey," and I am happy to report it no longer felt as though I was reading hieroglyphics. Instead I was able to properly investigate the approach it took for removing cycles. This involved, among other things, looking into the paper it cited, "Integer programming formulations and travelling salesman problems," to understand what inspired the method.
I began this week continuing my investigation into adapting the approach of "The orienteering problem: A survey." Uninspired by what I was currently looking at, I began to look for other sources. However, I could not see how to adapt the approach for paths to an entire subgraph. Thus, I began to seek alternative routes. Among these looking at another LP solution to TSP, though frankly that one failed to convince me that it worked. Eventually I decided to pursue my own approach inspired by the fact that a graph without cycles should have a topological ordering.
With another meeting came another task. I came to the realization after this meeting that I could use Gurobi's example sudoku.py as an example of how to assign a group of variables to essentially hold a permutation of 1 to n. Alas, integer programming was no longer the name of the game. It was just programming. Luckily, Johnson's cycle finding algorithm was finally able to make up for some of the misery it's paper caused, as I utilized its ability to find all the cycles, and thus all the items in cycles. Regardless, after spending a couple of days on my pseudocode, I was then able to put it together in Python and get it working.
This week was primarily about presentations and papers. After modifying my code slightly, I began work on my presentation. This included many more hours of manipulating pictures of graphs than was perhaps reasonable, but I'd like to believe that it paid off in aesthetics. After that, the focus was on the paper. While I thought that since the algorithm was programmed that would be the simplest part to write up, I came to the realization that abridging code into pseudocode is actually far more annoying than the other way around. Anyhow, with everything done and submitted, I'd like to give thanks to DIMACS, in particular Lazaros Gallos and Parker Hund, for organizing this program. As well as NSF HDR TRIPODS award CCF-1934924 for funding this project.
"On Rearrangement of Items Stored in Stacks", Mario Szegedy and Jingjin Yu - arXiv.
"2D Rubik's Cube?" - Stack Exchange.
"High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods," S. D. Han, N. M. Stiffler, A. Krontiris, K. E. Bekris, and J. Yu,- arXiv.
"Finding All the Elementary Circuits of a Directed Graph," Donald B. Johnson- Paper.
"The orienteering problem: A survey," P. Vansteenwegen, W. Souffriau, and D. Van Oudheusden - doi.
"Integer programming formulations and travelling salesman problems" C. E. Miller, A. W. Tucker, AND R. A. Zemlin - Scopus.
My Mentor: Dr. Jingjin Yu