Mosaic: Runtime-Efficient Multi-Agent Embodied Planning
MOSAIC combines agent-centric semantic memory and ILP optimization to enhance multi-agent embodied planning, achieving 30% faster execution and fewer failures.
Key Findings
Methodology
This paper introduces MOSAIC, a multi-agent planning framework integrating agent-centric semantic memory with Integer Linear Programming (ILP). Semantic memory stores environment objects relative to each agent, enabling geometric transformations and reducing spatial inference costs. At each planning step, LLMs generate candidate actions, which are then filtered through ILP constraints that enforce collision avoidance, task dependencies, and workload balance. The ILP optimizes action assignment by minimizing a cost function that penalizes failures, inefficiencies, and workload imbalance. This combination allows for dynamic, real-time, and globally consistent multi-agent coordination, significantly reducing failed actions and improving efficiency.
Key Results
- In AI2-THOR and search-and-rescue benchmarks, MOSAIC achieved 27-32% faster task execution, reduced LLM calls by 30-33%, and decreased steps by 25-31%. Failures dropped from 16% to around 4%, leading to a 4-10% increase in success rate. These improvements demonstrate its robustness and scalability across environments and agent counts.
- Compared to single-agent variants, MOSAIC shortened episode durations by 1.25-1.33× through coordinated action assignment, maintaining performance with five agents at 1.25-1.30× speedup. The system’s ability to adapt to environmental changes via continuous ILP optimization was validated.
- Experimental results confirm that agent-centric semantic memory and ILP-based scheduling effectively reduce redundant exploration and failed attempts, resulting in higher task success and efficiency, especially in complex, dynamic scenarios.
Significance
This work addresses critical bottlenecks in multi-agent embodied planning—namely, high latency due to failed actions and inefficient coordination. By integrating lightweight spatial memory with symbolic constraint optimization, MOSAIC enables low-latency, scalable multi-agent systems suitable for real-world applications like robotics, search-and-rescue, and household automation. It advances the state-of-the-art by providing a framework that balances semantic understanding with formalized, constraint-based scheduling, paving the way for more autonomous, reliable multi-agent systems capable of operating in complex environments with minimal delays.
Technical Contribution
The core technical innovations include the agent-centric semantic memory that tracks objects in relative coordinates, enabling geometric reasoning with low overhead, and the ILP-based action scheduler that filters candidate actions to ensure feasibility and optimality at each step. This hybrid approach combines the semantic richness of LLM proposals with the formal guarantees of symbolic optimization, allowing for dynamic, fine-grained coordination. The framework supports scalable, low-latency execution, with a formalized cost function balancing efficiency and failure risk, and demonstrates significant improvements over prior methods in both speed and success rate.
Novelty
This is the first work to unify agent-centric semantic spatial memory with real-time ILP-based action scheduling in multi-agent embodied planning. Unlike previous approaches that rely on coarse target allocation or reactive failure correction, MOSAIC performs fine-grained, step-by-step action-level optimization, enabling adaptive, collision-free coordination. Its innovative combination of geometric relative encoding and symbolic constraint solving sets a new standard for low-latency, scalable multi-agent systems.
Limitations
- The ILP solver’s computational cost may limit scalability in very large systems or highly dynamic environments, potentially requiring heuristic or hierarchical approaches.
- Dependence on accurate relative coordinate estimation makes the system sensitive to sensor noise and perception errors, which could affect memory updates and decision quality.
- The current framework primarily addresses planar navigation and object manipulation; extending to 3D complex environments remains a future challenge.
Future Work
Future research will focus on improving ILP scalability via hierarchical or approximate solvers, integrating learning-based heuristics for faster decision-making, and extending the framework to handle more complex, dynamic, and unstructured environments. Additionally, incorporating multi-modal perception and learning adaptive cost functions could further enhance robustness and autonomy in real-world scenarios.
AI Executive Summary
Multi-agent embodied planning has long been hindered by high latency and frequent failures, especially in complex environments requiring precise coordination. Existing approaches, often based solely on large language models (LLMs), generate action sequences without robust mechanisms for state tracking or conflict resolution, leading to repeated failures, redundant exploration, and significant delays. For instance, in search-and-rescue scenarios, failure rates can reach 16-50%, causing task durations to extend by several minutes, which is impractical for real-time applications.
To address these challenges, this paper introduces MOSAIC, a novel framework that synergizes agent-centric semantic memory with formal constraint optimization via Integer Linear Programming (ILP). The semantic memory component stores environment objects relative to each agent, enabling geometric reasoning without dense map construction. This lightweight memory is continuously updated based on observations and agent movements, facilitating accurate spatial grounding even when objects leave the field of view. Cross-agent transferability of relative coordinates ensures consistent environment understanding across multiple agents.
The ILP component acts as an action scheduler, taking candidate actions proposed by LLMs and filtering them through a set of constraints that enforce collision avoidance, task dependencies, and workload balance. By formulating the problem as an ILP, the system guarantees physically feasible and conflict-free actions at each step, dynamically adapting to environmental changes. The cost function further penalizes high-failure or inefficient actions, guiding the system toward optimal solutions.
Extensive experiments in AI2-THOR and search-and-rescue environments demonstrate that MOSAIC achieves 27-32% faster execution, reduces LLM calls by 30-33%, and cuts failed actions from 16% to 4%. These improvements translate into higher success rates and shorter task durations, with the system maintaining robustness even with five agents operating simultaneously. The results validate the effectiveness of combining lightweight spatial memory with symbolic constraint optimization for scalable, low-latency multi-agent planning.
Looking ahead, the authors plan to enhance ILP scalability through hierarchical or approximate methods, incorporate multi-modal perception, and extend the framework to more complex, dynamic environments. Overall, MOSAIC represents a significant step toward practical, autonomous multi-agent systems capable of real-time operation in real-world scenarios, with broad implications for robotics, automation, and intelligent virtual agents.
Deep Analysis
Background
多智能体embodied规划是机器人、虚拟代理等自主系统的重要研究方向。早期工作如Task and Motion Planning (TAMP)主要解决单智能体的路径规划问题，近年来，深度学习和大模型推动了多智能体协作的研究，诸如基于强化学习的分布式调度和符号推理方法。代表性研究包括DeepMind的Multi-Agent Reinforcement Learning，以及基于LLM的任务生成与调度系统。然而，现有方法在环境感知、状态追踪和实时协调方面仍存在瓶颈，尤其在复杂场景中容易出现失败，导致高延迟和低效率。
Core Problem
核心问题在于多智能体embodied规划中的状态追踪不准确和协调低效。部分观察限制导致环境信息不完整，影响动作生成的准确性；同时，缺乏有效的动作调度机制，导致冲突、冗余和失败频发。这些问题在实际应用中表现为高延迟、低鲁棒性，严重制约系统规模化和实用化。解决这些瓶颈，需在空间记忆和调度优化方面提出创新方案。
Innovation
创新点包括：1）提出基于相对坐标的代理中心语义记忆，减少空间推理成本，支持几何变换；2）引入ILP作为动作调度工具，将LLM生成的候选动作转化为全局一致的调度方案，确保物理可行性和任务协调；3）在每个规划步中动态优化动作组合，减少失败和冗余。该系统结合符号推理与学习模型，突破传统目标分配的局限，实现实时、细粒度的多智能体调度。
Methodology
- �� 设计代理中心语义记忆(ASM)，存储对象的相对坐标，支持几何变换和跨代理信息传递。
- �� 利用LLM（如GPT-4）生成每个智能体的候选动作，确保动作的语义合理性。
- �� 构建ILP模型，将候选动作作为变量，加入碰撞、任务依赖和负载平衡等约束。
- �� 设计成本函数，惩罚高失败风险和不均衡负载，优化调度方案。
- �� 每个规划步中，ILP求解器筛选出满足约束的最优动作组合，指导智能体执行。
- �� 通过不断更新记忆和约束，系统实现动态、实时的多智能体协调。
Experiments
在AI2-THOR家庭环境和搜救模拟环境中，采用标准的任务指标（成功率、执行时间、LLM调用次数）进行评估。对比基线包括纯LLM调度和粗粒度目标分配方法。超参数如候选动作数K、ILP求解时间限制等经过调优。还进行了消融实验，验证语义记忆和ILP的贡献。系统在不同智能体数量（1-5）下表现出一致的性能提升，验证了扩展性。
Results
实验结果显示，MOSAIC在AI2-THOR环境中成功率提升至85%，比基线高出10%；在搜救任务中，任务完成时间缩短了30%，LLM调用次数减少了33%。失败动作比例从16%降至4%，显著改善了效率和鲁棒性。多智能体系统中，整体速度提升达1.3倍，且在大规模系统中仍保持优异性能，验证了其实用性和扩展性。
Applications
该系统适用于家庭机器人、搜救无人机、工业自动化等场景，能实现高效、低延迟的多智能体协作。依赖于环境感知和语义理解，适合复杂、多变的环境中自主任务执行。未来可结合多模态感知和学习策略，进一步提升自主性和适应性，推动智能系统的广泛应用。
Limitations & Outlook
当前系统在极端复杂或动态变化环境中，ILP求解可能成为瓶颈，影响实时性。对传感噪声敏感，可能导致记忆更新误差。对非结构化环境和非平面运动的适应性仍需验证。未来需优化求解算法，增强鲁棒性，并扩展到更复杂的场景。
Plain Language Accessible to non-experts
想象你在厨房里准备一顿大餐，有多个厨师（智能体）同时工作。每个厨师都知道自己手边的食材（对象）和目标（菜肴），但他们不能随时看到整个厨房。为了不互相碰撞，也不重复做同样的事，他们需要一个共同的记忆——比如每个人都记着自己知道的食材位置。每次厨师准备下一步时，他们会根据自己的记忆和厨师长（系统）的建议，选择最合适的动作。系统会用一种聪明的方法（ILP）筛选出不会撞到人的方案，确保每个厨师都能顺利完成任务。这样，厨房里的厨师们就能高效协作，不会浪费时间，也不会出错。这个方法让厨房工作变得更快、更顺畅，也可以用在机器人、虚拟助手等地方，让它们更聪明、更合作。
ELI14 Explained like you're 14
想象你和几个朋友一起玩拼图游戏。每个人都知道自己手里的拼图片和目标位置，但你们不能一直看着整个拼图。为了拼得快，还要避免撞到对方或拼错地方，你们会用一种特别的办法：每个人都记着自己知道的拼图片位置，然后通过一个聪明的规则（像ILP）决定谁拼哪个块，确保不重复、不冲突。每次轮到某个人拼时，系统会帮忙筛选出最合适的拼图方案，这样大家就能更快完成拼图。这就像让每个人都知道自己该做什么，又能合作得很好，整个拼图过程变得又快又顺利。这个方法可以用在机器人或虚拟人物，让它们更聪明、更合作，帮我们完成各种复杂任务。
Abstract
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.