PaperlayerView exact revision on arXiv

Source-linked AI summary

Task Structure and Scalability in Multi-Robot Authoring

Christian Marowski, Byung-Cheol Min

arXiv:2610.22670v1cs.RO

TL;DR

The paper examines how task structure and allocation strategy affect the scaling benefit of adding robots to authoring work. It compares two allocation-routing pipelines on stroke graphs and finds stronger speedup scaling for shared-token allocation at larger teams, though it is not faster for every drawing.

  • Problem

    How task structure and allocation strategy affect the benefit of increasing robot team size remains an empirical question for multi-robot authoring.

    Source: §I · p. 1

  • Method

    The study compares component-level and shared-token allocation-routing pipelines across 385 stroke graphs and six robot-team sizes, with speedups normalized to each pipeline’s own single-robot baseline.

    Source: §I · p. 1, D. Performance Measures and Aggregation · p. 5

  • Results

    At eight robots, mean speedup was 2.426 for single-token allocation and 3.599 for shared-token allocation; shared-token was faster on 372 of 385 drawings, but not all.

    Source: A. Multi-Robot Scaling · p. 6, B. Allocation Strategy · p. 7

  • Takeaways & Limitations

    Structural descriptors are associated with differences in pipeline scaling, with total stroke length and component concentration producing the strongest separation.

    Source: §VI · p. 8

    Shared-token allocation does not reduce completion time for every drawing.

    Source: B. Allocation Strategy · p. 7

Abstract

from arXiv · show

Multi-robot authoring can reduce completion time by distributing drawing work, but the resulting speedup depends on task structure and the allocation-routing pipeline. We investigate these relationships by representing drawings as geometric stroke graphs and comparing component-level (single-token) allocation with shared-token (decomposed) allocation, which permits multiple robots to work within a connected component. A simulation study of 385 drawings and teams of one to eight robots shows diminishing speedup gains under single-token allocation and larger mean speedups under the shared-token pipeline, each normalized by its own single-robot completion time. Shared-token execution also exhibits lower idle-time shares at larger team sizes, although it does not reduce completion time for every drawing. Comparisons across structural attribute groups reveal associations between structural descriptors and differences in scaling behavior, with greater separation between several attribute groups at larger team sizes. These findings characterize empirical scaling in the evaluated pipelines and highlight the importance of considering within-component workload and graph structure alongside component count. Additional materials are available at https://sites.google.com/view/multirobotauthoring/home.

I. INTRODUCTION

The paper asks how task structure and allocation strategy affect the benefit of adding robots, comparing component-level and within-component work distribution. It situates this pipeline-level study among geometry-aware allocation and routing research.

I. INTRODUCTION

  • A stroke graph makes task structure explicit: single-token allocation assigns each connected component to one robot, while shared-token allocation distributes work within a component.The resulting concurrency interacts with route construction, non-drawing transit, and local robot interactions.Source: §I · p. 1, Figure 1 · p. 1
  • The study characterizes complete allocation-routing pipelines rather than isolating the causal effect of allocation granularity, because routing procedures also differ.It distinguishes direct completion-time gains from self-normalized scaling when relating performance to input structure.Source: §I · p. 1, §II · p. 2
  • The study compares component-level and shared-token allocation-routing pipelines across 385 stroke graphs and six robot-team sizes.It pairs completion-time analysis and robot-time accounting with descriptive analysis of associations between structural descriptors and scaling differences.Source: §I · p. 1

II. RELATED WORK

  • Prior work addresses geometry-aware decomposition and coordination in cooperative printing, while this study relates predefined stroke-graph descriptors to pipeline scaling across 2D drawings.Related coverage-planning methods divide area or grid work, whereas stroke authoring traverses specified drawing geometry and distinguishes drawing from non-drawing movement.Source: §II · p. 2

III. METHODOLOGY

The method represents planar vector strokes as a geometric graph with connected components, then assigns routes over required drawing edges. The input and completion definitions distinguish drawing work from transit and repeated traversal.

