1 Introduction↩︎

Motion planning is a fundamental problem in robotics, involving finding a path for a robot from its start configuration to a goal configuration without colliding with obstacles. A complete motion planner can either compute a collision-free path from the start to the goal or conclude that no such path exists. However, complete motion planning is challenging, and most approaches focus on finding a feasible plan with weaker notions of completeness. Resolution complete planners, typically those based on cell decomposition, offer completeness provided that the number of cells used to discretize the configuration space is sufficiently high [1]. Yet, in high-dimensional configuration spaces, such approaches tend to be computationally very expensive. Sampling-based motion planners [2], [3] are typically employed in such cases to find paths as quickly as possible. However, they are only probabilistically complete [4], meaning that if a plan exists, they will find it given enough time, but if no plan exists, they can run forever (or until a timeout). Therefore, a timeout is not a guarantee of infeasibility. In this work, we focus on the less examined path non-existence problem and present a simple algorithm that checks for motion planning infeasibility.

Motion infeasibility is a critical aspect of many robot planning methodologies. Task and motion planning [5]–[10] must consider the feasibility of motion plans to achieve the associated high-level tasks. When motion planning is deemed infeasible, alternative task plans must be generated. Similarly, feasibility checks are fundamental in manipulation tasks amidst clutter or rearrangement planning [11]–[14]. This often entails either displacing obstacles obstructing the task, usually identified through motion planning infeasibility, or positioning them at specific locations. The latter requires evaluating the feasibility of motion plans for different object placements. Similarly, in Navigation Among Movable Obstacles (NAMO) [15], [16], the environment is actively modified by rearranging obstacles to create feasible paths.

The main contribution of this paper is a simple and easy-to-implement algorithm for proving the infeasibility of motion planning.¹ Our framework is based on discretized configuration spaces which preserve the essential structure of their continuous counterparts. We refer to these as equivalent spaces, discussed in detail in Section 3. The key insight of our approach is that proving infeasibility does not require constructing the entire configuration space obstacle region— only a relevant subset (see Fig. 1).

We introduce a technique to demonstrate motion planning infeasibility by segmenting a discrete configuration space into distinct free regions isolated by the obstacle region. We note that such distinct free regions are referred to as connected components of the free space. Therefore, we use the terms distinct free region and connected component interchangeably. If the start and goal configurations are partitioned into separate free regions, motion planning is deemed infeasible.

However, computing a discrete configuration space is computationally expensive, especially for a robot with high degrees-of-freedom (DOF). To address this issue, we initially set the entire configuration space to free regions. Subsequently, we incrementally construct the configuration space by sampling and checking if the sampled configurations lie within the obstacle region. The key concept underpinning the incremental sampling is based on the principle that it is often unnecessary to sample the entire obstacle region. Instead, our objective is to draw a sufficient number of samples that establish the partition of the start and goal configurations into disconnected components of the configuration space. During each iteration, the partially constructed configuration space is segmented into distinct connected free regions as shown in Fig. 1 (c). The segmented configuration space is then queried to determine whether the start and the goal configurations belong to the same connected free region. In Section 3, we elucidate this approach in detail and further discuss methods to speed up the construction of the configuration space.

In Sections 1.1 to 1.3, we provide an overview of previous works related to motion planning infeasibility. These works are classified based on the different strategies employed to establish the non-existence of a feasible path. In Section 1.4, we highlight how our approach differs from these methods in terms of computational cost and scalability.

1.1 Approximate Configuration Space↩︎

Zhang et al. [17] decompose the configuration space into cells, which are then queried to determine if they lie within the obstacle region. Subsequently, a graph is constructed where the nodes represent the cells and the edges represent adjacent cells. Using the cells that contain free regions, the problem of path non-existence is transformed into a graph search problem. Checking the occupancy of each cell is computationally challenging in higher dimensions. In contrast, our approach does not always require checking the occupancy of every cell. In a different approach presented in [18], obstacle regions are decomposed into collections of simplices called alpha shapes. These simplices are then utilized to address connectivity queries. However, methods for computing higher-dimensional alpha shapes are presently unknown. Points in the obstacle region are sampled to identify possible facets of a separating polytope in [19]. A separating polytope is a closed polytope that separates the start and goal into disconnected components of the free configuration space. However, the generation of these facets is computationally expensive, which can lead to scalability issues, especially in higher-dimensional configuration spaces. Varava et al. [20] construct an approximation of the obstacle region by decomposing it into a set of slices corresponding to subspaces of fixed obstacle orientations. They then compute the free space as the complement of this approximated obstacle region, which is subsequently used to synthesize a connectivity graph. A rigid body passing through a narrow gate is considered in [21]. The orientations of the rigid body are discretized, and each orientation is individually checked for its ability to pass through the gate.

1.2 Learning-Based Infeasibility Estimation↩︎

In [22], a representative roadmap is learned from available training problems, along with the probability of the edges being collision-free. Yet, the authors only prove the infeasibility in the roadmap and not the configuration space. Approaches in [23], [24] learn a classifier that guides the robot toward feasible motions. However, the classifier is used only as a heuristic to quickly estimate the feasibility of high-level actions rather than as an infeasibility proof. Li et al.[25] combine supervised learning and sampling-based planning to certify motion planning infeasibility. Their approach constructs an infeasibility proof by learning a manifold that lies entirely within the obstacle region and querying whether it separates the start and goal configurations. However, their method assumes that it is always possible to sample points on the manifold and compute the configuration-space penetration depth of these samples. This approach is demonstrated for robots with up to 4 degrees of freedom (DOF). Scalability to 5-DOF robots is addressed in[26], where the triangulation method used to represent the learned manifold in [25] is significantly improved.

1.3 Feasibility Through Constraint Modification↩︎

The minimum constraint displacement (MCD) [27]–[29] and the minimum constraint removal (MCR) [30], [31] motion planning problems identify the minimum displacement of obstacles and the minimum number of obstacles to be removed, respectively, to guarantee a feasible motion plan. MCD class of problems does not inherently provide a means to prove infeasibility. If planning is infeasible, MCD computes the minimum displacement of obstacles required to ensure feasibility. The MCR class of problems is generally solved by partitioning the configuration space along the obstacle boundaries to obtain different connected regions that form a discrete graph. The MCR graph is then queried to determine the minimum number of obstacles to be removed to connect the start and the goal configuration. Implicitly, if the start and goal configurations are disconnected by obstacle regions, it implies that motion planning is infeasible. However, computing such partitions becomes intractable as the number of obstacles increases, especially in high-dimensional spaces.

