PaperlayerView exact revision on arXiv

Source-linked AI summary

Embedded Evaluation of Task Admission Coalescing in Decentralized Multi-Robot Systems

James Lott, Vahraz Honary

arXiv:2610.09187v1cs.RO

TL;DR

Online task releases can repeatedly update decentralized coordination while robots are already executing, and prior fixed-task studies did not examine that setting. This paper evaluates task-admission coalescing across decentralized allocators and execution platforms; work savings vary with arrival load, allocator behavior, and platform, while sparse batching can add substantial waiting latency.

  • Problem

    Online allocators must incorporate tasks released during ongoing execution, but prior fixed-task studies did not examine online releases, admission waiting, or computation-driven mission-time feedback.

    Source: §I · p. 1

  • Method

    A task-admission layer controls when released tasks become visible to four allocators, evaluated across policies and arrival loads on AGX Orin and RP2040 platforms.

    Source: §I · pp. 1–2

  • Results

    Coalescing lowers allocator work in most evaluated conditions, but sparse Count b = 4 raises online-target mean latency by 20.08–23.57 s, mainly through admission waiting.

    Source: A. Coalescing Tradeoff Across Arrival… · p. 4, §V · p. 7

  • Takeaways & Limitations

    The tradeoff depends on arrival intensity, allocator behavior, and platform; medium-arrival RP2040 HIPC Count b = 4 reduced mean work by 59.85% and service latency by 39.47%.

    Source: §V · p. 7

    Measured operating regions apply to four robots, exponential arrivals, lossless communication, and the evaluated implementations; hardware tests allocator execution within simulated missions rather than physical robot motion.

    Source: D. Generality and Deployment… · p. 7

Abstract

from arXiv · show

Multi-robot task allocators in dynamic missions commonly admit newly released tasks immediately, potentially invoking allocation for each new arrival. We evaluate task-admission coalescing as a mechanism for controlling allocator processor work while accounting for target-service latency, using CBAA, ACBBA, PI, and HIPC as a representative MRTA suite. The study comprises a 3,000-mission AGX Orin campaign with measured computation delay, 3,000 paired zero-compute missions, and a 96-mission Pololu 3pi+ RP2040 allocator hardware-in-the-loop campaign. Immediate (Eager) admission is compared with thresholds of two, four, and eight tasks and a four-task policy with a 10-s waiting bound across three arrival rates. Across the AGX experiments, coalescing reduces both allocator calls and processor work in 31 of 48 evaluated conditions, although the magnitude of the saving varies by allocator. The principal cost appears under sparse arrivals, where four-task batching increases online-target mean latency by 20.08-23.57 s, predominantly through admission waiting. Bounded admission reduces mean work in ten of twelve allocator-load conditions, including a 19.35% reduction with a 1.40-s mean latency increase for high-arrival HIPC. RP2040 experiments show that this tradeoff can become more favorable as processor constraints tighten. Across four matched medium-arrival HIPC scenarios, Count b=4 reduces mean RP2040 work by 59.85% and service latency by 39.47%, while the corresponding AGX cases increase latency by 27.69%. These results show that the usefulness of task-admission coalescing depends on arrival intensity, allocator-specific behavior, and the relative cost of computation on the execution platform.

I. INTRODUCTION

New tasks arriving during execution can repeatedly update decentralized coordination. This study evaluates whether controlling when released tasks become visible to allocators can moderate computation without excessive target-service delay.

I. INTRODUCTION

  • Prior approaches reduce repeated-update costs through replanning limits, retained information, suppressed broadcasts, or event-triggered negotiation,, [5],,.These approaches address computational and communication burdens of responding to dynamic information.Source: §I · p. 1
  • A task-admission layer controls when already released tasks become visible to allocators, trading pre-allocation waiting against computational activity after admission.The outcome depends on more than admission frequency because robots continue processing consensus information, repairing allocation state, and selecting work between admissions.Source: §I · p. 1
  • Studies [10] and [11] evaluated fixed sets of known targets; neither considered tasks released during execution, waiting before allocator admission, or feedback from allocator computation consuming mission time.Related robotic-routing and warehouse-batching studies show that delaying accumulated work before downstream decisions can be useful, but do not address decentralized MRTA with ongoing coordination and execution,.Source: §I · pp. 1–2
  • The study characterizes admission coalescing across four decentralized MRTA mechanisms, five policies, and three arrival loads, measuring processor work and target-service latency.It also examines how admission waiting, allocator-call frequency, and per-call work shape the tradeoff, and compares AGX with RP2040 execution.Source: §I · p. 2