A. Input, Task Representation, and Scope

  • The input is a finite set of planar vector strokes or an equivalent geometric stroke graph; each stroke is a coordinate sequence describing a polyline.QuickDraw waypoints define consecutive vector segments, and detected crossings and self-crossings are inserted as vertices.Source: A. Input, Task Representation, and Scope · p. 2
  • The graph G = (V, E) is partitioned into connected components C(G), with K denoting component count and n denoting robot count.Each required edge stores a geometric path and length; intersection processing and coincident geometry affect graph topology and available component-level tasks.Source: A. Input, Task Representation, and Scope · p. 2
  • Each robot route includes drawable and non-drawing portions, while completion requires the required drawing edges to be reproduced.This is a coverage condition, not a requirement to traverse every edge exactly once; CPP augmentation may repeat edges, and depot access or movement between disconnected portions is non-drawing.Source: A. Input, Task Representation, and Scope · p. 2

B. Structural Descriptors

The structural descriptors cover workload, topology, and spatial layout. They summarize component count and stroke length, graph branching and cyclicity, and geometric dispersion and density.

B. Structural Descriptors

  • Workload descriptors are component count K, total required stroke length L, and component concentration CL.A high CL indicates that nominal work is concentrated within one component.Source: B. Structural Descriptors · p. 3
  • Cyclicity uses cycle rank μ, while branching B sums vertex degrees in excess of two.These descriptors characterize graph topology alongside workload.Source: B. Structural Descriptors · p. 3
  • Spatial dispersion is computed from unique original QuickDraw waypoints, and stroke density is among the spatial descriptors.Duplicate waypoint coordinates are counted once in D; ratios with zero denominators remain undefined rather than receiving artificial values.Source: B. Structural Descriptors · p. 3

C. Allocation and Nominal Routing

Token allocation assigns each connected component as an indivisible task, while shared-token allocation partitions a fixed traversal so multiple robots can work within a component. The shared-token route partition is exact for that traversal, not globally optimal routing.

1) Token allocation:

  • Each component goes to one robot, which selects its nearest vertex, follows a CPP circuit, and receives the next queued component when available.Component order follows the saved graph order rather than estimated workload or completion time.Source: 1) Token allocation · p. 3

2) Shared-token (decomposed) allocation:

  • Shared-token routing builds a CPP circuit per component, then concatenates them into a fixed master traversal using a greedy nearest-component rule.The component circuits use shortest-path augmentation of odd-degree vertices and minimum-weight matching.Source: 2) Shared-token (decomposed) allocation · p. 3
  • Dynamic programming partitions the fixed traversal contiguously across robots, allowing boundaries between edge traversals within a component but not inside a stored edge.The partition can use fewer than n robots when the traversal has fewer edge traversals than robots.Source: 2) Shared-token (decomposed) allocation · p. 3
  • The exact partition is not globally optimal min-max k-CPP routing, and nominal route balancing need not minimize executed completion time after avoidance and waiting.Token uses a dynamic component queue while Shared-token partitions a fixed master route, so their comparison is between complete pipelines.Source: 2) Shared-token (decomposed) allocation · p. 3

D. Reactive Execution and Interface Assumptions

Robots execute assigned routes with a local proximity-based yielding protocol that leaves high-level routes unchanged. The simulation does not establish formal collision avoidance, deadlock freedom, or minimum avoidance overhead.

Reactive execution

  • A local proximity rule detects conflicts using current center distance and a trigger distance set by the larger of the configured radius and a one-step closure bound.Robots are homogeneous discs moving at fixed speed in a fixed-timestep simulation.Source: D. Reactive Execution and Interface… · p. 3

Execution and workflow

  • The execution layer separates required drawing from non-drawing transit and serializes departures from the shared depot.Finished robots at the depot leave subsequent active-obstacle checks; the workflow executes routes with reactive yielding and updates coverage.Source: D. Reactive Execution and Interface… · pp. 3–4

Reactive execution

  • Conflict components are handled jointly; one robot receives priority based on drawing or movement state, remaining active-segment distance, then robot ID.Priority remains fixed while the local conflict persists.Source: D. Reactive Execution and Interface… · pp. 3–4
  • Yielding robots sidestep perpendicularly when feasible, otherwise wait; after the priority robot passes, they return to an anchor and resume their original traversal.The anchor records the point from which planned traversal will resume.Source: D. Reactive Execution and Interface… · p. 4

