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

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

Introduction. 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 timestep. 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. We consider both purely symbolic execution domains where transition functions between world states are deterministic and hairier simulation execution domains that introduce stochasticity in environment states and transitions. Classical planning. Classical or automated task planning algorithms have been widely applied in autonomous spacecrafts, military logistics, manufacturing, games, and robotics.

Discussion / Conclusion. We propose TWOSTEP, a method to decompose a single agent planning problem into a two-agent planning problem in several symbolic domains and one simulated domain. TWOSTEP leverages commonsense from LLM to effectively divide a problem between two agents for faster execution, while also preserving execution success using classical planning guarantees. Our results show that LLM-based goal decomposition leads to faster planning time than the multiagent PDDL problem and shorter plan execution steps than the single agent execution. We additionally show that LLMinferred subgoals in TWOSTEP approximate those specified by a human expert.