Source-linked AI summary
GCS-Bridging: Restoring Connectivity of Disconnected Convex Sets for Graph-of-Convex-Sets Motion Planning
Xiaokai Zhou, Baoshi Cao, Yang Liu, Kui Sun, Boyu Ma, Zhengpu Wang, Zongwu Xie
TL;DR
Existing GCS motion-planning pipelines may fail when start and goal regions lie in different connected components. GCS-Bridging reconnects those components through collision-free local paths and convex-region inflation, achieving 99.8% success with pure RRT-C and 100% with a hybrid strategy. A 7-DoF single-arm experiment further demonstrated restored feasible GCS planning, while the approach remains limited by incomplete collision-free guarantees of several IRIS-based region-generation methods.
Problem
Existing GCS pipelines focus on optimizing over preconstructed connected convex regions and give limited attention to missing start-to-goal connectivity in internally disconnected maps.
Method
GCS-Bridging connects convex regions across components using RRT-C or a DirectLine-before-LocalRRTC hybrid strategy, followed by convex-region inflation.
Results
99.8% success was achieved with pure RRT-C-based GCS-Bridging and 100% with the hybrid strategy across six randomized disconnected scenarios and other IRIS initializations.
Takeaways & Limitations
GCS-Bridging restored feasible GCS motion planning on a 7-DoF single-arm robotic system with initially disconnected regions.
Takeaways & Limitations
The method relies on IRIS-related region-generation algorithms that do not provide complete collision-free guarantees, while rigorous alternatives suffer from high-dimensionality costs.
Abstract
from arXiv · showhide
Graph-of-Convex-Sets (GCS)-based trajectory optimization represents collision-free regions in configuration space as a finite collection of convex sets and directly performs collision-free trajectory planning over these sets, substantially simplifying the planning process. However, existing GCS-based trajectory planning methods generally assume sufficient connectivity among the convex regions and do not explicitly address cases in which the start and goal regions belong to different connected components of the initial GCS map. To address this limitation, we propose GCS-Bridging, which reconnects disconnected convex regions through collision-free point paths followed by convex region inflation, thereby recovering the feasibility of otherwise disconnected GCS planning problems. Extensive simulations across multiple IRIS-related algorithms and scenarios demonstrate that GCS-Bridging restores missing start-to-goal connectivity in the initial GCS map with a 99.8% success rate. In addition, a hardware experiment on a single-arm Franka platform in a real-world scenario with initially disconnected start and goal regions validates the effectiveness of the proposed method in practical motion planning. Project website: https://zhouxk1997.github.io/GCS_Bridging/
I. INTRODUCTION
Motion planning in configuration space can use reusable convex-region maps, but existing GCS pipelines give limited attention to repairing disconnected start-to-goal connectivity. GCS-Bridging addresses this gap through adaptive reconnection and region inflation, achieving near-complete simulated reconnection success.
- Motivation: Configuration-space motion planning avoids explicitly representing complete obstacle geometry by evaluating collision costs during trajectory generation.These direct motion-generation methods include sampling-based, optimization-based, and learning-based approaches.
- Research gap: Existing GCS pipelines optimize trajectories over preconstructed connected convex regions, while recovery of missing connectivity remains comparatively underexplored.The gap concerns cases where the initial GCS map is internally disconnected.
- Contributions: GCS-Bridging formulates insufficient initial-map connectivity as a connectivity repair problem.This reframes disconnected GCS planning as a repair task rather than only a trajectory-optimization task.
- Contributions: The proposed reconnection algorithm combines cross-component locally adaptive discrete paths with connectivity-aware convex-region inflation.The method extends the IRIS-based framework for convex-region generation and GCS motion planning.
- Evaluation: 99.8% overall reconnection success was achieved with the RRT-C-based method, compared with 100% for the hybrid method across four IRIS algorithms and six randomized scenarios.The evaluation also included a real-robot experiment.
II. PROBLEM FORMULATION
The problem formulation models collision-free convex regions and their connectivity as a graph of connected components. GCS trajectory optimization can be infeasible when the start and goal regions lie in different components, motivating construction of additional bridging regions.
- Configuration-space model: A redundant manipulator has configuration q in C ⊆ R^n, while C_free denotes its collision-free configuration space.The start and goal configurations are q_s and q_g, respectively.
- Configuration-space model: Each generated convex region R_i is assumed to lie within C_free, providing collision-free building blocks for the GCS map.The region-generation methods may be heuristic or probabilistically complete.
- Graph representation: The GCS map partitions regions into connected components, with edges representing nonempty intersections between regions in the same component.Within each component, connected regions have at least one feasible sequence linking them.
- Failure condition: GCS trajectory optimization may be infeasible when the regions containing q_s and q_g belong to different connected components.In that case, the solver cannot identify a connected convex-region sequence between the start and goal.
- Repair objective: GCS-Bridging constructs additional collision-free convex regions to connect the start and goal components and restore a feasible region sequence.When possible, it also reduces the configuration space to a single connected component.
III. GCS-BRIDGING ALGORITHM
GCS-Bridging repairs missing graph connectivity by identifying nearby regions across components, creating a collision-free local bridge, and inflating that path into connected convex regions. The procedure actively repairs the initial GCS topology instead of relying on its predefined edges.
- Bridge construction: The algorithm first computes the closest point pair between two convex regions in configuration space and initializes a bridge with LocalRRTC.Convex-region connectivity is subsequently constructed by inflating the RRT-C path.
- Component analysis: GCS-Bridging constructs the connectivity graph and connected components from the initially generated region set before testing whether bridging is needed.No further bridging is required when all regions already form one component.
- Candidate selection: Candidate region pairs from different components are sorted by ascending configuration-space distance together with their closest witness-point pairs.This ordering determines which cross-component connections are attempted first.
A. LocalRRTC Bridging
LocalRRTC bridges disconnected convex regions by searching for collision-free paths in a restricted local configuration-space domain. The algorithm validates witness points, adapts the sampling region, and records successful bridges after connectivity-aware inflation.
- A. LocalRRTC Bridging: LocalRRTC serves as a local bridge between previously generated collision-free convex regions rather than isolated configurations.It addresses high-dimensional planning challenges by searching for feasible connections between regions.
- A. LocalRRTC Bridging: Witness points are collision-checked before planning, and invalid points are retracted toward their regions’ interiors before rechecking.This prevents unreliable paths from starting at colliding endpoints.
- A. LocalRRTC Bridging: LocalRRTC performs bridging inside an axis-aligned local region after candidate points satisfy joint-limit, region-membership, and collision-free constraints.The restricted domain is intended to mitigate the curse of dimensionality in configuration space.
- A. LocalRRTC Bridging: If bridging fails, the half local margin is doubled and sampling is repeated with multiple random seeds to improve exploration.These modifications adapt the search domain and increase sampling diversity.
- A. LocalRRTC Bridging: The algorithm builds a connectivity graph, ranks cross-component region pairs, searches for paths, inflates successful paths, and updates connected components incrementally.Failed pairs are recorded, while successful pairs are marked as bridged and incorporated into the region set.
B. DirectLine Bridging
DirectLine provides a simple reconnection strategy by continuously checking the segment between witness points for collision freedom. It is efficient for simple region pairs, particularly in lower-dimensional settings, but is less adaptable when the straight segment is obstructed.
- B. DirectLine Bridging: DirectLine continuously collision-checks the segment between witness points to connect two regions.The method is straightforward and can be applied before LocalRRTC in the hybrid strategy.
- B. DirectLine Bridging: DirectLine is highly efficient in lower-dimensional scenarios and remains effective for simple cases in higher-dimensional spaces.Its suitability depends on the geometric simplicity of the region pair and connecting segment.
C. Binary Inflation
Binary inflation converts a collision-free piecewise-linear bridge into connected convex regions suitable for GCS optimization. It inflates selected path midpoints, verifies overlapping chains, and limits committed regions while retaining explicit safety checks.
- C. Binary Inflation: Binary inflation is required because GCS optimizes over connected convex regions, whereas LocalRRTC initially returns only a piecewise-linear path.The inflated regions must be representable as Ax ≤ b and connected through nonempty intersections.
- C. Binary Inflation: BinaryInflation stages parallel inflation results, rebuilds a temporary connectivity graph, and returns the shortest overlapping chain once the endpoint regions connect.Only staged regions belonging to the successful chain are returned.
- C. Binary Inflation: The procedure selects the midpoint of the largest unprocessed path interval, applies IRIS inflation there, and recursively processes the resulting subintervals.This coarse-to-fine ordering avoids inflating every path point.
- C. Binary Inflation: Parallel midpoint candidates are processed in batches, while additional candidates do not permanently increase the GCS graph size.This improves computational efficiency without committing redundant regions.
- C. Binary Inflation: GCS-Bridging is budget-constrained rather than guaranteed to succeed in arbitrary free spaces, because local sampling, finite restarts, and inflation limitations can leave bridges undiscovered.Committed results retain collision checks, collision-free inflated regions, verified intersections, and complete overlapping chains.
A. Methodology
The evaluation compares GCS-Bridging across multiple IRIS algorithms and reconnection scenarios using standardized experimental metrics. The comparison measures map structure, reconnection success, and reconnection time while excluding cases already connected at initialization.
- The evaluation covers multiple IRIS algorithms, six randomized initially disconnected scenarios, and a physical Franka Panda experiment.
- Table II compares DirectLine, RRT-C-based GCS-Bridging, and a hybrid strategy across single-arm and dual-arm planning scenarios.
- The reported metrics include initially generated regions, initial connected components, added regions, reconnection success rate, and reconnection time.
- Success rate counts reconnections excluding initialization cases in which the start and goal configurations were already connected.
- The comparison focuses on establishing a connected region sequence; subsequent GCSTrajOpt optimization is outside its scope.
B. Multiple IRIS Algorithm Comparison
GCS-Bridging is tested for compatibility with several IRIS-based convex-region generation algorithms. It connects all evaluated start and goal configurations, while computational cost increases when the initial graph is highly fragmented.
- The KUKA bimanual scenario evaluates compatibility with IRIS-NP, IRIS-NP2, IRIS-ZO, and IRIS-ZO-CUDA.
- GCS-Bridging successfully connects all evaluated start and goal configurations across the tested IRIS algorithms.
- RRT-C piecewise-linear paths support IRIS inflation, while LocalRRTC improves overall graph connectivity.
- Excessive initial connected components increase LocalRRTC, BinaryInflation, and final optimization costs, particularly for IRIS-ZO and IRIS-ZO-CUDA.
- Smaller regions from IRIS-ZO and IRIS-ZO-CUDA fragment the initial map, requiring additional regions and repeated connectivity evaluations.
C. Multiple Scenarios Comparison
The scenario comparison evaluates manual reconnection, DirectLine, RRT-C-based GCS-Bridging, and a hybrid strategy across single-arm and dual-arm planning tasks. DirectLine is efficient in simpler settings but performs worse in complex or high-dimensional environments.
- Manual reconnection depends strongly on environmental knowledge and prior experience, making systematic reproduction difficult.
- DirectLine avoids local path search and is computationally efficient, but collision-free linear connections become restrictive as complexity and robot degrees of freedom increase.
- The experiments compare DirectLine, RRT-C-based GCS-Bridging, and hybrid DirectLine/LocalRRTC across single-arm and dual-arm scenarios.
- 69.2% is the overall success rate for DirectLine, compared with 99.8% for RRT-C-based GCS-Bridging and 100% for the hybrid strategy.
- The hybrid strategy is retained as a practical CPU-based option for low-dimensional scenarios.
D. Hardware Validation on Bookshelf Environment
A real-world Franka Panda bookshelf experiment tests GCS-Bridging when start-to-goal regions are initially disconnected. The method reconnects the map and produces feasible collision-free paths, while its guarantees remain limited by the underlying region-inflation methods.
- The 7-DoF Franka Panda performs point-to-point motion planning in a camera-modeled bookshelf environment with sphere-based robot and cuboid bookshelf collision models.
- Five initial convex regions contain start, goal, and neutral configurations, while additional randomly initialized regions leave some start-to-goal regions disconnected.
- GCS-Bridging reconnects the initially infeasible map and generates feasible collision-free paths in the bookshelf scenario.
- GCS-Bridging reconnects disconnected convex-region components by using RRT-C or a DirectLine/LocalRRTC hybrid followed by convex-region inflation.
- The method is limited by IRIS-related inflation algorithms that lack complete collision-free guarantees or suffer from high-dimensional scaling difficulties.