論文の概要: Optimal Task Assignment and Path Planning using Conflict-Based Search
with Precedence and Temporal Constraints
- arxiv url: http://arxiv.org/abs/2402.08772v1
- Date: Tue, 13 Feb 2024 20:07:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 17:42:31.740368
- Title: Optimal Task Assignment and Path Planning using Conflict-Based Search
with Precedence and Temporal Constraints
- Title（参考訳）: 先行制約と時間制約を考慮した衝突探索による最適タスク割り当てと経路計画
- Authors: Yu Quan Chong, Jiaoyang Li, Katia Sycara
- Abstract要約: 本稿では,TAPF-PTC問題におけるタスク割り当てと経路探索について検討する。
我々は、競合ベースの検索(CBS)を拡張して、優先度と時間的制約に従うタスク割り当てと衝突のない経路を同時に生成する。
実験により,我々のアルゴリズムであるCBS-TA-PTCは,優先度と時間的制約を効果的に解決できることを示した。
- 参考スコア（独自算出の注目度）: 5.9176395108304805
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Multi-Agent Path Finding (MAPF) problem entails finding collision-free
paths for a set of agents, guiding them from their start to goal locations.
However, MAPF does not account for several practical task-related constraints.
For example, agents may need to perform actions at goal locations with specific
execution times, adhering to predetermined orders and timeframes. Moreover,
goal assignments may not be predefined for agents, and the optimization
objective may lack an explicit definition. To incorporate task assignment, path
planning, and a user-defined objective into a coherent framework, this paper
examines the Task Assignment and Path Finding with Precedence and Temporal
Constraints (TAPF-PTC) problem. We augment Conflict-Based Search (CBS) to
simultaneously generate task assignments and collision-free paths that adhere
to precedence and temporal constraints, maximizing an objective quantified by
the return from a user-defined reward function in reinforcement learning (RL).
Experimentally, we demonstrate that our algorithm, CBS-TA-PTC, can solve highly
challenging bomb-defusing tasks with precedence and temporal constraints
efficiently relative to MARL and adapted Target Assignment and Path Finding
(TAPF) methods.
- Abstract（参考訳）: MAPF(Multi-Agent Path Finding)問題では、エージェントの集合に対する衝突のないパスを見つけ出し、開始時点から目標地点まで誘導する。
しかしMAPFは、いくつかの実用的なタスク関連の制約を考慮していない。
例えば、エージェントは特定の実行時間でゴール位置でアクションを実行し、所定の順序と時間枠に従う必要がある。
さらに、目標の割り当てはエージェントに対して事前に定義されず、最適化の目的には明確な定義が欠落する可能性がある。
本稿では,タスクの割り当て,経路計画,ユーザ定義の目的をコヒーレントなフレームワークに組み込むため,タスクの割り当てと経路探索を優先順位と時間的制約(tapf-ptc)の問題で検討する。
RL(Regress Learning)におけるユーザ定義報酬関数の戻りによって定量化される目的を最大化することにより,優先的制約と時間的制約に従うタスク代入と衝突のない経路を同時に生成する。
実験により,本アルゴリズムであるcbs-ta-ptc は marl に対する優先度と時間制約を効率的に処理し,目標割当・経路探索 (tapf) 法を適用できることを実証した。
関連論文リスト
- Learning Hidden Subgoals under Temporal Ordering Constraints in Reinforcement Learning [14.46490764849977]
本稿では, bf 順序付き bf 制約 (LSTOC) に基づく bf l 隠れ bf サブゴールに対する新しい RL アルゴリズムを提案する。
本研究では,隠れたサブゴールとその時間的順序を同時に学習できる新しいコントラスト学習目標を提案する。
論文 参考訳（メタデータ） (2024-11-03T03:22:39Z) - Unified Task and Motion Planning using Object-centric Abstractions of
Motion Constraints [56.283944756315066]
本稿では,タスクとモーションプランニングを一つの検索に統一するTAMP手法を提案する。
我々のアプローチは、オフザシェルフAIサーチの計算効率を活用して、物理的に実現可能な計画が得られるような、オブジェクト中心の動作制約の抽象化に基づいている。
論文 参考訳（メタデータ） (2023-12-29T14:00:20Z) - Reinforcement Learning with Success Induced Task Prioritization [68.8204255655161]
本稿では,自動カリキュラム学習のためのフレームワークであるSuccess induced Task Prioritization (SITP)を紹介する。
アルゴリズムはエージェントに最速の学習を提供するタスクの順序を選択する。
我々は,SITPが他のカリキュラム設計手法と一致するか,あるいは上回っていることを実証する。
論文 参考訳（メタデータ） (2022-12-30T12:32:43Z) - Planning to Practice: Efficient Online Fine-Tuning by Composing Goals in
Latent Space [76.46113138484947]
汎用ロボットは、現実世界の非構造環境において困難なタスクを完了するために、多様な行動レパートリーを必要とする。
この問題に対処するため、目標条件強化学習は、コマンド上の幅広いタスクの目標に到達可能なポリシーを取得することを目的としている。
本研究では,長期的課題に対する目標条件付き政策を実践的に訓練する手法であるPlanning to Practiceを提案する。
論文 参考訳（メタデータ） (2022-05-17T06:58:17Z) - Optimal Multi-Agent Path Finding for Precedence Constrained Planning
Tasks [0.7742297876120561]
我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。
そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。
本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
論文 参考訳（メタデータ） (2022-02-08T07:26:45Z) - Conflict-Averse Gradient Descent for Multi-task Learning [56.379937772617]
マルチタスクモデルを最適化する際の大きな課題は、矛盾する勾配である。
本稿では、平均損失関数を最小化する衝突-逆勾配降下(CAGrad)を導入する。
CAGradは目標を自動的にバランスし、平均損失よりも最小限に確実に収束する。
論文 参考訳（メタデータ） (2021-10-26T22:03:51Z) - C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
ゴール条件強化学習は、ナビゲーションや操作を含む幅広い領域のタスクを解決できる。
本研究では,学習時間における探索を用いて,中間状態を自動生成する遠隔目標獲得タスクを提案する。
E-stepはグラフ検索を用いて最適な経路点列を計画することに対応し、M-stepはそれらの経路点に到達するための目標条件付きポリシーを学習することを目的としている。
論文 参考訳（メタデータ） (2021-10-22T22:05:31Z) - Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
k-Robust Conflict-BasedSearch (k-CBS)は、最大k遅延のロバストな座標と衝突のない計画を生成するアルゴリズムです。
そこで我々は,k-robust計画に特有な様々な対称性の破れ制約を導入し,矛盾するエージェントのペアに対して,効率よく相反する最適経路を見つける。
論文 参考訳（メタデータ） (2021-02-17T11:09:33Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳（メタデータ） (2021-01-11T10:42:38Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。