Open Source Robotics

高品質なオープンソースロボティクスプロジェクト、ツール、ソフトウェアの厳選コレクション。

PV-OSIMr: A Lowest Order Complexity Algorithm for Computing the Delassus Matrix

著者: Ajay Suresha Sathya, Wilm Decré, Jan Swevers · IEEE Robotics and Automation Letters (RA-L) 2024

ライセンス

  • オープンアクセス
  • 論文: CC BY-SA 4.0

以下の内容はすべて、論文のライセンス（CC BY-SA 4.0）に従い論文全文に基づいています。図は著者のクレジットを付けて掲載しています。

要約

PV-OSIM の計算順序を組み替えて、伝播される拘束が 6 次元を超えないようにし、Delassus 行列を O(n + m²) で計算する。著者らはこれが漸近的に最適であることを示している。

重要な理由

足と多指ハンドを持つヒューマノイドのように接触の多いロボットは、シミュレーションと制御のためにこの行列を高いレートで必要とするため、演算が少ないほどソルバは速くなる。m × m 行列の構築と全 n 関節の走査は避けられないため、著者らは O(n + m²) が最適なオーダーであると主張している。このアルゴリズムは CasADi のコード生成で実装され、論文によれば Pinocchio ライブラリにも C++ で実装された。

課題

Delassus 行列、すなわち逆操作空間慣性行列は、拘束力と拘束加速度を結び付けるものであり、拘束付き・接触ダイナミクスのシミュレーションや操作空間制御に必要で、MPC や RL ではしばしば最もコストの高いステップとなる。素朴に計算すると O(n³ + m²n) のコストがかかる。既知の最良アルゴリズムである EFPA は O(n + md + m²) を達成しているが、著者らの以前の PV-OSIM は O(n + m²d) であり、多数の拘束を多数の関節を通して伝播しなければならない場合にスケールしにくい。

提案手法

PV-OSIMr は PV-OSIM の後退スイープを修正し、拘束数とともに大きくなる拘束空間行列を伝播する代わりに、連続する分岐リンク（集合 N）の間で固定サイズ 6×6 の拡張力プロパゲータと空間逆慣性を伝播する。N 上の限定的な前進スイープで逆慣性を計算し、限定的な後退スイープで各エンドエフェクタの拘束空間プロパゲータを計算し、Delassus 行列の各ブロックを定数時間で組み立てる。これにより O(n + m²) の計算量が得られる。

主な知見

  • あるリンクが 6 を超える拘束次元を支える場合、拘束空間の項を直接伝播するより、6D の空間量を伝播して後から拘束空間の項を復元するほうが安価である。
  • コストの高い量は拘束されたリンクの最近共通祖先でのみ計算すればよいため、追加のスイープは縮小されたリンク集合の上でのみ実行される。
  • 漸近的計算量が低くても、小型ロボットで演算回数が少なくなるとは限らない。EFPA は 3 回のスイープ構造とリンクごとの座標変換のために、試験したほぼすべての機構で PV-OSIM や PV-OSIMr よりコストが高かった。
  • LTL-OSIM は計算量が高いにもかかわらず、単一の Shadow ハンドでは EFPA を上回った。ハンドの分岐構造が、LTL-OSIM が活用できる疎性を生むためである。

主な結果

  • 計算量：PV-OSIMr は O(n + m²)、これに対し PV-OSIM は O(n + m²d)、EFPA は O(n + md + m²)、KJR は O(n + m²d)、LTL-OSIM は O(nd² + m²d + md²)、素朴な方法は O(n³ + m²n)。
  • 片足あたり 4 つの 3D 点接触（片足あたり 12D）で立つ Atlas：PV-OSIM は PV-OSIMr より 19.9% 多い演算を必要とした。片足あたり 1 つの 6D 溶接拘束の場合、2 つのアルゴリズムは同一であった。
  • Shadow ハンド付きの Atlas（指先ごとに 3D 拘束、片手あたり 15D）：Section IV-D では次に効率的なアルゴリズムである PV-OSIM より最大約 34% 少ない演算と報告されている一方、Conclusions では Atlas の例で最大 24% の改善と述べられている。
  • 各分岐の先端に 6D 溶接拘束を持つ分岐テスト機構では、PV-OSIMr は分岐が 1 本のとき PV-OSIM と同等で、2 本以上ではより緩やかにスケールした。片側 10 本の分岐を持つ長い機構では、最終的に EFPA が PV-OSIM を上回った。
  • PV-OSIM の演算が約 1.5% 少なかったケースが 1 つある。両手と両足に 6D 溶接拘束を持つ Atlas で、拘束が浮遊ベースに達するまでに 3 つの関節しか通らない場合である。
  • すべてのベンチマークは CasADi 実装での演算回数であり、実時間の計測ではない。

制限事項

  • 6 を超える拘束次元が少数（3 つ以下）の 1 自由度（DoF）関節しか通らない場合、PV-OSIM のランク 1 更新が PV-OSIMr の 2 回のランク 6 計算に勝るため、PV-OSIM のほうが安価になりうる。
  • 拘束が浮遊ベースでしか合流しない場合や、機構が単一の連鎖である場合、PV-OSIMr は PV-OSIM に対して利得がない。
  • 結果は実測の実行時間ではなく演算回数として報告されている。
  • このアルゴリズムはキネマティックツリーを対象に提示されている。C++ の Pinocchio 版は採択後に公開される予定とされていた。

分野への影響

この論文は RA-L 2025 Best Paper Award を受賞し、被引用数は 4 である。著者らは CasADi 実装を GitHub でソースコードとして公開しており、C++ 版を Pinocchio ライブラリに実装し採択後に公開するとしている。

概要

本論文では、キネマティックツリーに対する Delassus 行列（逆操作空間慣性行列とも呼ばれる）を計算する効率的なアルゴリズム PV-OSIMr を提示する。その計算量のオーダーは文献で知られている中で最も低い。PV-OSIMr は、力とモーションのプロパゲータの合成可能性を利用して Popov-Vereshchagin（PV）ソルバの計算を最適化することで導出される。計算量は O(n + m²) であり、元の PV-OSIM アルゴリズムの O(n + m²d)、拡張力プロパゲータアルゴリズム（EFPA）の O(n+md+m²) と比べて低い。ここで n は関節数、m は拘束数、d はキネマティックツリーの深さである。Delassus 行列の計算には m × m サイズの行列の構築が必要であり、全 n 関節を少なくとも一度は考慮しなければならないため、PV-OSIMr の漸近的計算量は最適である。さらに本アルゴリズムのベンチマークを行い、実際には PV-OSIM や EFPA よりも効率的であることが多いことを確認した。

リンク

  • arXiv 2310.03676: https://arxiv.org/abs/2310.03676
  • DOI 10.1109/LRA.2024.3469829: https://doi.org/10.1109/LRA.2024.3469829
  • PDF: https://arxiv.org/pdf/2310.03676v1
  • コード: https://github.com/AjSat/spatial_V2

このウェブサイトにはJavaScriptが必要です。オープンソースロボティクスプロジェクトを閲覧するにはJavaScriptを有効にしてください。