Mosaic: Runtime-Efficient Multi-Agent Embodied Planning

LLM-based multi-agent embodied planning remains impractical due to prohibitively high execution latency. We identify failed actions as the dominant bottleneck, stemming from two core challenges: inaccurate state tracking under partial observability and inefficient coordination that produces redundant or conflicting actions. We introduce Mosaic, a runtime-efficient multi-agent planning framework that addresses both challenges. Mosaic maintains accurate yet lightweight state tracking through agent-centric semantic memory that stores objects in relative coordinates, enabling geometric transformations and coordination. It ensures efficient coordination through Integer Linear Programming that allocates actions at every planning step, enforcing physical feasibility and inter-agent coordination constraints. Across AI2-THOR and search-and-rescue benchmarks, Mosaic achieves 27–32% faster execution, 30–33% fewer LLM calls, 25–31% fewer steps, and 4–10% points higher success rates. These results demonstrate that efficient memory and constraint-guided coordination are critical for scalable, low-latency multi-agent planning.

Current AI systems that control multiple robots or virtual agents can solve complex tasks such as household chores or search-and-rescue missions, but they are often too slow for practical use. A major reason is that agents frequently make mistakes: they lose track of where objects are, repeat failed actions, or interfere with one another while trying to coordinate. These failures waste time and force the system to repeatedly stop and replan. We introduce Mosaic, a new framework that helps groups of AI agents work together more efficiently. First, Mosaic gives each agent a lightweight "semantic memory" that keeps track of important objects and locations relative to the agent’s own position. This helps agents better understand and share information about their surroundings, even when they cannot directly see everything. Second, Mosaic uses a mathematical optimization method to choose coordinated actions for all agents at every step, preventing conflicts, unsafe actions, and redundant work. We tested Mosaic in virtual household and rescue environments. Compared to previous systems, Mosaic completed tasks 27–32% faster, required fewer AI model calls, reduced unnecessary actions, and improved task success rates. Our results show that better memory and coordination are key to making multi-agent AI systems faster, more reliable, and more practical for real-world applications.