II. SYSTEM DESIGN AND ADMISSION POLICIES

The study adapts the Collaborative Visit benchmark to tasks released during execution, with task availability controlled separately from decentralized assignment and visit-order decisions.

A. Dynamic Collaborative Visit

  • The dynamic benchmark extends fixed-task Collaborative Visit [10] to four robots visiting 50 task cells, with eight tasks released initially and 42 released online.Release makes a task available to the admission policy; admission announces its location, and a robot with local knowledge completes it by searching the cell.Source: A. Dynamic Collaborative Visit · p. 2
  • Tasks crossed before a robot learns their admission do not count as completed.Completion requires searching the task cell after its location becomes locally known.Source: A. Dynamic Collaborative Visit · p. 2
  • Each robot maintains its own task knowledge, allocation state, and received peer information; the environment records releases and physical completions without selecting assignments.A common robot shell provides A* routing, movement, and communication, separating task-availability timing from decentralized ownership and visit-order decisions.Source: A. Dynamic Collaborative Visit · p. 2

B. Admission Policies

Admission policies determine when pending tasks enter allocator visibility; the allocator suite and execution architecture then govern how robots process admitted work and computational delay.

B. Admission Policies

  • Eager admits each online task immediately; Count admits batches of 2, 4, or 8, while Bounded uses batches of 4 or admits the remainder after a 10-s wait.A terminal rule admits a remaining batch only after no future release remains and previously admitted tasks are completed; the deadline limits queue residence, not later allocation or service time.Source: B. Admission Policies · p. 2

C. MRTA Allocator Suite

  • The suite pairs CBAA, ACBBA, PI, and HIPC with common Manhattan-distance costs and allocator-specific state repair and consensus behavior.Allocator calls can also follow consensus information, completion, invalidation, or local recovery; robots without actionable information sleep rather than poll.Source: C. MRTA Allocator Suite · p. 2

D. Execution Architecture

  • Measured allocator durations delay the calling robot’s virtual processor, while peer activity, releases, and message deliveries continue on the event clock.The zero-compute arm inserts no virtual computation time and recomputes decisions from evolving state rather than replaying causal-arm decisions; Fig. 1 depicts the admission and execution boundaries.Source: D. Execution Architecture · pp. 2–3, Figure 1 · p. 3

III. EXPERIMENTAL METHODOLOGY

The evaluation uses shared scenario inputs across loads, policies, allocators, and timing arms, with AGX Orin campaigns and a smaller RP2040 hardware-in-the-loop subset.

A. Workloads and Campaign Design

  • Task cells are sampled uniformly without replacement from the 357 non-start cells, and traversal and turning durations are modeled using testbed measurements.Cardinal traversal is 1.60 ± 0.10 s, quarter turns 0.30 s, and messages are delivered at 40 ms in simulations.Source: A. Workloads and Campaign Design · p. 3
  • Online releases use 42 independent unit-exponential increments, with low, medium, and high rates of 0.075, 0.30, and 0.60 tasks/s.Spatial layouts and arrival increments are shared across loads, and each scenario is reused across policies, allocators, and timing arms.Source: A. Workloads and Campaign Design · p. 3
  • The AGX design crosses four allocators, three arrival loads, five policies, and 50 scenarios, producing 3,000 missions per timing arm; the RP2040 subset contains 96 missions.The RP2040 subset uses the first four scenario blocks and compares Eager with Count b = 4.Source: A. Workloads and Campaign Design · p. 3, Table I · p. 3
  • Sixty causal terminations hit finite limits: 59 ACBBA stagnation limits and one HIPC total-event limit.Runs terminate on completion or at specified event limits.Source: A. Workloads and Campaign Design · p. 3

B. Platforms and Allocator Measurement

The study measures allocator execution on both AGX Orin and RP2040 platforms, with the timed boundary including selected allocation and control operations while excluding simulation and transport work.

B. Platforms and Allocator Measurement

  • AGX measurements use CPython 3.10.12 on Linux/aarch64 with five concurrent simulation workers.The host retains world state, routing, motion, and message scheduling.Source: B. Platforms and Allocator Measurement · p. 3
  • Four Pololu 3pi+ 2040 boards execute native MicroPython allocator transactions, one simulated four-robot mission at a time.The host restores robot checkpoints before calls; the boards measure allocator execution without physical robot movement.Source: B. Platforms and Allocator Measurement · p. 3
  • The timed boundary includes admission, consensus and completion callbacks, requested recovery, and goal selection or route repair, but excludes transport, routing, and motion.Garbage collection triggered inside a transaction is included; calls may run serially for measurement while durations are assigned to independent virtual robot processors.Source: B. Platforms and Allocator Measurement · p. 3

