TwoStep: Multi-agent Task Planning using Classical Planners and Large Language Models

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.

We propose decomposing multi-agent planning problem into two single agent planning problems by leveraging LLM's commonsense and reasoning contextualized with humans operating together in diverse scenarios. In particular, we consider a two-agent planning problem with a helper and main agent. For a given problem $\mathrm{P}$, the helper plans $\pi_h = \prod(i, g')$ to reach a subgoal state $g'$ from $\mathrm{P}$'s initial state $i$, using a planner $\prod$. This subgoal state ($g'$) then serves as the initial state ($i' = E(i, \prod(s, g')$) for the main agent plan $\pi_m = \prod(i', g)$ to reach the $\mathrm{P}$'s specified goal, $g$, where $E$ refers to Plan Execution. The helper conceives $g'$ using 2 modules: Subgoal Generator to produce a possible helper subgoal in English - English Subgoal, and Subgoal Translator to translate English subgoal into PDDL format goal - PDDL Subgoal. We hypothesize that the commonsense reasoning abilities of LLMs can be leveraged in this context to predict helper agent subgoals whose plan actions $\pi_h$ will be executable in parallel to those of the main agent $\pi_m$, where latter takes for granted that the former will achieve the subgoal eventually.