Multi-Robot Task Allocation -- Complexity and Approximation
- URL: http://arxiv.org/abs/2103.12370v1
- Date: Tue, 23 Mar 2021 08:12:27 GMT
- Title: Multi-Robot Task Allocation -- Complexity and Approximation
- Authors: Haris Aziz, Hau Chan, \'Agnes Cseh, Bo Li, Fahimeh Ramezani, Chenhao
Wang
- Abstract summary: Multi-robot task allocation is crucial for various real-world robotic applications such as search, rescue and area exploration.
We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task.
- Score: 37.231854068835005
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-robot task allocation is one of the most fundamental classes of
problems in robotics and is crucial for various real-world robotic applications
such as search, rescue and area exploration. We consider the Single-Task robots
and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each
task requires at least a certain number of robots and each robot can work on at
most one task and incurs an operational cost for each task. Our aim is to
consider a natural computational problem of allocating robots to complete the
maximum number of tasks subject to budget constraints. We consider budget
constraints of three different kinds: (1) total budget, (2) task budget, and
(3) robot budget. We provide a detailed complexity analysis including results
on approximations as well as polynomial-time algorithms for the general setting
and important restricted settings.
Related papers
- $\textbf{EMOS}$: $\textbf{E}$mbodiment-aware Heterogeneous $\textbf{M}$ulti-robot $\textbf{O}$perating $\textbf{S}$ystem with LLM Agents [33.77674812074215]
We introduce a novel multi-agent framework designed to enable effective collaboration among heterogeneous robots.
We propose a self-prompted approach, where agents comprehend robot URDF files and call robot kinematics tools to generate descriptions of their physics capabilities.
The Habitat-MAS benchmark is designed to assess how a multi-agent framework handles tasks that require embodiment-aware reasoning.
arXiv Detail & Related papers (2024-10-30T03:20:01Z) - COHERENT: Collaboration of Heterogeneous Multi-Robot System with Large Language Models [49.24666980374751]
COHERENT is a novel LLM-based task planning framework for collaboration of heterogeneous multi-robot systems.
A Proposal-Execution-Feedback-Adjustment mechanism is designed to decompose and assign actions for individual robots.
The experimental results show that our work surpasses the previous methods by a large margin in terms of success rate and execution efficiency.
arXiv Detail & Related papers (2024-09-23T15:53:41Z) - Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations.
We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation.
In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
arXiv Detail & Related papers (2024-08-29T20:22:22Z) - RoboScript: Code Generation for Free-Form Manipulation Tasks across Real
and Simulation [77.41969287400977]
This paper presents textbfRobotScript, a platform for a deployable robot manipulation pipeline powered by code generation.
We also present a benchmark for a code generation benchmark for robot manipulation tasks in free-form natural language.
We demonstrate the adaptability of our code generation framework across multiple robot embodiments, including the Franka and UR5 robot arms.
arXiv Detail & Related papers (2024-02-22T15:12:00Z) - Task Allocation using a Team of Robots [29.024300177453824]
We present a general formulation of the task allocation problem that generalizes several versions that are well-studied.
Our formulation includes the states of robots, tasks, and the surrounding environment in which they operate.
We describe how the problem can vary depending on the feasibility constraints, objective functions, and the level of dynamically changing information.
arXiv Detail & Related papers (2022-07-20T04:49:11Z) - Lifelong Robotic Reinforcement Learning by Retaining Experiences [61.79346922421323]
Many multi-task reinforcement learning efforts assume the robot can collect data from all tasks at all times.
In this work, we study a practical sequential multi-task RL problem motivated by the practical constraints of physical robotic systems.
We derive an approach that effectively leverages the data and policies learned for previous tasks to cumulatively grow the robot's skill-set.
arXiv Detail & Related papers (2021-09-19T18:00:51Z) - Towards Coordinated Robot Motions: End-to-End Learning of Motion
Policies on Transform Trees [63.31965375413414]
We propose to solve multi-task problems through learning structured policies from human demonstrations.
Our structured policy is inspired by RMPflow, a framework for combining subtask policies on different spaces.
We derive an end-to-end learning objective function that is suitable for the multi-task problem.
arXiv Detail & Related papers (2020-12-24T22:46:22Z) - Enabling human-like task identification from natural conversation [7.00597813134145]
We provide a non-trivial method to combine an NLP engine and a planner such that a robot can successfully identify tasks and all the relevant parameters and generate an accurate plan for the task.
This work makes a significant stride towards enabling a human-like task understanding capability in a robot.
arXiv Detail & Related papers (2020-08-23T17:19:23Z) - Optimal Sequential Task Assignment and Path Finding for Multi-Agent
Robotic Assembly Planning [42.38068056643171]
We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints.
We propose a hierarchical algorithm for computing makespan-optimal solutions to the problem.
arXiv Detail & Related papers (2020-06-16T00:45:07Z)
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.