Task Structure and Scalability in Multi-Robot Authoring

ICRA 2027

Abstract

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) al-location, 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.

Image Representation

Example input from the Google Quick, Draw! dataset is represented as vector strokes and converted into a graph of drawable segments and connected components. This graph representation lets us compare how different multi-robot allocation strategies divide the same drawing task. We evaluate both multi-robot component-level allocation and finer shared-token decomposition pipelines across different team sizes.

Research Questions

RQ1 How does each allocation-routing pipeline’s speedup change with robot count n?

RQ2 For which drawings and robot counts does the shared-token pipeline achieve a lower completion time than the single-token pipeline?

RQ3 Which stroke-graph characteristics are associated with differences in scaling behavior between the two pipelines?

Single-Token

Each connected component is an allocatble task. Only one robot is responsible for drawing the entire component.

Shared-Token

Connected components are split by their predefined stroke geometry. Each edge represents a drawable segment between two vertices. These segments are then allocated across robots using the min-max CPP algorithm.

Experiments

Simulator

Robot Count: 3

Method: Shared Token

Speed: 5x

Physical

Robot Count: 3

Method: Shared Token

Speed: 10x

Simulator

Robot Count: 3

Method: Shared Token

Speed: 5x

Physical

Robot Count: 3

Method: Shared Token

Speed: 10x.5

Results

Mean drawing speedup as robot count increases.

Relative completion-time difference between the two methods. Positive values indicate faster completion with decomposition, with the advantage generally increasing at larger team sizes.

Mean decomposition advantage across low, medium, and high levels of six drawing attributes.

Key Takeaways

Both allocation methods benefit from additional robots, but the gains from component-level allocation begin to plateau as team size increases.
Shared-token allocation exposes additional parallelism by allowing work within the same connected component to be divided across robots.
Task structure strongly affects scalability. Total stroke length and connected-component concentration produced the clearest differences between allocation methods.
Finer decomposition is most valuable when workload is concentrated. When connected components are already balanced, both approaches can perform similarly.

The Multi-Robot Scaling results show that both allocation-routing methods benefit from additional robots, but their scaling behavior diverges as team size increases. Token allocation exhibits progressively stronger diminishing returns, while decomposed allocation continues to achieve larger gains at higher robot counts. The Relative Completion-Time Difference results reinforce this trend: decomposed allocation is faster for most drawings at larger team sizes, although the wide distributions show that the advantage is not universal and depends on the input drawing.

The Structural Attribute Analysis helps explain this task dependence. Total stroke length and connected-component concentration show the strongest separation in decomposition advantage, followed by branching and cyclicity, while stroke density shows a smaller effect and spatial dispersion the weakest. Together, these results suggest that scaling differences are associated more strongly with workload distribution and graph structure than with the spatial spread of the drawing.

Google Sites

Report abuse