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

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 multiagent PDDL problems directly while simultaneously achieving fewer plan execution steps than a single agent plan alone and preserving execution success.

Symbolic planning problems specified in PDDL tend to explore single agent plans, and changing these domain specifications to enable planning with multiple agents requires a human expert. Unfortunately, multi-agent planning introduces an exponential growth in the search space over possible plans, since each agent can take an action at each time step. In this paper, we explore whether the commonsense reasoning abilities in LLMs can take advantage of the lexical semantics encoded in the variable, action, and other ontological names of an expert-written planning domain to predict subgoals for individual agents that, when executed together, will achieve a given global goal.