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

Antony Thomas; Giulio Ferro; Fulvio Mastrogiovanni; Michela Robba; Marco Baglietto

cs.ROSep 19, 2026

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

Authors: Antony Thomas, Giulio Ferro, Fulvio Mastrogiovanni, Michela Robba, Marco Baglietto

Organizations: Robotics Research Center, IIIT Hyderabad, Hyderabad 500032, India. · Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145 Genoa, Italy.

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: (a) A top-down view of a possible scenario where a simulated Pepper humanoid robot is required to navigate to the right-hand side of the environment, and must displace obstacles to that aim. (b) A mobile manipulator, restricted to moving between the green lines, encounters an obstacle blocking its path. To proceed, the manipulator must push the obstacle aside before continuing along the designated trajectory. The warehouse environment is simulated in Gazebo by modifying an off-the-shelf model available at https://github.com/belal-ibrahim/dynamic_logistics_warehouse .

Panel of Figure 2 — Figure 2: An example of the MOD problem not satisfying the optimal substructure property. (a) The robot must move from left (start location in green) to right (goal location in red) in the presence of three movable obstacles, referred to as $A$ , $B$ , and $C$ . (b) A solution to the MOD problem splitting it into two sub-problems (left and right of the dashed line). This leads to a feasible path by moving obstacles $A$ and $B$ with a total displacement magnitude of 4 units. (c) The optimal solution is obtained by displacing obstacle $C$ by 3 units.

Figure 3: Construction by reduction from the Partition problem: movable line segments (in cyan) may be displaced only in the vertical direction. The segments in black are static obstacles. To pass along the $x$ -axis (which connects start and goal locations) at location $i$ , the obstacle at $i$ has to be displaced at least by $p^{i}/2$ . Otherwise, the robot has to move vertically for a distance of $p^{i}/2$ to reach one of the ends of obstacle at $i$ , and then vertically by the same amount to reach again the $x$ -axis.

Figure 4: Movable rectangles are shown in cyan and can be displaced only by an amount $r^{i}$ . Drawn in black are the obstacles constructed to achieve the reduction of the Partition problem.

Figure 5: Construction for NP-hardness proof of MOD with circular obstacles. See text for further details.

Figure 6: An illustration of the horizon-slicing approach employed in this work. $x(\cdot)$ denotes the variables of interest. The input (initial state) to the original problem and the first slice of the sub-problem coincide, and are referred to as $x(1)$ . The output of the first slice $x(T^{\prime})$ is the initial state for the next slice. The values of the time-dependent variables are passed on to the slices that follow.

Panel of Figure 7 — Figure 7: (a) A robot is tasked to move from the left (start location in green) to the right-hand side (goal location in red) in the presence of 5 movable obstacles. The $y$ -coordinate of the robot is constrained to lie within the magenta lines. (b) Obstacles can only translate in the vertical direction. The cases $m=1$ and $m=2$ produce similar trajectories (obstacle displacements shown in cyan). (c)-(d) Odd obstacles (counting from left) can only move downward and even obstacles can only move upward. The optimal solution is given in (c). The case $m=2$ gives a sub-optimal solution (with $\epsilon=0.81$ ) as shown in (d) with the first sub-problem involving the first $3$ obstacles, as shown by the vertical trajectory after the third obstacle.

Panel of Figure 8 — Figure 8: Different domains are used to test our methods. In all the experiments, a circular robot is asked to move from the left (start location in green) to the right (goal location in red) hand side in the presence of movable circular obstacles (in cyan).

Panel of Figure 9 — Figure 9: Robot trajectories and obstacle displacements for SQUARE_1 and SQUARE_2 while the robot moves according to the model in ( 5 ). The rows are related to different values for $m$ , the top row being related to $m=1$ (exact solution), the second row to $m=2$ , and so on.

Panel of Figure 10 — Figure 10: Robot trajectories and obstacle displacements for ROBOT and RANDOM while the robot moves according to the model in ( 5 ). The rows are related to different values for $m$ , the top row being related to $m=1$ (exact solution), the second row to $m=2$ , and so on.

Panel of Figure 11 — Figure 11: Robot trajectories and obstacle displacements for SQUARE_1 and SQUARE_2 while the robot moves according to the model in ( 6 ). The first row corresponds to $m=1$ (no horizon slicing) for all four domains, the second row corresponds to $m=2$ , and so on.

Panel of Figure 12 — Figure 12: Robot trajectories and obstacle displacements for ROBOT and RANDOM while the robot moves according to the model in ( 6 ). The first row corresponds to $m=1$ (no horizon slicing) for all four domains, the second row corresponds to $m=2$ , and so on.

	SQUARE_2			ROBOT
Method	Length (m)	Displacement (m)	Time (s)	Length (m)	Displacement (m)	Time (s)
HS4MOD ( $m=5$ )	36.92	7.25	1.36	78.55	9.17	12.23
NAMO Baseline	41.00	7.26	4.57	78.20	10.80	17.82

Table 1: Comparison of robot path length, obstacle displacement and planning time for HS4MOD (

m=5

) and NAMO baseline.

		Robot model ( 5 )				Robot model ( 6 )
	m	CPU [ $s$ ]	Gap/ $\epsilon$	$J^{r}[m^{2}]$	$J^{o}[m^{2}]$	CPU [ $s$ ]	Gap/ $\epsilon$	$J^{r}[m^{2}]$	$J^{o}[m^{2}]$
	1	1011.41	0.00	45.12	0.27	1001.34	0.00	47.35	0.35
	2	516.44	0.59	48.02	0.55	11.85	0.45	48.67	0.61
SQUARE_1	3	3.58	0.89	44.64	0.72	3.06	1.28	48.49	1.09
	4	2.99	1.97	45.45	1.25	2.58	1.50	49.09	1.22
	5	1.50	2.76	46.21	1.64	1.37	2.83	51.97	1.99