C. Outcomes and Paired Analysis

Outcomes distinguish accumulated allocator work from mission delay and measure target service from release to first completion. Policy contrasts use common paired cohorts, with AGX uncertainty estimated by scenario bootstrap.

C. Outcomes and Paired Analysis

  • Total allocator processor work sums measured durations of valid allocator transactions, while invocation count records the number of transactions.Work includes full dispatched transactions even when virtual completion extends beyond the final task completion; it is not mission delay or total onboard computation.Source: C. Outcomes and Paired Analysis · p. 3
  • Target service latency is measured from release to first completion, with online-target latency separately averaging only the 42 online targets.Release-to-admission waiting and post-admission time decompose online-target service latency.Source: C. Outcomes and Paired Analysis · p. 3
  • Policy comparisons use scenarios completed under both policy and Eager within the same allocator, load, and platform, reporting paired absolute differences and percentage changes.Planned and completed counts remain separately visible.Source: C. Outcomes and Paired Analysis · p. 4
  • AGX uncertainty uses 10,000 shared scenario-bootstrap resamples with percentile 95% pointwise intervals, while hardware summaries show matched pairs descriptively.The intervals describe individual contrasts rather than simultaneous coverage across the matrix; selected examples are explanatory, not held-out validation.Source: C. Outcomes and Paired Analysis · p. 4
  • The within-scenario accounting identity separates call-count and per-call-work contributions before averaging.Supporting checks use zero-compute call counts and latency over the first 40 online tasks to examine timing feedback and terminal-remainder effects.Source: C. Outcomes and Paired Analysis · p. 4

IV. RESULTS AND DISCUSSION

AGX results show that coalescing can reduce computation while increasing service latency, but its workload and latency effects vary with arrival rate and allocator. A waiting bound can limit delay while retaining some work savings.

A. Coalescing Tradeoff Across Arrival Loads

  • 30 of 48 comparisons reduce both allocator calls and processor work while increasing mean service latency; 11 instead increase calls and work despite fewer admission epochs.These are observed mean-effect directions, with uncertainty shown for each contrast.Source: A. Coalescing Tradeoff Across Arrival… · p. 4
  • For the same Count b = 4 policy, CBAA work falls by 29.39% under low arrivals but rises by 22.82% under high arrivals.Count thresholds generally increase delay, but not consistently work savings; the eight-task threshold has the largest sparse-arrival latency penalty in every allocator row.Source: A. Coalescing Tradeoff Across Arrival… · p. 4
  • At 0.075 tasks/s, Count b = 4 increases online-target mean service latency by 20.08–23.57 s across the suite, with 83.3–96.7% attributable to release-to-admission waiting.The mean admission wait over the first 40 online targets is 19.51 s, close to the 20 s expected from the arrival process and policy.Source: A. Coalescing Tradeoff Across Arrival… · p. 4
  • Bounded admission lowers mean work in ten of twelve allocator–load conditions, while mean service latency increases in all twelve.For high-load HIPC, it reduces work by 19.35% with a 4.34% latency increase, versus Count b = 8's 25.32% work reduction and 20.93% latency increase.Source: A. Coalescing Tradeoff Across Arrival… · p. 4
  • The resulting operating regions depend jointly on admission waiting and the allocator workload generated after admission.The analysis next examines workload sources and how embedded execution shifts the tradeoff.Source: A. Coalescing Tradeoff Across Arrival… · p. 4

B. Sources of Computational Savings

The computational effects of coalescing reflect both call frequency and per-call work, and the same reduction in admission epochs can accompany different workload outcomes.

B. Sources of Computational Savings

  • Fig. 2 plots allocator-work change against mean target service-latency change relative to Eager, with arrival loads in columns and allocators in rows.Leftward indicates lower work and upward indicates greater latency; the latency scales differ between columns.Source: Figure 2 · p. 5
  • Both high-arrival comparisons reduce admission epochs by approximately 72%, but one reduces execution workload while the other increases it.This contrast shows that admission frequency alone does not determine the computational response.Source: B. Sources of Computational Savings · pp. 4–5
  • Bounded admission reduces HIPC allocator work by 19.35%, with reductions on 38 of 50 paired traces; 84.5% of mean savings is attributed to the call-count term.Mean target-service latency increases by 1.40 s, while mean per-call work changes only slightly.Source: B. Sources of Computational Savings · p. 5
  • Count b = 4 with CBAA increases total work by 22.82%, as calls rise by 7.43% and mean per-call work rises by 14.20%.Mean target-service latency rises by 4.21 s; the per-call term accounts for the larger share of added work.Source: B. Sources of Computational Savings · p. 5

