6 Search Results for "LaValle, Steven M."

Document
DOI: 10.4230/LIPIcs.WADS.2025.39
Sweeping a Domain with Line-Of-Sight Between Covisible Agents

Authors: Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes. Our approximations are obtained by introducing a new type of "window partition" of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are swept but not directly touched by the agents, may contain at most one hole.
Cite as

Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk. Sweeping a Domain with Line-Of-Sight Between Covisible Agents. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.WADS.2025.39,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{Sweeping a Domain with Line-Of-Sight Between Covisible Agents}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{39:1--39:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.39},
  URN =		{urn:nbn:de:0030-drops-242706},
  doi =		{10.4230/LIPIcs.WADS.2025.39},
  annote =	{Keywords: Polygon sweeping, collaborating agents, motion coordination, makespan optimization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.46
Guarding Offices with Maximum Dispersion

Authors: Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.
Cite as

Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer. Guarding Offices with Maximum Dispersion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.MFCS.2025.46,
  author =	{Fekete, S\'{a}ndor P. and Kobbe, Kai and Krupke, Dominik and Mitchell, Joseph S. B. and Rieck, Christian and Scheffer, Christian},
  title =	{{Guarding Offices with Maximum Dispersion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{46:1--46:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-241530},
  doi =		{10.4230/LIPIcs.MFCS.2025.46},
  annote =	{Keywords: Dispersive Art Gallery Problem, vertex guards, office-like polygons, orthogonal polygons, polyominoes, NP-completeness, worst-case optimality, dynamic programming, SAT solver}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.5
RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality

Authors: Franco Cordeiro, Samuel Tardieu, and Laurent Pautet

Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract
Robot planning in distributed systems, such as drone fleets performing active perception missions, presents complex challenges. These missions require cooperation to achieve objectives like collecting sensor data or capturing images. Multi-robot systems offer significant advantages, including faster execution and increased robustness, as robots can compensate for individual failures. However, resource costs, affected by environmental factors such as wind or terrain, are highly uncertain, impacting battery consumption and overall performance. Mission objectives are often prioritized by criticality, such as retrieving data from low-battery sensors to prevent data loss. Addressing these priorities requires sophisticated scheduling to navigate high-dimensional state-action spaces. While heuristics are useful for approximating solutions, few approaches extend to multi-robot systems or adequately address cost uncertainty and criticality, particularly during replanning. The Mixed-Criticality (MC) paradigm, extensively studied in real-time scheduling, provides a framework for handling cost uncertainty by ensuring the completion of high-critical tasks. Despite its potential, the application of MC in distributed systems remains limited. To address the decision-making challenges faced by distributed robots operating under cost uncertainty and objective criticality, we propose four contributions: a comprehensive model integrating criticality, uncertainty, and robustness; distributed synchronization and replanning mechanisms; the incorporation of mixed-criticality principles into multi-robot systems; and enhanced resilience against robot failures. We evaluated our solution, named RESCUE, in a simulated scenario and show how it increases the robustness by reducing the oversizing of the system and completing up to 40% more objectives. We found an increase in resilience of the multi-robot system as our solution not only guaranteed the safe return of every non-faulty robot, but also reduced the effects of a faulty robot by up to 14%. We also computed the performance gain compared to using MCTS in a single robot of up to 2.31 for 5 robots.
Cite as

Franco Cordeiro, Samuel Tardieu, and Laurent Pautet. RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cordeiro_et_al:LIPIcs.ECRTS.2025.5,
  author =	{Cordeiro, Franco and Tardieu, Samuel and Pautet, Laurent},
  title =	{{RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-377-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{335},
  editor =	{Mancuso, Renato},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.5},
  URN =		{urn:nbn:de:0030-drops-235835},
  doi =		{10.4230/LIPIcs.ECRTS.2025.5},
  annote =	{Keywords: Multi-Robot Systems, Embedded Systems, Safety/Mixed-Critical Systems, Real-Time Systems, Monte-Carlo Tree Search}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.5
Optimal Motion Planning for Two Square Robots in a Rectilinear Environment

Authors: Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren, Alex Steiger, and Martijn Struijs

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Let W ⊂ ℝ² be a rectilinear polygonal environment (that is, a rectilinear polygon potentially with holes) with a total of n vertices, and let A,B be two robots, each modeled as an axis-aligned unit square, that can move rectilinearly inside W. The goal is to compute an optimal collision-free motion plan π for A and B between a given pair of source and target configurations. We study two variants of this problem and obtain the following results. - Min-Sum: Here the goal is to compute a motion plan that minimizes the sum of the lengths of the paths of the robots. We present an O(n⁴log n)-time algorithm for computing an optimal solution to the min-sum problem. This is the first polynomial-time algorithm to compute an optimal, collision-free motion of two robots amid obstacles in a planar polygonal environment. - Min-Makespan: Here the robots can move with at most unit speed, and the goal is to compute a motion plan that minimizes the maximum time taken by a robot to reach its target location. We prove that the min-makespan variant is NP-hard.
Cite as

Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren, Alex Steiger, and Martijn Struijs. Optimal Motion Planning for Two Square Robots in a Rectilinear Environment. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2025.5,
  author =	{Agarwal, Pankaj K. and de Berg, Mark and Holmgren, Benjamin and Steiger, Alex and Struijs, Martijn},
  title =	{{Optimal Motion Planning for Two Square Robots in a Rectilinear Environment}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.5},
  URN =		{urn:nbn:de:0030-drops-231577},
  doi =		{10.4230/LIPIcs.SoCG.2025.5},
  annote =	{Keywords: Computational geometry, motion planning, multiple robots, rectilinear paths}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.44
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the Coordinated Sliding-Motion Planning (CSMP) problem. In this variant, we are given an undirected graph G, k robots R₁,… ,R_k positioned on distinct vertices of G, p ≤ k distinct destination vertices for robots R₁,… ,R_p, and 𝓁 ∈ ℕ. The problem is to decide if there is a serial schedule of at most 𝓁 moves (i.e., of makespan 𝓁) such that at the end of the schedule each robot with a destination reaches it, where a robot’s move is a free path (unoccupied by any robots) from its current position to an unoccupied vertex. The problem is known to be NP-hard even on full grids. It has been studied in several contexts, including coin movement and reconfiguration problems, with respect to feasibility, complexity, and approximation. Geometric variants of the problem, in which congruent geometric-shape robots (e.g., unit disk/squares) slide or translate in the Euclidean plane, have also been studied extensively. We investigate the parameterized complexity of CSMP with respect to two parameters: the number k of robots and the makespan 𝓁. As our first result, we present a fixed-parameter algorithm for CSMP parameterized by k. For our second result, we present a fixed-parameter algorithm parameterized by 𝓁 for the special case of CSMP in which only a single robot has a destination and the graph is planar. A crucial new ingredient for both of our results is that the solution admits a succinct representation as a small labeled topological minor of the input graph.
Cite as

Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.SoCG.2025.44,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.},
  title =	{{A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.44},
  URN =		{urn:nbn:de:0030-drops-231966},
  doi =		{10.4230/LIPIcs.SoCG.2025.44},
  annote =	{Keywords: coordinated motion planning on graphs, parameterized complexity, topological minor testing, planar graphs}
}
Document
DOI: 10.4230/DagSemProc.06421.7
Extracting Visibility Information by Following Walls

Authors: Anna Yershova, Benjamin Tovar, and Steven M. LaValle

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
This paper presents an analysis of a simple robot model, called Bitbot. The Bitbot has limited capabilities; it can reliably follow walls and sense a contact with a wall. Although the Bitbot does not have a range sensor or a camera, it is able to acquire visibility information from the environment, which is then used to solve a pursuit-evasion task. Our developments are centered on the characterization of the information the Bitbot acquires. At any given moment, due to the sensing uncertainty, the robot does not know the current state. In general, uncertainty in the state is one of the central issues in robotics; the Bitbot model serves as an example of how the notion of information space naturally handles uncertainty. We show that state estimation with the Bitbot is a challenging problem, related to the well-known open problem of characterizing visibility graphs in computational geometry. However, state estimation becomes unnecessary to the achievement of the Bitbot's visibility tasks. We show how pursuit-evasion strategy is derived from a careful manipulation with histories of observations, and present analysis of the algorithm and experimental results.
Cite as

Anna Yershova, Benjamin Tovar, and Steven M. LaValle. Extracting Visibility Information by Following Walls. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{yershova_et_al:DagSemProc.06421.7,
  author =	{Yershova, Anna and Tovar, Benjamin and LaValle, Steven M.},
  title =	{{Extracting Visibility Information by Following Walls}},
  booktitle =	{Robot Navigation},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.7},
  URN =		{urn:nbn:de:0030-drops-8678},
  doi =		{10.4230/DagSemProc.06421.7},
  annote =	{Keywords: Planning, localization, pursuit evasion, visibility}
}
  • Refine by Type
  • 6 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2007

  • Refine by Author
  • 2 Mitchell, Joseph S. B.
  • 1 Agarwal, Pankaj K.
  • 1 Cordeiro, Franco
  • 1 Eiben, Eduard
  • 1 Fekete, Sándor P.
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Computer systems organization → Real-time systems
  • 1 Computing methodologies → Planning and scheduling
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 1 Computational geometry
  • 1 Dispersive Art Gallery Problem
  • 1 Embedded Systems
  • 1 Monte-Carlo Tree Search
  • 1 Multi-Robot Systems
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact