Optimal Motion Planning for Two Square Robots in a Rectilinear Environment
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910001874862080 |
|---|---|
| author | Agarwal, Pankaj K. de Berg, Mark Holmgren, Benjamin Steiger, Alex Struijs, Martijn |
| author_facet | Agarwal, Pankaj K. de Berg, Mark Holmgren, Benjamin Steiger, Alex Struijs, Martijn |
| contents | Let $\mathcal{W} \subset \mathbb{R}^2$ 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 $\mathcal{W}$. The goal is to compute a collision-free motion plan $\boldsymbolπ$, that is, a motion plan that continuously moves $A$ from $s_A$ to $t_A$ and $B$ from $s_B$ to $t_B$ so that $A$ and $B$ remain inside $\mathcal{W}$ and do not collide with each other during the motion. We study two variants of this problem which are focused additionally on the optimality of $\boldsymbolπ$, and obtain the following results.
1. 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^4\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.
2. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_19147 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | 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 Let $\mathcal{W} \subset \mathbb{R}^2$ 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 $\mathcal{W}$. The goal is to compute a collision-free motion plan $\boldsymbolπ$, that is, a motion plan that continuously moves $A$ from $s_A$ to $t_A$ and $B$ from $s_B$ to $t_B$ so that $A$ and $B$ remain inside $\mathcal{W}$ and do not collide with each other during the motion. We study two variants of this problem which are focused additionally on the optimality of $\boldsymbolπ$, and obtain the following results. 1. 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^4\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. 2. 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. |
| title | Optimal Motion Planning for Two Square Robots in a Rectilinear Environment |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2601.19147 |