Fast Decomposition of Temporal Logic Specifications for Heterogeneous Teams

• URL: http://arxiv.org/abs/2010.00030v1
• Date: Wed, 30 Sep 2020 18:04:39 GMT
• Title: Fast Decomposition of Temporal Logic Specifications for Heterogeneous Teams
• Authors: Kevin Leahy, Austin Jones, Cristian-Ioan Vasile
• Abstract summary: We focus on decomposing large multi-agent path planning problems into smaller sub-problems that can be solved and executed independently. The agents' missions are given as Capability Temporal Logic (CaTL) formulas, a fragment of signal temporal logic. The approach we take is to decompose both the temporal logic specification and the team of agents.
• Score: 1.856334276134661
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we focus on decomposing large multi-agent path planning problems with global temporal logic goals (common to all agents) into smaller sub-problems that can be solved and executed independently. Crucially, the sub-problems' solutions must jointly satisfy the common global mission specification. The agents' missions are given as Capability Temporal Logic (CaTL) formulas, a fragment of signal temporal logic, that can express properties over tasks involving multiple agent capabilities (sensors, e.g., camera, IR, and effectors, e.g., wheeled, flying, manipulators) under strict timing constraints. The approach we take is to decompose both the temporal logic specification and the team of agents. We jointly reason about the assignment of agents to subteams and the decomposition of formulas using a satisfiability modulo theories (SMT) approach. The output of the SMT is then distributed to subteams and leads to a significant speed up in planning time. We include computational results to evaluate the efficiency of our solution, as well as the trade-offs introduced by the conservative nature of the SMT encoding.

Related papers

• Decomposition-based Hierarchical Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications [9.150196865878234]
  We formulate a decomposition-based hierarchical framework for robotic planning with temporal logic specifications. A Mixed Linear Program is used to assign sub-tasks to various robots. Our approach was experimentally applied to domains of navigation and manipulation.
  arXiv  Detail & Related papers  (2023-08-20T23:53:13Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• On the Complexity of Rational Verification [5.230352342979224]
  Rational verification refers to the problem of checking which temporal logic properties hold of a concurrent multiagent system. We show that the complexity of rational verification can be greatly reduced by specifications. We provide improved results for rational verification when considering players' goals given by mean-payoff utility functions.
  arXiv  Detail & Related papers  (2022-07-06T12:56:22Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence. We present a method that mitigates this issue to a certain extent.
  arXiv  Detail & Related papers  (2021-08-11T10:42:11Z)
• Multi-Agent Reinforcement Learning with Temporal Logic Specifications [65.79056365594654]
  We study the problem of learning to satisfy temporal logic specifications with a group of agents in an unknown environment. We develop the first multi-agent reinforcement learning technique for temporal logic specifications. We provide correctness and convergence guarantees for our main algorithm.
  arXiv  Detail & Related papers  (2021-02-01T01:13:03Z)
• Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems [10.781866671930851]
  We tackle the problem of multiagent pathfinding under uncertainty and partial observability. We use propositional logic and integrate them with the RL algorithms to enable fast simulation for RL.
  arXiv  Detail & Related papers  (2020-11-09T13:13:54Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks. This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions. We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• 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.