Paper deep dive
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation
Antony Thomas, Giulio Ferro, Fulvio Mastrogiovanni, Michela Robba, Marco Baglietto
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/22/2026, 5:42:20 AM
Summary
This paper investigates the Minimum Obstacle Displacement (MOD) planning problem, where a robot must determine a feasible path by displacing movable obstacles when no collision-free path initially exists. The authors prove that MOD is NP-hard for various obstacle shapes (polygons, line segments, rectangles, circles). They propose an exact solution using Mixed Integer Quadratic Programming (MIQP) and an approximate solution called Horizon Slicing for MOD (HS4MOD), which divides the problem into sub-problems to reduce computational intensity while providing a trade-off between path length and displacement cost.
Entities (15)
Relation Signals (10)
Minimum Obstacle Displacement → hascomplexity → NP-hard
confidence 99% · We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane.
Fulvio Mastrogiovanni → affiliatedwith → University of Genoa
confidence 95% · Fulvio Mastrogiovanni Email: fulvio.mastrogiovanni@unige.it
Antony Thomas → affiliatedwith → IIIT-Hyderabad
confidence 95% · Antony Thomas Email: antony.thomas@iiit.ac.in Address: Robotics Research Center, IIIT Hyderabad
Giulio Ferro → affiliatedwith → University of Genoa
confidence 95% · Giulio Ferro Email: giulio.ferro@unige.it Address: Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa
Michela Robba → affiliatedwith → University of Genoa
confidence 95% · Michela Robba Email: michela.robba@unige.it
Marco Baglietto → affiliatedwith → University of Genoa
confidence 95% · Marco Baglietto Email: marco.baglietto@unige.it
Minimum Obstacle Displacement → solvedby → Horizon Slicing for MOD
confidence 95% · We introduce one such method, which we refer to as Horizon Slicing for MOD (HS4MOD in short), by dividing a MOD problem into (a sequence of) sub-problems.
Minimum Obstacle Displacement → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.22974v1
- Canonical: https://arxiv.org/abs/2609.22974v1
Trouble viewing inline? Open PDF directly →
Full Text
94,911 characters extracted from source content.
Expand or collapse full text
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation Journal: Elsevier Antony Thomas Email: antony.thomas@iiit.ac.in Address: Robotics Research Center, IIIT Hyderabad, Hyderabad 500032, India. Giulio Ferro Email: giulio.ferro@unige.it Address: Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145 Genoa, Italy. Fulvio Mastrogiovanni Email: fulvio.mastrogiovanni@unige.it Address: Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145 Genoa, Italy. Michela Robba Email: michela.robba@unige.it Address: Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145 Genoa, Italy. Marco Baglietto Email: marco.baglietto@unige.it Address: 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. Keywords: Motion Planning, Movable Obstacles, Computational Complexity, Optimization 1 Introduction Classical approaches to robot motion planning aim at finding a feasible path from a start to a goal location [18]. The feasibility of a motion plan is scenario-specific. It involves different constraints, such as the robot’s mechanical design, its actuators’ performance, the robot’s perception capabilities, uncertainties in state estimation and control signals, and the employed collision avoidance strategy. In principle, a complete path planner systematically explores the search space induced by the environment and the available planning information, examining all candidate paths consistent with its search strategy. If no feasible path exists because of the workspace configuration or due to constraints violation, the planner terminates reporting failure, or otherwise planners complete in probability can be used [22]. However, in several application domains, it could be legitimate to evaluate the possibility of relaxing some of the constraints hindering a feasible path. For example, let us consider a robot arm tasked with reaching a target object in a cluttered tabletop setting. It may be the case that no collision-free path exists due to the specific arrangement of objects on the table. However, objects themselves could be moved aside, therefore allowing the robot to reach the target object. Likewise, mobile robots may reach goal locations provided that certain obstacles could be rearranged or moved aside. This may involve, for example, pushing aside chairs or other furniture, as well as opening doors along the path. The Minimum Constraint Displacement (MCD in short) problem introduced by Hauser [10] seeks to minimize the amount of space by which one or more objects may have to be displaced in order to yield a feasible path. The approach by Hauser treats objects in so far as they can be modeled as constraints for the motion planner. Therefore, in addition to relocating obstacles or modifying their configurations, the same framework demonstrates how a humanoid robot may modify its own body configuration to climb a ladder, for instance, by slightly increasing its hip angle limits, as well as finger and thumb strengths, that is, the mechanical constraints. All the constraints are represented in a graph, in particular as sub-graphs involving, for each obstacle, its candidate displacements (that is, a set of sampled displacements), which are associated with cost functions subject to a minimization procedure. One of the main contributions of [10] is the proof that the discrete version of MCD is NP-hard. Two approaches to solve the problem are discussed, namely, a theoretically exact method, which has exponential time complexity in the worst case, and an approximate (greedy) approach providing fast solutions, but characterized by an unbounded approximation error. (a) (b) 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. This work focuses on scenarios in which a mobile robot must employ simple manipulation actions (such as, for example, pushing an object) when the goal location is not reachable due to the peculiar configuration of the environment. A first example is shown in Fig. 1(a), where a Pepper robot must displace objects (tables and chairs) to navigate through the passages between two areas. A second example, illustrated in Fig. 1(b), shows a mobile manipulator operating in an warehouse environment, which has to move obstacles out of its path, which is constrained by the green lines. Specifically, this paper is about how a robot can reach an assigned goal location by displacing obstacles while minimizing the total amount of obstacle displacements, and being able to trade off the number of obstacles to be displaced and the corresponding amount. In this work, we formulate a Minimum Obstacle Displacement (MOD) problem that minimizes a weighted cost of (a) total obstacle displacement magnitudes, and (b) robot path length, as the robot navigates to the goal location. (a) (b) (c) 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. This problem is shown to be NP-hard in Section 3, and therefore it is appropriate to look into approximate methods. We introduce one such method, which we refer to as Horizon Slicing for MOD (HS4MOD in short), by dividing a MOD problem into (a sequence of) sub-problems. Solving MOD by separating it into sub-problems is an approximation as MOD does not exhibit the optimal substructure property [6], that is, optimal solutions to sub-problems – when combined – do not necessarily form an optimal solution to the overall problem. This can be easily illustrated by an example. Let us consider the simple scenario shown in Fig. 2. The robot is required to move from a start (in green) to a goal (in red) location in the presence of movable obstacles (A, B, and C in the Figure). The robot can reach the goal location either by displacing obstacles A and B (that is, following the upper path) or by displacing obstacle C (the lower path). We note here that the start and goal locations are chosen for the sake of this example such that the robot path length for both the upper and the lower paths are equal. In Fig. 2(b), the problem is split into two sub-problems. In the first sub-problem, the robot can either displace obstacle A by 2 space units or obstacle C by 3 units. Since minimum displacement is solicited (and path lengths are equal as argued above), the robot chooses to move obstacle A by 2 units. On the one hand, if the robot moved through the upper path by displacing A, in the next sub-problem it would have to move obstacle B by 2 units to reach the goal location, and therefore the total displacement magnitude would amount to 44 space units. On the other hand, displacing C by 3 units would generate a feasible path for the robot as shown in Fig. 2(c), and it would clearly be the optimal solution. This shows with a counterexample that the optimal solution to MOD cannot be obtained simply by juxtaposing optimal solutions to its sub-problems. It is important to note that, in this work, we are not concerned about how objects can be displaced, both in terms of task or motion planning [4]. Neither are we concerned about the weight of an obstacle, or whether it would be necessary to push or pull it, in case of displacement. What we are concerned with is the amount by which obstacles must be displaced to yield a feasible path and assume that the computed displacements can be achieved by appropriate robot-obstacle physical interactions. From an algorithmic perspective, this assumption allows us to (1) assume a planar, 2D projection of the 3D environment, and (2) compute only the locations on such a plane where the obstacles are to be displaced. The same assumption allows us to consider events (both robot motions as well as object displacements) as collapsed to discrete time instants. If the robot took T discrete time instants to reach the goal location, with 0≤k≤T0≤ k≤ T, we could associate both control actions and obstacle displacements (and zero displacements if an obstacle is not affected) to each time instant k in the sequence. In this work, we also disregard obstacle interactions, that is, the displaced obstacles are allowed to overlap with other obstacles, and therefore obstacle-obstacle collision avoidance is not considered. The main contributions of the paper are: 1. We prove that MOD is NP-hard even if all the obsatcles are line segments by a reduction from the Partition Problem, which is NP-hard [23]. We further show that MOD remains NP-hard when the obstacles are restricted to axis-aligned rectangles. In addition, we establish the NP-hardness of MOD for circular obstacles. Together, these results substantially strengthen the NP-hardness result for the discrete MCD problem reported in [10]. 2. We present an exact approach to MOD by formulating the problem as a Mixed Integer Quadratic Programming problem. This approach returns exact solutions able to weight between path length and displacement amount but has worst-case exponential time. 3. We introduce HS4MOD, an approximation method for MOD that divides MOD into m sub-problems and obtains a solution from a combination of optimal – yet local – solutions to these sub-problems. HS4MOD is shown to exhibit significant computational improvement over the exact approach even when the number of sub-problems is limited to two or three. For all the results presented in Section 6, we also compute the optimality gap, that is, the relative distance between the approximate and the optimal solution, with the aim of evaluating the quality of the solutions provided by HS4MOD. The paper is organized as follows. We discuss related literature in Section 2.1. In Section 2.2, we provide a formal definition of the problem. We show in Section 3 that MOD is NP-hard for polygonal obstacles in a plane. Section 4 presents an exact mixed integer quadratic program optimization for MOD, and in Section 5 we introduce an approximate strategy for its solution. HS4MOD obtains a solution to MOD that combines optimal yet local solutions to its sub-problems. In Section 6, we evaluate HS4MOD under varying domains, distinct robot models, and different numbers of obstacles. The discussion in Section 7 concludes the paper. 2 Background and Problem Definition 2.1 Related Work The problem we address in this paper shares some resemblance with a number of apparently similar problems discussed in the literature. Herein, we describe the related classes of problems highlighting similarities and differences, and we argue that MOD deserves a principled treatment on its own. The MCD planner presented and discussed in [10] proceeds by (1) building a road map of robot configurations, and (2) sampling random obstacle displacements. The quality of the solution is improved by iteratively expanding the road map and the displacement samples. The method is shown to asymptotically approach the true optimum as the number of samples (both robot configurations and displacements) grow in size. In contrast, we formulate an exact approach, incorporting the robot kinematics and solve it find the optimal solution. Furthermore, we present an approximate method and compute its deviation from the computed optimal solution. MCD focuses on pure motion planning in the sense that it ignores robot dynamics and other differential constraints, and finds the translations and rotations required to move the robot. In our case, we plan a trajectory taking into account robot dynamics and other constraints such as control limits and collision constraints, to find the sequence of control actions to move the robot to the goal location. The work in [37] examines minimum displacement planning for movable obstacles through a two-stage process. The first stage proceeds by finding a path through a set of movable obstacles while minimizing robot-obstacle overlaps. In the second stage, the overlapping obstacles are displaced iteratively by a distance factor until no overlap is found. However, the synthesized solutions are not necessarily optimal, and no guarantees or discussion regarding their quality are provided. Our approach computes the exact optimum and, for the proposed approximation algorithm, quantifies its solution quality with respect to the exact method across all experimental evaluations. In a general sense, the problem we address is closely related to the Navigation Among Movable Obstacles (NAMO) class of problems [30, 26, 31, 40, 42]. Most approaches for NAMO focus on connecting pairwise separated configuration regions by displacing objects as the robot proceeds to the goal location, and seek to find a motion plan that displaces the least number of obstacles while minimizing the work done to do it. Learning-based and language model-based approaches have also been explored for NAMO [48, 46]. However, these methods do not explicitly account for minimizing the displacement of manipulated objects during task execution. NAMO problems are shown to be NP-hard if the final obstacle locations are unspecified, and PSPACE-hard when the locations are specified instead [43]. Stilman and Kuffner [30] address linear problems of degree 1 (LP1LP_1), that is, two disjoint regions in the configuration space are linked by displacing a single obstacle. Subsequent studies [26, 31, 40] extend this concept to LPkLP_k, where at most k obstacles are displaced to connect two free configuration regions. As such, NAMO relies on keyhole solutions, where a keyhole is the sub-problem of moving one (LP1LP_1) or more objects (LPkLP_k) to connect two regions of the free configuration space. Unlike these approaches, our method does not partition the configuration space into disconnected regions, nor does it impose restrictions on the number of obstacles that may be displaced. Though NAMO incorporates manipulation actions by selecting from obstacle contact points, the obstacles may be displaced unnecessarily far. Exact MOD tackles both displacement and path optimality concurrently. Disconnection Proving in Motion Planning [2, 47, 19, 20] poses related challenges since it tries to find constraints preventing a robot to move from start to goal locations. Our approach does not need to consider explicitly hindering constraints, but adopts a horizon-slicing approximation, which requires connecting all the sub-optimal solutions. The work in [36] considers a unified approach for solving constraint displacement problems (MOD, MCR, NAMO) by varying the objective function of a common optimization framework. However, the solutions obtained are suboptimal and lack guarantees with respect to optimality. Manipulation Among Clutter or Rearrangement Planning [32, 8, 16, 13] is another related class of problems wherein objects may need to be displaced or rearranged to perform a given task. However, in these problems, the final location of the objects is either specified, or it could occur that displaced objects may be placed anywhere in the (free) workspace. Similarly, approaches for integrated Task and Motion Planning (TaMP) [12, 29, 7, 9, 33, 14] also bear resemblance to the problem discussed in this paper since task execution may require dealing with, at the motion planning level, constraints not considered at the task planning level. It is worth noting that the problem we consider here could be one of the key elements in such classes of problems. The Minimum Constraint Removal problem (MCR) [11] finds the minimum number of movable obstacles that should be removed to yield a feasible path, but does not determine where the obstacles should be moved for creating such a path. Different algorithms for MCR exist in the literature [5, 45, 17, 44, 35], and the problem is proven to be NP-hard for convex polygonal obstacles [11]. Our formulation supersedes this class of approaches in that it determines also each object’s displacement. 2.2 The Minimum Obstacle Displacement Problem Let us consider a generic robot, and let kx_k denote the robot state at any time instant k. Let us consider, for the sake of the discussion, a scenario where a mobile robot should reach a goal location, and therefore kx_k may denote its pose in terms of position and orientation. We assume a standard motion model for the robot given by k+1=f(k,k),x_k+1=f(x_k,u_k), (1) where ku_k is the control action applied at time instant k, where k∈0,…,T−1k∈\0,…,T-1\. Furthermore, let sx^s and gx^g denote the start and goal configurations, respectively. We shall denote the robot position at time k by k⊆kp_k _k, and the sequence of all the positions from 00 to T as p. Let =oi∣1≤i≤||O=\o^i 1≤ i≤|O|\ represent the set of obstacles in the environment, where ℳ⊆M is the set of movable obstacles. We will use kio^i_k to denote the obstacle state associated with the obstacle oio^i at time k. As it has been argued in the previous Section, at each time instant k, obstacles in ℳM are associated with a displacement set k=dki∈ℝn| 1≤i≤ℳD_k=\d^i_k ^n|\ 1≤ i \ representing the corresponding obstacle displacements, where dki=0d^i_k=0 in case the object oi∈ℳo^i is not displaced at time k. Both kx_k and all obstacle locations kio^i_k are, in principle, elements of the configuration space. It may be useful to define a function O that, when applied to the robot pose at time instant k, maps to the set of points corresponding to the robot body, namely O(k)O(x_k), and when applied to an obstacle pose kio^i_k, maps to the set of points corresponding to the obstacle itself, namely O(ki)O(o^i_k). Before formally defining the problem addressed in this paper, we will rephrase the conceptual perimeter of this work: 1. We do not focus on how objects are displaced; 2. We do not take into account the weight of the obstacles, and instead we focus solely on their 2D projections; 3. This work does not take into consideration collision avoidance among obstacles. 4. We assume that a map of the environment is available a priori. Consequently, the proposed method is an offline planning approach that computes the required displacement for each obstacle before execution. Now, we proceed to formally define the problem that is the focus of this paper. Definition 1. The Minimum Obstacle Displacement (MOD) planning problem finds a sequence of control actions 0,…,T−1u_0,…,u_T-1 which make the robot navigate from sx^s to gx^g with obstacle displacement magnitudes D1,…,DℳD^1,…,D^M and is defined as minwxc()+wd∑i=1ℳci(Di), min w^xc(p)+w^d _i=1^Mc^i(D^i), (2a) s.t. [ $ min$][c] [ $min$][l] 1.00006pts.t. c()=∑k=0T−1‖k+1−k‖2+wg‖T−g‖2, c(p)=Σ _k=0^T-1 \! _k+1-p_k ^2+w^g \! _T-p^g ^2, (2b) O(k)∩⋃i=1||O(ki)=∅,∀k∈[1,T], O(x_k)∩ _i=1^|O|O(o_k^i)=\ \,\ ∀ k∈[1,T], (2c) c(Di)=∑k=0Tdki, c(D^i)= _k=0^Td^i_k, (2d) 1=s. _1=x^s. (2e) The objective function (2a) aims to minimize two components: the first component c()c(p) is composed of two terms as given in (2b), which represent the length of the robot path while keeping track of the goal (g)(p^g) as terminal position, weighted by wgw^g; in the second component, ci(Di)c^i(D^i) are functions of displacement magnitudes; wxw^x, wdw^d are the respective weights for the two components. By tuning the weights in an appropriate way, it is possible to trade off path length and the magnitude of displacements, thereby allowing for shortest paths or more disruptive obstacle displacements. Condition (2c) guarantees that the robot does not intersect obstacles at any time. We note here that for obstacles with fixed position, O(ki)O(o_k^i) remains constant throughout. Condition (2d) defines the total displacement of obstacles, and the initial condition is established in (2e). It can be easily verified that when all displacements DiD^i are equal to 00, MOD solves the classical motion planning problem (see Section 6 for an example). Furthermore, MOD solves the shortest path problem if c()c(p) measures the path length, and wd=wxLsw^d=w^xL^s, where LsL^s is equal to the length of the shortest feasible path. MOD can also be employed to determine the minimum number of obstacles to be removed to find a feasible path, which is basically the MCR problem with constraints being obstacles. This is achieved by assigning wx=0w^x=0 and limiting di=0,1d^i=\0,1\, that is, di=0d^i=0 for the obstacles being present and di=1d^i=1 for the obstacles that are removed (an example is given in Section 6). It is noteworthy that by modifying ci(Di)c^i(D^i) to incorporate the work done by the robot, MOD solves a variant of the NAMO problem [30]. Similarly, by relaxing wdw^d, MOD may be employed to solve variants of the re-arrangement planning problem. Therefore, it can be deduced that MOD can generalize different classes of motion planning problems, and it deserves a treatment on its own. 3 Complexity of the MOD Problem 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 pi/2p^i/2. Otherwise, the robot has to move vertically for a distance of pi/2p^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. In this Section, we show that MOD is NP-hard for polygonal obstacles in the plane by considering two special cases, namely obstacles (1) as line segments, and (2) as axis-aligned rectangles with a unique displacement value. Furthermore, we also prove that MOD is NP-hard for circular-shaped obstacles. 3.1 MOD for Line Segments is NP-hard We consider the class of problems in which obstacles are disjoint (vertical) line segments and do not touch each other. Therefore, there exists a feasible path (in the classical motion planning sense). However, it might be useful to displace some obstacles to obtain a shorter path. We consider the decision variant of the problem, that is, if there is a feasible path to a goal location given a maximum path length of LmL^m and a maximum displacement budget DmD^m. This problem is NP-hard by reduction from the Partition problem, which is NP-complete [23]. We now prove the hardness. Given a set P=p12,…,pn2P= \ p^12,…, p^n2 \ of n positive integers, the Partition problem checks whether two sets P1P1 and P2=P−P1P2=P-P1 exist such that S(P1)=S(P2)=S(P)/2S(P1)=S(P2)=S(P)/2, where S(⋅)S(·) computes the sum of the elements in the set. With reference to Fig. 3, we place the goal location gx^g at a distance of n+1n+1 units along the x-axis from the start location sx^s. We have n line segments, whereas each line segment i is of length pip^i, and is placed at a distance of i units from the start location. We set Dm=S(P)2D^m= S(P)2 and Lm=2(S(P)2)+(n+1).L^m=2 ( S(P)2 )+(n+1). Furthermore, we construct two vertical and two horizontal line segments as static obstacles close to each of the n movable obstacles. The fixed vertical line segments have a length of 2Lm+12L^m+1 and are separated from each other by a distance δ=1/4nδ=1/4n, which is assumed to be small enough for the robot to pass through. They are constructed to lie to the left of each movable obstacle at a distance of δ. The horizontal obstacle segments have a length of (1−2δ)(1-2δ), and are placed touching the right end of each obstacle at i and lie symmetrically at a distance of pi/2p^i/2 from the x-axis. As a consequence of this construction, the set P can be partitioned into two sets P1P1 and P2=P−P1P2=P-P1 such that S(P1)=S(P2)S(P1)=S(P2) only if there is a path from sx^s to gx^g of length at most LmL^m, and displacement cost of at most DmD^m. Thus, MOD for (vertical) line segments in a plane is NP-hard. Figure 4: Movable rectangles are shown in cyan and can be displaced only by an amount rir^i. Drawn in black are the obstacles constructed to achieve the reduction of the Partition problem. 3.2 MOD for Axis-aligned Rectangles with Constant Displacement Cost is NP-hard In this configuration, each axis-aligned rectangle i is allowed a single displacement11 1 We note here that while the result presented is of theoretical interest, in the real world the single-displacement value considered here can be mapped to obstacles moving to a specified final location – for example, the transportation of pallets in logistics [24]. of magnitude rir^i. We consider again the decision version of the problem, that is, given a set of n movable obstacles in the form of axis-aligned rectangles, we want to ascertain if there is a feasible path from sx^s to gx^g such that the maximum path length and displacement do not exceed LmL^m and DmD^m, respectively. The NP-hardness can be proved by reduction from the Partition problem. In order to prove the hardness, the scenario as shown in Fig. 4 is constructed. We place sx^s and gx^g at a distance of 2n+12n+1 units along the x-axis. Each left end of a movable rectangle i is placed at 2i−12i-1 units from sx^s. The rectangles have a length of rir^i and a width of 11 unit, and are allowed to be displaced of rir^i units in the vertical direction. At a distance of 2(i−1)+δ2(i-1)+δ units from sx^s we place two rectangular obstacles, vertically separated by a distance δ=1/4nδ=1/4n, which is small enough for the robot to pass through. Each of these rectangles has a length of 2Lm+12L^m+1 and a width of 1−2δ1-2δ. Now, let us consider a set R=r1,…,rnR=\r^1,…,r^n\ and let Dm=S(R)2D^m= S(R)2 and Lm=S(R)2+(2n+1).L^m= S(R)2+(2n+1). The set R can be partitioned into two sets R1R1 and R2=R−R1R2=R-R1 such that S(R1)=S(R2)S(R1)=S(R2) only if there is a path from sx^s to gx^g of length at most LmL^m, and displacement cost of at most DmD^m. Thus, the problem of deciding if there is a path with length at most LmL^m and displacement cost at most DmD^m is NP-hard. Figure 5: Construction for NP-hardness proof of MOD with circular obstacles. See text for further details. 3.3 MOD for Circular Obstacles is NP-hard Let us consider a scenario where circular obstacles are located on the plane. When the robot encounters an obstacle at point p (refer to Fig. 5), it navigates along the arc pp′ p if the obstacle remains stationary, with p′p denoting the point where the robot departs from the obstacle’s boundary. If the obstacle is displaced, the shortest path pp′¯ p for the robot is achieved by displacing the obstacle at least by an amount d=ab¯d= ab, with oa¯⟂pp′¯ oa p , and o being the center of the obstacle. Thus, for a given displacement d, the shortest path pp′¯ p may easily be computed as pp′¯=2r2−(r−d)2, p =2 r^2-(r-d)^2, with r denoting the radius of the obstacle. If the obstacle is displaced by an amount d, the robot path length decreases by an amount pp′ −pp′¯ to12.87pt to9.96pt 6.43402pt -1.94443pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-6.43402pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -8.9 0) @hbox61 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to12.87pt to9.46pt 6.43402pt -1.94443pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-6.43402pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -8.9 0) @hbox61 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to10.95pt to7.16pt 5.47478pt -1.36108pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-5.47478pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -7.58 0) @hbox61 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to10.1pt to5.19pt -0.9722pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @transformcm1.00.00.01.0-5.05098pt0.0pt @begingroup@transform=matrix(1.0 0.0 0.0 1.0 -6.99 0) @hbox61 @closescope @closescope @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope to0pt to0pt 0.0pt 0.0pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @stroke @drawpath@unclippedM -9.18 12.06 C -2.45 14.51 2.45 14.51 9.18 12.06fill:none @inpgf@ignorespaces @closescope to0.0pt @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope - p . For the discussion that follows, the decrease in the path length for a given d will be referred to as the value associated with d. We now establish the NP-hardness of the MOD problem by a polynomial-time reduction from the Multiple-Choice Knapsack Problem (MCKP), which is NP-hard [15]. We consider the budget-constrained discrete special case of MOD, in which a finite set of admissible displacements is specified for each movable obstacle and the total obstacle displacement is bounded by a given budget DmD^m. In an instance of MCKP, there are n mutually disjoint classes M1,…,MnM^1,…,M^n of items and a knapsack of capacity c. Each item j∈Mij∈ M^i has a weight WijW^ij and a profit PijP^ij. The objective is to select exactly one item from each class such that ∑i=1nWiji≤c _i=1^nW^ij_i≤ c, while maximizing ∑i=1nPiji _i=1^nP^ij_i. We construct an instance of the budget-constrained discrete MOD problem with n movable circular obstacles, where obstacle i corresponds to class MiM^i. For every item j∈Mij∈ M^i, we construct one admissible displacement dijd^ij and its corresponding path-length reduction vijv^ij. The construction is chosen such that dij=Wij,vij=Pijd^ij=W^ij,v^ij=P^ij. The latter correspondence is realizable from the circular-obstacle geometry since the path-length reduction produced by a displacement d of a circular obstacle of radius rir_i is Vi(d)=2ri2−(ri−d)2=22rid−d2.V_i(d)=2 r_i^2-(r_i-d)^2=2 2r_id-d^2. For a prescribed value PijP^ij, an appropriate radius and displacement can be selected so that Vi(dij)=PijV_i(d^ij)=P^ij. In particular, the geometric parameters can be constructed using the inverse relation ri=(Pij)2+4(dij)28dijr_i= (P^ij)^2+4(d^ij)^28d^ij, with the construction chosen consistently for the admissible displacement set of obstacle i. We then set the maximum total displacement to Dm=cD^m=c. Consequently, selecting one displacement for each obstacle gives ∑i=1ndiji≤Dm⟺∑i=1nWiji≤c _i=1^nd^ij_i≤ D^m _i=1^nW^ij_i≤ c, while maximizing the total path-length reduction gives max∑i=1nviji⟺max∑i=1nPiji _i=1^nv^ij_i _i=1^nP^ij_i. Thus, every feasible selection of one item from each MCKP class corresponds to a feasible selection of one displacement for each obstacle, with identical objective value, and vice versa. Hence, an optimal solution of the constructed MOD instance yields an optimal solution of the original MCKP instance. The construction requires only a polynomial number of obstacle parameters and displacement choices, and therefore can be performed in polynomial time. Hence, the budget-constrained discrete special case of MOD, and consequently MOD itself, is NP-hard. 4 An Exact Approach to Solve MOD In this Section, we present an exact approach to solve MOD that achieves an optimal, global solution, albeit computationally expensive as the set of obstacles O and the robot workspace grow. 4.1 The Optimization Problem Using the models related to robots and obstacles, we formulate MOD as an optimization problem that finds a feasible path for the robot to the goal location while minimizing a trade off between path length and obstacle displacements. While doing so, control inputs and state variables must lie within their respective feasible sets, and the robot should not collide with obstacles. Starting from the general formulation of the MOD problem, the overall optimization problem can be thus formalized as follows. minJ=wxc()+wd∑i=1ℳci(Di), min J=w^xc(p)+w^d _i=1^Mc^i(D^i), (3a) s.t. [ $ min$][c] [ $min$][l] 1.00006pts.t. k+1=f(k,k), _k+1=f(x_k,u_k), (3b) k+1=g(k,k), _k+1=g(o_k,d_k), (3c) ¯≤k≤¯, x _k≤ x, (3d) ¯≤k≤¯, u _k≤ u, (3e) ¯≤k≤¯, o _k≤ o, (3f) ¯≤k≤¯, d _k≤ d, (3g) O(k)∩⋃i=1||O(ki)=∅,∀k∈[0,T], O(x_k)∩ _i=1^|O|O(o_k^i)=\ \,\ ∀ k∈[0,T], (3h) ∀k∈1,…,T, ∀ k∈\1,…,T\, where an obstacle at time k, denoted by oko_k, is displaced by kid^i_k according to some function g(⋅)g(·), which denotes the employed robot strategy to move away objects. The robot and obstacle dynamics are represented in constraints (3b)-(3c) subject to the upper and lower bounds on the state and control variables as given in (3d)-(3g). Finally, constraint (3h) represents the collision avoidance constraint between the robot and the obstacles. 4.2 Obstacles’ Model As we noted before, we are not concerned about how obstacles are displaced by a robot, and we assume that they can be re-positioned irrespective of the nature of the required robot-obstacle interaction. In the formulation of the optimization problem, this is encoded in a generic function g(⋅)g(·). Therefore, an obstacle may be moved without any constraints. Each obstacle is capable of translation and rotation and hence the state i=[oi,x,oi,y,oi,θ]o^i=[o^i,x,o^i,y,o^i,θ] includes translations in the x and y directions, as well as a rotation. This yields the following linear model for an obstacle oio^i: ok+1i,x=oki,x+dki,x,ok+1i,y=oki,y+dki,y,ok+1i,θ=oki,θ+dki,θ, splito^i,x_k+1&=o^i,x_k+d^i,x_k,\\ o^i,y_k+1&=o^i,y_k+d^i,y_k,\\ o^i,θ_k+1&=o^i,θ_k+d^i,θ_k,\\ split (4) where ki=[dki,x,dki,y,dki,θ]d^i_k=[d^i,x_k,d^i,y_k,d^i,θ_k] specify the obstacle’s displacement between time instants k and k+1k+1. Thus, the displacement between two time instants for the obstacle oio^i is dki=‖ki‖d^i_k= \! ^i_k . In analogy to the standard motion model introduced in (1), we may write (4) compactly as k+1=g(k,k)o_k+1=g(o_k,d_k). We note that, in many warehouse, logistics, and other structured environments, the placement regions for movable objects are predefined. In such scenarios, these placement regions can be directly treated as displacement sets from which the object configurations are sampled. This eliminates the need to explicitly formulate the obstacle model as described above, thereby reducing the solution search space and, consequently, the computational complexity of the problem. 4.3 Robot’s Model We do not assume any specific robot motion model for the validity of our work, and we refer to any standard motion model as in the form given in (1). However, as it will become clear in later Sections, we distinguish between linear and nonlinear robot models. In this paper, we consider two different linear models. The first is a trivial model similar to the obstacle model in (4), such as xk+1=xk+τukx,yk+1=yk+τuky,θk+1=θk+τukθ, splitx_k+1&=x_k+τ u^x_k,\\ y_k+1&=y_k+τ u^y_k,\\ _k+1&= _k+τ u^θ_k,\\ split (5) with k=[xk,yk,θk]x_k=[x_k,y_k, _k] as the robot pose and k=[ukx,uky,ukθ]u_k=[u^x_k,u^y_k,u^θ_k] as the applied control at time instant k. We also consider the linear dynamics model borrowed from [38] with a robot state k=[xk,yk,vkx,vky]x_k=[x_k,y_k,v^x_k,v^y_k] consisting of its location and velocity, and with acceleration input k=[akx,aky]u_k=[a^x_k,a^y_k]. The corresponding model is xk+1=xk+τvkx+τ22akx,yk+1=yk+τvky+τ22aky,vk+1x=vkx+τakx,vk+1y=vky+τaky, splitx_k+1&=x_k+τ v^x_k+ τ^22a^x_k,\\ y_k+1&=y_k+τ v^y_k+ τ^22a^y_k,\\ v^x_k+1&=v^x_k+τ a^x_k,\\ v^y_k+1&=v^y_k+τ a^y_k,\\ split (6) where τ is, again, the duration of a time step. The use of linear models allows for obtaining optimal, global solutions, albeit dependent on the nature of the objective function as well as other constraints. However, the motion model of mobile robots is often nonlinear. Nonlinear and non-convex models provide weak theoretical guarantees and the optimization often results in local minima. Nevertheless, we evaluate our approach on two different nonlinear models. The first model is a simple differential drive model [18] given by xk+1=xk+τukcosθk,yk+1=yk+τuksinθk,θk+1=θk+τωk, splitx_k+1&=x_k+τ u_k _k,\\ y_k+1&=y_k+τ u_k _k,\\ _k+1&= _k+τ _k, split (7) where k=[xk,yk,θk]x_k=[x_k,y_k, _k] is the robot state and k=[uk,ωk]u_k=[u_k, _k] is the applied control at time instant k. We then consider the case of a non-holonomic car-like robot [39] xk+1=xk+τvkcosθk,yk+1=yk+τvksinθk,θk+1=θk+τvktanϕkl,vk+1=vk+τak, splitx_k+1&=x_k+τ v_k _k,\\ y_k+1&=y_k+τ v_k _k,\\ _k+1&= _k+τ v_k _kl,\\ v_k+1&=v_k+τ a_k, split (8) where k=[xk,yk,θk,vk]x_k=[x_k,y_k, _k,v_k] is the robot state consisting of its pose and speed, k=(ak,ϕk)u_k=(a_k, _k) is the applied control consisting of the acceleration and steering wheel angle, τ is the duration of a time-step, and l is the length of the robot. 4.4 Collision Avoidance So far we have been agnostic to the structure of the constraint in (3h). In the following paragraphs, we formulate the collision avoidance constraint more precisely. We will consider two such constrains, namely (1) polygon-shaped obstacles, and (2) circle-shaped obstacles. 4.4.1 Polygonal Obstacles A polygonal obstacle can be represented as a polyhedron P, that is, the intersection of N∈ℕN halfspaces, such that =x∈ℝ2|Ax≤b,P=\x ^2|Ax≤ b\, (9) where A=(a1,…,aN)TA= (a^1,…,a^N )^T and b=(b1,…,bN)Tb= (b^1,…,b^N )^T. Each row aix≤bia^ix≤ b^i defines one of the halfspaces of P. For this specific shape, the collision avoidance constraint can be written by means of a mixed integer formulation as ai(k−)≥bi−ckiM,i=1,…,Na^i (p_k-o^i_k )≥ b^i-c_k^iM, i=1,…,N (10) ∑i=1Ncki≤N−1, _i=1^Nc^i_k≤ N-1, (11) where cki∈0,1c^i_k∈ \0,1 \ are binary auxiliary variables and M is a constant suitably large. It is important to note that (10) and (11) holds ∀k∈1,…,T−1∀ k∈\1,…,T-1\ and ∀i∈1,…,||∀ i∈\1,…,|O|\. 4.4.2 Circular Obstacles It is common practice to model robot and obstacles using approximate bounding volume spheres [27, 34]. In such cases, the collision avoidance constraint is given by ‖k−‖≥r+ro, \! _k-o^i_k ≥ r^r+r^o, (12) where kp_k, o^i_k are the midpoints of the robot and obstacle circles (that is, the 2D projections of the sphere on the supporting plane), respectively, whereas r^r and ror^o are the corresponding radii. When the robot and all the obstacles are modeled as circles, the collision avoidance constraint in (12) can be linearized by introducing j binary auxiliary variables ξkj,i∈0,1ξ^j,i_k∈ \0,1 \ for each obstacle i∈o^i at every time instant k. The constraint (12) is thus rewritten as xk−oki,x≥r+ro−ξk1,iM, x_k-o^i,x_k≥ r^r+r^o-ξ^1,i_kM, (13) −(xk−oki,x)≥r+ro−ξk2,iM, - (x_k-o^i,x_k )≥ r^r+r^o-ξ^2,i_kM, (14) yk−oki,y≥r+ro−ξk3,iM, y_k-o^i,y_k≥ r^r+r^o-ξ^3,i_kM, (15) −(yk−oki,y)≥r+ro−ξk4,iM, - (y_k-o^i,y_k )≥ r^r+r^o-ξ^4,i_kM, (16) ∑j=14ξkj,i≤3, _j=1^4ξ^j,i_k≤ 3, (17) where it holds ∀k∈1,…,T−1∀ k∈\1,…,T-1\ and ∀i∈1,…,||∀ i∈\1,…,|O|\, and M is a suitably large constant. As a result of (10), (11), (13)-(17) the optimization problem in (3) can be effectively converted into a Mixed Integer Quadratic Programming (MIQP) problem. MIQPs are a class of optimization problems with a quadratic objective function subject to linear constraints, and involving both continuous and discrete decision variables. It is well known from Operations Research theory that there are algorithms guaranteeing global optimality for this type of optimization problem. In case of nonlinear robot dynamics, the optimization problem (3) is an instantiation of Nonlinear Programming (NLP). However, due to the non-convex nature of the NLP formulation, it is not possible to guarantee a global optimum [28]. If we choose to reformulate the collision avoidance constraints by introducing auxiliary variables (as shown in (10)-(11) and (13)-(17), the optimization problem transforms into a Mixed Integer Nonlinear Programming (MINLP) problem. This change in problem class increases complexity further due to the combinatorial aspects introduced by the use of binary variables. Moreover, global optimization algorithms for MINLPs often necessitate convexity in both the objective and constraint functions [3]. Therefore, for nonlinear robot models, we resort to solving the NLP formulation to obtain sub-optimal solutions. 5 A Horizon-Slicing Heuristic to Solve MOD In the previous Section, we have modeled MOD as an optimization problem, as formulated in (3). The exact solution method does not solve all problem instances efficiently, because of its inherent intractability, and it seems beneficial to search for approximate solutions. This is the case in many practical situations in which we are concerned with obtaining a feasible yet sub-optimal solution that has the major advantage of being computed easily. As discussed above, in MIQP problems, the worst-case computational complexity grows exponentially with the number of binary and/or integer decision variables [25]. As a case in point, consider the linearisation of (12), where for each obstacle we have introduced four binary variables (13)-(16) to formulate the optimization as an MIQP problem when the robot dynamics is linear. The number of feasible combinations of the binary variables is thus 24×T×||2^4× T×|O|, where T is the number of time steps required to reach the goal location. With the increase in the number of movable obstacles and the environment size (in the sense that the larger the environment, the higher the value of T on average), the optimization process tends to be computationally unfeasible. The computational burden could be reduced by decreasing the number of variables. One naïve way to achieve this result is by progressively solving subsets of the overall problem, each subset being computationally less expensive compared to solving the complete optimization problem at once. However, we have already seen that MOD does not exhibit the optimal substructure property. Therefore, solving subsets of the whole problem does not necessarily guarantee an optimal solution at the global level. Figure 6: An illustration of the horizon-slicing approach employed in this work. x(⋅)x(·) 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)x(1). The output of the first slice x(T′)x(T ) is the initial state for the next slice. The values of the time-dependent variables are passed on to the slices that follow. 5.1 HS4MOD In order to reduce the computational effort (at the expense of giving up optimality) we temporally partition the whole optimization problem into m sub-problems, each one of duration T′T such that mT′=TmT =T. In this paper, we simply slice the number of time steps required to reach the goal location into a smaller duration, and solve the optimization problem for each slice separately. Once each sub-problem undergoes a specific optimization process, the values of time-dependent variables are passed on to the sub-problem that follows. This concept is illustrated in Fig. 6. It should be pointed out that different, probably smarter strategies to horizon-slicing may be employed, for instance related to the adopted motion planning approach. A comprehensive analysis of such strategies is outside the scope of this paper, whereas the adopted horizon-slicing approach serve the purpose of allowing us to draw a number of general conclusions about sub-optimality and time complexity, which can be used as prerequisite work to ground further strategies. Let us consider the objective function J in (3a), and let us denote the optimal objective function without horizon-slicing as J⋆J . We thus have: J⋆=wxc()+wd∑i=1ℳci(Di)=∑k=0T−1wx‖k+1−k‖2+wxwg‖T−g‖2+wd∑i=1ℳ∑k=0Tdki=∑k=0T−1(wx‖k+1−k‖2+wd∑i=1ℳdki)+wxwg‖T−g‖2+wd∑i=1ℳdTi. splitJ &=w^xc(p)+w^d _i=1^Mc^i(D^i)\\ &=Σ _k=0^T-1w^x \! _k+1-p_k ^2+w^xw^g \! _T-p^g ^2+\\ &\ \ \ \ \ w^d _i=1^M _k=0^Td^i_k\\ &=Σ _k=0^T-1 (w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k )+\\ &\ \ \ \ \ w^xw^g \! _T-p^g ^2+w^d _i=1^Md^i_T.\\ split (18) Let us now focus on the terms inside the bracket. This sum can be re-written as ∑k=0T−1wx‖k+1−k‖2+wd∑i=1ℳdki=[∑k=0T′−1wx‖k+1−k‖2+wd∑i=1ℳdki]+…+[∑k=(m−1)T′T−1wx‖k+1−k‖2+wd∑i=1ℳdki]=J0→T′−1⋆,s+…+J(m−1)T′→T−1⋆,s=∑j=1mJ(j−1)T′→jT′−1⋆,s, split&Σ _k=0^T-1w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k\\ &= [Σ _k=0^T -1w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k ]+\\ &\ \ \ \ \ …+\\ &\ \ \ \ [Σ _k=(m-1)T ^T-1w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k ]\\ &=J ,s_0→ T -1+…+J ,s_(m-1)T → T-1\\ &= _j=1^mJ ,s_(j-1)T → jT -1,\\ split (19) where J(j−1)T′→jT′−1⋆,s=∑k=(j−1)T′jT′−1(wx‖k+1−k‖2+wd∑i=1ℳdki),J ,s_(j-1)T → jT -1= _k=(j-1)T ^jT -1 (w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k ), (20) and m is the number of slices. Thus, (18) can be written as J⋆=∑j=1mJ(j−1)T′→jT′−1⋆,s+wxwg‖T−g‖2+wd∑i=1ℳdTi.J = _j=1^mJ ,s_(j-1)T → jT -1+w^xw^g \! _T-p^g ^2+w^d _i=1^Md^i_T. (21) Let us now consider the scenario wherein we partition the horizon and address m distinct optimization problems. For each horizon slice j, the corresponding objective function is formulated as Jj=∑k=(j−1)T′jT′−1(wx‖k+1−k‖2+wd∑i=1ℳdki)+wxwg‖jT′−1−g‖2+wd∑i=1ℳdjT′−1i.J^j= _k=(j-1)T ^jT -1 (w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k )+\\ w^xw^g \! _jT -1-p^g ^2+w^d _i=1^Md^i_jT -1. (22) Let us define ηj=wxwg‖jT′−1−g‖2+wd∑i=1ℳdjT′−1iη^j=w^xw^g \! _jT -1-p^g ^2+w^d _i=1^Md^i_jT -1. Using the simplification employed in (19), (22) can be written as Jj=J(j−1)T′→jT′−1j,s+ηj.J^j=J^j,s_(j-1)T → jT -1+η^j. (23) Adding the objective function for the m horizon slices and using the fact that ηm=wxwg‖T−g‖2+wd∑i=1ℳdTi,η^m=w^xw^g \! _T-p^g ^2+w^d _i=1^Md^i_T, (24) we have J=∑j=1m(J(j−1)T′→jT′−1j,s+ηj)=∑j=1mJj,s(j−1)T′→jT′−1+∑j=1m−1ηj+wxwg‖T−g‖2+wd∑i=1ℳdTi. splitJ&= _j=1^m (J^j,s_(j-1)T → jT -1+η^j )\\ &= _j=1^mJ^j,s_(j-1)T → jT -1+ _j=1^m-1η^j\ \ +\ \ \\ &\ \ \ \ w^xw^g \! _T-p^g ^2+w^d _i=1^Md^i_T.\\ split (25) Algorithm 1 HS4MOD 1: T,T′,m,s,g,,ℳ,wx,wd,wg,f(⋅),g(⋅)T,T ,m,x^s,x^g,O,M,w^x,w^d,w^g,f(·),g(·) 2: for j=1,…,mj=1,…,m do 3: Jj←0J^j← 0 4: for k=(j−1)T′,…,jT′−1k=(j-1)T ,…,jT -1 do 5: Jj←Jj+wx‖k+1−k‖2+wd∑i=1ℳdkiJ^j← J^j+w^x \! _k+1-p_k ^2+w^d _i=1^Md^i_k 6: k+1=f(k,k)x_k+1=f(x_k,u_k) 7: k+1=g(k,k)o_k+1=g(o_k,d_k) 8: such that (3b)-(3h) 9: end for 10: Jj←Jj+wxwg‖jT′−1−g‖2+wd∑i=1ℳdjT′−1iJ^j← J^j+w^xw^g \! _jT -1-p^g ^2+w^d _i=1^Md^i_jT -1 11: MinimizeJjsuch that(3b)−(3h)Minimize\,\,J^j\,\,such that\,\, eq:cost_fn1- eq:cost_fn7 12: end for 13: J,0,…,TJ,\x_0,…,x_T, dki∀i∈ℳand∀k∈1,…,T\d^i_k\\ ∀ i \ and\ ∀ k∈\1,…,T\ It can be readily verified that equation (25) exhibits a structure similar to (19), but with an added terminal cost for each slice except the final one. This additional term is present in each sub-problem as it enables the robot to keep track of the goal. The overall HS4MOD algorithm is summarized in Algorithm 1. For each slice j the exact optimization is performed (lines 2-7). The summation in (22) is carried out (as shown in line 4), and the goal tracking term is added (line 8) to obtain the objective function JjJ^j (22) for each slice. The optimization is then carried out subject to the constraints given in (3b)-(3h). 5.2 Analysis of the Approximate Solution In order to establish a meaningful comparison between J and J⋆J , we introduce a new objective function, denoted as J′J , which aggregates the cost obtained by summing up the costs of all the m individual slices, and is thus given by J′=J−∑j=1m−1ηj.J =J- _j=1^m-1η^j. (26) J′J has a structure similar to that of J⋆J . As observed before, from an algorithmic perspective, a subset of an optimal solution is not necessarily globally optimal for the particular problem we consider. However, it can be easily verified that the solutions to all the subsets are naturally feasible solutions. Therefore, the horizon-slicing approach results in a feasible solution to the original problem, and therefore the value of J′J must be an upper bound to J⋆J , that is, J′≥J⋆J ≥ J . For this reason, we have that J′=∑j=1mJ(j−1)T′→jT′−1j,s+ηm=∑j=1m(J(j−1)T′→jT′−1⋆,s+δi)+ηm≤∑j=1m(J(j−1)T′→jT′−1⋆,s+δmax)+ηm≤(∑j=1mJ(j−1)T′→jT′−1⋆,s+ηm)+mδmax≤J⋆+mδmax, splitJ &= _j=1^mJ^j,s_(j-1)T → jT -1+η^m\\ &= _j=1^m (J ,s_(j-1)T → jT -1+δ^i )+η^m\\ &≤ _j=1^m (J ,s_(j-1)T → jT -1+δ^max )+η^m\\ &≤ ( _j=1^mJ ,s_(j-1)T → jT -1+η^m )+mδ^max\\ &≤ J +mδ^max, split (27) where δi=J(j−1)T′→jT′−1j,s−J(j−1)T′→jT′−1⋆,s,δ^i=J^j,s_(j-1)T → jT -1-J ,s_(j-1)T → jT -1, (28) with each δiδ^i bounded by ±δmax±δ^max, that is δi∈[−δmax,+δmax].δ^i∈[-δ^max,+δ^max]. (29) From (27), we thus have J⋆≤J′≤J⋆+mδmax.J ≤ J ≤ J +mδ^max. (30) Let the deviation from the optimal solution J′−J⋆J -J be a factor of J⋆J , that is, J′−J⋆=ϵJ⋆J -J =ε J . Ideally, we would want ϵ→0ε→ 0 with considerable computational efficiency. We note here that, in optimization literature, the standard metric used to compute the relative distance between an approximate and the optimal solution is the optimality gap. Essentially, ϵε computes this relative distance and is therefore equivalent to the optimality gap since optimality gap=J′−J⋆J⋆=ϵJ⋆J⋆=ϵ. optimality gap= J -J J = ε J J =ε. (31) From (30), we have J′−J⋆≤mδmax⟹ϵJ⋆≤mδmaxJ -J ≤ mδ^max ε J ≤ mδ^max (32) and therefore ϵ≤mδmaxJ⋆.ε≤ m δ^maxJ . (33) This relation characterizes the relative deviation for a given problem instance; it should not be interpreted as an a priori approximation guarantee. Clearly, for a given problem, as the number of horizon slices or sub-problems increase, the value of ϵε grows as well. The exact deviation ϵε for a given m is problem-specific (see Fig. 7) since δmaxδ^max depends on a number of parameters such as the robot and obstacle dynamics, size of the environment, distribution of the obstacles in the environment, number of slices. In Section 6, we provide an empirical analysis to determine the best m by performing different experiments while varying some of the parameters stated above. (a) (b) (c) (d) 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=1m=1 and m=2m=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=2m=2 gives a sub-optimal solution (with ϵ=0.81ε=0.81) as shown in (d) with the first sub-problem involving the first 33 obstacles, as shown by the vertical trajectory after the third obstacle. 6 Evaluation and Discussion In this Section, we evaluate our approach using (1) the optimal but computationally demanding exact approach discussed in Section 4, and (2) the HS4MOD sub-optimal approach, which was introduced in Section 5. The optimization problem in (3) is performed using the IBM ILOG CPLEX Optimization Studio V12.10.0 in MATLAB under the YALMIP interface [21]. When the robot model is nonlinear, optimization is achieved employing the IPOPT solver [41]. In both cases, the time limit has been set up to 1000 seconds. The performance is evaluated on an Intel® i7-10850H CPU @ 2.70GHz with 32 GB RAM under Windows 11. The horizon T was set between 23 and 29 for the SQUARE and RANDOM environments and to 50 for the ROBOT environments. All experiments were conducted in MATLAB/YALMIP using CPLEX with its default relative and absolute MIP gaps (10−410^-4 and 10−610^-6) and IPOPT with an overall tolerance of 10−710^-7, feasibility and complementarity tolerances of 10−410^-4, and acceptable termination after 15 consecutive iterations satisfying a tolerance of 10−610^-6. The objective weights were selected to prioritize goal attainment, followed by displacement minimization. (a) (b) (c) (d) 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). HS4MOD has been tested on three different domains, namely, (1) a SQUARE domain, of size 24×2424× 24 meters, with 3636 obstacles — we consider two domains with the same obstacle configurations but different goal locations, naming them as SQUARE_1 (see Fig. 8(a)) and SQUARE_2 (Fig. 8(b)), (2) a ROBOT domain, of size 79×1879× 18 meters, with 7474 obstacles (Fig. 8(c)), and (3) a RANDOM domain, of size 24×2424× 24 meters, with 100100 obstacles (Fig. 8(d)). The robot must move from a start location (marked in green in Fig. 8) to a goal location (marked in red) in the presence of movable circular obstacles (in cyan). As discussed in Section 4, m denotes the number of horizon slices and m=1m=1 corresponds to the exact approach. At present, the values of wgw^g, wxw^x, and wdw^d are determined through empirical tuning. Unless otherwise specified, we use wg=10w^g=10, wx=0.5w^x=0.5, and wd=100w^d=100 for all the experiments. (a) (b) (c) (d) (e) (f) (g) (h) (a) (b) 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=1m=1 (exact solution), the second row to m=2m=2, and so on. (a) (b) (c) (d) (e) (f) (g) (h) (a) (b) 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=1m=1 (exact solution), the second row to m=2m=2, and so on. (a) (b) (c) (d) (e) (f) (g) (h) (a) (b) 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=1m=1 (no horizon slicing) for all four domains, the second row corresponds to m=2m=2, and so on. (a) (b) (c) (d) (e) (f) (g) (h) (a) (b) 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=1m=1 (no horizon slicing) for all four domains, the second row corresponds to m=2m=2, and so on. 6.1 Linear Robot Model We first test HS4MOD adopting the robot dynamics in (5). The robot trajectory and the computed obstacle displacements are visualized in Fig. 9 and in Fig. 10. Obstacles that have been displaced by the robot passage are characterized by a shaded trail of previous locations, whereas the cyan color represents their final location after the displacement. Various statistics for the same values are presented in Table 2 under the robot model (5) column. The exact optimization case is denoted by m=1m=1, and shows substantial computational load, as seen from Table 2 — the first line of each domain. As it has been argued before, the computational complexity is exponential in the number of binary variables, which is proportional to the number of movable obstacles, and it is particularly evident from the computational time in the ROBOT and RANDOM domains, with 7474 and 100100 obstacles, respectively. The complexity depends also on (1) the spread of the obstacles with respect to the start and goal locations, and (2) the size of the environment. The first factor accounts for the difference in computation time for the cases m=1m=1 and m=2m=2 in the SQUARE_1 and SQUARE_2 domains, despite having the same number of binary variables. The two factors yield a higher computational time for the ROBOT domain than the RANDOM domain. Analogous results can be seen when employing the linear robot model in (6) — the robot trajectory and obstacle movements visualized in Fig. 11 and Fig. 12. Clearly, in all domains, for both robot models, as m increases, the deviation from the optimal solution increases as well thereby resulting in sub-optimal solutions as corroborated by the rise in ϵε values. At the same time, higher values of m result in great computational efficiency. Keeping in mind a pragmatic trade-off between optimality and computational efficiency, the statistics in Table 2 suggest that for a small number of movable obstacles, for example in the domains SQUARE_1 and SQUARE_2, m=2m=2 may be used. For domains with a larger number of obstacles (ROBOT and RANDOM), m=3m=3 may be employed. Let us now consider again a simulated Pepper humanoid robot having to move through a cluttered environment as seen in Fig. 1(a). Pepper is asked to move to the other room, but its path is blocked by the specific configuration of the tables. Employing the robot model (5) with m=2m=2 and wg=1w^g=1, wx=1w^x=1, wd=10w^d=10, a 7-obstacle solution with a displacement magnitude of 4.44.4 meters is obtained (see Fig. 15(a)). Penalizing large displacements by increasing αoα^o from 10 to 1000, a longer path with a 2-obstacle solution (see Fig. 15(b)) can be obtained with a lower displacement magnitude of 0.40.4 meters. We recall here that the cost for the last time step is the deviation of the robot location from its goal. Baseline comparison. We additionally compare HS4MOD against a NAMO baseline on the SQUARE_2 and ROBOT environments. Similar to [30, 37], the baseline first constructs the robot’s configuration space and computes a path to the goal using an A⋆A search that minimizes the number of obstacles intersecting the path. The obstacles intersecting the path are then displaced to obtain a collision-free trajectory, following the approach proposed in [36]. Table 1 compares the robot path length, total obstacle displacement, and planning time HS4MOD and the NAMO baseline. In the SQUARE_2 environment, HS4MOD produces a shorter robot path with nearly identical obstacle displacement, while reducing planning time by more than a factor of three. In the ROBOT environment, both methods generate paths of comparable length, but HS4MOD requires less obstacle displacement and achieves a lower planning time. These results demonstrate that HS4MOD, even when m=5m=5 offers a favorable trade-off between solution quality and runtime. Table 1: Comparison of robot path length, obstacle displacement and planning time for HS4MOD (m=5m=5) and NAMO baseline. SQUARE_2 ROBOT Method Length (m) Displacement (m) Time (s) Length (m) Displacement (m) Time (s) HS4MOD (m=5m=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 6.2 Nonlinear Robot Model As argued in Section 4, when a nonlinear robot model is adopted for the optimization problem (3), optimality cannot be guaranteed. We test HS4MOD with the nonlinear models (7) and (8) on SQUARE_1 and SQUARE_2. The corresponding robot trajectories and the obstacle displacements with varying m for both the robot models are visualized in Fig. 13 and Fig. 14, respectively. The results indicate that regardless of the robot model, the trajectories exhibit a similar pattern. However, it is observed that certain obstacles are displaced unnecessarily, such as, when m=5m=5 (last row) in Fig. 13(a), m=4m=4 in Fig. 13(b), and m=5m=5 in Fig. 14(b). This phenomenon can be attributed to the non-convexity of the optimization problem, resulting in solutions that are local optima. Numerical results are presented in Table 3. As argued in Section 4, due to the nonlinearity of the models, m=1m=1 does not guarantee an optimal solution. In contrast to the findings in Table 2, in Table 3, the change in ϵε is not monotonic with an increase in m (note that ϵε is computed with respect to m=1m=1). This behavior results from the interaction between horizon discretization and nonlinear dynamics, whereby increasing the number of slices can alter the feasible trajectory and the associated obstacle displacements without necessarily yielding a progressively improved solution. Therefore, no particular value of m can be identified as providing a consistent trade-off between solution quality and computational efficiency for the nonlinear models. Moreover, ϵε should be interpreted as a relative measure with respect to the m=1m=1 solution, rather than as a direct measure of the true optimality gap. Therefore, using a nonlinear model in (3b) precludes any validation on ϵε. Nonetheless, in such scenarios, a linear model can initially be employed to determine the necessary path and displacements using HS4MOD. As a consequence, a trajectory-tracking algorithm can be employed to calculate the requisite controls for the nonlinear model. Robot model (5) Robot model (6) m CPU [s] Gap/ϵε Jr[m2]J^r[m^2] Jo[m2]J^o[m^2] CPU [s] Gap/ϵε Jr[m2]J^r[m^2] Jo[m2]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 1 1601.58 0.00 51.20 0.28 1000.98 0.00 51.22 0.28 2 27.92 0.62 59.17 0.56 116.37 0.76 59.33 0.65 SQUARE_2 3 4.79 0.90 53.87 0.74 7.19 1.06 54.38 0.84 4 1.32 2.10 59.44 1.35 1.95 3.03 64.91 1.85 5 1.02 3.08 59.29 1.88 1.36 3.72 65.90 2.22 1 28814.74 0.00 122.99 0.28 28808.67 0.00 132.70 0.32 2 17367.71 0.25 121.64 0.52 19564.10 0.18 133.00 0.49 ROBOT 3 128.68 0.37 121.08 0.63 147.85 0.31 127.93 0.66 4 24.23 0.98 119.32 1.19 28.83 0.71 136.78 0.99 5 11.62 1.21 142.74 1.28 12.24 0.75 128.16 1.08 1 16009.18 0.00 51.86 1.13 18010.40 0.00 39.15 1.60 2 12813.12 0.78 49.56 2.24 14413.58 0.77 52.28 2.93 RANDOM 3 6403.36 0.99 46.68 2.55 771.53 1.35 48.39 3.99 4 897.14 1.83 48.85 3.71 44.76 1.43 43.72 4.16 5 14.43 2.05 46.70 4.03 20.47 2.16 47.55 5.44 Table 2: Different statistics for the four domains considered in this paper, while employing the linear robot models in (5) and (6). m=1m=1 corresponds to the scenario with no horizon-slicing. CPU denotes the computation time in seconds for the optimization problem in (3), Jr=c()J^r=c(p), and Jo=∑i=1ℳ∑k=0TdkiJ^o= _i=1^M _k=0^Td^i_k. Robot model (7) Robot model (8) m CPU [s] Gap/ϵε Jr[m2]J^r[m^2] Jo[m2]J^o[m^2] CPU [s] Gap/ϵε Jr[m2]J^r[m^2] Jo[m2]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 1 141.78 0.00 62.43 0.30 71.53 0.00 67.75 0.65 2 47.33 0.89 49.75 0.45 29.18 0.44 45.15 0.45 SQUARE_2 3 125.09 0.22 52.67 0.85 146.78 0.49 43.76 1.81 4 86.29 0.61 60.75 3.28 68.66 0.37 45.16 1.42 5 60.09 0.18 51.55 1.40 74.10 0.72 95.50 3.15 Table 3: Average computation time, Gap- wrt to m=1m=1, path (Jr=c()) (J^r=c(p) ) and displacement function (Jo=∑i=1ℳ∑k=0Tdki) (J^o= _i=1^M _k=0^Td^i_k ) values while employing the nonlinear robot models in (7) and (8). (a) (b) (c) (d) (e) (f) (g) (h) (a) (b) 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=1m=1 (no horizon slicing), the second row corresponds to m=2m=2, and so on. (a) (b) (c) (d) (e) (f) (g) (h) (a) (b) 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=1m=1 (no horizon slicing), the second row corresponds to m=2m=2, and so on. (a) (b) 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 77 obstacles. (b) Increasing the obstacle displacement factor (JoJ^o) weight from 10 to 1000, the robot finds a path with lower obstacle displacement but with a higher path length. (a) (b) (c) 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=3m=3 gives an approximate 2-obstacle MCR path. 6.3 Two Different Problems We have previously noted how MOD encompasses various classes of motion planning problems. In this Section, we explore two such problems using a linear robot model. Let us consider again the simulated Pepper humanoid robot scenario depicted in Fig.1(a), where we remove a table blocking the top doorway. By employing the exact approach, a solution to the classical motion planning problem is obtained in approximately 8.318.31 seconds (visualized in Fig.16(a)). This demonstrates that when a collision-free path exists, MOD resolves the classical motion planning problem with all displacements set to zero. The MCR problem identifies the minimum number of obstacles that must be removed to yield a feasible path. To transform MOD into MCR, we allow collisions with obstacles and modify the cost function (2d) such that it assigns a cost of 11 for collision with an obstacle, and 00 otherwise. The exact approach produces a solution in approximately 6.376.37 seconds (see Fig. 16(b)), revealing that at least one obstacle must be removed to achieve a feasible path. MCR, likewise MOD, has been proven to be NP-hard, and HS4MOD may be equally applied to MCR. To evaluate this possibility, we solve the problem using m=3m=3, and obtain a 2-obstacle approximation in 0.670.67 seconds, as shown in Fig. 16(c). This result is interesting in so far as MCR is known to have an O(n)O( n) approximation for rectilinear polygons and disks [1]. While the analysis of HS4MOD in the context of MCR is an intriguing avenue for exploration, it falls beyond the scope of this work and is left for future research. 7 Conclusions and Future Work This paper formalizes and discusses a minimum obstacle displacement (MOD) problem for robot navigation tasks requiring the manipulation of obstacles in the way. This work proves that the problem is NP-hard for polygonal obstacles in the plane, even when such obstacles are modeled as simple line segments. The paper presents an exact approach, which generalizes a number of existing problems in the literature, which is computationally intractable in the worst case. Furthermore, the paper discusses a trade-off between path length and the amount of object displacements, and it introduces an approximate albeit sub-optimal horizon-slicing approach characterized by a high computational gain when compared to the exact approach. Both approaches are validated using different theoretical examples, scenarios with up to 100100 obstacles, and different robot motion models. The solution quality of the approximate method is measured in terms of its optimality gap, and the validations suggest that the approximate method can provide a desirable trade-off between the optimality gap and computation time. The models presented in the paper are characterized by a few limitations. First, we do not deal with obstacles interacting with each other, that is, obstacles themselves are not collision-free. Interaction between obstacles can be incorporated by adding collision avoidance constraints among obstacles; similar to (3h) an additional constraint of the form O(kj)∩⋃i=1,i≠j||O(ki)=∅O(o_k^j)∩ _i=1,i≠ j^|O|O(o_k^i)= should be added to (3). However, for a large number of obstacles, taking such collisions into account increases the computational burden due to the addition of the corresponding binary variables. Second, the approaches discussed in the paper are restricted to robot and obstacle classes allowing for linearizing the collision constraint since the optimization problem for MOD requires the linearisation of the collision constraint in (3h). For the interaction between circles or axis-aligned rectangles, this can be achieved by introducing four binary constraints (for an example, see (13)-(17)). Other polygonal projections of the robot and the obstacles require a careful formulation of the linear constraints (10)-(11). However, with an increasing number of obstacles, there is a higher computational burden due to the increased number of auxiliary variables. As argued throughout the paper, we are not concerned about the weight of the obstacles and assume that the computed displacements can be achieved. Yet, an obstacle might be too heavy for being moved even though it accounts for a minimum displacement solution. This aspect may be incorporated with heavy obstacles being penalized more by assuming a higher weight than other obstacles. Future work includes incorporating additional aspects such as the work done by the robot which addresses similar concerns through the force required to move the obstacles. Furthermore, the proposed method is intended as an offline planning approach, where the required displacement for each obstacle is computed prior to execution under the assumption that the environment map is known. In a practical deployment, however, the robot may have access only to a locally observed portion of the environment through its onboard sensors. In such a setting, HS4MOD could be extended to an online incremental planning framework by repeatedly constructing and solving the horizon-sliced optimization problem using the currently observed environment, and updating the plan as the robot moves and new obstacles or obstacle configurations become available. While the development and evaluation of such an online replanning strategy are beyond the scope of the present work, investigating this extension represents an interesting direction for future research. We consider environments with movable obstacles, where the robot itself is responsible for displacing the obstacles and therefore the focus is on scenarios where no feasible path initially exists for the robot. Thus, the change in the environment arises from deliberate robot–object interactions, rather than from independently evolving or time-varying dynamics. One could argue that partitioning the planning horizon based on obstacle encounters would be more effective than using equal-length horizon slices. However, such an approach requires either prior knowledge of the solution trajectory or an additional preprocessing stage to identify the obstacle encounter events, thereby increasing the computational complexity. In contrast, equal horizon slicing provides a simple, general, and computationally efficient decomposition strategy that can be applied without any prior knowledge of the trajectory. Nevertheless, the investigation of adaptive horizon partitioning strategies represents an interesting direction for future research. Finally, it is worth noting that the evaluation domains used in this paper have been rather abstract in nature. Yet, this is by no means a limitation, and many practical applications exist to the minimum obstacle displacement problem, such as for example those related to automated logistics [24]. References [1] S. Bandyapadhyay, N. Kumar, S. Suri, and K. Varadarajan (2020) Improved approximation bounds for the minimum constraint removal problem. Computational Geometry 90, p. 101650. Cited by: §6.3. [2] J. Basch, L. Guibas, D. Hsu, and A. T. Nguyen (2001) Disconnection proofs for motion planning. In Proceedings of the 2001 IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea. Cited by: §2.1. [3] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan (2013) Mixed-integer nonlinear optimization. Acta Numerica 22, p. 1–131. Cited by: §4.4.2. [4] A. Capitanelli, M. Maratea, F. Mastrogiovanni, and M. Vallati (2018) On the manipulation of articulated objects in human-robot cooperation scenarios. Robotics and Autonomous Systems 109, p. 139–155. Cited by: §1. [5] L. I. R. Castro, P. Chaudhari, J. Tůmová, S. Karaman, E. Frazzoli, and D. Rus (2013) Incremental sampling-based algorithm for minimum-violation motion planning. In Proceedings of the 52nd IEEE Conference on Decision and Control (CDC), Florence, Italy. Cited by: §2.1. [6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2009) Introduction to algorithms. MIT Press. Cited by: §1. [7] N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki (2016) Incremental task and motion planning: a constraint-based approach. In Proceedings of the 12th International Conference Robotics: Science and Systems (RSS XII), Ann Arbor, Michigan, USA. Cited by: §2.1. [8] M. Dogar and S. Srinivasa (2011) A framework for push-grasping in clutter. In Proceedings of the 7th International Conference Robotics: Science and Systems (RSS VII), Los Angeles, CA, USA. Cited by: §2.1. [9] C. R. Garrett, T. Lozano-Perez, and L. P. Kaelbling (2018) FFRob: leveraging symbolic planning for efficient task and motion planning. The International Journal of Robotics Research 37 (1), p. 104–136. Cited by: §2.1. [10] K. Hauser (2013) Minimum constraint displacement motion planning.. In Proceedings of the 9th International Conference Robotics: Science and Systems (RSS IX), Berlin, Germany. Cited by: item 1, §1, §2.1. [11] K. Hauser (2014) The minimum constraint removal problem with three robotics applications. The International Journal of Robotics Research 33 (1), p. 5–17. Cited by: §2.1. [12] L. P. Kaelbling and T. Lozano-Pérez (2013) Integrated task and motion planning in belief space. The International Journal of Robotics Research 32 (9-10), p. 1194–1227. Cited by: §2.1. [13] H. Karami, A. Thomas, and F. Mastrogiovanni (2020) Task allocation for multi-robot task and motion planning: a case for object picking in cluttered workspaces. In Proceedings of the 20th International Conference of the Italian Association for Artificial Intelligence (AIxIA), Milan, Italy. Cited by: §2.1. [14] H. Karami, A. Thomas, and F. Mastrogiovanni (2025) A task and motion planning framework using iteratively deepened and/or graph networks. Robotics and Autonomous Systems 189, p. 104943. External Links: ISSN 0921-8890, Document, Link Cited by: §2.1. [15] H. Kellerer, U. Pferschy, D. Pisinger, H. Kellerer, U. Pferschy, and D. Pisinger (2004) The multiple-choice knapsack problem. Knapsack Problems, p. 317–347. Cited by: §3.3. [16] A. Krontiris and K. E. Bekris (2015) Dealing with difficult instances of object rearrangement. In Proceedings of the 11th International Conference Robotics: Science and Systems (RSS XI), Rome, Italy. Cited by: §2.1. [17] A. Krontiris and K. E. Bekris (2017) Trade-off in the computation of minimum constraint removal paths for manipulation planning. Advanced Robotics 31 (23-24), p. 1313–1324. Cited by: §2.1. [18] S. M. LaValle (2006) Planning algorithms. Cambridge University Press, Cambridge, UK. Cited by: §1, §4.3. [19] S. Li and N. T. Dantam (2021) Learning proofs of motion planning infeasibility. In Proceedings of the 17th International Conference Robotics: Science and Systems (RSS XVII), Anywhere on Earth. Cited by: §2.1. [20] S. Li and N. T. Dantam (2023) Scaling infeasibility proofs via concurrent, codimension-one, locally-updated coxeter triangulation. IEEE Robotics and Automation Letters 8 (12), p. 8303–8310. Cited by: §2.1. [21] J. Löfberg (2004) YALMIP: a toolbox for modeling and optimization in MATLAB. In Proceedings of the IEEE International Symposium on Computer-Aided Control Systems Design (CACSD), Taipei, Taiwan. Cited by: §6. [22] F. Mastrogiovanni, A. Sgorbissa, and R. Zaccaria (2009) Robust navigation in an unknown environment with minimal sensing and representation. IEEE Transactions on Systems, Man, and Cybernetics 39 (1), p. 212–229. Cited by: §1. [23] G. Michael and D. Johnson (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco. Cited by: item 1, §3.1. [24] I. S. Mohamed, A. Capitanelli, F. Mastrogiovanni, S. Rovetta, and R. Zaccaria (2019) Detection, localisation, and tracking of pallets using machine learning techniques and 2D range data. Neural Computing and Applications 32, p. 8811–8828. Cited by: §7, footnote 1. [25] V. V. Naik (2018) Mixed-integer quadratic programming algorithms for embedded control and estimation. Ph.D. Thesis, IMT School for Advanced Studies Lucca. Cited by: §5. [26] D. Nieuwenhuisen, A. F. van der Stappen, and M. H. Overmars (2008) An effective framework for path planning amidst movable obstacles. In Proceedings of the 7th Workshop on the Algorithmic Foundations of Robotics (WAFR VII), New York, NY, USA. Cited by: §2.1, §2.1. [27] C. Park, J. S. Park, and D. Manocha (2018) Fast and bounded probabilistic collision detection for high-DOF trajectory planning in dynamic environments. IEEE Transactions on Automation Science and Engineering 15 (3), p. 980–991. Cited by: §4.4.2. [28] R. Salcedo (1992) Solving nonconvex nonlinear programming and mixed-integer nonlinear programming problems with adaptive random search. Industrial & Engineering Chemistry Research 31 (1), p. 262–273. Cited by: §4.4.2. [29] S. Srivastava, E. Fang, L. Riano, R. Chitnis, S. Russell, and P. Abbeel (2014) Combined task and motion planning through an extensible planner-independent interface layer. In Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, China. Cited by: §2.1. [30] M. Stilman and J. J. Kuffner (2005) Navigation among movable obstacles: real-time reasoning in complex environments. International Journal of Humanoid Robotics 2 (4), p. 479–503. Cited by: §2.1, §2.1, §2.2, §6.1. [31] M. Stilman and J. Kuffner (2008) Planning among movable obstacles with artificial constraints. The International Journal of Robotics Research 27 (11-12), p. 1295–1307. Cited by: §2.1, §2.1. [32] M. Stilman, J. Schamburek, J. Kuffner, and T. Asfour (2007) Manipulation planning among movable obstacles. In Proceedings of the 2007 IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy. Cited by: §2.1. [33] A. Thomas, F. Mastrogiovanni, and M. Baglietto (2021) MPTP: motion-planning-aware task planning for navigation in belief space. Robotics and Autonomous Systems 141, p. 103786. Cited by: §2.1. [34] A. Thomas, F. Mastrogiovanni, and M. Baglietto (2022) Safe motion planning with environment uncertainty. Robotics and Autonomous Systems 156, p. 104203. External Links: ISSN 0921-8890, Document, Link Cited by: §4.4.2. [35] A. Thomas, F. Mastrogiovanni, and M. Baglietto (2024) Revisiting the Minimum Constraint Removal Problem in Mobile Robotics. In Intelligent Autonomous Systems 18, Cham, p. 31–41. External Links: ISBN 978-3-031-44851-5 Cited by: §2.1. [36] A. Thomas, F. Mastrogiovanni, and M. Baglietto (2026) Locally optimal solutions to constraint displacement problems via path-obstacle overlaps. Robotics and Autonomous Systems 196, p. 105251. External Links: ISSN 0921-8890, Document, Link Cited by: §2.1, §6.1. [37] A. Thomas and F. Mastrogiovanni (2022) Minimum displacement motion planning for movable obstacles. In International Conference on Intelligent Autonomous Systems, p. 155–166. Cited by: §2.1, §6.1. [38] J. Van Den Berg, P. Abbeel, and K. Goldberg (2011) LQG-MP: optimized path planning for robots with motion uncertainty and imperfect state information. The International Journal of Robotics Research 30 (7), p. 895–913. Cited by: §4.3. [39] J. Van Den Berg, S. Patil, and R. Alterovitz (2012) Motion planning under uncertainty using iterative local optimization in belief space. The International Journal of Robotics Research 31 (11), p. 1263–1278. Cited by: §4.3. [40] J. Van Den Berg, M. Stilman, J. Kuffner, M. Lin, and D. Manocha (2009) Path planning among movable obstacles: a probabilistically complete approach. In Proceedings of the 8th Workshop on the Algorithmic Foundations of Robotics (WAFR VIII), Guanajuato, Mexico. Cited by: §2.1, §2.1. [41] A. Wächter and L. T. Biegler (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming 106, p. 25–57. Cited by: §6. [42] J. J. Weeda, S. Bakker, G. Chen, and J. Alonso-Mora (2025) Pushing through clutter with movability awareness of blocking obstacles. In 2025 IEEE International Conference on Robotics and Automation (ICRA), p. 512–518. Cited by: §2.1. [43] G. Wilfong (1991) Motion planning in the presence of movable obstacles. Annals of Mathematics and Artificial Intelligence 3 (1), p. 131–150. Cited by: §2.1. [44] B. Xu, L. Chen, and K. Xu (2020) Deep learning algorithm for minimum constraint removal (MCR) problem. In Proceedings of the 12th International Conference on Machine Learning and Computing (ICMLC), Shenzhen, China. Cited by: §2.1. [45] B. Xu and H. Min (2016) Solving minimum constraint removal (mcr) problem using a social-force-model-based ant colony algorithm. Applied Soft Computing 43, p. 553–560. Cited by: §2.1. [46] T. Yang, J. Hwang, J. Jeong, M. Yoon, and S. Yoon (2025) Efficient navigation among movable obstacles using a mobile manipulator via hierarchical policy learning. In 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 17130–17137. Cited by: §2.1. [47] L. Zhang, Y. J. Kim, and D. Manocha (2008) A simple path non-existence algorithm using C-obstacle query. In Proceedings of the 7th Workshop on the Algorithmic Foundations of Robotics (WAFR VII), Cited by: §2.1. [48] Y. Zhang and Y. Kantaros (2025) NAMO-LLM: Efficient Navigation Among Movable Obstacles With Large Language Model Guidance. IEEE Robotics and Automation Letters 10 (12), p. 13026–13033. External Links: Document Cited by: §2.1.