1.4 Comparative Analysis with Prior Approaches↩︎

For most approaches categorized as approximate configuration space or learning-based, the input typically consists of an approximate configuration space computed using techniques such as cell decomposition or sampling-based methods [2], [3]. Importantly, the overall computation time for determining infeasibility in these methods does not account for the time required to construct the approximate configuration space, as it is provided as input. In contrast, our approach incrementally constructs the configuration space during execution, which constitutes the primary computational effort, as demonstrated in Section 4.

MCD and MCR implicitly address infeasibility by identifying minimal obstacle displacements or removals that restore feasibility. However, these problems are NP-hard and scale poorly with increasing dimensionality.

Current state-of-the-art infeasibility certification methods scale only up to 4- or 5-DOF robots [25], [26], with experiments completing in minutes using parallel computing. While our experiments use different benchmark scenes, we achieve comparable runtimes for 4- and 5-DOF robots, even in the absence of parallel computing. Moreover, by leveraging quotient-space topology [32], we extend our approach to 6-DOF and 7-DOF manipulators, thereby demonstrating its practical feasibility for high-dimensional motion planning infeasibility certification.

2 Preliminaries↩︎

We consider a robot \(\mathcal{R}\), which operates in the workspace \(\mathcal{W} \subset \mathbb{R}^a\), with \(a = 2\) or \(a = 3\). An obstacle in \(\mathcal{W}\) will be denoted by \(\mathcal{O}_i \in \mathcal{O}\) and \(\mathcal{C}\) will be used to denote the configuration space (C-space in short) of the robot \(\mathcal{R}\). A configuration \(q\in \mathcal{C}\) of \(\mathcal{R}\) completely specifies the volume occupied by \(\mathcal{R}\), and will be denoted by a list of \(n\) parameters \(q = (q_1,\ldots,q_n)\), where \(n\) is the dimension of \(\mathcal{C}\). Therefore, given a configuration \(q\) of \(\mathcal{R}\), the corresponding placement of \(\mathcal{R}\) in \(\mathcal{W}\) will be denoted by \(\mathcal{R}(q)\). Every obstacle \(\mathcal{O}_i \subset \mathcal{W}\) maps into \(\mathcal{C}\) to a C-obstacle \(=\{q\in \mathcal{C}\;| \;\mathcal{R}(q) \cap \mathcal{O}_i \neq \emptyset \}\) and the union of all C-obstacles is the C-obstacle region. Finally, C-free is the region in \(\mathcal{C}\) given by \(\mathcal{C}\setminus\)C-obstacle region, that is, C-free \(=\{q\in \mathcal{C}\;| \;\mathcal{R}(q) \cap \mathcal{O} = \emptyset\}\). The start and goal configurations will be denoted as \(q_s\) and \(q_g\), respectively.

In this work, we limit the C-space to a discrete set, where each DOF is constrained to finite values. This discretized C-space will be called the C-space bitmap \(\mathcal{CB}\). Thus, for a C-space of dimension \(n\) (corresponding to \(n\) DOF), we obtain an \(N_1 \times N_2 \times \ldots \times N_n\) C-space bitmap, denoted by \(\mathcal{CB}\), where \(N_i\) represents the number of discrete divisions along the \(i\)-th DOF (or dimension) of the C-space. In other words, \(\mathcal{CB}\) is a grid cell represented as a multidimensional array of size \(N_1 \times N_2 \times \ldots \times N_n\), and the resolution along the \(i\)-th dimension is given by \((\overline{q}_i - \underline{q}_i)/N_i\), where \(\underline{q}_i\) and \(\overline{q}_i\) denote the lower and upper joint limits, respectively. Each cell of the \(n\)-dimensional \(\mathcal{CB}\) corresponds either to the C-free (denoted by 1) or the C-obstacle (denoted by 0)

As argued above, any configuration \(q \in \mathcal{C}\) of \(\mathcal{R}\) can be mapped to the subset of \(\mathcal{W}\) occupied by \(\mathcal{R}\), that is, \(\mathcal{R}(q)\). Therefore, \(\mathcal{CB}\) may be constructed by iterating over all possible \(n\)-tuples \(q = (q_1,\ldots,q_n)\) belonging to the \(N_1\times N_2\times \ldots \times N_n\) binary array such that \(\mathcal{CB}(q) = 1\) when \(\mathcal{R}(q)\) does not collide with any obstacle and \(\mathcal{CB}(q) = 0\), when \(\mathcal{R}(q)\) collides with at least one obstacle. Checking for collision with obstacles for all configurations is computationally expensive, especially when dealing with higher resolutions and dimensions of configuration spaces. For the 4-DOF robot depicted in Fig. 8 (b), generating the complete \(\mathcal{CB}\) with a resolution of \(36\times 36\times 36\times 36\) required approximately 58 minutes². While methods for efficiently computing discrete C-space exist [34], [35], they tend to become prohibitively expensive as the dimension of the C-space increases.

3 Approach↩︎

In a general perspective, our approach incrementally constructs the C-space bitmap \(\mathcal{CB}\), by sampling configurations in C-obstacle. During each iteration, the updated \(\mathcal{CB}\) is segmented into different sets of adjacent free regions, akin to identifying distinct groups or regions of connected pixels in an image. We subsequently check whether the start (\(q_s\)) and the goal (\(q_g\)) reside in separate regions. Motion planning is infeasible if \(q_s\) and \(q_g\) are in different C-free regions. If the check fails, the iteration is repeated.

The overall approach is summarized in Algorithm 2. Initially, all cells in the bitmap \(\mathcal{CB}\) are initialized to 1 (C-free). In each iteration, the subroutine SampleCobstacle is invoked (Algorithm 2, line 4), which samples at least \(ns\) configurations lying in C-obstacle. The cells of \(\mathcal{CB}\) corresponding to these C-obstacle samples are then set to zeros. The updated \(\mathcal{CB}\) is segmented (line 5) to check the connected components to which \(q_s\) and \(q_g\) belong (line 6). If they are in different connected components, motion planning is infeasible. However, if they are in the same connected component, either a motion plan exists, or \(\mathcal{CB}\) must be further updated with additional samples from the C-obstacle to establish infeasibility, continuing the iteration to draw new samples as needed.

3.1 Sampling C-obstacle↩︎

The fundamental concept underlying incremental sampling from the C-space is that it is not necessary to sample the entire C-obstacle region. Instead, it suffices to draw enough samples from the C-obstacle to separate the start and goal configurations into disconnected components within the C-space.

