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

• URL: http://arxiv.org/abs/2403.17246v1
• Date: Mon, 25 Mar 2024 22:47:13 GMT
• Title: TwoStep: Multi-agent Task Planning using Classical Planners and Large Language Models
• Authors: Ishika Singh, David Traum, Jesse Thomason,
• Abstract summary: Two-agent planning goal decomposition leads to faster planning times than solving multi-agent PDDL problems directly. We find that LLM-based approximations of subgoals can achieve similar multi-agent execution steps than those specified by human experts.
• Score: 7.653791106386385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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

Related papers

• Hindsight Planner: A Closed-Loop Few-Shot Planner for Embodied Instruction Following [62.10809033451526]
  This work focuses on building a task planner for Embodied Instruction Following (EIF) using Large Language Models (LLMs) We frame the task as a Partially Observable Markov Decision Process (POMDP) and aim to develop a robust planner under a few-shot assumption. Our experiments on the ALFRED dataset indicate that our planner achieves competitive performance under a few-shot assumption.
  arXiv  Detail & Related papers  (2024-12-27T10:05:45Z)
• Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions [5.5233853454863615]
  Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations. Although many MAPF algorithms can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability.
  arXiv  Detail & Related papers  (2024-12-16T11:36:24Z)
• Nl2Hltl2Plan: Scaling Up Natural Language Understanding for Multi-Robots Through Hierarchical Temporal Logic Task Representation [8.180994118420053]
  Nl2Hltl2Plan is a framework that translates natural language commands into hierarchical Linear Temporal Logic (LTL) First, an LLM transforms instructions into a Hierarchical Task Tree, capturing logical and temporal relations. Next, a fine-tuned LLM converts sub-tasks into flat formulas, which are aggregated into hierarchical specifications.
  arXiv  Detail & Related papers  (2024-08-15T14:46:13Z)
• Language Models can Infer Action Semantics for Symbolic Planners from Environment Feedback [26.03718733867297]
  We propose Predicting Semantics of Actions with Language Models (PSALM) PSALM learns action semantics by leveraging the strengths of both symbolic planners and Large Language Models (LLMs) Experiments show PSALM boosts plan success rate from 36.4% (on Claude-3.5) to 100%, and explores the environment more efficiently than prior work to infer ground truth domain action semantics.
  arXiv  Detail & Related papers  (2024-06-04T21:29:56Z)
• Planning with Multi-Constraints via Collaborative Language Agents [13.550774629515843]
  This paper introduces Planning with Multi-Constraints (PMC), a zero-shot methodology for collaborative multi-agent systems. PMC simplifies complex task planning with constraints by decomposing it into a hierarchy of subordinate tasks. PMC achieved an average 42.68% success rate on TravelPlanner, significantly higher than GPT-4 (2.92%), and outperforming GPT-4 with ReAct on API-Bank by 13.64%.
  arXiv  Detail & Related papers  (2024-05-26T10:33:17Z)
• NL2Plan: Robust LLM-Driven Planning from Minimal Text Descriptions [8.004470925893957]
  We present NL2Plan, the first domain-agnostic offline LLM-driven planning system. We evaluate NL2Plan on four planning domains and find that it solves 10 out of 15 tasks. In addition to using NL2Plan in end-to-end mode, users can inspect and correct all of its intermediate results.
  arXiv  Detail & Related papers  (2024-05-07T11:27:13Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• Skip-Plan: Procedure Planning in Instructional Videos via Condensed Action Space Learning [85.84504287685884]
  Skip-Plan is a condensed action space learning method for procedure planning in instructional videos. By skipping uncertain nodes and edges in action chains, we transfer long and complex sequence functions into short but reliable ones. Our model explores all sorts of reliable sub-relations within an action sequence in the condensed action space.
  arXiv  Detail & Related papers  (2023-10-01T08:02:33Z)
• AdaPlanner: Adaptive Planning from Feedback with Language Models [56.367020818139665]
  Large language models (LLMs) have recently demonstrated the potential in acting as autonomous agents for sequential decision-making tasks. We propose a closed-loop approach, AdaPlanner, which allows the LLM agent to refine its self-generated plan adaptively in response to environmental feedback. To mitigate hallucination, we develop a code-style LLM prompt structure that facilitates plan generation across a variety of tasks, environments, and agent capabilities.
  arXiv  Detail & Related papers  (2023-05-26T05:52:27Z)
• Planning to Practice: Efficient Online Fine-Tuning by Composing Goals in Latent Space [76.46113138484947]
  General-purpose robots require diverse repertoires of behaviors to complete challenging tasks in real-world unstructured environments. To address this issue, goal-conditioned reinforcement learning aims to acquire policies that can reach goals for a wide range of tasks on command. We propose Planning to Practice, a method that makes it practical to train goal-conditioned policies for long-horizon tasks.
  arXiv  Detail & Related papers  (2022-05-17T06:58:17Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.