- Minimum Active Buffers in Object Rearrangement
- Project Year:
2020
- REU Student (s):
Polina Kochetova | Rutgers University-New Brunswick NJ
- Student 1 Institution:
Rutgers University-New Brunswick
- Project Mentor:
Jingjin Yu
- Project Mentor Area:
Computer Science
- Project Abstract:
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.
