Integer Programming for Multi-Robot Planning: A Column Generation Approach

• URL: http://arxiv.org/abs/2006.04856v1
• Date: Mon, 8 Jun 2020 18:19:14 GMT
• Title: Integer Programming for Multi-Robot Planning: A Column Generation Approach
• Authors: Naveed Haghani, Jiaoyang Li, Sven Koenig, Gautam Kunapuli, Claudio Contardo, Julian Yarkony
• Abstract summary: We consider the problem of coordinating a fleet of robots in a warehouse so as to maximize the reward achieved within a time limit. We formulate the problem as a weighted set packing problem where elements are defined as being the space-time positions a robot can occupy and the items that can be picked up and delivered. We enforce that robots do not collide, that each item is delivered at most once, and that the number of robots active at any time does not exceed the total number available.
• Score: 21.217989597414384
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of coordinating a fleet of robots in a warehouse so as to maximize the reward achieved within a time limit while respecting problem and robot specific constraints. We formulate the problem as a weighted set packing problem where elements are defined as being the space-time positions a robot can occupy and the items that can be picked up and delivered. We enforce that robots do not collide, that each item is delivered at most once, and that the number of robots active at any time does not exceed the total number available. Since the set of robot routes is not enumerable, we attack optimization using column generation where pricing is a resource-constrained shortest-path problem.

Related papers

• Multi-Robot Informative Path Planning for Efficient Target Mapping using Deep Reinforcement Learning [11.134855513221359]
  We propose a novel deep reinforcement learning approach for multi-robot informative path planning. We train our reinforcement learning policy via the centralized training and decentralized execution paradigm. Our approach outperforms other state-of-the-art multi-robot target mapping approaches by 33.75% in terms of the number of discovered targets-of-interest.
  arXiv  Detail & Related papers  (2024-09-25T14:27:37Z)
• 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)
• Decentralised construction of a global coordinate system in a large swarm of minimalistic robots [0.8701566919381223]
  In this study, we present an algorithm to enable positional self-awareness in a swarm of minimalistic error-prone robots. Despite being unable to measure the bearing of incoming messages, the robots running our algorithm can calculate their position within a swarm deployed in a regular formation. Our solution has fewer requirements than state-of-the-art algorithms and contains collective noise-filtering mechanisms.
  arXiv  Detail & Related papers  (2023-02-28T14:14:17Z)
• GenLoco: Generalized Locomotion Controllers for Quadrupedal Robots [87.32145104894754]
  We introduce a framework for training generalized locomotion (GenLoco) controllers for quadrupedal robots. Our framework synthesizes general-purpose locomotion controllers that can be deployed on a large variety of quadrupedal robots. We show that our models acquire more general control strategies that can be directly transferred to novel simulated and real-world robots.
  arXiv  Detail & Related papers  (2022-09-12T15:14:32Z)
• REvolveR: Continuous Evolutionary Models for Robot-to-robot Policy Transfer [57.045140028275036]
  We consider the problem of transferring a policy across two different robots with significantly different parameters such as kinematics and morphology. Existing approaches that train a new policy by matching the action or state transition distribution, including imitation learning methods, fail due to optimal action and/or state distribution being mismatched in different robots. We propose a novel method named $REvolveR$ of using continuous evolutionary models for robotic policy transfer implemented in a physics simulator.
  arXiv  Detail & Related papers  (2022-02-10T18:50:25Z)
• 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)
• Multi-Robot Routing with Time Windows: A Column Generation Approach [19.425263342626007]
  We consider the problem of coordinating a fleet of robots performing picking operations in a warehouse. We propose an efficient optimization scheme that avoids consideration of every increment within the time windows. We also propose a pricing algorithm that can efficiently solve the pricing subproblem.
  arXiv  Detail & Related papers  (2021-03-16T03:39:42Z)
• Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph Policy Gradients [122.85280150421175]
  We present a learning method to solve the unlabelled motion problem with motion constraints and space constraints in 2D space for a large number of robots. We employ a graph neural network (GNN) to parameterize policies for the robots.
  arXiv  Detail & Related papers  (2021-02-11T21:57:43Z)
• Co-Evolution of Multi-Robot Controllers and Task Cues for Off-World Open Pit Mining [0.6091702876917281]
  This paper presents a novel method for developing scalable controllers for use in multi-robot excavation and site-preparation scenarios. The controller starts with a blank slate and does not require human-authored operations scripts nor detailed modeling of the kinematics and dynamics of the excavator. In this paper, we explore the use of templates and task cues to improve group performance further and minimize antagonism.
  arXiv  Detail & Related papers  (2020-09-19T03:13:28Z)
• 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.