Interface assumptions

  • Avoidance leaves high-level routes unchanged and does not establish formal collision avoidance, deadlock freedom, or minimum avoidance overhead.Physical overlaps are recorded if they occur; physical deployment requires a compatible motion controller, drawing-state control, and localization.Source: D. Reactive Execution and Interface… · p. 4

IV. EXPERIMENTS

The experiments compare how speedup changes with robot count across two allocation-routing pipelines, when shared-token completes drawings faster, and which graph characteristics are associated with scaling differences.

A. Research Questions and Compared Pipelines

  • RQ1 asks how each allocation-routing pipeline’s speedup changes with robot count n.The comparison distinguishes Token (single-token/component-level) from Decomposed (shared-token/subgraph-level) allocation.Source: A. Research Questions and Compared… · p. 4
  • RQ2 asks which drawings and robot counts yield lower completion time for the shared-token pipeline than for the single-token pipeline.The routing policies are not assumed identical, so this is a pipeline-level comparison rather than an isolated allocation-granularity intervention.Source: A. Research Questions and Compared… · p. 4
  • RQ3 asks which stroke-graph characteristics are associated with differences in scaling behavior between the two pipelines.Source: A. Research Questions and Compared… · p. 4

B. Drawing Corpus and Preprocessing

The study evaluates a coverage-constrained sample of 385 Quick, Draw! drawings represented as geometric stroke graphs in a fixed-timestep simulator. Its results are bounded by the selected corpus and modeled execution setting.

B. Drawing Corpus and Preprocessing

  • The 385 Quick, Draw! drawings use simplified stroke waypoints, with detected intersections inserted as vertices and intersecting segments split.Geometry is preserved relative to the selected representation, not necessarily raw unsimplified trajectories.Source: B. Drawing Corpus and Preprocessing · p. 4
  • Coverage-constrained random sampling selects drawings to span variation in component count and other graph characteristics, limiting the empirical scope to this corpus rather than all vector-authoring inputs.The original corpus description reports at least one drawing from each object category.Source: B. Drawing Corpus and Preprocessing · pp. 4–5

C. Simulator and Experimental Configurations

  • The simulator uses homogeneous fixed-size, fixed-speed discs with waypoint-based displacement; low-level physical dynamics are omitted and transit is non-drawing.Source: C. Simulator and Experimental… · p. 5
  • Runs start from and return to a common depot; departures are serialized, and completion requires all drawing and return travel to finish.Staging waits count as avoidance time, while depot travel counts as transit.Source: C. Simulator and Experimental… · p. 5
  • Both pipelines run at six team sizes, N = {1, 2, 3, 4, 6, 8}, yielding 4,620 graph-count-pipeline configurations before repeated trials.No simulations timed out; geometric overlap occurred in 1,428 runs (30.9%) and increased at larger team sizes, so reactive conflict resolution is not a collision-free guarantee.Source: C. Simulator and Experimental… · p. 5

D. Performance Measures and Aggregation

The section defines completion-time, speedup, paired pipeline comparison, and robot-time measures, then explains how structural-group results are aggregated. Robot-time composition describes resource use rather than decomposing elapsed completion time.

D. Performance Measures and Aggregation

  • Completion time includes finishing all assigned drawing work and depot returns, while robot-time composition separately summarizes time spent drawing, moving, avoiding, and idling.The four robot-time categories are mutually exclusive, and their fractions are averaged per drawing; they are not an additive decomposition of elapsed completion time.Source: D. Performance Measures and Aggregation · p. 5
  • Each pipeline’s speedup is normalized by its own single-robot completion time for the same drawing, and the scaling curve averages per-drawing ratios.This is a mean of ratios, not a ratio of mean completion times.Source: D. Performance Measures and Aggregation · p. 5
  • The paired completion-time difference indicates which pipeline finishes faster: positive values favor shared-token, while negative values favor single-token.Its box plots summarize across-drawing variation, not repeated-run variability.Source: D. Performance Measures and Aggregation · p. 5
  • Structural attributes are ranked across the corpus and divided into low, medium, and high groups; tied values stay together, so group sizes may differ.All 385 drawings remain in each comparison, and sample-count-weighted group means reproduce aggregate mean ∆S.Source: D. Performance Measures and Aggregation · pp. 5–6

