CS Paper Radar

Coverage Path Planning for Redundant Manipulators using Generalized Spanning Trees

Raksi Kopo, Kostas J. Kyriakopoulos

cs.RO ·submitted 2026-09-08 08:17 UTC · v1
published

Abstract

Surface coverage with task-redundant manipulators is challenging because each surface point may admit multiple inverse kinematics (IK) solutions, and configuration choices strongly affect motion quality. This paper extends the classical Spanning Tree Coverage (STC) method to redundant manipulators through offline and online Joint Spanning Tree Coverage (JSTC) algorithms. Offline JSTC samples multiple Inverse Kinematics (IK) solutions per grid cell and formulates the problem as a Generalized Minimum Spanning Tree (GMST), selecting one configuration per cell and tracing the resulting tree to obtain a non-revisiting coverage path. Online JSTC incrementally expands and backtracks a spanning tree with feasibility and cost evaluation while handling dynamic grid updates. Simulation results show that offline JSTC reduces computation time, reconfigurations, and joint motion compared to other methods, while online JSTC achieves fast per-step planning in dynamic scenarios.

Comment
Accepted for publication in IROS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

TRACE: Coverage Path Planning for Unknown Environments Using Hierarchical Coverage Tree

cs.RO ·2026-09-18 ·Zongyuan Shen, Haodong Liu, Gao Wang, Shancheng Zhao, Dehua Zhou +4 more
similarity 0.61
Abstract

This paper presents a novel online coverage path planning (CPP) algorithm, called TRACE, for real-time coverage of unknown environments. TRACE is built upon a hierarchical coverage tree that provides a global representation of the evolving connectivity of the uncovered space. As the environment is incrementally revealed and covered, newly discovered obstacles and covered cells may fragment the remaining uncovered space into disconnected regions. TRACE recursively expands the corresponding tree nodes to explicitly represent these regions and organize them for subsequent coverage planning. Based on the updated tree, an incremental global tour is maintained to guide the coverage process. TRACE locally refines only the affected portions while preserving the visiting order of unchanged regions, thereby reducing the computational burden of global replanning and maintaining a consistent coverage progression. Guided by the global tour, a local planner generates back-and-forth coverage paths and switches to global-tour-aware planning to efficiently complete the target regions. Theoretical analysis establishes the computational complexity and complete coverage property of TRACE, and derives an approximation bound for the incremental global tour refinement. The performance of TRACE is evaluated through extensive high-fidelity simulations and real-robot experiments using a mobile robot. Comparative evaluations against six existing CPP methods demonstrate significant improvements in coverage time, path length, overlap ratio, and number of turns.

0.10

FWIK: Multi-Waypoint IK Selection via Lookahead Graph Search

cs.RO ·2026-11-04 ·Jinglan Cao, Guohui Zhong, Chengwei Zhang
similarity 0.60
Abstract

An ordered sequence of end-effector poses can give a redundant robot arm multiple valid joint configurations at each waypoint. Inverse kinematics (IK) computes these configurations. Choosing a configuration only for the next waypoint can leave the arm poorly placed for later waypoints. This may increase planned motion time or cause a later planning failure. This paper presents Future-Window Inverse Kinematics (FWIK), an online method that selects IK solutions by considering a small window of future waypoints. FWIK generates several IK candidates, connects them in a layered joint-space graph, and ranks candidate paths with a simple motion-time estimate. A learned model removes paths whose transitions are likely to cause self-collision. A standard MoveIt 2 planner then checks the next-waypoint IK goals from the remaining paths in ranked order, and the first goal that yields a valid trajectory is selected for execution. We evaluate FWIK in simulation on two 7-DoF manipulators, the Franka Emika Panda and the KUKA LBR iiwa. Each method-planner setting contains five repetitions of 100 sequences with 50 waypoints. Across Pilz, RRT-Connect, CHOMP, and STOMP, FWIK completes 96.8-100% of sequences and gives the shortest planned trajectory duration in all eight robot-planner settings. Its mean duration is 12.8-13.1% lower than STAMPEDE, 22.5-25.6% lower than IKLink, and 27.5-37.2% lower than retry-based TRAC-IK. The results show that a small future window can improve sequence completion and reduce planned motion time while leaving final trajectory validation to the motion planner.

0.17

A Hierarchical Coverage Path Planning Algorithm for Unknown Environments

cs.RO ·2026-09-11 ·Zongyuan Shen, Haodong Liu, Gao Wang, Hongbin Ma, Yaming Ou +2 more
similarity 0.59
Abstract

This paper presents an online coverage path planning algorithm for unknown environments. During navigation, the initially unknown search area is progressively decomposed into disconnected subareas as new obstacle information is acquired and coverage proceeds. These subareas are organized in an incrementally constructed decomposition tree that preserves their hierarchical parent-child relationships. Based on this tree, a global coverage tour is maintained and updated online by prioritizing newly generated child subareas according to their exploration states and distances from the robot. A local planner then generates coverage motions within each selected subarea, allowing the robot to adapt its trajectory as the environment is gradually revealed. Its performance is evaluated via high-fidelity simulations in complex scenarios. The results show improved coverage efficiency in terms of path length and overlap ratio in comparison to three baseline algorithms.

0.26

Rapidly-Iterating Grid-Based Near-Optimal Kinodynamic Motion Planning

cs.RO ·2026-09-19 ·Michael Moncton, Eric Frew
similarity 0.58
Abstract · Submitted to IEEE Transactions on Robotics

