PaperlayerView exact revision on arXiv

Source-linked AI summary

Coverage Path Planning for Redundant Manipulators using Generalized Spanning Trees

Raksi Kopo, Kostas J. Kyriakopoulos

arXiv:2609.08409v1cs.RO

TL;DR

Surface coverage with task-redundant manipulators must select among multiple IK solutions while managing motion quality, and existing approaches leave online coverage in this setting unaddressed. The paper extends STC with offline and online JSTC, using a GMST formulation offline and incremental tree expansion and backtracking online. Simulations report improved computation time and motion quality over GTSP-based baselines offline, and low per-step computation across obstacle and update scenarios online.

  • Problem

    Task-redundant surface coverage involves multiple possible IK solutions per point, while existing manipulator methods primarily target offline settings and no prior method is identified for online coverage that accounts for those alternatives.

    Source: §I · p. 1, B. CPP methods for surface coverage… · p. 2

  • Method

    Offline JSTC selects IK solutions through a GMST formulation and traces the resulting tree, while online JSTC incrementally expands and backtracks a tree as the surface graph changes.

    Source: §I · p. 1, §IV · p. 4

  • Results

    Simulations report that offline JSTC improves computational time and motion quality over GTSP-based baselines, while online JSTC has low per-step computation across obstacle and update scenarios.

    Source: §VI · p. 7

  • Takeaways & Limitations

    The simulations support JSTC for coverage in both offline settings and online scenarios involving obstacles or graph updates.

    Source: §VI · p. 7

    Experimental validation and extension to curved surfaces remain future work.

    Source: §VI · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Surface coverage with task-redundant manipulators must choose among multiple IK configurations while maintaining motion quality; online coverage also needs to accommodate partially known or changing environments. The section introduces JSTC as an extension of STC and situates it alongside existing coverage methods.

I. INTRODUCTION

  • Multiple IK solutions may exist for each surface point, and the configuration choice strongly affects motion quality; dynamic or partially known settings require online coverage.Source: §I · p. 1
  • STC builds a grid spanning tree and traces its sub-cells to produce a non-revisiting tour; its online version constructs the tree with DFS in O(N) time.Source: §I · p. 1
  • The paper extends STC to redundant manipulators with offline and online JSTC; its offline formulation is identified as a Generalized Minimum Spanning Tree problem.Source: §I · p. 1

II. LITERATURE REVIEW

  • CPP spans varied applications, robot types, environments, and objectives, including energy use, turns, overlap, and manipulator reconfigurations.Source: §II · p. 1

A. Online 2D CPP methods

  • Online CPP methods address environments that are gradually discovered or change over time, using approaches such as random walks, decomposition, and incremental replanning.Source: A. Online 2D CPP methods · p. 2

B. CPP methods for surface coverage with manipulators

Manipulator surface coverage requires connecting IK choices across surface points while avoiding costly reconfigurations. The section identifies a gap in online methods for task-redundant manipulators and presents offline and online JSTC as contributions addressing it.

B. CPP methods for surface coverage with manipulators

III. OFFLINE JSTC

This section formalizes offline coverage for known surfaces and presents the offline JSTC algorithm, with its steps illustrated in Fig. 1.

III. OFFLINE JSTC

  • The section addresses offline coverage on known surfaces and presents the offline JSTC algorithm.Source: §III · p. 2
  • Fig. 1 illustrates the offline JSTC algorithm.Source: §III · p. 2
  • The algorithm is introduced through an illustrative diagram.Source: §III · p. 2

A. Problem Formulation

The formulation represents a surface as a grid of mega-cells and sub-cells and defines coverage through tool poses and IK solutions. It also specifies reconfiguration criteria and the path objective of visiting each sub-cell once with low joint motion and few reconfigurations.

