Distributed Allocation and Scheduling of Tasks with Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams

• URL: http://arxiv.org/abs/2109.03089v1
• Date: Tue, 7 Sep 2021 13:44:28 GMT
• Title: Distributed Allocation and Scheduling of Tasks with Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams
• Authors: Barbara Arbanas Ferreira, Tamara Petrovi\'c, Matko Orsag, J. Ramiro Mart\'inez-de-Dios, Stjepan Bogdan
• Abstract summary: We present a distributed task allocation and scheduling algorithm for missions where the tasks of different robots are tightly coupled with temporal and precedence constraints. An application of the planning procedure to a practical use case of a greenhouse maintained by a multi-robot system is given.
• Score: 2.294915015129229
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: To enable safe and efficient use of multi-robot systems in everyday life, a robust and fast method for coordinating their actions must be developed. In this paper, we present a distributed task allocation and scheduling algorithm for missions where the tasks of different robots are tightly coupled with temporal and precedence constraints. The approach is based on representing the problem as a variant of the vehicle routing problem, and the solution is found using a distributed metaheuristic algorithm based on evolutionary computation (CBM-pop). Such an approach allows a fast and near-optimal allocation and can therefore be used for online replanning in case of task changes. Simulation results show that the approach has better computational speed and scalability without loss of optimality compared to the state-of-the-art distributed methods. An application of the planning procedure to a practical use case of a greenhouse maintained by a multi-robot system is given.

Related papers

• Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks [60.085771314013044]
  Low-altitude economy holds significant potential for development in areas such as communication and sensing. We propose a Clustering-based Multi-agent Deep Deterministic Policy Gradient (CMADDPG) algorithm to address the multi-UAV cooperative task scheduling challenges in SAGIN.
  arXiv  Detail & Related papers  (2024-12-14T06:17:33Z)
• A Hybrid Evolutionary Approach for Multi Robot Coordinated Planning at Intersections [0.0]
  Coordinated multi-robot motion planning at intersections is key for safe mobility in roads, factories and warehouses. We propose a new evolutionary-based algorithm using a parametric lattice-based configuration and the discrete-based RRT for collision-free multi-robot planning at intersections.
  arXiv  Detail & Related papers  (2024-12-02T03:40:04Z)
• Dependency-Aware CAV Task Scheduling via Diffusion-Based Reinforcement Learning [12.504232513881828]
  We propose a novel dependency-aware task scheduling strategy for dynamic unmanned aerial vehicle-assisted connected autonomous vehicles (CAVs) We formulate a joint scheduling priority and subtask assignment optimization problem with the objective of minimizing the average task completion time. We propose a diffusion-based reinforcement learning algorithm, named Synthetic DDQN based Subtasks Scheduling, which can make adaptive task scheduling decision in real time.
  arXiv  Detail & Related papers  (2024-11-27T11:07:31Z)
• 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)
• Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences [20.879194337982803]
  Multi-Agent Path-Finding (MAPF) algorithms have shown promise in discrete 2D domains, providing rigorous guarantees. We propose an approach for accelerating conflict-based search algorithms by leveraging their repetitive and incremental nature.
  arXiv  Detail & Related papers  (2024-03-29T20:31:07Z)
• A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems [6.853165736531941]
  A multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths. We propose an efficient conflict-guided method to compute the next best assignment. We extensively evaluate our algorithm for up to a hundred robots on several benchmark workspaces.
  arXiv  Detail & Related papers  (2024-02-19T19:04:19Z)
• Distributed Mission Planning of Complex Tasks for Heterogeneous Multi-Robot Teams [2.329625852490423]
  We propose a distributed multi-stage optimization method for planning complex missions for heterogeneous multi-robot teams. The proposed approach involves a multi-objective search of the mission, represented as a hierarchical tree that defines the mission goal. We demonstrate the method's ability to adapt the planning strategy depending on the available robots and the given optimization criteria.
  arXiv  Detail & Related papers  (2021-09-21T11:36:11Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• 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)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.