TwoStep: Multi-agent Task Planning using Classical Planners and Large
  Language Models
Ishika Singh David Traum Jesse Thomason
Classical planning formulations like the Planning Domain Definition Language
(PDDL) admit action sequences guaranteed to achieve a goal state given an
initial state if any are possible. However, reasoning problems defined in PDDL
do not capture temporal aspects of action taking, for example that two agents
in the domain can execute an action simultaneously if postconditions of each do
not interfere with preconditions of the other. A human expert can decompose a
goal into largely independent constituent parts and assign each agent to one of
these subgoals to take advantage of simultaneous actions for faster execution
of plan steps, each using only single agent planning. By contrast, large
language models (LLMs) used for directly inferring plan steps do not guarantee
execution success, but do leverage commonsense reasoning to assemble action
sequences. We combine the strengths of classical planning and LLMs by
approximating human intuitions for two-agent planning goal decomposition. We
demonstrate that LLM-based goal decomposition leads to faster planning times
than solving multi-agent PDDL problems directly while simultaneously achieving
fewer plan execution steps than a single agent plan alone and preserving
execution success. Additionally, we find that LLM-based approximations of
subgoals can achieve similar multi-agent execution steps than those specified
by human experts. Website and resources at https://glamor-usc.github.io/twostep