A. Problem Formulation

  • The tool’s coverage-effective pose is represented by its position and axis direction, and the task leaves rotation about the tool axis free.Source: A. Problem Formulation · p. 2
  • The surface grid uses four-neighbor connectivity, with each mega-cell divided into four equal sub-cells.Source: A. Problem Formulation · p. 2
  • A configuration is an IK solution when its tool pose matches a cell’s coverage target; the manipulator is task-redundant for this task when k > 5.Source: A. Problem Formulation · pp. 2–3
  • Fig. 1 depicts mega-cell IK solutions in red and sub-cell IK solutions in green, and illustrates offline steps and online tree updates.Source: Figure 1 · p. 3
  • The coverage path visits each sub-cell once using an IK solution, aiming for low joint motion and few reconfigurations.Source: A. Problem Formulation · p. 3
  • A transition is defined as a reconfiguration when its endpoints are not neighboring cells or when it meets either of the stated joint-motion or tool-deviation conditions.Source: A. Problem Formulation · p. 3

B. Offline JSTC Algorithm

Offline JSTC samples and propagates IK solutions, selects a low-cost tree over mega-cells, and traces its sub-cells to form a configuration-space coverage path.

B. Offline JSTC Algorithm

  • Offline JSTC samples IK solutions for mega-cells, propagates them to four sub-cells, and removes any mega-cell with no solution that propagates to all four.IK sampling uses joint-limit seeds and an optimization-based solver.Source: B. Offline JSTC Algorithm · pp. 3–4
  • The generalized graph clusters feasible IK solutions by mega-cell and connects solutions of neighboring mega-cells; GMSTP selects a tree with one IK solution per mega-cell.The edge-weight formulation includes a large positive penalty for reconfigurations between neighboring mega-cells.Source: B. Offline JSTC Algorithm · p. 4
  • Sub-cell tracing follows admissible moves around the selected tree without crossing its edges, using propagated IK solutions for the resulting path.A move between mega-cells is allowed only when their mega-cells share a selected tree edge.Source: B. Offline JSTC Algorithm · p. 4

IV. ONLINE JSTC

Online JSTC addresses partially known or changing surface graphs by updating its coverage forest and constructing the generalized spanning tree and sub-cell path during execution.

IV. ONLINE JSTC

  • At each planning step, graph updates add newly discovered mega-cells or remove regions no longer available or required for coverage.Source: §IV · p. 4
  • The online goal is to cover every sub-cell of each reachable mega-cell that remains in the updated graph, rather than assume a fixed graph in advance.Source: §IV · p. 4
  • The algorithm maintains a forest whose trees correspond to connected graph components and store tree edges, mega-cell and sub-cell IK solutions, and visited sub-cell order.Each tree is rooted at its initialization mega-cell, with parent relations used during backtracking.Source: §IV · pp. 4–5
  • If the robot is outside an unfinished tree, the nearest unfinished tree is selected and RRT-Connect connects the robot configuration to it.Source: §IV · p. 5

B. Online JSTC Algorithm

Online JSTC grows trees through feasible extensions and backtracks when extension fails, while incorporating graph updates and choosing low-cost transitions.

B. Online JSTC Algorithm

  • Helper operations propagate a mega-cell IK solution to its sub-cells, check whether unvisited sub-cells remain connected, and append stored IK solutions along a path.A reconfiguration transition is planned using RRT-Connect.Source: B. Online JSTC Algorithm · p. 5
  • The procedure initializes a tree from the robot’s current mega-cell and sub-cell, then alternates extension and backtracking until the forest’s trees are finished.When another tree is not directly reachable through the coverage graph, RRT-Connect connects the robot to it.Source: B. Online JSTC Algorithm · p. 5
  • After each iteration, removed mega-cells are deleted from trees; disconnected unfinished components become separate trees, and feasible uncovered components receive new trees.Source: B. Online JSTC Algorithm · p. 5
  • Extension tries a neighboring mega-cell, propagates an IK solution, and forms a tree edge only if propagation succeeds; valid paths must preserve connectivity of remaining unvisited sub-cells.Among valid extensions, the algorithm selects the one with the lowest transition cost.Source: B. Online JSTC Algorithm · p. 5
  • When no valid extension exists, backtracking traces admissible unvisited sub-cells to the parent mega-cell, or visits the root’s remaining sub-cells and finishes that tree.Source: B. Online JSTC Algorithm · p. 5

