PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-Free Distributed Multi-Robot Task Allocation under Partial Observations Using Labeled Multi-Bernoulli Filtering

Takumi Ito, Akiya Kamimura

arXiv:2609.39416v1cs.ROcs.SYeess.SY

TL;DR

Communication-free task allocation is challenging when robots rely on noisy, partial local observations and must account for task-specific robot counts. The paper combines LMB-based neighbor estimation with independent auction allocation, and reports robust success under severe clutter compared with KF and PHD estimates.

  • Problem

    Communication-free allocation must work from local, range-limited sensing despite noise, missed detections, and clutter, while preserving information about how many robots are available for each task.

    Source: §I · p. 1

  • Method

    Each robot uses LMB filtering to estimate neighboring robots and independently allocates tasks through an auction-based approach without inter-robot communication.

    Source: §V · p. 8

  • Results

    96.5% and 78.0% LMB success in the 10-robot/3-task and 15-robot/4-task scenarios under severe clutter (λc=2.0), versus KF’s 61.5% and 10.5% and PHD’s 82.5% and 59.0%.

    Source: C. Results and Discussion · p. 7

  • Takeaways & Limitations

    Labeled robot estimates suit cardinality-dependent allocation better than density-only representations, and the proposed approach remains robust across clutter conditions.

    Source: §I · p. 1, C. Results and Discussion · p. 8

    Success decreased from nearly 100% in the 10-robot/3-task scenario to approximately 80% in the 15-robot/4-task scenario, indicating degradation as problem size increases.

    Source: C. Results and Discussion · p. 7

Abstract

from arXiv · show

This paper proposes a communication-free multi-robot task allocation framework based solely on local observations. In this study, tasks are defined as reaching target locations. Each robot estimates the positions of neighboring robots using a Labeled Multi-Bernoulli (LMB) filter and independently assigns tasks through a greedy auction-based strategy. By continuously updating state estimates and reallocating tasks during execution, the proposed method enables decentralized coordination without explicit communication. Monte Carlo simulations demonstrate that the proposed method enables effective cooperative task allocation without inter-robot communication while remaining robust to measurement clutter and observation uncertainty.

I. INTRODUCTION

The paper addresses communication-free task allocation when robots have only uncertain local observations and must account for how many robots each task requires. It connects labeled multi-target estimation to decentralized allocation and formulates tasks as reaching known target locations with prescribed robot demands.

Related Work

  • Centralized MRTA uses globally collected information, while distributed methods let robots decide independently but commonly rely on inter-robot communication.Prior communication-free methods include incomplete-information games, neighbor-based allocation, and distance-constrained control.Source: §I · p. 1, Related Work · p. 2

I. INTRODUCTION

  • Communication-free cooperative allocation remains challenging when sensing is range-limited and affected by noise, missed detections, and clutter.Prior approaches often assume reliable observations or access to task-related information from neighboring robots.Source: §I · p. 1
  • The proposed LMB-based framework estimates neighboring robots from partial observations and supports independent task allocation while accounting for task cardinality.The paper also compares KF-, PHD-, and LMB-based estimation representations under realistic operating conditions.Source: §I · pp. 1–2

II. PROBLEM FORMULATION

  • The problem assumes robots know task locations and demands beforehand, while each uses range-limited sensing to observe nearby robots without identifiers.Measurements may contain clutter, and assignments use locally available information.Source: §II · p. 2

A. Robot and Task Models

  • A task is a target location requiring a prescribed number of robots, and it is complete when that number reaches within a specified distance.The formulation assumes the sum of task demands does not exceed the number of robots.Source: A. Robot and Task Models · p. 2

B. Observation Model

Each robot forms an unlabeled local measurement set from range-limited observations of nearby robots. The model accounts for distance-dependent detection, uncertain positions, and clutter.

B. Observation Model

  • Detection probability depends on inter-robot distance, and the sensing region limits which neighboring robots can be observed.The observation process models detected robot measurements separately from clutter.Source: B. Observation Model · pp. 2–3
  • A detected robot’s position measurement is modeled as Gaussian, with distance-dependent uncertainty scaling.The measurement model is conditioned on successful detection.Source: B. Observation Model · p. 2
  • Clutter counts follow a Poisson model, and clutter measurements are sampled uniformly over the sensing region.The expected clutter count per scan is λc.Source: B. Observation Model · p. 3
  • Each robot receives an unlabeled finite set of position measurements, without unique robot identifiers.It recursively estimates observed and unobserved neighboring robots from measurement history.Source: B. Observation Model · p. 3

III. LMB FILTER BASED TASK ALLOCATION

The framework uses an LMB representation to estimate other robots from each robot’s unlabeled local measurements. Its labeled Bernoulli components retain individual identities and existence estimates.

