Conflict-Based Search (CBS-TA) Performance Analysis 🤖

Overview

A research study profiling Conflict-Based Search with Task Assignment (CBS-TA) — an optimal multi-agent path-finding algorithm that simultaneously allocates tasks and plans collision-free routes. We benchmarked CBS-TA on 32×32 and 8×8 grids (up to 100 agents), measured runtime, memory, cache behaviour, and pinpointed scalability bottlenecks.

Key Contributions

• Empirically showed runtime grows exponentially & conflicts quadratically beyond 80 agents.
• Captured processor-level stats with perf and Cachegrind – billions of instructions, L1 miss hotspots.
• Proposed heuristics, memory-layout tweaks, and parallel low-level search to cut runtime & RAM.
• Authored the full IEEE-style paper (10 pp) and automated data-collection scripts.

In Depth

The analysis revealed a dramatic spike in search-tree size once agent count passes 50, with memory soaring from 50 MB to over 300 MB at 100 agents. Profiling on an 8×8 grid isolated cache-usage inefficiencies driving these costs. The paper outlines heuristic conflict prioritisation, bounded-suboptimal search, and parallelised low-level A* replanning as practical paths forward.

The analysis revealed a dramatic spike in search-tree size once agent count passes 50, with memory soaring from 50 MB to over 300 MB at 100 agents. Profiling on an 8×8 grid isolated cache-usage inefficiencies driving these costs.