V. SIMULATIONS

The simulations compare offline JSTC with JGTSP and HJGTSP on Scan Floor and test online JSTC in five table-cleaning scenarios.

V. SIMULATIONS

  • Offline JSTC is compared with JGTSP and HJGTSP on the Scan Floor benchmark, where a Franka Emika Panda with a handheld detector scans for potential chemical or radioactive leaks.GLKH is used to solve the GTSPs associated with JGTSP and HJGTSP.Source: §V · pp. 5–6
  • Online JSTC is tested on an 8 × 8 table grid with a 7 DoF KUKA LBR iiwa in five cases: free grid, external obstacle, internal obstacles, disconnected graph, and removed tree mega-cells.Source: §V · p. 6
  • All methods are tested on a laptop with an Intel Core i9-11900H processor at 2.50 GHz and 32 GB RAM.Source: §V · p. 6

A. Offline JSTC test results

Offline JSTC outperforms JGTSP in computation time, reconfigurations, and total joint motion. HJGTSP reduces computation time through a smaller representative set, but its reduced representativeness can increase joint motion.

A. Offline JSTC test results

  • Offline JSTC outperforms JGTSP in computation time, number of reconfigurations, and total joint motion.The comparison averages 10 runs to account for randomness in IK sampling.Source: A. Offline JSTC test results · p. 6
  • JSTC solves a GMST over 179·m nodes, compared with JGTSP's graph of up to 674·m nodes, helping explain its computation-time advantage.The passage attributes JGTSP's weaker reconfiguration and joint-motion performance to heuristic-solver performance deteriorating with larger graphs.Source: A. Offline JSTC test results · p. 6
  • HJGTSP uses 24 exemplars to reduce computation time, but reduced representativeness can yield higher total joint motion than JSTC.JSTC uses a denser higher-level discretization of 179 mega-cells.Source: A. Offline JSTC test results · p. 6
  • JSTC produces horizontal and vertical path segments, whereas mesh-based GTSP methods may use diagonal edges and sharper turns.Source: A. Offline JSTC test results · p. 6

B. Online JSTC test results

Online JSTC was tested on free, obstacle, disconnected-grid, and grid-update cases. Extension and backtracking steps took less than 70 ms on average, and update processing was also reported as low.

B. Online JSTC test results

  • The tests covered workspace-limited and collision-blocked cells, connected and disconnected internal-obstacle grids, and a row-removal update that split the tree and path.The robot completed paths for the resulting components using remaining unvisited mega-cells.Source: B. Online JSTC test results · p. 6
  • Average extension-step and backtracking-step computation times were below 70 ms across all five cases.The authors report low computation time for grid, tree, and path updates in the fifth case.Source: B. Online JSTC test results · p. 7
  • Average joint displacement per step was described as acceptable, although online JSTC optimizes joint motion locally rather than globally.Offline JSTC and JGTSP optimize joint motion globally.Source: B. Online JSTC test results · p. 7

VI. CONCLUSION

The paper presents offline and online JSTC for surface coverage with task-redundant manipulators. Simulations report improved computation time and motion quality for offline JSTC over GTSP-based baselines, and low per-step computation for online JSTC.

VI. CONCLUSION

  • Offline JSTC selects one IK solution per mega-cell through a GMST formulation and traces the tree into a non-revisiting sub-cell coverage path.Source: §VI · p. 7
  • The illustrated online cases include connected and disconnected grids with internal obstacles, using transitions between trees spanning disconnected components.Source: Figure 4 · p. 7
  • Simulations show offline JSTC improves computation time and motion quality over GTSP-based baselines, while online JSTC achieves low per-step computation.Source: §VI · p. 7
  • Online JSTC incrementally extends and backtracks the tree while handling dynamic graph updates.Source: §VI · p. 7
Loading 2609.08409v1…