Solving Deadlock Problem for Consensus‐Based Bundle Algorithm in Distributed Systems With Practical Fuel Consumption Evaluation

ABSTRACT

This paper proposes the Deadlock‐Free Consensus‐Based Bundle Algorithm (DF‐CBBA) to address deadlock in distributed multi‐agent task allocation problems with practical fuel consumption evaluation. A more practical optimization problem, which intentionally violates the Diminishing Marginal Gains (DMG) property, is formulated by enhancing the fuel consumption penalty within the time‐window task allocation framework. Under this formulation, the marginal benefit of a task is no longer computed using a pre‐defined objective function formula. Instead, it is derived from the actual increase in the overall objective value resulting from the task's insertion. The critical innovation of the proposed DF‐CBBA is a redesigned bidding strategy equipped with adaptive conflict‐resolution mechanisms, enabling agents to dynamically re‐evaluate task valuations during the bundle construction phase. Theoretical analysis and simulation results validate the performance of the algorithm.