Since we initialize all cells in \(\mathcal{CB}\) as C-free, we need to sample configurations in C-obstacle to progressively build \(\mathcal{CB}\). We maintain a set \(SS\) (Algorithm 2, line 2) that stores the linear indices \((idx)\) corresponding to the multidimensional array representation of \(\mathcal{CB}\). The value \(\mathcal{CB}[idx]\) denotes the grid cell associated with index \(idx\). Algorithm 3 samples without replacement from \(SS\) (lines 3–4) until at least \(ns\) configurations within the C-obstacle are selected. Each sampled configuration \(q\) is then checked for collision (Algorithm 3, line 6). If \({\color{revisioncolor} q} \in \text{C-obstacle}\), the subroutine CollisionCheck returns true (\(cc\)), and the corresponding \(\mathcal{CB}\) cell is updated to \(false\) (Algorithm 3, line 8), indicating that the cell belongs to the C-obstacle.

The CollisionCheck subroutine also returns \(p\), the set of links of robot \(\mathcal{R}\) that are in collision with obstacles for the given configuration \(q\). This set \(p\) is subsequently used by the SpeedUp subroutine, which enables classification of certain cells as belonging to the obstacle region without explicitly invoking the collision checker. Further details on this procedure are provided in the following paragraphs.

We also check for neighboring configurations that may be in collision (lines 10–16). This leverages the fact that if a configuration is in collision, nearby configurations are also likely to be in collision. To this end, we randomly select \(d\) neighbors of each sampled \(q \in\) C-obstacle. The total number of possible neighbors of \(q\) depends on the C-space dimension, as further discussed in Section 5. The subroutine SampleCobstacle thus returns an updated \(\mathcal{CB}\), which is then segmented into connected components to assess motion-planning infeasibility.

We note that, in each iteration, although \(ns\) configurations are explicitly sampled from the C-obstacle, both the SpeedUp subroutine and the selection of \(d\) neighboring configurations contribute additional samples within the C-obstacle. Consequently, Algorithm 3 ensures that at least \(ns\) configurations are processed per iteration.

Subroutine SpeedUp: A significant computational bottleneck in Algorithm 3 is the CollisionCheck subroutine, which, for each sampled configuration \(q\), checks for collisions between \(\mathcal{R}(q)\) and all obstacles in the environment. To optimize this process, we employ a simple heuristic that allows for avoiding unnecessary collision checks for certain configurations \(q\). We will clarify this with an illustrative example. Let us consider an articulated robot with \(n\) links. Suppose that the \(j\)-th link, for a sampled configuration \(q = (q_1, \ldots, q_j, \ldots, q_n)\), collides with an obstacle. In such a case, it is readily observed that \[\forall q \;| \;q = (q_1, \ldots, q_j, \ast) \implies q \in \text{C-obstacle}\] where \(\ast\) denotes the fact that the components \((q_{j+1}, \ldots, q_n)\) may assume any admissible values. In other words, for all configurations where the components from the first link to the \(j\)-th link are fixed (values corresponding to those that resulted in collision with the obstacle), any combinations of the \((j+1)\)-th to \(n\)-th links will still collide with that obstacle. Thus, without querying the CollisionCheck subroutine, all the cells in \(\mathcal{CB}\) corresponding to such configurations may be updated. Algorithm 4 summarizes this procedure.

A similar principle has recently been exploited in motion planning through the use of quotient-space decompositions, where infeasible equivalence classes of configurations in the C-space are pruned based on admissibility in lower-dimensional projections [36]. This strategy effectively reduces the sampling space and has been shown to achieve runtime improvements of at least an order of magnitude.

An analogous heuristic can also be applied when the C-obstacle arises due to self-collision. If the \(i\)-th link and the \(j\)-th link collide, it is verified that \[\forall q \;| \;q = (\ast, q_i, \ldots, q_j, \ast) \implies q \in \text{C-obstacle}\] where \(\ast\) denotes the fact that the components \((q_{1}, \ldots, q_{i-1})\), \((q_{j+1}, \ldots, q_n)\) may assume any admissible values.

The process described above is achieved by calling the SpeedUp subroutine (line 9), which takes the colliding link(s) \(p\) as input. Similarly, in the case of a mobile robot that can rotate and translate, if a sampled configuration \(q\) is such that \(q \in \text{C-obstacle}\), and the rotation axis of the robot intersects with an obstacle, then all rotations of the robot at that location will result in a collision. Hence, the configurations corresponding to all possible rotations with the fixed robot location are readily classified as C-obstacle, eliminating the need to query the CollisionCheck subroutine.

3.2 \(\mathcal{CB}\) Segmentation↩︎

Since we only consider kinematic motion planning, infeasibility arises from the obstacle region (C-obstacle) in the C-space. Therefore, a motion plan exists only if \(q_s\) and \(q_g\) are not separated by C-obstacle; in other words, they must reside in the same connected component of the C-free space. Conversely, motion planning is infeasible if \(q_s\) and \(q_g\) are separated by C-obstacle into different connected components. Formally, an infeasibility proof is a closed manifold that entirely resides within C-obstacle and separates the start and the goal [25].

The SegmentCB subroutine (Algorithm 2, line 5) segments \(\mathcal{CB}\) into different connected C-free regions separated by C-obstacle. The SegmentCheck function (Algorithm 2, line 6) verifies whether the start and goal components are separated by C-obstacle. If they are divided into different C-free regions, then motion planning is infeasible.

To achieve segmentation, we employ an off-the-shelf segmentation function that utilizes a union–find algorithm with a computational complexity of \(O(n \log^* n)\), where \(n\) is the size of \(\mathcal{CB}\). This complexity is effectively near-linear [37] and provides substantial computational advantages over traditional search-based methods such as \(A^\star\). We experimentally validate this complexity under varying C-space dimensions in Section 5.1. The segmentation function assigns unique labels to the connected C-free regions. If \(q_s\) and \(q_g\) receive the same label, it indicates that they belong to the same connected C-free region, and thus, a motion plan exists. However, if they are assigned different labels, it does not immediately imply the absence of a motion plan. This is because, in scenarios involving motion planning for manipulators, it is essential to consider that orientations are defined modulo \(2\pi\) (when there are no joint limits). Therefore, when verifying the disconnection between \(q_s\) and \(q_g\), the SegmentCheck subroutine accounts for the fact that orientation wraps around at \(2\pi\) for joints without limits.

3.3 Analysis of \(\mathcal{CB}\) Resolution↩︎

