3 Search Results for "Meijer, Erik"


Document
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch

Authors: Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


Abstract
We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Despite a broad range of other non-trivial results for multi-object motion planning, previous work has largely focused on sequential schedules, in which one robot moves at a time, with objectives such as the number of moves; attempts to minimize the overall makespan of a coordinated parallel motion schedule (with many robots moving simultaneously) have defied all attempts at establishing the complexity in the absence of obstacles, as well as the existence of efficient approximation methods. We resolve these open problems by developing a framework that provides constant-factor approximation algorithms for minimizing the execution time of a coordinated, parallel motion plan for a swarm of robots in the absence of obstacles, provided their arrangement entails some amount of separability. In fact, our algorithm achieves constant stretch factor: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d). Various extensions include unlabeled robots and different classes of robots. We also resolve the complexity of finding a reconfiguration plan with minimal execution time by proving that this is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) may be required. On the positive side, we establish a stretch factor of O(N^{1/2}) even in this case. The intricate difficulties of computing precise optimal solutions are demonstrated by the seemingly simple case of just two disks, which is shown to be excruciatingly difficult to solve to optimality.

Cite as

Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.SoCG.2018.29,
  author =	{Demaine, Erik D. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian and Meijer, Henk},
  title =	{{Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.29},
  URN =		{urn:nbn:de:0030-drops-87423},
  doi =		{10.4230/LIPIcs.SoCG.2018.29},
  annote =	{Keywords: Robot swarms, coordinated motion planning, parallel motion, makespan, bounded stretch, complexity, approximation}
}
Document
10152 Abstracts Collection – Relationships, Objects, Roles, and Queries in Modern Languages

Authors: Guido Boella, Erik Meijer, David J. Pearce, Friedrich Steimann, and Frank Tip

Published in: Dagstuhl Seminar Proceedings, Volume 10152, Relationships, Objects, Roles, and Queries in Modern Programming Languages (2010)


Abstract
From 11/04/10 to 16/04/10, the Dagstuhl Seminar 10152 ``Relationships, Objects, Roles, and Queries in Modern Programming Languages'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Guido Boella, Erik Meijer, David J. Pearce, Friedrich Steimann, and Frank Tip. 10152 Abstracts Collection – Relationships, Objects, Roles, and Queries in Modern Languages. In Relationships, Objects, Roles, and Queries in Modern Programming Languages. Dagstuhl Seminar Proceedings, Volume 10152, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{boella_et_al:DagSemProc.10152.1,
  author =	{Boella, Guido and Meijer, Erik and Pearce, David J. and Steimann, Friedrich and Tip, Frank},
  title =	{{10152 Abstracts Collection – Relationships, Objects, Roles, and Queries in Modern Languages}},
  booktitle =	{Relationships, Objects, Roles, and Queries in Modern Programming Languages},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10152},
  editor =	{Guido Boella and Erik Meijer and David J. Pearce and Friedrich Steimann and Frank Tip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10152.1},
  URN =		{urn:nbn:de:0030-drops-25750},
  doi =		{10.4230/DagSemProc.10152.1},
  annote =	{Keywords: Relationships, Roles, Software Modelling, Programming Languages}
}
Document
10152 Executive Summary – Relationships, Objects, Roles, and Queries in Modern Languages

Authors: Guido Boella, Erik Meijer, David J. Pearce, Friedrich Steimann, and Frank Tip

Published in: Dagstuhl Seminar Proceedings, Volume 10152, Relationships, Objects, Roles, and Queries in Modern Programming Languages (2010)


Abstract
During the 4 days of the seminar, 21 talks, 4 tutorials and 6 demos were given by the participants. In addition, a beauty contest was run on the last day, where participants were invited to solve a benchmark problem using their system.

Cite as

Guido Boella, Erik Meijer, David J. Pearce, Friedrich Steimann, and Frank Tip. 10152 Executive Summary – Relationships, Objects, Roles, and Queries in Modern Languages. In Relationships, Objects, Roles, and Queries in Modern Programming Languages. Dagstuhl Seminar Proceedings, Volume 10152, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{boella_et_al:DagSemProc.10152.2,
  author =	{Boella, Guido and Meijer, Erik and Pearce, David J. and Steimann, Friedrich and Tip, Frank},
  title =	{{10152 Executive Summary – Relationships, Objects, Roles, and Queries in Modern Languages}},
  booktitle =	{Relationships, Objects, Roles, and Queries in Modern Programming Languages},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10152},
  editor =	{Guido Boella and Erik Meijer and David J. Pearce and Friedrich Steimann and Frank Tip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10152.2},
  URN =		{urn:nbn:de:0030-drops-25743},
  doi =		{10.4230/DagSemProc.10152.2},
  annote =	{Keywords: Relationships, Roles, Software Modelling, Programming Languages}
}
  • Refine by Author
  • 2 Boella, Guido
  • 2 Meijer, Erik
  • 2 Pearce, David J.
  • 2 Steimann, Friedrich
  • 2 Tip, Frank
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Programming Languages
  • 2 Relationships
  • 2 Roles
  • 2 Software Modelling
  • 1 Robot swarms
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2010
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail