PBW-CBBA: A Policy-Based Bid Warping Approach for Distributed Multi-Robot Task Allocation with Non-Submodular Rewards

Distributed Multi-Robot Task Allocation (MRTA) algorithms typically require submodular score functions to guarantee convergence. To overcome this limitation, this paper proposes a Policy-based Bid Warping Consensus-Based Bundle Algorithm (PBW-CBBA). Using the representative distributed algorithm CBBA as a baseline, this work incorporates a policy-driven bid adjustment mechanism, supported by a reversible rollback operation, into the standard framework. This approach enables robots to select tasks based on true internal and potentially non-submodular score functions while externally publishing bids that satisfy the Diminishing Marginal Gain (DMG) property. Meanwhile, the rollback mechanism ensures that artificial bid elevations introduced by bid warping are restored during the conflict resolution phase, preventing warped bid values from being retained after bundle changes and thereby avoiding value assessment biases. Consequently, PBW-CBBA preserves the original convergence and performance guarantees of CBBA without requiring the explicit construction of a submodular score function. Simulation results across diverse collaborative MRTA scenarios demonstrate that PBW-CBBA achieves stable convergence and efficient task allocation under non-submodular score conditions, effectively improving assignment stability and overall system performance.