The C-obstacle region divides the C-free of the C-space \(\mathcal{C}\) into different connected components. For a given \(\mathcal{R}\) and \(\mathcal{W}\), let us denote the different connected components by \(C_1, \ldots, C_m\), whose union results in C-free, denoted as C-free \(= \bigcup C_j\). Let the connected components in \(\mathcal{CB}\) be denoted by \(D_1, \ldots, D_l\). We say that \(\mathcal{CB}\) is equivalent to \(\mathcal{C}\) if

1. \(l = m\)

2. \(D_1 \subset C_1, \ldots, D_l \subset C_m\)

3. \(q_s \in \bigcup D_j\)

4. \(q_g \in \bigcup D_j\)

Let \(q_s \in C_i\) and \(q_g \in C_j\), so that motion planning is infeasible. From the definition of an equivalent \(\mathcal{CB}\), we have \(D_k \subset C_k, \forall k\leq l\), \(q_s \in \bigcup D_k\), and \(q_g \in \bigcup D_k\). Therefore, it follows that \(q_s \in D_i\) and \(q_g \in D_j\). Thus, no motion plan exists. Thus, if motion planning between \(q_s\) and \(q_g\) remain infeasibile in \(\mathcal{C}\), then it remains infeasible in an equivalent \(\mathcal{CB}\).

The concept of equivalent C-space is visualized in Fig. 5. A 2-link robot in its workspace, without any joint limits is shown in Fig. 5 (a), where the start and goal states are represented by green and red, respectively. Various obstacles are shown in different colors. The corresponding C-space \(\mathcal{C}\) is displayed in Fig. 5 (b), which illustrates how obstacles in the workspace translate into the C-space. The C-space is discretized at \(0.1\) degree for each DOF, resulting in a 3600\(\times\)​3600 bitmap.

Since there are no joint limits, the C-space topology forms a torus, where the top and bottom edges are connected, as well as the left and right edges. Thus, there are three connected components, and no feasible motion plan exists since \(q_s\) and \(q_g\) are not in the same connected component. Figure 5 (c) illustrates a \(\mathcal{CB}\) of size \(36 \times 36\), corresponding to a discretization of \(10^\circ\) along each dimension. This bitmap is equivalent to the continuous C-space \(\mathcal{C}\). It can be easily verified that there is no collision-free path between \(q_s\) and \(q_g\) since they are in different connected components. Figure 5 (d) depicts a \(\mathcal{CB}\) with a coarser discretization of \(20^\circ\) per dimension (resulting in an \(18 \times 18\) array). Although the number of connected components remains unchanged, Condition 4 is violated (\(q_g\) is incorrectly identified as inside a C-obstacle), and consequently, \(\mathcal{CB}\) is not equivalent to \(\mathcal{C}\). Finally, Figure 5 (e) shows a \(\mathcal{CB}\) with an even lower resolution of \(30^\circ\) along each dimension. With only a single connected component, it is clearly not equivalent to \(\mathcal{C}\), and wrongly certifies that motion planning is feasible. These examples highlight how a reduction in discretization fidelity can distort the topological structure of \(\mathcal{C}\), leading to incorrect connectivity inference in the bitmap representation. This motivates the need for a principled approach to selecting an appropriate resolution that ensures \(\mathcal{CB}\) remains topologically consistent with \(\mathcal{C}\).

3.4 Choosing a resolution for \(\mathcal{CB}\)↩︎

Let us consider a robot with \(n\) revolute joints operating in a 3D workspace with known obstacle geometries and locations. Let \(\mathcal{O}_1, \mathcal{O}_2, \dots\) denote the obstacles, each with a known size \(w_{{obs}}^{(k)}\) and pairwise inter-obstacle distances \(d_{{gap}}^{(k,\ell)}\) between obstacles \(\mathcal{O}_k\) and \(\mathcal{O}_\ell\) in the workspace. The inter-obstacle distance is defined as the minimal translation required for one obstacle to touch the other.

By abuse of notation, let \(\mathcal{R} \subset \mathbb{R}^3\) be the set of all points that constitute the robot’s body in the workspace. The forward kinematics map \(f\) can be defined as \[f: \mathcal{C} \times \mathcal{R} \rightarrow \mathbb{R}^3, \quad f(q, x_r) = x\] that is, it maps a configuration \(q \in \mathcal{C}\) and a robot body point \(x_r \in \mathcal{R}\) to a point \(x \in \mathbb{R}^3\) in the workspace. Furthermore, let \(\mathcal{R}_i \subset \mathcal{R}\) denote the set of points belonging to the \(i^\text{th}\) robot link. Configuration changes \(\Delta q\) can be mapped to corresponding displacements in the workspace \(\|\Delta x\|\) as \[\|\Delta x\| = \|J(q, x_r) \Delta q\|\] where the Jacobian \(J(q, x_r)\) is the manipulator Jacobian \[J(q, x_r) = \frac{\partial f(q, x_r)}{\partial q}\] Therefore, a configuration change \(\Delta q\) causes a robot’s body point \(x_r\) to sweep an arc of length \(\|\Delta x\|\). To ensure that the discretization map does not allow the robot to sweep over an obstacle (mistaking it for free space), and does not falsely connect distinct free regions separated by obstacles, we must enforce the following requirements.

1. For each obstacle \(\mathcal{O}_k\) and robot link \(i\), the maximum sweep \(\|J(q, x_r) \Delta q\|\) (for \(x_r \in \mathcal{R}_i\)) must be less than the obstacle’s thickness, that is, \[\|J(q, x_r) \Delta q\| < w_{{obs}}^{(k)}\]

2. For each pairwise obstacles \((\mathcal{O}_k, \mathcal{O}_\ell)\), the maximum sweep must be less than the inter-obstacle gap, that is, \[\|J(q, x_r) \Delta q\| < d_{{gap}}^{(k,\ell)}\]

where \(\| \cdot \|\) denotes the 2-norm of a matrix. Since it holds that \(\|J(q, x_r) \Delta q\| \leq \|J(q, x_r)\| \cdot \|\Delta q\|\), we obtain that \[\|\Delta q\| < \frac{\min(w_{\mathrm{obs}}^{(k)}, d_{\mathrm{gap}}^{(k,\ell)})}{\|J(q, x_r)\|}\] By minimizing across all robot points \(x_r \in \mathcal{R}\), links \(i\), and obstacles \(k, \ell\), we can therefore define the resolution \[\delta^\star = \inf_{q \in \mathcal{C},\; x_r \in \mathcal{R}} \left( \frac{\min(w_{\mathrm{obs}}, d_{\mathrm{gap}})}{\|J(q, x_r)\|} \right) \label{eq:delta95star}\tag{1}\]

