Metraipolis › archive › dc_cc109dc99f00

A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation — arXiv:2609.22974

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.22974
License (as archived)
CC0-1.0
Archived
2026-10-09T22:23:42.002Z
SHA-256 of the archived text
75578431cb098f41835f8e3b37f3d7ae1c3466d609da6136ef955a17ba8cc11c
Stable URL of this page
https://metraipolis.com/documento/dc_cc109dc99f00

How to cite

A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation — arXiv:2609.22974 — arXiv (en), https://arxiv.org/abs/2609.22974 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cc109dc99f00 (Metraipolis archive dc_cc109dc99f00, sha256 75578431cb098f41835f8e3b37f3d7ae1c3466d609da6136ef955a17ba8cc11c)
BibTeX
@misc{dccc109dc99f00,
  title = {A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation — arXiv:2609.22974},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.22974},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cc109dc99f00; sha256 75578431cb098f41835f8e3b37f3d7ae1c3466d609da6136ef955a17ba8cc11c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22974. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this paper, we investigate the Minimum Obstacle Displacement Planning problem from a robot motion planning perspective. The problem involves determining a feasible path to a goal location by displacing movable obstacles when no collision-free path initially exists. We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane. Besides an exact formulation of the minimum obstacle displacement problem generalizing other problems in the literature, and the associated optimal solution, this paper proposes an approximate solution that is less intensive from a computational standpoint, and differs from the optimal solution by a fraction of the optimal cost, being able to trade-off between path length and amount of obstacle displacements.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-22 in cs.RO).
Categorie arXiv: Robotics (cs.RO) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2609.22974 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:59:59.519Z dalla pagina https://arxiv.org/catchup/cs.RO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).