Beyond Shared Plans: Alignment-Constrained Tree Search for Embodied Collaboration

Large language model (LLM) based embodied agents increasingly use shared plans to coordinate long-horizon collaboration. However, a coherent plan does not guarantee coherent execution: agents may progress at different rates, causing ongoing work to be reassigned, completed work to remain active, or new actions to conflict with the current physical state. We study this planning–execution mismatch as the cognition–execution gap and propose Alignment-Constrained Tree Search (ACTS). ACTS connects collaborative planning with ongoing embodied execution through three steps: (1) Planning with Persistent Responsibilities keeps each agent’s active assignment, grounded target, and execution stage across planning calls; (2) Search with Responsibility Constraints admits only continuations supported by current execution evidence before reflection and expansion, while using unmet conditions to revise rejected proposals; and (3) Updating Responsibilities after Execution uses observed progress and confirmed effects to close completed work, preserve compatible ongoing work, and update the state for subsequent planning. Together, ACTS turns repeated plan revision into a closed planning–execution loop in which collaborative search remains consistent with physical progress. Experiments on TDW-MAT and C-WAH validate ACTS’s planning–execution alignment and demonstrate competitive task performance on both benchmarks.