Thus, any resolution³ \(\delta < \delta^\star\) ensures that \(\mathcal{CB}\) faithfully preserves the connectivity structure of the continuous space, preventing the robot from sweeping over obstacles or erroneously jumping across narrow passages. Though 1 gives a theoretical framework for computing \(\delta^\star\), it requires minimizing a Jacobian-based bound over all robot configurations and all body points, which is a hard optimization problem. Below we give a practical method to compute \(\delta^\star\).

3.5 Computing \(\delta^\star\)↩︎

To determine a suitable discretization resolution \(\delta\) for the configuration space, we propose a sampling-based procedure that empirically estimates the minimum joint displacement required to traverse each obstacle (or inter-obstacle distance) in the environment. The procedure is summarized in Algorithm 6 and described in detail below.

For each obstacle \(\mathcal{O}_i \in \mathcal{O}\), a reference point \(p_l\) is selected on a chosen boundary face. In addition, a set of \(S\) points \(\{p_u^{(i)}\}_{i=1}^S\) are sampled on the obstacle boundary. Note that for primitive shapes it is relatively straightforward to identify the faces corresponding to the minimum dimension of the obstacle which represents the thinnest and most constrained direction of traversal. A fixed reference point \(p_l\) is selected on this face, and a set of \(S\) are drawn on the opposite face.

A progressive strategy is then adopted in which the robot is considered as a sequence of partial chains \(\mathcal{R}_{1:m}\), for \(m = 1, \dots, n\), where \(\mathcal{R}_{1:m}\) denotes the sub-chain comprising the first \(m\) links. For each partial chain, inverse kinematics is solved independently for the reference point \(p_l\) and each sample \(p_u^{(i)}\), yielding configurations \(c_l^{(m)}\) and \(c_u^{(m)}\) respectively, along with corresponding geometric Jacobians \(J_l^{(m)}\) and \(J_u^{(m)}\) (lines 5 and 7, Algorithm 6) For each partial chain \(\mathcal{R}_{1:m}\) and each sample \(p_u^{(i)}\), the joint displacement vector is computed (lines 8, Algorithm 6) which is then scaled by the average Jacobian for the \(m\)-link chain (line 10), to account for the differing kinematic contributions of each joint to Cartesian motion. The \(min\) over \(\Delta c(k) \|J_{\text{avg}}(:,k)\|\) identifies \(\delta_{\mathcal{O}_j, m}\) (line 11), the most conservative weighted displacement for each joint \(m\), and the \(max\) over \(\delta_{\mathcal{O}_j, m}\) selects the discretization that most meaningfully encodes the obstacle geometry for that chain. Taking the \(max\) is motivated by the fact that different links of the robot may interact with the same obstacle differently. Taking the \(max\) across \(\delta_{\mathcal{O}_j, m}\) identifies the joint whose motion most faithfully encodes the obstacle geometry in Cartesian space, as joints with near-zero weighted displacement are not meaningfully participating in the traversal of that obstacle and should not drive the resolution estimate.⁴ The required resolution is then obtained as the minimum \(\delta_{\mathcal{O}_j}\) across all the obstacles.

To compare the resolution estimate of Algorithm 6 against a direct numerical evaluation of 1 , we consider the scenario shown in Fig. 7, consisting of a robot arm and a spherical obstacle of radius 0.1 m. For Algorithm 6, 200 points are sampled uniformly from the obstacle surface. To numerically evaluate 1 , we sample 80,000 random joint configurations and identify those for which at least one link segment geometrically intersects the sphere, determined analytically via the quadratic intersection of the parametric link segment with the sphere. For each intersecting link, the entry and exit points with the obstacle surface are computed, and 50 points are sampled uniformly along the chord between them. This is done since the Jacobian \(J(q, x_r)\) varies along the link interior, and the largest \(\|J(q,x_r)\|\), may occur at an interior point rather than at the link endpoint frames.

Algorithm 6 yields a value of \(\delta^\star = 7.54^\circ\) and completes in 15 seconds on average, whereas the numerical implementation of 1 yields \(\delta^\star = 6.97^\circ\) and requires approximately 170 seconds.

4 Experimental Analysis and Discussion↩︎

We conduct experiments on six different motion planning problems in both 2D and 3D workspaces. The 3D workspace scenarios, inspired by [25], are performed using the 4-DOF Kinova MICO arm. The scenarios are as follows:

• A scenario involving a 2D robot capable of translation and rotation (see Fig. 8 (a)),

• A scenario with a 4-DOF articulated robot, as depicted in Fig. 8 (b),

• A scenario where the Kinova arm is trying to reach inside a frame (see Fig. 9 (a)),

• A scenario with the Kinova arm attempting to grasp the cyan block from a position outside the shelf, as shown in Fig. 9 (b),

• A scenario involving a 5-DOF articulated robot aiming to reach a goal configuration (Fig. 8 (c)),

• A 5-DOF robot (Fig. 9 (c)) trying to reach inside a frame from a position outside it.

Iterations denotes the average number of iterations to determine motion planning infeasibility. Segmentation time denotes the total execution time of the SegmentCB subroutine, aggregated over all iterations. Total time is the overall time taken to report plan infeasibilty.

For all scenarios, we empirically set \(ns = 100\) and \(d = 5\). We recall that \(ns\) denotes the minimum number of samples generated by the SampleCobstacle subroutine in a single iteration of Algorithm 2, while \(d\) represents the number of nearby configurations examined for collision. A detailed justification for these parameter choices will be provided later. Collision detection for the Kinova MICO arm is conducted using the checkCollision⁵ feature of the MATLAB Robotics and Autonomous Systems toolbox. However, for the 2D scenarios, both the robot and obstacle polygons are subdivided into triangles, and a triangle intersection algorithm [33] is utilized for collision detection. The segmentation of \(\mathcal{CB}\) in the SegmentCB subroutine is accomplished by utilizing the MATLAB function bwlabeln⁶. This function returns a labeled matrix, assigning labels to different connected components. The performance is evaluated on a Lenovo ThinkPad laptop equipped with an Intel® Core i7-10510U CPU\(@\)​1.80GHz\(\times\)​8 with 16GB RAM under Ubuntu 18.04 LTS.

The experimental scenario corresponds to the non-existence of a path between the start and the goal configurations. To establish the ground truth for plan infeasibility, for the Kinova arm scenarios, we run RRT-Connect [3] continuously for more than 30 minutes, and for the other three scenarios, we run PRM [2] for more than 30 minutes. For each experiment, we conduct 30 trials and record the following metrics:

