# A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation

arXiv: https://arxiv.org/abs/2609.22974 · HTML: https://mlsanity.com/paper/2609.22974/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 19 Sep 2026.

## Builds on (most cited first, 14 of 14)

- [FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning](https://mlsanity.com/paper/1608.01335/) (2016)
- [Detection, localisation and tracking of pallets using machine learning techniques and 2D range data](https://mlsanity.com/paper/1803.11254/) (2018)
- [Incremental Sampling-based Algorithm for Minimum-violation Motion Planning](https://mlsanity.com/paper/1305.1102/) (2013)
- [On the manipulation of articulated objects in human-robot cooperation scenarios](https://mlsanity.com/paper/1801.01757/) (2018)
- [MPTP: Motion-Planning-aware Task Planning for Navigation in Belief Space](https://mlsanity.com/paper/2104.04696/) (2021)
- [Task Allocation for Multi-Robot Task and Motion Planning: a case for Object Picking in Cluttered Workspaces](https://mlsanity.com/paper/2110.04089/) (2021)
- [Minimum Displacement Motion Planning for Movable Obstacles](https://mlsanity.com/paper/2204.12740/) (2022)
- [NAMO-LLM: Efficient Navigation Among Movable Obstacles with Large Language Model Guidance](https://mlsanity.com/paper/2505.04141/) (2025)
- [Revisiting the Minimum Constraint Removal Problem in Mobile Robotics](https://mlsanity.com/paper/2305.01272/) (2023)
- [Safe motion planning with environment uncertainty](https://mlsanity.com/paper/2305.06004/) (2023)
- [A Task and Motion Planning Framework Using Iteratively Deepened AND/OR Graph Networks](https://mlsanity.com/paper/2503.07700/) (2025)
- [Pushing Through Clutter With Movability Awareness of Blocking Obstacles](https://mlsanity.com/paper/2502.20106/) (2025)
- [Efficient Navigation Among Movable Obstacles using a Mobile Manipulator via Hierarchical Policy Learning](https://mlsanity.com/paper/2506.15380/) (2025)
- [Locally Optimal Solutions to Constraint Displacement Problems via Path-Obstacle Overlaps](https://mlsanity.com/paper/2511.12203/) (2025)

## Abstract (arXiv)

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.