Convergence analysis of the Hybrid Information and Plan Consensus Algorithm

This paper presents a rigorous analysis of the Hybrid Information and Plan Consensus (HIPC) Algorithm previously introduced in Ref. [1]. HIPC leverages the ideas of local plan consensus and implicit coordination to exploit the features of both paradigms. Prior work on HIPC has empirically shown that it reduces the convergence time and number of messages required for distributed task allocation algorithms. This paper further explores HIPC to rigorously prove convergence and provides a worst case on the time to convergence. This worst-case bound is no slower than a comparable plan consensus algorithm, Bid Warped CBBA [2], requiring two times the number of tasks times the network diameter iterations for convergence. Additionally, the analysis of convergence highlights why the performance of HIPC is significantly better than this on average. Convergence bounds of this type are essential creating trustworthy autonomy, and for guaranteeing performance when using these algorithms in the field.