Mosaic: Runtime-Efficient Multi-Agent Embodied Planning

Noosaga Placements

• Multiagent Systemssubfield95%
  The paper directly addresses multi-agent coordination, task allocation, and communication in embodied planning, which are core topics in multiagent systems.
  LLM-based multi-agent embodied planning remains impractical due to prohibitively high execution latency.Mosaic, a runtime-efficient multi-agent planning framework that addresses both challenges.It ensures efficient coordination through Integer Linear Programming that allocates actions at every planning step, enforcing physical feasibility and inter-agent coordination constraints.
• Large Language Modelsframework90%
  The paper explicitly uses Large Language Models (LLMs) as planners and action generators, and the framework is built around LLM calls for task decomposition, action proposal, and verification.
  Recent works have explored the use of Large Language Models (LLMs) as planners in such multi-agent environments.Mosaic uses one LLM to handle all LLM-Planner, LLM-Actor, and LLM-Verifier calls; this LLM is selected from GPT-4o, Claude Sonnet 4.5, or Gemini 3 Flash.
• Planning And Searchsubfield80%
  The paper focuses on planning action sequences for multiple agents, using constraint optimization to select feasible joint actions, which is a planning problem.
  Mosaic maintains accurate yet lightweight state tracking through agent-centric semantic memory that stores objects in relative coordinates, enabling geometric transformations and coordination.Action Selection via Constraint Optimization addresses the coordination challenge by selecting one action per agent from LLM-generated candidates at each timestep via an Integer Linear Programming (ILP) framework.
• Actor Modelframework70%
  The paper uses a centralized planning architecture where a single LLM generates actions for all agents, which aligns with the actor model of multiagent systems where a central coordinator dispatches actions.
  Mosaic is designed to be compatible with general LLM-based planning frameworks. Here, we describe its instantiation within a state-of-the-art centralized planning architecture.At each planning step, a centralized LLM-Actor proposes joint actions for all agents based on the currently open subtasks.
• Natural Language Processingsubfield70%
  The system uses LLMs for task decomposition, action proposal, and verification, which are NLP tasks, but the core contribution is in planning and coordination rather than language modeling.
  Recent works have explored the use of Large Language Models (LLMs) as planners in such multi-agent environments.Mosaic uses one LLM to handle all LLM-Planner, LLM-Actor, and LLM-Verifier calls.
• Task and Motion Planningframework60%
  The paper compares its approach to Task and Motion Planning (TAMP) frameworks, noting that TAMP uses preconditions and logical rules but lacks LLM flexibility, while Mosaic combines LLM proposals with symbolic optimization.
  Symbolic approaches leverage preconditions and logical rules to proactively reason about feasibility, commonly through Task and Motion Planning (TAMP) frameworks, but lack the flexible reasoning capabilities of LLMs.Neuro-symbolic coordination uses LLMs to propose actions and symbolic optimization to enforce action feasibility.
• Roboticssubfield60%
  The work is situated in embodied environments (AI2-THOR, SAR) and deals with physical actions, but the focus is on high-level planning rather than low-level robot control or perception.
  Many real-world embodied tasks such as collaborative search and rescue, household rearrangement, and environmental exploration require multiple agents operating simultaneously in shared spaces.We evaluate our framework in two environments: AI2-THOR and Search and Rescue (SAR).
• Multi-Agent Reinforcement Learningframework50%
  The paper mentions multi-agent reinforcement learning as a related approach but does not use it; it compares its neuro-symbolic method to neural methods that are largely reactive.
  Neural methods propose candidate actions from learned experience but are largely reactive in failure handling, correcting errors only after execution.Multi-Agent Reinforcement Learning is listed as a related framework but not directly used.

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.

Paper Context