C. Embedded Execution

Embedded execution shows that coalescing’s work–latency tradeoff varies across platforms, allocators, and arrival loads. Medium-arrival HIPC improves on both measures on RP2040, unlike the matched AGX cases.

C. Embedded Execution

  • The RP2040 comparison evaluates Count b = 4 against Eager across all four allocators and three arrival loads.The test asks whether tighter processor constraints make work savings sufficient to offset batching delay and improve target service.Source: C. Embedded Execution · p. 5
  • On four matched medium-arrival HIPC scenarios, Count b = 4 reduced RP2040 mean allocator work by 59.85% and mean target-service latency by 39.47%, while AGX latency increased 27.69%.The RP2040 work change was from 353.31 to 141.85 processor-seconds; the AGX comparison showed a 7.79% work decrease.Source: Figure 3 · p. 6, C. Embedded Execution · p. 6
  • Across the RP2040 matrix, low-load batching increased target-service latency for every allocator, while joint work and latency reductions appeared in selected medium- and high-load conditions.The campaign retained 38 complete Eager–Count pairs from 48 planned blocks.Source: C. Embedded Execution · p. 6
  • RP2040 outcomes varied by allocator and load: PI improved on both measures at high load, while CBAA lacked the same favorable region at medium or high load.HIPC’s mean work increased by 7.39% at high load; ACBBA’s medium-load joint reduction came from only two complete pairs, with possible execution-failure bias.Source: C. Embedded Execution · p. 6

D. Generality and Deployment Implications

The zero-compute comparison largely preserves allocator call-count response, and the principal latency effects persist when analysis excludes the final residual targets. The measured operating regions remain bounded by the evaluated mission and implementation settings.

D. Generality and Deployment Implications

  • Call-count change direction matched between causal and zero-compute runs in 43 of 48 contrasts; coalescing reduced calls in 36 causal and 31 zero-compute contrasts.Five reversals had causal mean changes of only 0.37–4.22%, consistent with computation-delay feedback shifting conditions near the boundary between increased and reduced allocator activity.Source: D. Generality and Deployment… · p. 6
  • Analyzing only the first 40 online targets preserved the principal latency effects, including sparse-arrival penalties, after removing the final residual from comparison.The results therefore reflect the admission mechanism rather than the terminal residual alone.Source: D. Generality and Deployment… · p. 6
  • Coalescing is most beneficial when it meaningfully reduces downstream allocator activity without introducing excessive admission waiting.The computational reduction becomes more consequential as allocator execution occupies a larger fraction of mission time.Source: D. Generality and Deployment… · p. 7
  • The measured operating regions cover four robots, exponential arrivals, lossless communication, and the evaluated implementations; other team sizes, communication conditions, arrival structures, and hardware remain to be tested.Hardware results measure allocator execution within simulated missions rather than physical robot motion.Source: D. Generality and Deployment… · p. 7

V. CONCLUSION

The conclusion finds that admission coalescing usually reduces allocator work, but its value depends on allocator response, arrival conditions, and platform. Embedded HIPC results show that the same policy can reduce both work and service latency on RP2040 while increasing latency on AGX.

V. CONCLUSION

  • Across four allocators, coalescing lowers allocator work in most evaluated conditions, but savings depend on allocator response after admission, not admission count alone.The direction of call-count response was unchanged in 43 of 48 contrasts when computation was removed from simulated time.Source: §V · p. 7
  • For high-arrival HIPC on AGX, Bounded admission reduced mean allocator work by 19.35% with a 1.40-s increase in mean target-service latency.The conclusion identifies sparse arrivals as the main cost region, where waiting for a batch can dominate added target-service latency.Source: §V · p. 7
  • Across four medium-arrival HIPC scenarios on RP2040, Count b = 4 reduced mean allocator work by 59.85% and target-service latency by 39.47%.Joint improvements also appeared in other allocator–load conditions, but usefulness depends on savings relative to introduced waiting.Source: §V · p. 7
Loading 2610.09187v1…