• Iterations: The average number of iterations required to establish motion planning infeasibility. Each iteration of Algorithm 2 involves sampling at least \(ns\) configurations within the C-obstacle. Depending on the robot’s geometry and the spatial distribution of obstacles in the workspace, a single iteration may not yield sufficient samples within the C-obstacle to successfully segment \(q_s\) and \(q_g\) into distinct connected components. Consequently, multiple iterations may be necessary to certify infeasibility.

• Segmentation time: The cumulative execution time of the SegmentCB subroutine, summed across all iterations.

• Total time: The overall computational time required by Algorithm 2 to ascertain plan infeasibility. This includes the segmentation time.

Table ¿tbl:tab:statistics? reports the above metrics. To ensure that the chosen \(\mathcal{CB}\) is equivalent to the respective continuous \(C\)-spaces, we run Algorithm 6 to compute \(\delta^\star\). The resulting values of \(\delta^\star\) for \(S_2\) to \(S_6\) are \(41.79^\circ\), \(15.44^\circ\), \(15.25^\circ\), \(23.51^\circ\), and \(16.72^\circ\), respectively. In our experiments, however, we use finer resolutions of \(10^\circ\), \(7.5^\circ\), and \(5^\circ\). Performance is evaluated across these resolutions to assess the associated computational cost.

4.1 3-DOF scenario↩︎

Infeasibility is detected within a few seconds for all the three resolutions of \(\mathcal{CB}\). It is worth noting that the segmentation of the \(\mathcal{CB}\) into connected components takes only a fraction of a second for all three resolutions reported. We can conclude that the approach is applicable to 3-DOF robots.

4.2 4-DOF experiments↩︎

The scenarios depicted in Fig. 8 (b) (\(S_2\)) and Fig. 9 (\(S_3\), \(S_4\)) correspond to a four-dimensional C-space. For \(S_2\), as shown in Table ¿tbl:tab:statistics?, the total runtime remains below 3 seconds across all three resolutions of \(\mathcal{CB}\), with infeasibility being established in the first iteration. Due to the sparse distribution of obstacles, each sampled configuration \(q\) in C-obstacle, when processed using the SpeedUp subroutine and analyzed along with its \(d\) neighboring configurations, quickly identifies C-obstacle configurations contributing to infeasibility.

Although the scenarios \(S_3\) and \(S_4\) also correspond to a 4-DOF robot, their total computational time is significantly higher compared to \(S_2\). This increase is primarily attributed to the differences in the CollisionCheck subroutine: in the 2D scenario \(S_2\), triangle intersection tests employed are computationally efficient, whereas for \(S_3\) and \(S_4\), the checkCollision function introduces a substantially higher computational overhead.

Comparing \(S_3\) and \(S_4\), we observe that \(S_4\) incurs a slightly higher computational cost. In \(S_3\), the frame contributes to the infeasibility, whereas in \(S_4\), the two red blocks obstruct the robotic arm from reaching the target position. This implies that if the red blocks are removed from the workspace, a feasible path exists. The current random sampling strategy generates redundant samples from the C-obstacle region contributed by the shelf, which, while contributing to the analysis, are not necessarily required for proving infeasibility. This results in unnecessary computations and increases the overall runtime. Overall, the experiments demonstrate that the proposed approach is well-suited for motion planning in 4-DOF robotic systems.

4.3 5-DOF scenario↩︎

The proposed approach demonstrates effective scalability to a 5-dimensional C-space, as evidenced by the last two rows of Table ¿tbl:tab:statistics?. Compared to \(S_5\), scenario \(S_6\) exhibits an approximately threefold increase in computation time for the \(36\) and \(48\) resolution cases. Similar to the 4-DOF scenarios, this increase is primarily attributed to the higher cost of the CollisionCheck subroutine in 3D environments relative to 2D.

Furthermore, as the bitmap resolution increases to \(72\), the segmentation stage dominates the overall computation time. Consequently, minimizing the number of iterations becomes important, as multiple iterations would significantly increase the total runtime. With \(ns = 100\) for \(S_6\), the method requires approximately three iterations on average. Increasing the sample count to \(ns = 300\) reduces this to a single iteration, but at the expense of additional sampling cost, thereby contributing to the overall computation time.

5 Discussion↩︎

5.1 Advantages of Segmentation over Search-Based Methods↩︎

One may argue that, given a discretized C-space, traditional graph-based search algorithms such as \(A^\star\) could be employed directly to certify infeasibility, instead of segmenting the C-space into connected components. However, search-based methods must exhaustively explore all possible nodes in the absence of a feasible path, leading to significantly higher computational overhead compared to our segmentation approach.

To provide a baseline comparison, we implemented an \(A^\star\)-based infeasibility check by replacing the SegmentCB subroutine in Line 5 of Algorithm 2 with a standard \(A^\star\) search. If the search terminates without finding a path from \(q_s\) to \(q_g\), the problem is deemed infeasible. The comparison was performed for scenarios \(S_2\) and \(S_3\), and the corresponding computation times for the proposed segmentation-based method and the \(A^\star\) baseline are shown in Fig. 10.

For scenario \(S_2\), the proposed method required between 0.6-2.6 seconds, whereas the \(A^\star\) approach took 550-8000 seconds. Similarly, for scenario \(S_3\), the proposed method completed within 25-107 seconds, while the \(A^\star\) search required 650-11,000 seconds. These results demonstrate that the proposed segmentation-based approach is approximately two to four orders of magnitude faster than the \(A^\star\)-based baseline across the tested environments.

We further evaluate the segmentation performance across scenarios \(S_2\) and \(S_3\) for varying C-space resolutions corresponding to \(\mathcal{CB}\) sizes of \(36^4\), \(48^4\), \(60^4\), \(72^4\), \(84^4\), \(100^4\), \(120^4\), and \(144^4\). The corresponding segmentation times are plotted in Fig. 11. As observed from the figure, the measured computation times closely follow the expected \(O(n \log^* n)\) growth trend, thereby validating the near-linear complexity of the segmentation algorithm.

5.2 Choosing \(ns\) and \(d\)↩︎

We first examine the effect of fixing \(d\). While lower values of \(d\) resulted in similar overall runtime performance, higher values (\(d > 5\)) led to increased runtimes. This is because checking \(d\) neighboring samples for collisions requires additional calls to the collision checker, thereby increasing computational cost. Based on our observations, \(d = 5\) provides a practical balance.

