Multi-agent Path Planning Based on Conflict-Based Search (CBS) Variations for Heterogeneous Robots

Abstract

Abstract This article introduces a novel Multi-agent path planning scheme based on Conflict Based Search (CBS) for heterogeneous holonomic and non-holonomic agents, designated as Heterogeneous CBS (HCBS). The proposed methodology employs a hybrid $$A^*$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>A</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:math> algorithm for non-holonomic car-like robots and a conventional $$A^*$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>A</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:math> algorithm for holonomic robots. Following this, a body conflict detection strategy is utilized to construct the conflict tree, bridging the initial path planning with the resolution of conflicts among agents. Moreover, we present two variants of HCBS: the Enhanced Conflict-Based Search (EHCBS) and the Depth-First Conflict-Based Search (DFHCBS). We evaluate the efficacy of our proposed algorithms—HCBS, EHCBS, and DFHCBS—against a standard prioritized planning algorithm, focusing on success rates and computational efficiency in environments with varying numbers of agents and obstacles. The empirical results demonstrate that EHCBS exhibits superior computational efficiency in small, dense environments, while DFHCBS performs well in larger-scale environments. This highlights the adaptability of our proposed approaches in various settings, proving the computational advantage of EHCBS and DFHCBS over traditional methods.