論文の概要: Graph-Based Heuristics for Minimum Constraint Removal in Cluttered Robot Motion Planning
- arxiv url: http://arxiv.org/abs/2610.12609v1
- Date: Thu, 08 Oct 2026 18:30:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.248636
- Title: Graph-Based Heuristics for Minimum Constraint Removal in Cluttered Robot Motion Planning
- Title（参考訳）: クラッタロボット運動計画における最小制約除去のためのグラフベースヒューリスティック
- Abstract要約: 本稿では,実現可能な集合生成とMCRグラフ上の固定長探索を組み合わせたグラフベースパイプラインを提案する。
ベンチマークの1つでは、7つの妨害対象ではなく2つを選択することで、MCR、逆運動学、運動計画時間が84.72秒から30.59秒に短縮される。
- 参考スコア（独自算出の注目度）: 2.80151930790841
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Humanoid and service robots operating in clut- tered human environments may encounter motion planning problems that are infeasible when all surrounding objects are treated as fixed obstacles. The Minimum Constraint Removal problem, which we refer to as MCR, addresses this situation by identifying the minimum number of constraints, such as movable objects, whose removal enables a collision-free path. However, computing an optimal MCR solution is NP-hard. In this work, we propose a graph-based heuristic pipeline that combines bidirectional feasible-set generation with fixed- length searches over reduced MCR graphs. We further derive an extended feasible-set generator for instances in which the candidates produced by the first generator do not contain a complete optimal removal set. Across six benchmarks, the evaluated pipeline matches the exact solution in three cases and, in the remaining cases, selects at most 31.25% more obstacles than the optimum, while being between 3.4 and 33.7 times faster than exact search. In one of the benchmarks, involving a manipulation task amidst clutter, selecting two rather than seven obstructing objects reduces the combined MCR, inverse- kinematics, and motion planning time from 84.72 s to 30.59 s. These results indicate that the proposed approach provides a practical compromise between computational efficiency and solution quality for motion planning among movable obstacles.
- Abstract（参考訳）: 人型ロボットやサービスロボットは、周囲の物体が固定された障害物として扱われると不可能な動作計画問題に遭遇する可能性がある。
MCRと呼ばれる最小制約除去問題は、衝突のない経路を可能にする可動物体などの最小限の制約を識別することで、この問題に対処する。
しかし、最適MCR解の計算はNPハードである。
本研究では,MCRグラフの最小長探索と双方向のファジブル・セット生成を組み合わせたグラフベースのヒューリスティック・パイプラインを提案する。
さらに、第1生成元が生成する候補が完全な最適除去セットを含まないインスタンスに対して、拡張可能な生成元を導出する。
6つのベンチマークで、評価されたパイプラインは3つのケースで正確な解と一致し、残りのケースでは、最適値よりも少なくとも31.25%多くの障害を選択し、正確な探索の3.4倍から33.7倍の速度である。
クラッタ中の操作タスクを含むベンチマークの1つでは、7つの障害物物体ではなく2つを選択することで、MCR、逆運動学、運動計画時間が84.72秒から30.59秒に短縮される。
これらの結果から, 移動障害物間の運動計画における計算効率と解の質との間には, 現実的な妥協がもたらされることが示唆された。
関連論文リスト
- A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation [4.380320667336912]
この問題は計算的に困難であり、特に、障害物が平面上のポリゴンとしてモデル化される場合、NPハードであることが示される。
本稿では,計算の立場から計算量が少ない近似解を提案する。
論文 参考訳（メタデータ） (2026-09-19T11:51:40Z) - LOInK: Learned Optimal Inverse Kinematics via Structured Neural Surrogate Models [5.583126580016643]
本稿では,逆キネマティクス問題に対する近似最適解を生成する方法であるLearned Optimal Inverse Kinematics (LOInK)を紹介する。
LOInKは、構成空間から切り離されたタスク/遅延空間へのバイリプシッツ可逆写像を学習する。
制限された最適化アプローチよりも平均31倍、最大100倍高速で、ほぼ最適解を生成することができる。
論文 参考訳（メタデータ） (2026-09-18T03:41:25Z) - Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
本稿では,最小時間移動計画凸障害物に対して,収束が保証されるバイアプローチを提案する。
提案手法は,変数の最先端分解を生成するために,時間とともに高品質な軌道を生成する。
論文 参考訳（メタデータ） (2026-08-03T19:48:24Z) - Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
乱雑な環境におけるマルチロボット制御は、複雑な物理的制約を伴う難しい問題である。
タスクとモーションプランニングを協調的に最適化するハイブリッドマルチロボット制御フレームワークを提案する。
我々のアプローチは、動作に依存しないベースラインとVLAベースのベースラインよりもタスクの成功を継続的に改善する。
論文 参考訳（メタデータ） (2026-04-22T22:58:47Z) - Integrated Multi-Drone Task Allocation, Sequencing, and Optimal Trajectory Generation in Obstacle-Rich 3D Environments [0.0]
IMD-TAPP(Integrated Multi-Drone Task Allocation and Path Planning)は,多ゴールアロケーション,ツアーシークエンシング,および障害物の多い空間で動作する四角形チームのための安全な軌道生成を行うエンドツーエンドのフレームワークである。
複数の目標を達成する2つのドローンによる代表的なケーススタディでは、提案手法は実行中に必要な安全制約を維持しながら、最低ミッション時間は136秒に達する。
論文 参考訳（メタデータ） (2026-03-26T00:46:26Z) - Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
マルチロボット運動計画(MPMP)は、共有された連続作業空間で動作する複数のロボットのための軌道を生成する。
離散マルチエージェント探索(MAPF)法は,その拡張性から広く採用されているが,粗い離散化の軌道品質は高い。
本稿では、制約付き生成拡散モデルを用いた離散MAPF解法を導入することにより、2つのアプローチの限界に対処する。
論文 参考訳（メタデータ） (2025-08-27T17:59:36Z) - Self-Adaptive Ising Machines for Constrained Optimization [0.4450107621124637]
制約のラグランジュ緩和を用いてエネルギー景観を形作る自己適応型IMを提案し, 罰則の事前調整を回避する。
我々は,多次元クナップサック問題 (MKP) と二次クナップサック問題 (QKP) でアルゴリズムをベンチマークし,後者は線形制約を持つイジング問題である。
その結果,探索中にエネルギー環境に適応することで,制約付き最適化のためにIMを高速化できることが示唆された。
論文 参考訳（メタデータ） (2025-01-09T05:02:50Z) - A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot
Systems [6.853165736531941]
マルチロボットアプリケーションは、衝突のない経路を確保しながら、各ロボットにユニークな目標を割り当てることを目的としている。
そこで本研究では,次の最適な割り当てを計算するための効率的な競合誘導手法を提案する。
複数のベンチマークワークスペース上で,最大100個のロボットに対して,我々のアルゴリズムを広範囲に評価した。
論文 参考訳（メタデータ） (2024-02-19T19:04:19Z) - DDPEN: Trajectory Optimisation With Sub Goal Generation Model [70.36888514074022]
本稿では,エスケープネットワークを用いた微分動的プログラミング(DDPEN)を提案する。
本稿では,環境の入力マップとして,所望の位置とともにコストマップの形で利用する深層モデルを提案する。
このモデルは、目標に導く可能性のある将来の方向を生成し、リアルタイムに実行可能なローカルなミニマを避ける。
論文 参考訳（メタデータ） (2023-01-18T11:02:06Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - MLE-guided parameter search for task loss minimization in neural
sequence modeling [83.83249536279239]
ニューラル自己回帰シーケンスモデルは、さまざまな自然言語処理(NLP)タスクのシーケンスを生成するために使用される。
本稿では,現在のパラメータとその周辺における乱探索の混合である更新方向の分布から,最大至適勾配の分布をサンプリングする,最大至適誘導パラメータ探索(MGS)を提案する。
以上の結果から,MGS は,機械翻訳における最小リスクトレーニングに比べて,繰り返しや非終端の大幅な削減を図り,シーケンスレベルの損失を最適化できることが示唆された。
論文 参考訳（メタデータ） (2020-06-04T22:21:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。