Large language models (LLMs) face challenges in multi-agent planning due to coordination failures arising from independently generated plans, 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}$, where N is the number of agents, H is the timesteps, and A is the actions. Canonical Polyadic (CP) and Tucker decompositions are employed to identify latent coordination structures. The minimal epsilon-approximate CP rank $R^*$ defines a computable coordination complexity measure, formulated as $CC(Pi)=(R^*-N)/N$. We prove that $R^*=N$ is both 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 an average of 1.4 iterations, 80% of 3-agent cases within 3.2 iterations, and 60% of 4-agent cases within 4.0 iterations. The CP rank scaled approximately linearly as $R^*(N) = 3.9N + 0.5$, supporting its use as a predictor of coordination complexity.
Blogger's Review: Tensor-Coord presents an innovative approach to tackle multi-agent coordination issues, effectively reducing conflicts through algebraic decomposition techniques that enhance planning efficiency. Its experimental results across various scenarios demonstrate practicality and reliability, offering new insights for future multi-agent system planning.