論文の概要: Multi-Robot Routing with Time Windows: A Column Generation Approach
- arxiv url: http://arxiv.org/abs/2103.08835v1
- Date: Tue, 16 Mar 2021 03:39:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-17 13:21:08.162563
- Title: Multi-Robot Routing with Time Windows: A Column Generation Approach
- Title（参考訳）: タイムウインドウを用いたマルチロボットルーティング:列生成アプローチ
- Authors: Naveed Haghani, Jiaoyang Li, Sven Koenig, Gautam Kunapuli, Claudio
Contardo, Amelia Regan, Julian Yarkony
- Abstract要約: 倉庫内でのピッキング作業を行うロボット群をコーディネートすることの問題点を考察する。
我々は,時間内インクリメントの考慮を回避する効率的な最適化手法を提案する。
また,価格サブ問題を効率的に解くための価格アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 19.425263342626007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Robots performing tasks in warehouses provide the first example of
wide-spread adoption of autonomous vehicles in transportation and logistics.
The efficiency of these operations, which can vary widely in practice, are a
key factor in the success of supply chains. In this work we consider the
problem of coordinating a fleet of robots performing picking operations in a
warehouse so as to maximize the net profit achieved within a time period while
respecting problem- and robot-specific constraints. We formulate the problem as
a weighted set packing problem where the elements in consideration are items on
the warehouse floor that can be picked up and delivered within specified time
windows. We enforce the constraint that robots must not collide, that each item
is picked up and delivered by at most one robot, and that the number of robots
active at any time does not exceed the total number available. Since the set of
routes is exponential in the size of the input, we attack optimization of the
resulting integer linear program using column generation, where pricing amounts
to solving an elementary resource-constrained shortest-path problem. We propose
an efficient optimization scheme that avoids consideration of every increment
within the time windows. We also propose a heuristic pricing algorithm that can
efficiently solve the pricing subproblem. While this itself is an important
problem, the insights gained from solving these problems effectively can lead
to new advances in other time-widow constrained vehicle routing problems.
- Abstract（参考訳）: 倉庫でタスクを実行するロボットは、輸送と物流に自動運転車を広く採用する最初の例である。
これらの作業の効率は、実際に広く変化する可能性があるが、サプライチェーンの成功の重要な要因である。
本研究では,倉庫内でピッキング作業を行うロボット群を協調させ,問題やロボット特有の制約を尊重しながら,時間内に達成した純利益を最大化する問題を考える。
本稿では, 倉庫床の要素が所定の時間窓で拾い上げ, 届けられる商品である重み付け組立問題として, 問題を定式化する。
我々は、ロボットが衝突してはならないという制約を課し、各アイテムが少なくとも1つのロボットによって拾われて配送されるようにし、いつでも活動するロボットの数は利用可能な総数を超えないようにする。
経路の集合は入力の大きさが指数関数的であるので、列生成による整数線形プログラムの最適化を攻撃し、そこでは、基本資源制約された最短経路問題の解決に費用がかかる。
我々は,時間内インクリメントの考慮を回避する効率的な最適化手法を提案する。
また,価格帯を効率的に解くことができるヒューリスティック価格アルゴリズムを提案する。
これはそれ自体が重要な問題であるが、これらの問題を解決することで得られた洞察は、他の時間制限された車両ルーティング問題に新たな進歩をもたらす可能性がある。
関連論文リスト
- Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
本稿では,ワークステーションの注文処理,アイテムポッドの割り当て,ワークステーションでの注文処理のスケジュールを最適化することで,ウェアハウジングにおけるロボット部品対ピッカー操作を支援する。
そこで我々は, 大規模近傍探索を用いて, サブプロブレム生成に対する学習を最適化する手法を提案する。
Amazon Roboticsと共同で、我々のモデルとアルゴリズムは、最先端のアプローチよりも、実用的な問題に対するより強力なソリューションを生み出していることを示す。
論文 参考訳（メタデータ） (2024-08-29T20:22:22Z) - Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses [1.2810395420131764]
MAPF(Multi-Agent Path Finding)は、自動倉庫や工場にロボットを配置する際の重要な最適化問題である。
ロボットの群れが各注文の商品を棚からワークステーションに届ける倉庫において、オンラインでの注文配達の現実的な問題を考える。
これにより、相互依存型ピックアップおよびデリバリタスクのストリームが生成され、関連するMAPF問題は、現実的な衝突のないロボット軌道の計算によって構成される。
論文 参考訳（メタデータ） (2024-08-26T15:13:38Z) - DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in
Complex Environments [55.204450019073036]
本稿では,倉庫環境における移動ロボットのためのタスク割り当てと分散ナビゲーションアルゴリズムを提案する。
本稿では,共同分散タスク割り当てとナビゲーションの問題について考察し,それを解決するための2段階のアプローチを提案する。
ロボットの衝突のない軌道の計算では,タスク完了時間において最大14%の改善と最大40%の改善が観察される。
論文 参考訳（メタデータ） (2022-09-07T00:35:27Z) - Simultaneous Contact-Rich Grasping and Locomotion via Distributed
Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
移動, 把握, 接触問題を同時に解くための効率的な運動計画フレームワークを提案する。
ハードウェア実験において提案手法を実証し, より短い計画時間で, 傾斜角45degで自由クライミングを含む様々な動作を実現できることを示す。
論文 参考訳（メタデータ） (2022-07-04T13:52:10Z) - Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
本稿では,最小時間ステップにおけるシーンマップ構築の完全化を目的としたマルチロボットアクティブマッピングの問題点について検討する。
この問題の鍵は、より効率的なロボットの動きを可能にするゴール位置推定にある。
本稿では,ニューラルコマッピング(NeuralCoMapping)という新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-30T14:03:17Z) - Machine-learning-based arc selection for constrained shortest path
problems in column generation [5.08128537391027]
本研究では,機械学習に基づく新しい価格アルゴリズムを提案する。
目的は、ネットワークのサイズを小さくし、PPを加速することであり、線形緩和溶液の一部となる確率の高い弧のみを保持することである。
この方法は、公共交通機関における車両と乗員のスケジューリング問題と、時間窓による車両のルーティング問題という2つの特定の問題に適用されている。
論文 参考訳（メタデータ） (2022-01-07T16:49:12Z) - Large Scale Distributed Collaborative Unlabeled Motion Planning with
Graph Policy Gradients [122.85280150421175]
本研究では,運動制約と空間制約を多数のロボットに対して2次元空間で解くための学習法を提案する。
ロボットのポリシーをパラメータ化するためにグラフニューラルネットワーク(GNN)を用いる。
論文 参考訳（メタデータ） (2021-02-11T21:57:43Z) - Optimal Sequential Task Assignment and Path Finding for Multi-Agent
Robotic Assembly Planning [42.38068056643171]
本研究では,タスク間優先制約のあるアプリケーションにおいて,ロボットの大規模チームに対する逐次的タスク割り当てと衝突のないルーティングの問題について検討する。
本稿では,その問題に対する等間隔最適解を計算するための階層的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T00:45:07Z) - Integer Programming for Multi-Robot Planning: A Column Generation
Approach [21.217989597414384]
本研究では,倉庫内のロボット群を,一定時間内に達成した報酬を最大化するために調整する問題を考察する。
本稿では,ロボットが占有できる時空の位置として要素が定義される重み付けセットパッキング問題として,その問題を定式化する。
ロボットは衝突せず、各アイテムが最大1回配達され、常にアクティブなロボットの数が利用可能な総数を超えないことを強制する。
論文 参考訳（メタデータ） (2020-06-08T18:19:14Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。