Independently of \(d\), smaller values of \(ns\) (\(ns < 100\)) did not significantly impact performance for scenarios \(S_1\)-\(S_4\), as the segmentation times are negligible. However, larger values of \(ns\) could lead to longer runtimes simply due to the acquisition of more samples (and thereby calls to CollisionCheck) than necessary to establish infeasibility. In \(S_5\), where segmentation time constitutes a major portion of the total runtime, setting \(ns < 100\) could result in multiple iterations (as opposed to the single iteration currently required for \(S_5\), as shown in the sixth column of Table ¿tbl:tab:statistics?), increasing runtime. The same reasoning extends to \(S_6\), for which \(ns < 300\) leads to more than one iteration.

To provide a quantitative assessment, we fix \(ns = 100\) and vary \(d \in \{0, 3, 5, 8,\) \(15, 25\}\) for scenarios \(S_3\) and \(S_4\), analyzing the resulting computation times across three different C-space discretization densities. The results, summarized in Table 1, reveal a consistent trend across both scenarios and all resolutions: the runtime initially decreases as \(d\) increases from 0 to 5, indicating improved efficiency from incorporating limited local neighborhood information. Beyond this range (\(d > 8\)), the runtime increases again due to the additional collision-checking overhead associated with larger neighborhoods.

For instance, in \(\mathcal{CB}\) of size \(36^4\) for \(S_3\), the runtime decreases from 34.37 s (\(d=0\)) to 24.52 s (\(d=5\)), but rises to 47.38 s at \(d=25\). A similar pattern is observed for \(S_4\), where the runtime reduces from 47.54 s (\(d=0\)) to 28.10 s (\(d=5\)), before increasing again to 48.72 s at \(d=25\). This trend is consistent at higher resolutions as well—for example, in the \(\mathcal{CB}\) of size \(72^4\), \(S_3\) shows a sharp drop from 219.51 s to 107.27 s between \(d=0\) and \(d=5\), while \(S_4\) drops from 247.61 s to 136.01 s over the same range. These results collectively demonstrate that \(d = 5\) consistently achieves the best computational trade-off across both scenarios. We also perform the same analysis for the 5-DOF scenario \(S_6\) at a resolution of \(36^\circ\). A trend similar to that observed in Table 1 is obtained. To make this explicit, we compare the runtimes with \(S_3\), as illustrated in Fig. 12 (a).

To examine the effect of the sampling density on computational performance, we fix the neighborhood parameter at \(d=5\) and vary the number of samples \(ns \in \{50, 80, 100, 150, 200, 300, 400\}\) for scenarios \(S_3\) and \(S_4\). Table 2 reports the corresponding average runtimes over 30 runs for three different C-space discretization densities. A consistent trend is observed across both scenarios: the runtime increases gradually with \(ns\), reflecting the additional computational cost of generating and evaluating larger sample sets. However, the rate of increase is sublinear for moderate \(ns\) values, indicating that the cost of sampling amortizes well up to about \(ns=150\).

For instance, in \(\mathcal{CB}\) of size \(36^4\) for \(S_3\), the runtime increases moderately from 21.18 s (\(ns=50\)) to 30.62 s (\(ns=150\)), but rises sharply to 69.63 s at \(ns=400\). A similar pattern is evident for \(S_4\), where the runtime grows from 27.97 s at \(ns=50\) to 34.09 s at \(ns=150\), before reaching 103.42 s at \(ns=400\). Larger C-space resolutions exhibit the same qualitative behavior, with proportionally higher runtimes due to the increased collision-checking cost per configuration. Overall, these results suggest that \(ns\) values between 80 and 150 offer a favorable trade-off between computational efficiency and sampling coverage.

An interesting case is observed for \(ns = 300\) and \(ns = 400\) in scenario \(S_3\), where both C-space resolutions result in similar runtimes. For \(ns < 300\), Algorithm 2 requires multiple iterations (see Table ¿tbl:tab:statistics?, row 3, column 6). In contrast, for \(ns \geq 300\), Algorithm 2 converges in a single iteration. As a result, the elimination of these repeated iteration overheads offsets the additional cost associated with the higher C-space resolution. Consequently, the only remaining difference is the segmentation time, which is negligible for the considered C-space resolutions (see Table ¿tbl:tab:statistics?, row 3, column 7). The same reasoning also applies to scenario \(S_4\), for \(ns=400\), where the C-space resolutions \(36^4\) and \(48^4\) exhibit similar runtimes.

We also examine the effect of varying \(ns\) for the the 5-DOF scene \(S_6\). A similar trend in computation time is observed as in the 4-DOF scenarios, as shown in Fig. 12 (b).

5.3 Obstacle Volume↩︎

As discussed in Section 3, the proposed method is based on the principle that it is not necessary to sample all points in the C-obstacle, but only those required to establish infeasibility. The primary computational challenge lies in determining whether a sampled configuration belongs to the C-free or C-obstacle region, which necessitates executing the CollisionCheck subroutine.

Thin obstacles in the workspace (those occupying less volume) correspond to narrow C-obstacle regions in the C-space, making it more challenging to sample from the C-obstacle. This is because a large proportion of random samples may correspond to collision-free configurations. Conversely, thick obstacles (those with larger volume) result in broader C-obstacle regions, making sampling easier. However, in such cases, an excessive number of configurations may be sampled, potentially exceeding what is necessary to establish infeasibility, thereby leading to increased runtime.

To analyze this effect, Fig. 13 presents two modified versions of \(S_3\) (Fig. 9 (a)). In Fig. 13 (a), the obstacle volume is 2.4 times that of \(S_3\), whereas in Fig. 13 (b), it is reduced to \(4/11\) of the volume of \(S_3\). The runtime comparison (average across 30 trials) for all the scenarios (including \(S_3\)) is provided in Fig. 14 (a). For the thick-obstacle case, the runtime remains comparable to \(S_3\). However, for the thin-obstacle case, as expected, the runtime increases, also exhibiting a larger standard deviation.

Currently, no specialized sampling technique is employed; instead, we randomly sample without replacement from the \(\mathcal{CB}\) bitmap to check for occupancy. A more engineered approach to sampling from C-obstacle could significantly mitigate the above bottleneck by avoiding the selection of numerous C-free elements, thereby reducing unnecessary calls to the CollisionCheck subroutine.

5.4 Complexity Analysis↩︎

A rigorous theoretical characterization of the computational complexity of the proposed approach is nontrivial and lies beyond the scope of this study. To gain empirical insight, we analyzed the scaling behavior of computation time for scenarios \(S_2\) and \(S_3\) by varying the C-space discretization with grid sizes of \(36^4\), \(48^4\), \(60^4\), \(72^4\), \(84^4\), \(100^4\), \(120^4\), and \(144^4\). The measured computation times were fitted against several functional models, including linear, quadratic, and cubic polynomials, as well as power, exponential, and \(x \log x\) relationships.

