Tensor-Coord: Algebraic Decomposition of Joint Plan Tensors for Conflict-Free Multi-Agent LLM Planning
2026-06-15 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors studied how multiple agents can plan their actions together without causing problems like collisions or delays. They created a math tool called Tensor-Coord that uses tensors to represent all agents’ plans across time and actions, then breaks this down using special decompositions to find hidden coordination patterns. Their method measures how complex the coordination is and identifies conflicts automatically without needing specific rules. They tested this on multi-robot delivery tasks and showed their approach helped agents fix conflicts and find smooth plans efficiently. The complexity measure also grew predictably with more agents, helping to understand coordination challenges.
large language modelsmulti-agent planningtensorthird-order tensorCanonical Polyadic decompositionTucker decompositioncoordination complexityplan independenceconflict localizationrobot delivery tasks
Authors
Mudit Rastogi
Abstract
Large language models (LLMs) remain limited in multi-agent planning because independently generated plans can create coordination failures such as spatial collisions, resource contention, and temporal deadlocks. We introduce Tensor-Coord, a multilinear algebra framework that represents the joint plan of N agents as a third-order tensor \(T \in R^{N \times H \times A}\) over agents, timesteps, and actions. Canonical Polyadic (CP) and Tucker decompositions are used to identify latent coordination structure. The minimal epsilon-approximate CP rank R* defines a computable coordination complexity measure, with \(CC(Pi)=(R*-N)/N\). We prove that R*=N is necessary and sufficient for plan independence. The residual \(E=T-T_{R*}\) defines a conflict score over agent pairs, timesteps, and actions, localizing failures without domain-specific rules. Tucker factors provide interpretable agent roles, temporal phases, and action clusters that are converted into natural language constraints for iterative LLM replanning. Experiments on multi-robot delivery tasks across Easy (2 agents, 5x5 grid), Medium (3 agents, 5x5 grid), and Hard (4 agents, 5x5 grid) settings show convergence to conflict-free plans in 100% of 2-agent cases within 1.4 iterations on average, 80% of 3-agent cases within 3.2 iterations, and 60% of 4-agent cases within 4.0 iterations. CP rank scaled approximately linearly as \(R*(N) = 3.9N + 0.5\), supporting its use as a predictor of coordination complexity.