This paper develops the Rapidly-iterating kinoDynamic Grid (RDG) algorithm, an asymptotically near-optimal kinodynamic motion planning algorithm that produces high quality solutions through rapid iteration. The algorithm leverages a state space grid decomposition to perform node selection, dynamics propagation, and graph revision in constant time complexity with respect to the number of nodes in the trajectory tree. Through a covering ball sequence induction proof, the algorithm is shown to be asymptotically near-optimal and probabilistically complete. Different subsystems of the algorithm are evaluated against common nearest-neighbor search-based methods at generating exploration bias. The RDG algorithm is evaluated through simulated trials in complex, kinodynamic motion planning problem environments up to 10 DOF relative to similar sparse, kinodynamic planning algorithms with optimality guarantees, SST and DIRT. The RDG algorithm outperforms both SST and DIRT in mean final solution quality by up to 104% and 40% respectively. Additionally, RDG maintained a 100% success rate, even on a 10-DOF test case where both SST and DIRT did not.

0.17

dRVG: Quadtree-Guided, Resolution-Complete Online Motion Planning for Polygonal Robots in Unknown Environments

cs.RO ·2026-09-25 ·Duo Zhang, Hechen Zhang, Junshan Huang, Jingjin Yu
similarity 0.57
Abstract

We present the dynamic rotation-stacked visibility graph (dRVG), an online motion planner that guides polygonal robots to specified goals in initially unknown, static environ- ments. It merges local roadmaps from successive observations to plan collision-free translations and rotations without a uniform position grid. A spatial quadtree schedules sensing goals across regions to reduce repeated visits while retaining all orientation configurations for routing. Under exact sensing and geometric computation and star-shaped robot and envelope assumptions, dRVG with center scans is resolution-complete relative to full- map RVG at the same angular resolution. In experiments using footprint scans, dRVG solves all 140 cases across 20 difficult maps and seven angular resolutions within a 20 s planning budget, with a median planning time of 1.18 s at 360 orientation layers. Six microMVP demonstrations illustrate the complete online planning loop on a physical robot.

0.16

Real-Time Conformal-Seeded Hybrid Inverse Kinematics for Offset Redundant Manipulators

cs.RO eess.SY ·2026-10-03 ·Duc Cuong Vu, Van Tung Nguyen, Duc Hai Nguyen, Manh Cuong Nguyen, Vu Trung Tran +1 more
top venuetheory similarity 0.56
Abstract

This paper presents a conformal-seeded hybrid strategy for solving inverse kinematics of offset, redundant 7-DoF robot arms of the humanoid class. Analytical inverse kinematics (AIK) provides closed-form solutions with very low computational cost. However, for offset kinematic structures, the exact closed-form solution is generally unavailable, and practical AIK must rely on an approximate or simplified kinematic model. In contrast, numerical inverse kinematics (NIK) can achieve high-precision solutions on the full kinematic model. However, its convergence is highly sensitive to initialization. To overcome these limitations, we propose a two-stage hybrid inverse kinematics framework with conformal-calibrated seed selection. First, an approximate analytical model efficiently enumerates a finite set of candidate joint solutions. Second, we rank these candidates using a lightweight learned predictor of post-refinement difficulty, wrapped by split-conformal prediction into a calibrated upper bound that serves as the selection score. The best-ranked seed is then refined using a Levenberg-Marquardt solver on the full kinematic model. The proposed method combines fast candidate generation, learned seed ranking with a calibrated difficulty bound, and accurate numerical refinement, achieving real-time performance of less than 40us and a success rate of 100% in our evaluation on reachable targets. We validate the approach through large-scale stochastic simulation across the workspace and experimental demonstrations with motion planning on a humanoid robot arm. Demonstration videos are available at https://youtu.be/aeiBmw1XRbw.

0.50

Obstacle-Aware Autonomous Coverage and Navigation for Outdoor Robots

cs.RO ·2026-09-01 ·Leonardo Gargani, Matteo Frosi, Matteo Matteucci
similarity 0.55
Abstract

Long-duration outdoor coverage with autonomous platforms remains challenging beyond classical planning: deployments face localization drift in open spaces, obstacles in cluttered sites, controller feasibility in turn-heavy maneuvers, and persistent autonomy with energy management. We propose a unified ROS 2 architecture for single-robot outdoor coverage: a dual-antenna RTK-GNSS fused in an EKF keeps both position and heading accurate across long missions; three controller-aware refinements extend a mature coverage planner; a Nav2-based behavior-tree mission executive coordinates multi-goal execution, layered recovery, cost-aware goal management, and autonomous docking for return-to-charge. In real-world trials across five outdoor areas with varying geometries and obstacle densities, the robot completed every coverage route, sweeping 93.1% to 96.1% of the planned coverage area.

0.29

Distributed area coverage path planning subject to the inclusion of a headland path

cs.RO ·2026-10-11 ·Mogens Plessen
similarity 0.55
Abstract · 9 pages, 8 figures

A deterministic method for the problem of distributed area coverage path planning subject to the inclusion of a headland path is presented. Given a, in general, non-convex area to be covered that may, in general, include obstacle areas, multiple robots, at least one robot depot, and constraints on each machinery such as a working width, work capacity limits, travel capacity limits, nonholonomic dynamical constraints and, possibly, a robot start and end depot assignment, distributed paths for each machinery are calculated that collectively enable full area coverage. Variations are discussed, in particular, a scenario where unconstrained depots assignment can attain a global optimal solution to the problem. The importance of inclusion of a headland path for area coverage, as well as the benefits in comparison to an alternative Boustrophedon-pattern based approach are highlighted.

0.41