Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

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

verfasst von : Aviv Adler, Mark de Berg, Dan Halperin, Kiril Solovey

Erschienen in: Algorithmic Foundations of Robotics XI

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the following motion-planning problem: we are given \(m\) unit discs in a simple polygon with \(n\) vertices, each at their own start position, and we want to move the discs to a given set of \(m\) 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\left( n\log n+mn+m^2\right) \) 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel Navigation of Distinct Euclidean Particles via Hierarchical Clustering
Literatur
1.
Aronov, B., de Berg, M., van der Stappen, A.F., Švestka, P., Vleugels, J.: Motion planning for multiple robots. Discret. Comput. Geom. 22(4), 505–525 (1999)CrossRefMATH
2.
3.
Dumitrescu, A., Jiang, M.: On reconfiguration of disks in the plane and related problems. Comput. Geom.: Theory Appl. 46(3), 191–202 (2013)CrossRefMATHMathSciNet
4.
Goldreich, O.: Shortest move-sequence in the generalized 15-puzzle is NP-hard. Manuscript, Laboratory for Computer Science, MIT 1 (1984)
5.
6.
Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1–2), 72–96 (2005)CrossRefMATHMathSciNet
7.
Hirsch, S., Halperin, D.: Hybrid motion planning: coordinating two discs moving among polygonal obstacles in the plane. In: Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 239–255. Springer, New York (2002)
8.
Hopcroft, J.E., Schwartz, J.T., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the warehouseman’s problem. Int. J. Robot. Res. 3(4), 76–88 (1984)CrossRef
9.
Kavraki, L.E., Švestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)CrossRef
10.
Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discret. Comput. Geom. 1, 59–70 (1986)CrossRefMATHMathSciNet
11.
Kloder, S., Hutchinson, S.: Path planning for permutation-invariant multi-robot formations. In: ICRA, pp. 1797–1802 (2005)
12.
Kornhauser, D.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. M.Sc. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (1984)
13.
Krontiris, A., Luna, R., Bekris, K.E.: From feasibility tests to path planners for multi-agent pathfinding. In: Symposium on Combinatorial Search (2013)
14.
Kuffner, J.J., Lavalle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: International Conference on Robotics and Automation (ICRA), pp. 995–1001 (2000)
15.
Papadimitriou, C.H., Raghavan, P., Sudan, M., Tamaki, H.: Motion planning on a graph. In: Foundations of Computer Science, pp. 511–520 (1994)
16.
Salzman, O., Hemmer, M., Halperin, D.: On the power of manifold samples in exploring configuration spaces and the dimensionality of narrow passages to appear, Workshop on the Algorithmic Foundations of Robotics (WAFR) (2012)
17.
Sanchez, G., Latombe, J.C.: Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In: International Conference on Robotics and Automation (ICRA) (2002)
18.
Schwartz, J.T., Sharir, M.: On the piano movers problem: II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4(3), 298–351 (1983)CrossRefMATHMathSciNet
19.
Schwartz, J.T., Sharir, M.: On the piano movers problem: III. Coordinating the motion of several independent bodies. Int. J. Robot. Res. 2(3), 46–75 (1983)CrossRefMathSciNet
20.
Sharir, M., Sifrony, S.: Coordinated motion planning for two independent robots. Ann. Math. Artif. Intell. 3(1), 107–130 (1991)CrossRefMATHMathSciNet
21.
Solovey, K., Halperin, D.: \(k\)-color multi-robot motion planning. Int. J. Robot. Res. (2013, in press (already appeared on-line))
22.
Solovey, K., Salzman, O., Halperin, D.: Finding a needle in an exponential haystack: discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. CoRR 1305.​2889 (2013)
23.
24.
Švestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23, 125–152 (1998)CrossRef
25.
Turpin, M., Michael, N., Kumar, V.: Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In: International Conference on Robotics and Automation (ICRA), pp. 842–848 (2013)
26.
van den Berg, J., Snoeyink, J., Lin, M.C., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: Robotics: Science and Systems (RSS) (2009)
27.
Wagner, G., Choset, H.: M*: A complete multirobot path planning algorithm with performance bounds. In: International Conference on Intelligent Robots and Systems (IROS), pp. 3260–3267 (2011)
28.
Wagner, G., Kang, M., Choset, H.: Probabilistic path planning for multiple robots with subdimensional expansion. In: International Conference on Robotics and Automation (ICRA), pp. 2886–2892 (2012)
29.
Yap, C.K.: Coordinating the motion of several discs. Technical report, Courant Institute of Mathematical Sciences, Michigan State University, New York (1984)
30.
Yu, J., LaValle, S.M.: Distance optimal formation control on graphs with a tight convergence time guarantee. In: IEEE International Conference on Decision and Control, pp. 4023–4028 (2012)
Metadaten
Titel
Efficient Multi-robot Motion Planning for Unlabeled Discs in Simple Polygons
verfasst von
Aviv Adler
Mark de Berg
Dan Halperin
Kiril Solovey
Copyright-Jahr
2015
Buch
Algorithmic Foundations of Robotics XI

Print ISBN: 978-3-319-16594-3

Electronic ISBN: 978-3-319-16595-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-16595-0_1

Neuer Inhalt

    Bildnachweise