Simultaneous Task Allocation and Planning for Multi-Robots under
Hierarchical Temporal Logic Specifications
- URL: http://arxiv.org/abs/2401.04003v2
- Date: Fri, 12 Jan 2024 15:52:29 GMT
- Title: Simultaneous Task Allocation and Planning for Multi-Robots under
Hierarchical Temporal Logic Specifications
- Authors: Xusheng Luo and Changliu Liu
- Abstract summary: We introduce a hierarchical structure to specifications with requirements on syntax and semantics, and prove that they are more expressive than their flat counterparts.
We employ a search-based approach to synthesize plans for a multi-robot system, accomplishing simultaneous task allocation and planning.
- Score: 10.007538582534302
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Past research into robotic planning with temporal logic specifications,
notably Linear Temporal Logic (LTL), was largely based on singular formulas for
individual or groups of robots. But with increasing task complexity, LTL
formulas unavoidably grow lengthy, complicating interpretation and
specification generation, and straining the computational capacities of the
planners. By leveraging the intrinsic structure of tasks, we introduced a
hierarchical structure to LTL specifications with requirements on syntax and
semantics, and proved that they are more expressive than their flat
counterparts. Second, we employ a search-based approach to synthesize plans for
a multi-robot system, accomplishing simultaneous task allocation and planning.
The search space is approximated by loosely interconnected sub-spaces, with
each sub-space corresponding to one LTL specification. The search is
predominantly confined to a single sub-space, transitioning to another
sub-space under certain conditions, determined by the decomposition of
automatons. Moreover, multiple heuristics are formulated to expedite the search
significantly. A theoretical analysis concerning completeness and optimality is
conducted under mild assumptions. When compared with existing methods on
service tasks, our method outperforms in terms of execution times with
comparable solution quality. Finally, scalability is evaluated by testing a
group of 30 robots and achieving reasonable runtimes.
Related papers
- Conformal Temporal Logic Planning using Large Language Models [29.57952582715011]
This paper addresses a new motion planning problem for mobile robots tasked with accomplishing multiple high-level sub-tasks.
These sub-tasks should be accomplished in a temporal and logical order.
Our goal is to design robot plans that satisfy tasks defined over NL-based atomic propositions.
arXiv Detail & Related papers (2023-09-18T19:05:25Z) - 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) - 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) - A Memetic Algorithm with Reinforcement Learning for Sociotechnical
Production Scheduling [0.0]
This article presents a memetic algorithm with applying deep reinforcement learning (DRL) to flexible job shop scheduling problems (DRC-FJSSP)
From research projects in industry, we recognize the need to consider flexible machines, flexible human workers, worker capabilities, setup and processing operations, material arrival times, complex job paths with parallel tasks for bill of material manufacturing, sequence-dependent setup times and (partially) automated tasks in human-machine-collaboration.
arXiv Detail & Related papers (2022-12-21T11:24:32Z) - Fast Inference and Transfer of Compositional Task Structures for
Few-shot Task Generalization [101.72755769194677]
We formulate it as a few-shot reinforcement learning problem where a task is characterized by a subtask graph.
Our multi-task subtask graph inferencer (MTSGI) first infers the common high-level task structure in terms of the subtask graph from the training tasks.
Our experiment results on 2D grid-world and complex web navigation domains show that the proposed method can learn and leverage the common underlying structure of the tasks for faster adaptation to the unseen tasks.
arXiv Detail & Related papers (2022-05-25T10:44:25Z) - Neural Architecture Search From Fr\'echet Task Distance [50.9995960884133]
We show how the distance between a target task and each task in a given set of baseline tasks can be used to reduce the neural architecture search space for the target task.
The complexity reduction in search space for task-specific architectures is achieved by building on the optimized architectures for similar tasks instead of doing a full search without using this side information.
arXiv Detail & Related papers (2021-03-23T20:43:31Z) - 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) - Fast Decomposition of Temporal Logic Specifications for Heterogeneous
Teams [1.856334276134661]
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.
arXiv Detail & Related papers (2020-09-30T18:04:39Z) - 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) - MTL-NAS: Task-Agnostic Neural Architecture Search towards
General-Purpose Multi-Task Learning [71.90902837008278]
We propose to incorporate neural architecture search (NAS) into general-purpose multi-task learning (GP-MTL)
In order to adapt to different task combinations, we disentangle the GP-MTL networks into single-task backbones.
We also propose a novel single-shot gradient-based search algorithm that closes the performance gap between the searched architectures.
arXiv Detail & Related papers (2020-03-31T09:49:14Z)
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.