Consensus-Based Bundle Algorithm

Each agent greedily builds a bundle of tasks that maximizes its own marginal utility. The agent iteratively adds the task with the highest score until no further tasks can be added without violating constraints. The marginal score for a task is calculated as the difference in utility with and without that task in the bundle, ensuring that each addition provides positive value. This phase uses a greedy heuristic to approximate the optimal bundle, as exact combinatorial optimization is NP-hard.

Agents share their winning bids and winning scores with neighbors to resolve overlapping task assignments. When two agents claim the same task, the one with the higher bid retains it, and the loser must release the task and all subsequent tasks in its bundle that depended on it. This process uses a consensus rule based on timestamps and scores to ensure a consistent, conflict-free allocation across the distributed network. The resolution propagates through the fleet until a Nash equilibrium is reached.

The score function encodes the agent's utility for a task given its current bundle. It must be diminishing marginal gain (DMG) compliant, meaning the value of adding a task decreases as the bundle grows. This property guarantees convergence. A typical formulation: c_ij = max(0, u_i(b_i ⊕ j) - u_i(b_i)), where u_i is the utility function and b_i is the current bundle. The score function can incorporate time-discounting, fuel costs, and capability matching.

CBBA is proven to converge to a conflict-free assignment within a finite number of iterations, bounded by N_D * min(N_T, L_t) where N_D is the network diameter, N_T is the number of tasks, and L_t is the maximum bundle size. The algorithm guarantees 50% optimality in the worst case for submodular objective functions, and often achieves near-optimal performance in practice. Convergence speed depends on network topology and communication frequency.

CBBA operates without a central auctioneer, relying solely on peer-to-peer communication. Each agent maintains a local winning bid list and winning agent list for all tasks, updated through message passing. This architecture eliminates single points of failure and scales horizontally. Communication is typically asynchronous and event-driven, with agents broadcasting updates only when their local state changes, reducing bandwidth requirements in large fleets.

Several extensions address real-world constraints: Asynchronous CBBA handles message delays and out-of-order arrivals. Coupled-Constraint CBBA incorporates shared resource limits across agents. Dynamic CBBA allows tasks to be added or removed during execution. Heterogeneous CBBA supports agents with different capability profiles. These variants maintain the core two-phase structure while adapting the consensus rules and score functions to specific operational requirements.