Table 2: Different statistics for the four domains considered in this paper, while employing the linear robot models in ( 5 ) and ( 6 ).

m=1

corresponds to the scenario with no horizon-slicing. CPU denotes the computation time in seconds for the optimization problem in ( 3 ),

J^{r}=c(\mathbf{p})

, and

J^{o}=\sum_{i=1}^{\mathcal{M}}\sum_{k=0}^{T}d^{i}_{k}

		Robot model ( 7 )				Robot model ( 8 )
	m	CPU [ $s$ ]	Gap/ $\epsilon$	$J^{r}[m^{2}]$	$J^{o}[m^{2}]$	CPU [ $s$ ]	Gap/ $\epsilon$	$J^{r}[m^{2}]$	$J^{o}[m^{2}]$
	1	88.59	0.00	52.19	0.20	307.17	0.00	52.31	0.61
	2	96.99	0.09	46.73	0.27	150.38	0.92	41.86	0.24
SQUARE_1	3	61.81	0.43	46.89	0.46	128.93	0.46	43.27	0.38
	4	26.53	1.35	47.75	0.89	97.34	0.37	43.83	0.41
	5	12.22	4.69	50.00	2.49	35.24	0.12	42.28	0.57

Table 3: Average computation time, Gap- wrt to

m=1

, path

\left(J^{r}=c(\mathbf{p})\right)

and displacement function

\left(J^{o}=\sum_{i=1}^{\mathcal{M}}\sum_{k=0}^{T}d^{i}_{k}\right)

values while employing the nonlinear robot models in ( 7 ) and ( 8 ).

Panel of Figure 13 — Figure 13: Robot trajectories and obstacle displacements for SQUARE_1 and SQUARE_2 domains while the robot moves according to the model in ( 7 ). The first row corresponds to $m=1$ (no horizon slicing), the second row corresponds to $m=2$ , and so on.

Panel of Figure 14 — Figure 14: Robot trajectories and obstacle displacements are depicted for the SQUARE_1 and SQUARE_2 domains, where the robot moves according to the model in ( 8 ). Each row corresponds to a different value of $m$ : the first row corresponds to $m=1$ (no horizon slicing), the second row corresponds to $m=2$ , and so on.

Panel of Figure 15 — Figure 15: Two trajectories related to the example scenario that was introduced at the beginning of the paper. A humanoid Pepper robot must navigate to the right-hand side of the map, and to that aim it must displace movable obstacles to pass through one of the two available passages. (a) Pepper finds a short path that implies displacing $7$ obstacles. (b) Increasing the obstacle displacement factor ( $J^{o}$ ) weight from 10 to 1000, the robot finds a path with lower obstacle displacement but with a higher path length.

Panel of Figure 16 — Figure 16: (a) Example of MOD solving the classical motion planning problem when a collision-free path exists. (b) The MOD cost is modified to obtain the MCR path using the exact approach. (c) HS4MOD with $m=3$ gives an approximate 2-obstacle MCR path.

Motion Planning

Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.

See all 392 papers

Navigate or Relocate? Planning Among Movable Obstacles in Unknown Environments
Sep 17, 2026Yuqing Zhang, Haoyu Zhu, Yiannis KantarosRobot Task Planning Motion Planning
Department of Electrical and Systems Engineering, Washington University in St. Louis, St. Louis, MO, USA
Graph-Based Heuristics for Minimum Constraint Removal in Cluttered Robot Motion Planning
Oct 8, 2026Antony Thomas, Fulvio Mastrogiovanni, Marco BagliettoMotion Planning Robot Motion Planning
Robotics Research Center, IIIT Hyderabad, 500032, Hyderabad, India. · Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, 16145, Genoa, Italy.
Optimal Path Planning in Hostile Environments
Mar 19, 2026Andrzej Kaczmarczyk, Šimon Schierreich, Nicholas Axel Tanujaya +1Multi-Agent Path Finding Graph-Based Planning
Czech Technical University in Prague · AGH University of Krakow · Bina Nusantara University +1

Sep 17, 2026J/K move · Enter open · S save

Navigate or Relocate? Planning Among Movable Obstacles in Unknown Environments

Yuqing Zhang, Haoyu Zhu, Yiannis Kantaros

Department of Electrical and Systems Engineering, Washington University in St. Louis, St. Louis, MO, USA

Robot Task Planning Motion Planning Sampling-Based Motion Planning

Open paper AskPDF arXiv

Conventional robot planning methods seek collision-free paths to a goal but fail when all paths are blocked. In these cases, the robot must determine which objects to relocate, in what order, and where to place them to clear a path---a problem known as Navigation Among Movable Obstacles (NAMO). Most NAMO planners assume a known environment, while existing approaches for unknown environments typically reason locally about relocations and cannot plan interdependent relocation sequences. We consider NAMO in unknown environments revealed through onboard sensing, where the robot must decide whether a blocked route requires relocation or a feasible path may exist through unexplored space. We propose an online framework that addresses this ambiguity by selecting between navigation and relocation using shortest paths that treat discovered movable objects as obstacles or as removable. Navigation relies on existing motion planners, while relocation uses a sampling-based approach that, unlike existing approaches for unknown environments, searches over interdependent relocation sequences and uses an LLM to bias sampling. Numerical experiments demonstrate scalability to cluttered environments requiring interdependent relocations and improved plan quality over existing baselines.

Abstract

Motion Planning

Explore similar work

Navigate or Relocate? Planning Among Movable Obstacles in Unknown Environments

Graph-Based Heuristics for Minimum Constraint Removal in Cluttered Robot Motion Planning

Optimal Path Planning in Hostile Environments