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
- 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) - Towards Practical Multi-Robot Hybrid Tasks Allocation for Autonomous
Cleaning [40.715435411065336]
We formulate multi-robot hybrid-task allocation under the uncertain cleaning environment as a robust optimization problem.
We establish a dataset of emph100 instances made from floor plans, each of which has 2D manually-labeled images and a 3D model.
We provide comprehensive results on the collected dataset using three traditional optimization approaches and a deep reinforcement learning-based solver.
arXiv Detail & Related papers (2023-03-12T01:15:08Z) - Logic programming for deliberative robotic task planning [2.610470075814367]
We present a survey on recent advances in the application of logic programming to the problem of task planning.
We analyze different planners and their suitability for specific robotic applications, based on expressivity in domain representation, computational efficiency and software implementation.
arXiv Detail & Related papers (2023-01-18T14:11:55Z) - 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) - Can Foundation Models Perform Zero-Shot Task Specification For Robot
Manipulation? [54.442692221567796]
Task specification is critical for engagement of non-expert end-users and adoption of personalized robots.
A widely studied approach to task specification is through goals, using either compact state vectors or goal images from the same robot scene.
In this work, we explore alternate and more general forms of goal specification that are expected to be easier for humans to specify and use.
arXiv Detail & Related papers (2022-04-23T19:39:49Z) - 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) - Learning Multi-Arm Manipulation Through Collaborative Teleoperation [63.35924708783826]
Imitation Learning (IL) is a powerful paradigm to teach robots to perform manipulation tasks.
Many real-world tasks require multiple arms, such as lifting a heavy object or assembling a desk.
We present Multi-Arm RoboTurk (MART), a multi-user data collection platform that allows multiple remote users to simultaneously teleoperate a set of robotic arms.
arXiv Detail & Related papers (2020-12-12T05:43:43Z) - 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.