Model fitting was evaluated using both the coefficient of determination and mean squared error metrics. Across both scenarios, a third-order polynomial in the C-space size per dimension yielded the best fit, indicating a cubic dependence of computation time on the discretization density of the C-space. The fitted curves and experimental data are presented in Fig. 15.

5.5 Runtime Reduction↩︎

The CollisionCheck subroutine, particularly for scenarios \(S_3\) and \(S_4\), remains the most computationally expensive component. Implementing faster collision-checking techniques [38], [39] can significantly accelerate the process. Another approach to enhancing computational efficiency is to parallelize Algorithm 3. However, in its current form, Algorithm 3 is not embarrassingly parallel, as the RandomSample subroutine may generate identical samples across parallel tasks. If this limitation is disregarded, the for loop can be naively parallelized.

To this end, we rerun \(S_3\) and \(S_4\) by parallelizing Algorithm 3 using MATLAB’s Parallel Computing Toolbox, enabling execution across four cores. The average runtimes are compared in Fig. 14 (b), where it can be observed that the computation time is reduced by about 2.4 times for both \(S_3\) and \(S_4\). The computations were conducted on a Lenovo ThinkPad laptop equipped with an Intel® Core i7-10510U CPU\(@\)​1.80GHz\(\times\)​8 and 16GB RAM running Ubuntu 18.04 LTS. Leveraging the parallelism of modern high-performance CPUs and GPUs can further improve computational efficiency.

5.6 Feasible Plan Experiments↩︎

Though the primary goal of this work is to certify infeasibility, the approach can be naturally extended to run a motion planner in parallel with Algorithm 2. In this setting, if a feasible plan exists, the motion planner returns a solution; otherwise, if the problem is infeasible, Algorithm 2 provides a certificate of infeasibility. Both the motion planner and the infeasibility detection algorithm are executed concurrently on independent workers. The main thread waits at a synchronization point and resumes as soon as the first worker completes. Upon completion, the remaining worker is immediately terminated. This parallel formulation ensures that feasibility is established as quickly as possible when a solution exists, while still guaranteeing certification of infeasibility otherwise. Algorithm 16 summarizes this parallel strategy.

We modify scenarios \(S_3\), \(S_4\), and \(S_6\) to ensure the existence of a feasible path. For \(S_3\) and \(S_6\), the frame is translated away from the robot base to make reaching inside the frame feasible. The magnitude of translation differs across the two cases, resulting in a narrower passage in \(S_3\) compared to \(S_6\). For \(S_4\), the red block on the right side of the scene is removed, thereby creating a narrow passage. The resulting planning times for obtaining a feasible path are reported in Table ¿tbl:tab:feasible?. Path planning is performed using RRT-Connect.

5.7 Scaling to Higher Dimensions↩︎

The proposed approach is effective for up to 5-DOF C-spaces. Higher-dimensional C-spaces introduce complexity in both space (for representing \(\mathcal{CB}\)) and time (for segmentation). However, we make the following observation: in many motion planning problems involving a manipulator, infeasibility is often attributed to a specific link, typically one of the earlier links in the kinematic chain. Consequently, infeasibility proofs can often be formulated in lower-dimensional spaces while remaining valid in higher-dimensional spaces— an approach grounded in quotient space topology [32], [36].

To illustrate this, we conduct experiments on two scenarios: (a) \(S_7\), where a 6-DOF robot arm is tasked with picking up a green object and placing it inside a shelf (see Fig. 17 (a)), and (b) \(S_8\), where a 7-DOF robot arm attempts to reach outside the table from the inside (Fig. 17 (b)). In both scenarios, infeasibility is caused by the third link, allowing us to consider a reduced 3-DOF C-space to establish infeasibility. The runtime results are presented in Table ¿tbl:tab:statistics2?, demonstrating that infeasibility for all three resolutions in both scenarios is proven in under 50 seconds.

While determining the appropriate reduced C-space remains a challenge, these examples suggest that many high-dimensional infeasibility problems can be addressed by proving infeasibility in a lower-dimensional C-space. Identifying such a minimal C-space dimension may require progressively building from lower dimensions. Nevertheless, pursuing these simplifications can significantly enhance the scalability of the proposed approach.

6 Conclusion↩︎

In this paper, we introduce a simple algorithm that is easy to implement for checking motion planning infeasibility. Our approach relies on the approximation of the C-space using a discretized bitmap. Initially, all cells of this bitmap are designated as C-free. Subsequently, our algorithm incrementally builds the bitmap by randomly sampling from the C-space and verifying the occupancy of each sampled cell. The constructed bitmap is then segmented into different connected components, which are separated by C-obstacles. Afterward, we query the connectivity of the start and goal cells. Through the incremental construction of the C-space, we only need to draw a sufficient number of samples to establish the partition between the start and goal configurations. The approach is validated through experiments involving robots with up 5-DOF. Additionally, we explore enhancements to accelerate the algorithm, presenting promising directions for future work. We also discuss scalability to higher dimensions and validate the approach through experiments on 6-DOF and 7-DOF robots.

Acknowledgments↩︎

The authors are grateful to the reviewers for their insightful comments and suggestions.

Work on this article by Antony Thomas is supported in part by the International Institute of Information Technology (IIIT) Hyderabad (Grant No. IIIT/R&D Office/Seed-Grant/2025-26/002).

References↩︎

---

1. In Section 5.6, we show that the approach can be naturally extended to incorporate plan feasibility by running a motion planner in parallel with the proposed method. In this setting, a feasible plan is returned if one exists; otherwise, the proposed method provides an infeasibility certificate.↩︎

2. To check for collisions with obstacles, both the robot and obstacle polygons are subdivided into triangles, and a triangle intersection algorithm [33] is used. Computation performed on an Intel® Core i7-10510U CPU\(@\)​1.80GHz\(\times\)​8 with 16GB RAM under Ubuntu 18.04 LTS.↩︎

3. \(\delta^\star\) is valid uniformly over all joint angles.↩︎

4. Note that this may be viewed as a discrete approximation of the norm of the Jacobian in 1 .↩︎

5. Web: https://it.mathworks.com/help/robotics/ref/rigidbodytree.checkcollision.html↩︎

6. Web: https://it.mathworks.com/help/images/ref/bwlabeln.html↩︎