Efficient, High-Quality Stack Rearrangement

被引：15

作者：

Han S.D. ^{[1
]}

Stiffler N.M. ^{[1
]}

Bekris K.E. ^{[1
]}

Yu J. ^{[1
]}

机构：

[1] Department of Computer Science, Rutgers, State University of New Jersey Piscataway, 08901, NJ

来源：

Han, Shuai D. (shuai.han@rutgers.edu) | 1608年 / Institute of Electrical and Electronics Engineers Inc., United States卷 / 03期

基金：

美国国家科学基金会;

关键词：

Foundations of automation; inventory management; manipulation planning; planning; scheduling and coordination; task planning;

D O I：

10.1109/LRA.2018.2800116

中图分类号：

学科分类号：

摘要：

This work studies rearrangement problems involving the sorting of robots or objects in stack-like containers, which can be accessed only from one side. Two scenarios are considered: one where every robot or object needs to reach a particular stack, and a setting in which each robot has a distinct position within a stack. In both cases, the goal is to minimize the number of stack removals that need to be performed. Stack rearrangement is shown to be intimately connected to pebble motion problems, a useful abstraction in multi-robot path planning. Through this connection, feasibility of stack rearrangement can be readily addressed. Lower and upper bounds on optimality are established, which differ only by a logarithmic factor, in terms of stack removals. An algorithmic solution is then developed that produces suboptimal paths much quicker than a pebble motion solver. Furthermore, informed search-based methods are proposed for finding high-quality solutions. The efficiency and desirable scalability of the methods are demonstrated in simulation. © 2016 IEEE.

引用

页码：1608 / 1615

页数：7

共 43 条

[1]

Aronov B., De Berg M., Stappen Den Van A.F., Svestka P., Vleugels J., Motion planning for multiple robots, Discrete Comput. Geometry, 22, 4, pp. 505-525, (1999)

[2]

Solovey K., Yu J., Zamir O., Halperin D., Motion planning for unlabeled discs with optimality guarantees, Proc. Robot.: Sci. Syst, (2015)

[3]

Solovey K., Halperin D., On the hardness of unlabeled multi-robot motion planning, Proc. Robot.: Sci. Syst, (2015)

[4]

Berg Den Van J., Overmars M., Prioritized motion planning for multiple robots, Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst, pp. 2217-2222, (2005)

[5]

Leroy S., Laumond J.-P., Simeon T., Multiple path coordination for mobile robots: A geometric algorithm, Proc. Int. Joint Conf. Artif. Intell, pp. 1118-1123, (1999)

[6]

Kornhauser D., Miller G., Spirakis P., Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, Proc. IEEE Symp. Foundations Comput. Sci, pp. 241-250, (1984)

[7]

Calinescu G., Dumitrescu A., Pach J., Reconfigurations in graphs and grids, SIAM J. Discrete Math, 22, 1, pp. 124-138, (2008)

[8]

Auletta V., Monti A., Parente D., Persiano G., A linear time algorithm for the feasibility of pebble motion on trees, Algorthmica, 23, pp. 223-245, (1999)

[9]

Goraly G., Hassin R., Multi-color pebble motion on graphs, Algorthmica, 58, 3, pp. 610-636, (2010)

[10]

Krontiris A., Luna R., Bekris K.E., From feasibility tests to path planners for multi-agent pathfinding, Proc. Int. Symp. Combinatorial Search, pp. 1-9, (2013)

← 1 2 3 4 5 →