{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihujb6c447vfqypwxx222t3tgr7pqusm2lwe33tnzcdbgwrden3ca",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhp6skn22np2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.19502v1",
  "publishedAt": "2026-03-23T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Tsuri Farhana",
    "Omrit Filtser",
    "Shalev Goldshtein"
  ],
  "textContent": "**Authors:** Tsuri Farhana, Omrit Filtser, Shalev Goldshtein\n\nWe study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al. (SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least $4$, and start--target distances of at least $3$, but without optimality guarantees. Solovey et al. (RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least $4$, and at least $\\sqrt{5}\\approx2.236$ from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is $2\\tfrac{2}{3}$ and the obstacles-separation is $1\\tfrac{2}{3}$, or (ii) the robots-separation is $\\approx3.291$ and the obstacles-separation $\\approx1.354$. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only $2$, and the obstacles-separation is $3$. Finally, we show that without any robots-separation assumption, obstacles-separation of at least $1.5$ may be necessary for a solution to exist.",
  "title": "Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs"
}