2026-07-31T04:52:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23157 2025-10-02T12:41:26Z ddc:004 open_access

Optimal Motion Planning for Two Square Robots in a Rectilinear Environment Agarwal, Pankaj K. de Berg, Mark Holmgren, Benjamin Steiger, Alex Struijs, Martijn Computational geometry motion planning multiple robots rectilinear paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Mark de Berg and Benjamin Holmgren and Alex Steiger and Martijn Struijs 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.5 urn:nbn:de:0030-drops-231577 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode