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

Sep 17, 2026

Navigate or Relocate? Planning Among Movable Obstacles in Unknown Environments

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.

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

Ask PDF

Oct 8, 2026

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

Humanoid and service robots operating in clut- tered human environments may encounter motion planning problems that are infeasible when all surrounding objects are treated as fixed obstacles. The Minimum Constraint Removal problem, which we refer to as MCR, addresses this situation by identifying the minimum number of constraints, such as movable objects, whose removal enables a collision-free path. However, computing an optimal MCR solution is NP-hard. In this work, we propose a graph-based heuristic pipeline that combines bidirectional feasible-set generation with fixed- length searches over reduced MCR graphs. We further derive an extended feasible-set generator for instances in which the candidates produced by the first generator do not contain a complete optimal removal set. Across six benchmarks, the evaluated pipeline matches the exact solution in three cases and, in the remaining cases, selects at most 31.25% more obstacles than the optimum, while being between 3.4 and 33.7 times faster than exact search. In one of the benchmarks, involving a manipulation task amidst clutter, selecting two rather than seven obstructing objects reduces the combined MCR, inverse- kinematics, and motion planning time from 84.72 s to 30.59 s. These results indicate that the proposed approach provides a practical compromise between computational efficiency and solution quality for motion planning among movable obstacles.

Antony Thomas, Fulvio Mastrogiovanni, Marco Baglietto

Robotics Research Center, IIIT Hyderabad, 500032, Hyderabad, India. · Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, 16145, Genoa, Italy.

Motion Planning Robot Motion Planning Graph-Based Planning

Ask PDF

Mar 19, 2026

Optimal Path Planning in Hostile Environments

Coordinating agents through hazardous environments, such as aid-delivering drones navigating conflict zones or field robots traversing deployment areas filled with obstacles, poses fundamental planning challenges. We introduce and analyze the computational complexity of a new multi-agent path planning problem that captures this setting. A group of identical agents begins at a common start location and must navigate a graph-based environment to reach a common target. The graph contains hazards that eliminate agents upon contact but then enter a known cooldown period before reactivating. In this discrete-time, fully-observable, deterministic setting, the planning task is to compute a movement schedule that maximizes the number of agents reaching the target. We first prove that, despite the exponentially large space of feasible plans, optimal plans require only polynomially-many steps, establishing membership in NP. We then show that the problem is NP-hard even when the environment graph is a tree. On the positive side, we present a polynomial-time algorithm for graphs consisting of vertex-disjoint paths from start to target. Our results establish a rich computational landscape for this problem, identifying both intractable and tractable fragments.

Andrzej Kaczmarczyk, Šimon Schierreich, Nicholas Axel Tanujaya +1

Czech Technical University in Prague · AGH University of Krakow · Bina Nusantara University +1

Multi-Agent Path Finding Graph-Based Planning

Ask PDF

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