III. LMB FILTER BASED TASK ALLOCATION

  • The LMB filter estimates other robots from unlabeled local measurements while handling data association, missed detections, and clutter.The filter is used for each robot’s observations.Source: A. Labeled Multi-Bernoulli State… · p. 3
  • Each Bernoulli component has an existence probability and a unique label that distinguishes the represented robot.Labels encode birth time and an index distinguishing components born at the same time.Source: A. Labeled Multi-Bernoulli State… · p. 3
  • For computational efficiency, the implementation approximates each Bernoulli density with a single Gaussian component.Each component’s spatial density is modeled as Gaussian.Source: A. Labeled Multi-Bernoulli State… · p. 3

1) Prediction:

The prediction step propagates each existing component’s existence probability and Gaussian parameters using the survival probability.

1) Prediction:

  • Existing components are predicted using survival probability pS, set to 1−10^-6 because robots are assumed rarely to disappear.The prediction step propagates the Gaussian parameters along with existence probability.Source: 1) Prediction · p. 3

2) Update and data association:

The update associates unlabeled measurements with predicted Bernoulli tracks while accounting for missed detections. Murty’s algorithm limits the association hypotheses, and previously observed out-of-range tracks remain available through prediction.

2) Update and data association:

  • The filter updates predicted densities from unlabeled measurements by mapping each track label to a measurement or ⊥ for a missed detection.The augmented measurement set includes the missed-detection option.Source: 2) Update and data association · p. 3
  • Murty’s algorithm generates the KA highest-scoring association hypotheses because exhaustive enumeration is computationally expensive.Each hypothesis maps track labels to measurements or a missed-detection event.Source: 2) Update and data association · pp. 3–4
  • Association-hypothesis weights are marginalized to calculate the posterior existence probability.The highest-weight component is retained for the posterior Gaussian density.Source: 2) Update and data association · p. 4
  • Outside sensing range, a track is propagated by prediction with unchanged existence probability, keeping previously observed robots available to downstream decisions.Tracks within range are updated by measurements; false tracks gradually lose existence probability without consistent observations.Source: 2) Update and data association · p. 4

3) Track Birth and Pruning:

Unexplained measurements initialize new Bernoulli components, while pruning and uncertainty-based selection limit which tracks reach task allocation and collision avoidance.

3) Track Birth and Pruning:

  • Measurements outside every existing track’s two-dimensional chi-square gate initialize Bernoulli birth components for the next time step.The implementation uses γB = 5.99, corresponding to a 95% confidence region.Source: 3) Track Birth and Pruning · p. 4
  • Each new birth component is initialized with existence probability r = 0.01 and covariance diag(0.18, 0.18, 4.0, 4.0).The initial covariance is set to P0.Source: 3) Track Birth and Pruning · p. 4
  • To limit track growth and computational cost in clutter, components with r(ℓ) < 0.5 or tr(P) > 60 are discarded.Source: 3) Track Birth and Pruning · p. 4
  • Surviving tracks with r ≥ 0.5 are ranked by tr(P), and the lowest-uncertainty tracks are passed to allocation and collision avoidance while preserving a task for the ego robot.Source: 3) Track Birth and Pruning · p. 4

B. Greedy Auction-Based Task Assignment

Each robot locally computes bids from estimated robot and task positions, then greedily assigns tasks subject to robot availability and task capacity. Assignments are revisited during execution to reduce switching and respond to higher-bid occupancy.

B. Greedy Auction-Based Task Assignment

  • Each robot independently bids for tasks using a softmax of robot-to-task and estimated-neighbor-to-task distances, with bids normalized to sum to one per robot.All robots use the same deterministic assignment rule.Source: B. Greedy Auction-Based Task Assignment · p. 4
  • Robot–task bids are processed in descending order, accepting a pair only if the robot is unassigned and the task has not reached its required number of robots.The process continues until a task is assigned to the ego robot.Source: B. Greedy Auction-Based Task Assignment · p. 4
  • Every 20 time steps, majority vote determines the task; robots switch when a higher-bid robot occupies their current task, distributing robots without communication.Otherwise, robots continue toward their current tasks.Source: B. Greedy Auction-Based Task Assignment · p. 5

C. Task Execution and Collision Avoidance Control

Robots follow a nominal command toward assigned tasks, then a Control Barrier Function-based module minimally adjusts control inputs to enforce collision-avoidance constraints using estimated neighboring states.

C. Task Execution and Collision Avoidance Control

  • The nominal velocity command is directed toward the assigned task, with its magnitude limited by vmax.The control gain is kp and sat(·) limits velocity magnitude.Source: C. Task Execution and Collision… · p. 5
  • A Control Barrier Function defines a safe set using the estimated position of a neighboring robot and the required safe distance.The condition hiℓ ≥ 0 indicates membership in the collision-free set.Source: C. Task Execution and Collision… · p. 5
  • At each control step, a quadratic program obtains a collision-free input that minimally modifies the nominal command while enforcing constraints against estimated neighboring-robot states.Source: C. Task Execution and Collision… · p. 5
  • Repeated estimation, task assignment, and control adapt assignments to the locally estimated robot distribution while satisfying each task’s required robot count.Source: C. Task Execution and Collision… · p. 5

