Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons

被引：26

作者：

Adler, Aviv ^{[1
]}

de Berg, Mark ^{[2
]}

Halperin, Dan ^{[3
]}

Solovey, Kiril ^{[3
]}

机构：

[1] MIT, Dept Elect Engn & Comp Sci, Cambridge, MA 02139 USA

[2] TU Eindhoven, Dept Math & Comp Sci, NL-5612 AZ Eindhoven, Netherlands

[3] Tel Aviv Univ, Blavatnik Sch Comp Sci, IL-69978 Tel Aviv, Israel

来源：

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING | 2015年 / 12卷 / 04期

基金：

以色列科学基金会;

关键词：

Computational geometry; motion planning; multi-robot motion planning; UNION; DISKS;

D O I：

10.1109/TASE.2015.2470096

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the following motion-planning problem: we are given unit discs in a simple polygon with vertices, each at their own start position, and we want to move the discs to a given set of target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in O(m(2) +mn) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.

引用

页码：1309 / 1317

页数：9

共 34 条

[1] APPROXIMATE MOTION PLANNING AND THE COMPLEXITY OF THE BOUNDARY OF THE UNION OF SIMPLE GEOMETRIC-FIGURES [J].

ALT, H ;

FLEISCHER, R ;

KAUFMANN, M ;

MEHLHORN, K ;

NAHER, S ;

SCHIRRA, S ;

UHRIG, C .

ALGORITHMICA, 1992, 8 (5-6) :391-406

[2]

[Anonymous], 1983, Advances in Applied Mathematics, DOI DOI 10.1016/0196-8858(83)90014-3

[3] Motion planning for multiple robots [J].

Aronov, B ;

de Berg, M ;

van der Stappen, AE ;

Svestka, P ;

Vleugels, J .

DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 22 (04) :505-525

[4]

Becker A, 2013, PROCEEDINGS OF THE TWENTY-NINETH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SOCG'13), P345

[5] SLIDING DISKS IN THE PLANE [J].

Bereg, Sergey ;

Dumitrescu, Adrian ;

Pach, Janos .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2008, 18 (05) :373-387

[6] Finding the medial axis of a simple polygon in linear time [J].

Chin, F ;

Snoeyink, J ;

Wang, CA .

DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 21 (03) :405-420

[7]

De Berg M., 2008, Computational Geometry: Algorithms and Applications, V17

[8] On reconfiguration of disks in the plane and related problems [J].

Dumitrescu, Adrian ;

Jiang, Minghui .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2013, 46 (03) :191-202

[9]

Goldreich O., 1984, LAB COMPUTER S UNPUB, V1

[10] Multi-Color Pebble Motion on Graphs [J].

Goraly, Gilad ;

Hassin, Refael .

ALGORITHMICA, 2010, 58 (03) :610-636

← 1 2 3 4 →