- Award ID(s):
- 1734419
- NSF-PAR ID:
- 10071651
- Date Published:
- Journal Name:
- 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Fast algorithms for optimal multi-robot path planning are sought after in real-world applications. Known methods, however, generally do not simultaneously guar- antee good solution optimality and good (e.g., polynomial) running time. In this work, we develop a first low-polynomial running time algorithm, called SplitAndGroup (SaG), that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor makespan optimal solutions on average over all problem in- stances. That is, SaG is an average case O(1)-approximation algorithm and computes solutions with sub-linear makespan. SaG is capable of handling cases when the density of robots is extremely high - in a graph-theoretic setting, the al- gorithm supports cases where all vertices of the underly- ing graph are occupied. SaG attains its desirable proper- ties through a careful combination of a novel divide-and- conquer technique, which we denote as global decoupling, and network flow based methods for routing the robots. Solutions from SaG, in a weaker sense, are also a constant factor approximation on total distance optimality.more » « less
-
Fast algorithms for optimal multi-robot path planning are sought after in both research and real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and fast run time for difficult instances. In this work, we develop a low-polynomial running time algorithm, called SplitAndGroup, that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor time- and distance-optimal solutions, in expectation. In particular, SplitAndGroup computes solutions with sub-linear makespan. SplitAndGroup is capable of handling cases when the density of robot is extremely high - in a graph-theoretic setting, the algorithm supports cases where all vertices of the underlying graph are occupied by robots. SplitAndGroup attains its desirable properties through a careful combination of divide-and-conquer technique and network flow based methods for routing the robots.more » « less
-
A great number of robotics applications demand the rearrangement of many mobile objects, for example, organizing products on store shelves, shuffling containers at shipping ports, reconfiguring fleets of mobile robots, and so on. To boost the efficiency/throughput in systems designed for solving these rearrangement problems, it is essential to minimize the number of atomic operations that are involved, for example, the pick-n-places of individual objects. However, this optimization task poses a rather difficult challenge due to the complex inter-dependency between the objects, especially when they are tightly packed together. In this work, in tackling the aforementioned challenges, we have developed a novel algorithmic tool, called Rubik Tables, that provides a clean abstraction of object rearrangement problems as the proxy problem of shuffling items stored in a table or lattice. In its basic form, a Rubik Table is an n Γ n table containing n2items. We show that the reconfiguration of items in such a Rubik Table can be achieved using at most n column and n row shuffles in the partially labeled setting, where each column (resp., row) shuffle may arbitrarily permute the items stored in a column (resp., row) of the table. When items are fully distinguishable, additional n shuffles are needed. Rubik Tables allow many generalizations, for example, adding an additional depth dimension or extending to higher dimensions. Using Rubik Table results, we have designed a first constant-factor optimal algorithm for stack rearrangement problems where items are stored in stacks, accessible only from the top. We show that, for nd items stored in n stacks of depth d each, using one empty stack as the swap space, O( nd) stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where [Formula: see text] for arbitrary fixed m > 0. Rubik Table results also allow the development of constant-factor optimal solutions for solving multi-robot motion planning problems under extreme robot density. These algorithms based on Rubik Table results run in low-polynomial time.
-
Let G = (V, E) be an m_1 \times \ldots \times m_k grid for some arbitrary constant k. We establish that O(\sum_{i=1}^km_i) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multi-robot path planning can be realized on G in O(|V|^2) running time, even when vertices of G are fully occupied by robots. When all dimensions are of equal sizes, the running time approaches O(|V|). Using this base line algorithm, which provides average case O(1)-approximate (i.e., constant-factor) time-optimal solutions, we further develop a first worst case O(1)-approximate algorithm that again runs in O(|V|^2) time for two and three dimensions. We note that the problem has a worst case running time lower bound of \Omega(|V|^2).more » « less
-
Hazay, Carmit ; Stam, Martijn (Ed.)We study the computational problem of finding a shortest non-zero vector in a rotation of β€π , which we call β€ SVP. It has been a long-standing open problem to determine if a polynomial-time algorithm for β€ SVP exists, and there is by now a beautiful line of work showing how to solve it efficiently in certain very special cases. However, despite all of this work, the fastest known algorithm that is proven to solve β€ SVP is still simply the fastest known algorithm for solving SVP (i.e., the problem of finding shortest non-zero vectors in arbitrary lattices), which runs in 2π+π(π) time. We therefore set aside the (perhaps impossible) goal of finding an efficient algorithm for β€ SVP and instead ask what else we can say about the problem. E.g., can we find any non-trivial speedup over the best known SVP algorithm? And, if β€ SVP actually is hard, then what consequences would follow? Our results are as follows. We show that β€ SVP is in a certain sense strictly easier than SVP on arbitrary lattices. In particular, we show how to reduce β€ SVP to an approximate version of SVP in the same dimension (in fact, even to approximate unique SVP, for any constant approximation factor). Such a reduction seems very unlikely to work for SVP itself, so we view this as a qualitative separation of β€ SVP from SVP. As a consequence of this reduction, we obtain a 2π/2+π(π) -time algorithm for β€ SVP, i.e., the first non-trivial speedup over the best known algorithm for SVP on general lattices. (In fact, this reduction works for a more general class of latticesβsemi-stable lattices with not-too-large π1 .) We show a simple public-key encryption scheme that is secure if (an appropriate variant of) β€ SVP is actually hard. Specifically, our scheme is secure if it is difficult to distinguish (in the worst case) a rotation of β€π from either a lattice with all non-zero vectors longer than π/logπβΎβΎβΎβΎβΎβΎβΎβ or a lattice with smoothing parameter significantly smaller than the smoothing parameter of β€π . The latter result has an interesting qualitative connection with reverse Minkowski theorems, which in some sense say that ββ€π has the largest smoothing parameter.β We show a distribution of bases π for rotations of β€π such that, if β€ SVP is hard for any input basis, then β€ SVP is hard on input π . This gives a satisfying theoretical resolution to the problem of sampling hard bases for β€π , which was studied by Blanks and Miller [9]. This worst-case to average-case reduction is also crucially used in the analysis of our encryption scheme. (In recent independent work that appeared as a preprint before this work, Ducas and van Woerden showed essentially the same thing for general lattices [15], and they also used this to analyze the security of a public-key encryption scheme. Similar ideas also appeared in [5, 11, 20] in different contexts.) We perform experiments to determine how practical basis reduction performs on bases of β€π that are generated in different ways and how heuristic sieving algorithms perform on β€π . Our basis reduction experiments complement and add to those performed by Blanks and Miller, as we work with a larger class of algorithms (i.e., larger block sizes) and study the βprovably hardβ distribution of bases described above. Our sieving experiments confirm that heuristic sieving algorithms perform as expected on β€π .more » « less