E. Physical Experimental Setup

The physical setup evaluates representative robot executions and compares their scaling with simulation for the same drawing. The results section is organized around scaling, direct completion-time differences, and structural variation.

E. Physical Experimental Setup

  • One representative airplane drawing was tested with one, two, and three HamsterS robots; physical dimensions and interaction distances were not scaled proportionally to simulation.Robots began at individual staging positions, and completion time ended when all returned to their staging positions.Source: E. Physical Experimental Setup · p. 6
  • A representative three-robot trial is shown, and physical speedups are compared with simulation results for the same drawing.Representative robot executions are also shown in the supplementary video.Source: E. Physical Experimental Setup · p. 6

V. RESULTS

  • The results compare speedup across robot counts, paired completion-time differences, and variation in within-pipeline speedup across structural attribute levels.Figures 4 and 5 present mean per-drawing speedup relative to each pipeline’s own single-robot time and paired relative completion-time differences, respectively.Source: §V · p. 6, Figure 4 · p. 6, Figure 5 · p. 6

A. Multi-Robot Scaling

Across the evaluated team sizes, both allocation-routing pipelines gain speedup, but single-token gains diminish while shared-token scaling remains stronger at larger teams. Robot-time composition and structural-group comparisons further show that utilization and scaling differences vary with allocation strategy and drawing structure.

A. Multi-Robot Scaling

  • At eight robots, mean speedup is 2.426 for the single-token pipeline and 3.599 for the shared-token pipeline, with single-token gains diminishing as team size grows.Both pipelines’ mean per-drawing speedups increase over the evaluated robot counts, but the separation is greatest at larger teams.Source: A. Multi-Robot Scaling · p. 6
  • Component count and unequal component workloads can limit simultaneous drawing under single-token allocation, whereas shared-token allocation permits robots to share work within a component.Across several structural descriptors, group-mean differences become more pronounced at larger team sizes; these patterns motivate considering workload distribution and graph topology alongside component count.Source: A. Multi-Robot Scaling · p. 6, C. Structural Characteristics · p. 7

B. Allocation Strategy

  • At eight robots, the median relative completion-time difference is 33.67%; shared-token finishes 372 drawings faster, while single-token finishes 13 faster, with no ties.The distribution becomes more dispersed as robot count increases, so the aggregate shared-token advantage is not universal across drawings.Source: B. Allocation Strategy · p. 7
  • At eight robots, mean per-drawing idle-time share is 49.65% under single-token allocation and 9.80% under shared-token allocation.Figs. 6 and 7 show robot-time compositions as normalized shares; larger movement or avoidance fractions do not establish larger absolute durations.Source: B. Allocation Strategy · p. 7, Figure 6 · p. 7, Figure 7 · p. 7

C. Structural Characteristics

  • At eight robots, high-minus-low mean ∆S contrast is 1.225 for component concentration, 1.108 for total stroke length, and 0.090 for spatial dispersion.High branching, cyclicity, and stroke-density groups also show larger mean ∆S than their low groups as robot count increases; Fig. 8 summarizes these group comparisons.Source: C. Structural Characteristics · p. 7, Figure 8 · p. 7

D. Physical Validation

Physical experiments on a selected airplane drawing showed the same qualitative scaling trend as simulation. The paper concludes that its findings characterize the evaluated pipelines and that simulation runs with geometric robot overlap are not collision-free completion-time measurements.

D. Physical Validation

  • For the selected airplane drawing, physical experiments showed the same qualitative scaling trend as simulation: Token gains leveled off after two robots, while Decomposed continued scaling through three.The denser physical setting provides additional context for the reduced speedup at three robots; Table II compares simulated and physical speedup.Source: D. Physical Validation · p. 8, Table II · p. 8

VI. CONCLUSION

  • The study characterizes evaluated allocation-routing pipelines rather than isolating decomposition’s causal effect, and simulated runs include geometric robot overlap.The conclusion highlights considering within-component workload and graph structure when selecting a pipeline and team size; overlapped simulation runs should not be read as collision-free completion-time measurements.Source: §VI · p. 8
Loading 2610.22670v1…