An Incremental Sampling and Segmentation-Based Approach for Motion Planning Infeasibility

Antony Thomas, Fulvio Mastrogiovanni, Marco Baglietto · 2025

Read An Incremental Sampling and Segmentation-Based Approach for Motion Planning Infeasibility by Antony Thomas, Fulvio Mastrogiovanni, Marco Baglietto (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11434.txt.

Introduction

Antony Thomas, Fulvio Mastrogiovanni, and Marco Baglietto present a robot planning method from 2025 for proving that no safe path exists. Most planners search for a path and fail in silence when none exists. Their method instead builds proof that start and goal lie apart.

The idea cuts the robot pose space into a grid and marks cells blocked by obstacles. As more blocked cells are sampled, the free space splits into zones. If start and goal fall in distinct zones, no path can join them. The team shows the method on scenes with up to five joints, then speeds it up and tests arms with six and seven joints.

Catalog record

CREATORAntony Thomas, Fulvio Mastrogiovanni, Marco Baglietto
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11434

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Incremental Sampling and Segmentation-Based Approach for Motion Planning Infeasibility Antony Thomas, Fulvio Mastrogiovanni, Marco Baglietto Abstract We present a simple and easy-to-implement algorithm to detect plan infeasibility in kinematic motion planning. Our method involves approximating the robot’s configuration space to a discrete space, where each degree of freedom has a finite set of values. The obstacle region separates the free configuration space into different connected regions. For a path to exist between the start and goal configurations, they must lie in the same connected region of the free space. Thus, to ascertain plan infeasibility, we merely need to sample adequate points from the obstacle region that isolate start and goal. Accordingly, we progressively construct the configuration space by sampling from the discretized space and updating the bitmap cells representing obstacle regions. Subsequently, we partition this partially built configuration space to identify different connected components within it and assess the connectivity of the start and goal cells. We illustrate this methodology on five different scenarios with configuration spaces having up to 5 degree-of-freedom (DOF). I 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. (a) (b) (c) Figure 1: (a) A representative discrete configuration space with the start and goal configuration cells colored in green and red, respectively. Other colored cells represent obstacle regions, while uncolored cells represent free space. (b) The sampled obstacle region is colored in blue. This partially constructed configuration space is sufficient to establish motion planning infeasibility since there exists no path from the start to the goal. (c) Segmented representation of the configuration space as shown in (b). There are two regions denoted by 1’s and 2’s, respectively, separated by the obstacle region indicated by 0’s. Since the start configuration belongs to region 1 and the goal configuration belongs to region 2, motion planning is infeasible. Motion infeasibility is a critical aspect of many robot planning methodologies. Task and motion planning [ 5 , 6 , 7 , 8 , 9 , 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 , 12 , 13 , 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. The main contribution of this paper is a simple and easy-to-implement algorithm for proving the infeasibility of motion planning. 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 a high degree-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 . 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 IV , we elucidate this approach in detail and further discuss methods to speed up the construction of the configuration space. II Related Work In this Section, 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. Approximate configuration space: Zhang et al. [ 15 ] 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 [ 16 ] , 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 [ 17 ] . 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. [ 18 ] 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 [ 19 ] . The orientations of the rigid body are discretized, and each orientation is individually checked for its ability to pass through the gate. Learning based: Li et al. [ 20 ] combine supervised learning and sampling based planning to prove motion planning infeasibilty. They

Read the complete text