IV. SIMULATION

Monte Carlo simulations assess task assignment with randomly generated robot and task locations, comparing KF-, PHD-, and LMB-based neighboring-robot estimation. In the comparisons, only the state-estimation module changes; task allocation and control remain fixed.

IV. SIMULATION

  • Monte Carlo simulations with randomly generated robot and task locations compare KF-, PHD-, and LMB-based neighboring-robot estimation for task assignment.Source: §IV · p. 5

A. Comparison methods

  • Only neighboring-robot state estimation changes across comparison methods; task allocation and control remain fixed.Source: A. Comparison methods · p. 5

1) Ground Truth (GT):

  • Ground truth supplies exact positions of all robots and serves as an approximate upper bound under shared state information.Source: 1) Ground Truth (GT) · p. 5

2) Kalman Filter (KF):

  • KF tracks use 1.0 m Euclidean gating; confirmation requires three successful associations, while five in-range misses or tr(P) > 60 removes tracks.Source: 2) Kalman Filter (KF) · p. 5

3) PHD Filter (PHD):

  • GM-PHD represents multi-target states as Gaussian-mixture intensity without explicit association; estimates use components above w = 0.5 and discard those with tr(P) > 60.Source: 3) PHD Filter (PHD) · p. 5

1) Setting:

  • At a sensing distance of 1 m, observation covariance is 0.082I3, and the probability observation error exceeds dsafe is approximately 10−32.Source: 1) Setting · pp. 5–6
  • The simulated 50 m×50 m area contains either 10 robots and 3 tasks or 15 robots and 4 tasks, with sensor ranges ds0 = 4.5 and ds1 = 5.5 m.Source: 1) Setting · p. 6
  • Across 200 shared random initial-state seeds, KF-, PHD-, and LMB-based estimates are tested at clutter intensities λc ∈{0.0, 0.5, 1.0, 2.0}.Source: 1) Setting · p. 6

2) Evaluation Metrics:

The section defines task-allocation metrics and reports Monte Carlo comparisons across clutter levels and two team sizes. LMB retains high success under severe clutter, although results degrade as problem size increases.

2) Evaluation Metrics:

  • Evaluation uses task-completion success rate, and measures travel distance, completion time, and reassignment count only in successful trials.The metrics are used to reflect how estimation uncertainty affects allocation; the success criterion has a 180 s timeout, and conventional OSPA tracking metrics are not used.Source: 2) Evaluation Metrics · p. 6

C. Results and Discussion

  • In the 10-robot/3-task example, assignments update as observations arrive, unsupported clutter tracks fade, and all tasks are completed.Repeated reassignment gradually reduces inconsistencies among robots’ estimates as more observations become available.Source: C. Results and Discussion · p. 6, Figure 2 · p. 7
  • At low clutter (λc = 0 and 0.5), KF and LMB had higher success rates than PHD, with similar completion times, travel distances, and reassignment counts.The passage attributes this pattern to KF and LMB maintaining individual robot hypotheses, unlike PHD’s intensity-based representation, which does not directly preserve identities needed for task-cardinality decisions.Source: C. Results and Discussion · p. 6
  • At λc = 1.0, PHD had lower success than KF and LMB in the smaller scenario but higher success than KF in the larger one; LMB remained near its low-clutter performance.Source: C. Results and Discussion · pp. 6–7
  • At λc = 2.0, success rates were 96.5% and 78.0% for LMB, versus KF’s 61.5% and 10.5% and PHD’s 82.5% and 59.0% in the 10-robot/3-task and 15-robot/4-task scenarios.Similar trends were observed in completion time and travel distance.Source: Figure 3 · p. 7, C. Results and Discussion · p. 7
  • Success fell from nearly 100% in the 10-robot/3-task scenario to approximately 80% in the 15-robot/4-task scenario, while LMB maintained low reassignment counts as KF and PHD counts rose substantially.Source: C. Results and Discussion · p. 7

V. CONCLUSION

The paper combines LMB filtering with auction-based task allocation so robots can estimate neighbors and assign tasks using local observations, without communication. Monte Carlo simulations report higher task-completion success and fewer reassignments than KF- and PHD-based methods, with future work targeting convergence guarantees and larger-scale performance.

V. CONCLUSION

  • Each robot estimates neighboring robots from local observations and independently assigns tasks by combining LMB filtering with auction-based allocation, without communication.Source: §V · p. 8
  • Monte Carlo simulations showed higher task-completion success and fewer task reassignments than KF- and PHD-based methods, with competitive completion times and travel distances.The results underscore the importance of preserving robot identities and existence probabilities under uncertain observations.Source: §V · p. 8
  • Future work includes establishing convergence guarantees, improving performance in larger-scale scenarios, and extending the approach to more practical task settings.Source: §V · p. 8
Loading 2609.39416v1…