(57)【要約】 本発明の運動解析方法を実現する情報処理装置１００は、物体表面上の各点に印加された外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて連立一次方程式の解を算出するＣＰＵ１０１を備える。定式化した連立一次方程式の解を算出する際、ある加速度間の拘束を無視することによって一次独立の接触問題として解を求め、解を求めた後に全ての加速度間の拘束をチェックする。
2007094451.tif 000002
【特許請求の範囲】
【請求項１】
表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析方法において、
各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて前記連立一次方程式の解を算出し、前記連立一次方程式の途中結果及び最終結果をメモリに記録することを特徴とする運動解析方法。
【請求項２】
前記行列分解は、ＱＲ分解であることを特徴とする請求項１に記載の運動解析方法。
【請求項３】
ＱＲ分解を用いて前記係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて１又は複数回の列交換及びギブンス回転を行うことを特徴とする請求項１又は請求項２に記載の運動解析方法。
【請求項４】
前記上三角行列から零である対角要素を探索し、零である対角要素が探索された場合、該対角要素の右隣から順に非零である要素を探索し、非零である要素が探索された場合、該要素を含む列ベクトルと前記対角要素を含む列ベクトルとの間の列交換を行うことを特徴とする請求項３に記載の運動解析方法。
【請求項５】
前記物体は、床面を歩行する歩行ロボットであり、前記外力は前記床面から受ける抗力であることを特徴とする請求項１乃至請求項４に記載の運動解析方法。
【請求項６】
表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析装置において、
各点に印加された外力と外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化する手段と、行列分解を用いて前記係数行列から非特異小行列を抽出する手段と、抽出した非特異小行列を用いて前記連立一次方程式の解を算出する手段と、前記連立一次方程式の途中結果及び最終結果をメモリに記録する手段とを備えることを特徴とする運動解析装置。
【請求項７】
コンピュータに、表面上の複数の点に外力が印加された場合の物体の運動を解析させるコンピュータプログラムにおいて、
コンピュータに、各点に印加された外力と外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化させるステップと、コンピュータに、行列分解を用いて前記係数行列から非特異小行列を抽出させるステップと、コンピュータに、抽出させた非特異小行列を用いて前記連立方程式の解を算出させるステップとを有することを特徴とするコンピュータプログラム。
【請求項８】
コンピュータに、表面上の複数の点に外力が印加された場合の物体の運動を解析させるコンピュータプログラムが記録されているコンピュータでの読み取りが可能な記録媒体において、
コンピュータに、各点に印加された外力と外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化させるステップと、コンピュータに、行列分解を用いて前記係数行列から非特異小行列を抽出させるステップと、コンピュータに、抽出させた非特異小行列を用いて前記連立方程式の解を算出させるステップとを有するコンピュータプログラムが記録されていることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列方程式を用いて運動解析を行う運動解析方法、運動解析装置、コンピュータプログラム、及び記録媒体に関する。
【背景技術】
【０００２】
ヒューマノイドロボットの挙動を解析する動的シュミレーションでは、外部から印加される外力（接触力および衝突）を注意深く取り扱う必要がある。近年、正確かつ有効な解を見出すために精力的な研究がなされており、ペナルティ手法、撃力ベースの手法、解析的手法などの手法により運動の解析が行われている。【０００３】
ペナルティ手法は、拘束を違反した度合いに応じて力を加えることで、シミュレーションを進めるうちに拘束違反を解消する手法である（例えば、非特許文献１及び２参照）。接触力を正確に求めたい場合などに用いられてきた。拘束力は、侵入量（すなわち、拘束違反の量）と速度とから直接的に求まるが、拘束が解消するまでシミュレーションを繰り返す必要があるという問題点を有している。【０００４】
撃力ベースの手法では、瞬間的な撃力が物体の速度を変化させるとして衝突および接触を解析する手法である（例えば、非特許文献３参照）。この手法では、物体同士の相互作用やエネルギーの伝搬に着目しており、シュミレーションの正確さよりも、むしろ物体の挙動を視覚化することに主眼を置いている。【０００５】
一方、解析的手法は、幾つかの制約があるものの現実のロボットの挙動を正確にシミュレートするのに最も適している。解析的手法では、線形拘束条件を取り扱い、拘束条件の式と運動方程式とを連立させて解くことで、拘束条件を満たすために必要な力を計算する（例えば、特許文献４及び５参照）。このように解析的手法では、拘束条件を満たす力を解くため、シミュレーションの時間をある程度広くとっても正確なシミュレーションを行うことができる。
【非特許文献１】ウィルヘルム（J. Wilhelms）、他２名著、「動的アニメーション：相互作用と制御（Dynamic  animation: interaction and control）」、ビジュアルコンピュータ（Visual Computer）、１９８８年、第４巻、Ｐ２８３−２９５
【非特許文献２】パンネ（M. van de Panne）、他１名著、「センサ−アクチュエータ  ネットワーク（Sensor-actuator network）」、プロシーディングス  エーシーエム  シーグラフ（Proc. ACM SIGGRAPH）、１９９３年、第２７（２）巻、Ｐ３３５−３４３
【非特許文献３】シュミドル（H. Schmidl）、他１名著、「剛体シュミレーションのための瞬間的な接触（A fast impulsive contact suite for rigid body simulation）」、視覚化とコンピュータグラフィックス（Visualization and Computer Graphics）、２００４年、第１０巻、Ｐ１８９−１９７
【非特許文献４】フェザーストーン（R. Featherstone）著、「ロボット力学のアルゴリズム（Robot Dynamics Algorithms）」、クルワーアカデミック（Kluwer Academic）、１９８７年
【非特許文献５】バラフ（D. Baraff）著、「非侵入剛体に対する接触力の計算（Fast contact force computation for nonpenetratingrigid bodies）」、シーグラフ  ９４  コンファレンス（SIGGRAPH ９４ Conference）、１９９４年、Ｐ２３−３４
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、前述した解析的手法では、全ての接触点について剛体の運動を表す行列方程式を解く必要があるため、接触点が多い場合などに多くの計算時間を必要とすることが問題となっていた。【０００７】
また、剛体上の複数の点に作用する接触力と加速度との関係が一次独立となり、係数行列が正則でありさえすれば、ＬＵ分解法、ＱＲ分解法等の行列分解を用いることにより解を求めることが可能であるが、実際には、多くの接触状態において一次従属の拘束を含むことが知られており、係数行列について独立性を仮定することはできない。この場合、ある拘束条件を無視し、他のすべての拘束条件を満たす解を求める手法がよく採用されるが、接触力自体を求めるのと同様に複雑な計算を要するという問題点を有している。【０００８】
本発明は斯かる事情に鑑みてなされたものであり、接触点が多く、かつ接触力と加速度との関係が一次従属となる場合であっても、各接触点に印加される外力及び加速度を速やかに求めることができる運動解析方法、運動解析装置、コンピュータプログラム、及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００９】
第１発明に係る運動解析方法は、表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析方法において、各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて前記連立一次方程式の解を算出し、前記連立方程式の途中結果及び最終結果をメモリに記録することを特徴とする。【００１０】
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。【００１１】
第２発明に係る運動解析方法は、前記行列分解は、ＱＲ分解であることを特徴とする。【００１２】
本発明にあっては、行列分解としてＱＲ分解を用いるため、既知の演算によって非特異小行列が抽出される。【００１３】
第３発明に係る運動解析方法は、ＱＲ分解を用いて前記係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて１又は複数回の列交換及びギブンス回転を行うことを特徴とする。【００１４】
本発明にあっては、ＱＲ分解により係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換及びギブンス回転を行うようにしているため、計算コストが低減される。【００１５】
第４発明に係る運動解析方法は、前記上三角行列から零である対角要素を探索し、零である対角要素が探索された場合、該対角要素の右隣から順に非零である要素を探索し、非零である要素が探索された場合、該要素を含む列ベクトルと前記対角要素を含む列ベクトルとの間の列交換を行うことを特徴とする。【００１６】
本発明にあっては、上三角行列から零である対角要素と、その対角要素の右側の列ベクトルに含まれる非零の要素とを探索する。そして、両要素が探索された場合、探索された対角要素及び非零である要素を含む２つの列ベクトルを交換するようにしているため、非特異小行列が速やかに抽出される。【００１７】
第５発明に係る運動解析方法は、前記物体は、床面を歩行する歩行ロボットであり、前記外力は前記床面から受ける抗力であることを特徴とする。【００１８】
本発明にあっては、解析対象として歩行ロボットを採用し、歩行ロボットが床面から受ける抗力を接触力問題として解くことができる。【００１９】
第６発明に係る運動解析装置は、表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析装置において、各点に印加された外力と外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化する手段と、行列分解を用いて前記係数行列から非特異小行列を抽出する手段と、抽出した非特異小行列を用いて前記連立一次方程式の解を算出する手段と、前記連立一次方程式の途中結果及び最終結果をメモリに記録する手段とを備えることを特徴とする。【００２０】
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。【００２１】
第７発明に係るコンピュータプログラムは、コンピュータに、表面上の複数の点に外力が印加された場合の物体の運動を解析させるコンピュータプログラムにおいて、コンピュータに、各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化させるステップと、コンピュータに、行列分解を用いて前記係数行列から非特異小行列を抽出させるステップと、コンピュータに、抽出させた非特異小行列を用いて前記連立方程式の解を算出させるステップとを有することを特徴とする。【００２２】
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。【００２３】
第８発明に係る記録媒体は、コンピュータに、表面上の複数の点に外力が印加された場合の物体の運動を解析させるコンピュータプログラムが記録されているコンピュータでの読み取りが可能な記録媒体において、コンピュータに、各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化させるステップと、コンピュータに、行列分解を用いて前記係数行列から非特異小行列を抽出させるステップと、コンピュータに、抽出させた非特異小行列を用いて前記連立方程式の解を算出させるステップとを有するコンピュータプログラムが記録されていることを特徴とする。【００２４】
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。
【発明の効果】
【００２５】
第１発明及び第６発明による場合は、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしている。したがって、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除して線形独立の関係のみを残すことができ、物体に印加されている外力及び加速度を解析的に速やかに求めることができる。【００２６】
第２発明による場合は、行列分解として特定のＱＲ分解を用いるため、既知の演算によって非特異小行列を抽出することができる。【００２７】
第３発明による場合は、ＱＲ分解により係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換及びギブンス回転を行うようにしているため、計算コストを低減することができる。【００２８】
第４発明による場合は、上三角行列から零である対角要素と、その対角要素の右側の列ベクトルに含まれる非零の要素とを探索する。そして、両要素が探索された場合、探索された対角要素及び非零である要素を含む２つの列ベクトルを交換するようにしているため、非特異小行列を速やかに抽出することができる。【００２９】
第５発明による場合は、解析対象として歩行ロボットを採用し、歩行ロボットが床面から受ける抗力を接触力問題として解くことができる。【００３０】
第７発明及び第８発明による場合は、上述した発明に記載の運動解析方法をコンピュータプログラム及び記録媒体に記録されたコンピュータプログラムにより実現できるため、適宜のコンピュータを用いて物体に印加されている外力及び加速度を解析的に速やかに求めることができる。
【図面の簡単な説明】
【００３１】
【図１】本実施の形態に係る運動解析装置の内部構成を示すブロック図である。
【図２】２つの手法の計算コストの比較結果を示すグラフである。
【図３】列交換プロセスを用いた場合の計算コストを示すグラフである。
【図４】消去及び挿入プロセスを用いた場合の計算コストを示すグラフである。
【図５】非零要素の探索手法を模式的に説明する説明図である。
【図６】本発明に係るコンピュータプログラムにより実行される処理の手順を説明するフローチャートである。
【符号の説明】
【００３２】
１００  情報処理装置  
１０１  ＣＰＵ  
１０２  ＲＯＭ  
１０３  ＲＡＭ
１０４  記憶装置
１０５  入出力ＩＦ
１０６  キーボード
１０７  モニタ
１０８  補助記憶装置
１０９  バス
１１０  記録媒体
【発明を実施するための最良の形態】
【００３３】
図１は本実施の形態に係る運動解析装置の内部構成を示すブロック図である。本実施の形態に係る運動解析装置は、パーソナルコンピュータ、ワークステーション等の情報処理装置１００により実現される。情報処理装置１００は、演算手段としてのＣＰＵ１０１を備えており、このＣＰＵ１０１には、ＲＯＭ１０２、ＲＡＭ１０３、記憶装置１０４、入出力ＩＦ１０５、補助記憶装置１０８等のハードウェアがバス１０９を介して接続されている。【００３４】
ＲＯＭ１０２には、バス１０９に接続された各種ハードウェアの動作を制御するための制御プログラムが格納されている。ＣＰＵ１０１は、この制御プログラムをＲＡＭ１０３上にロードして実行することにより、ハードウェア全体の動作を制御する。また、ＲＡＭ１０３には、運動解析の途中結果及び最終結果が適宜書き出される。【００３５】
記憶装置１０４は、ハードディスクドライブを備えており、本実施の形態で説明する運動解析方法を具体的に実現するためのコンピュータプログラム、及びこのコンピュータプログラムを実行する際に必要となるデータが記憶される。【００３６】
入出力ＩＦ１０５には、入力デバイスであるキーボード１０６、及び出力デバイスであるモニタ１０７が接続される。情報処理装置１００は、キーボード１０６を通じて運動解析の開始指示、運動解析に必要なパラメータの入力を受付ける。また、情報処理装置１００は、キーボード１０６を通じて入力されたパラメータ、前述したコンピュータプログラムの演算結果等をモニタ１０７上に表示する。【００３７】
補助記憶装置１０８は、本発明に係るコンピュータプログラムが記録されたＦＤ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の記録媒体１１０からコンピュータプログラムを読み取るためのＦＤドライブ、ＣＤ−ＲＯＭドライブ、ＤＶＤ−ＲＯＭドライブ等を備えている。補助記憶装置１０８により読み取られたコンピュータプログラムは記憶装置１０４に記憶される。ＣＰＵ１０１は、必要に応じて記憶装置１０４から前述のコンピュータプログラムをＲＡＭ１０３上にロードして実行することにより、情報処理装置１００を本実施の形態に係る運動解析装置として動作させる。【００３８】
情報処理装置１００による運動解析の対象として歩行ロボットを採用し、歩行ロボットが床面を歩行する際の運動を解析する手法を以下で説明する。歩行ロボットは、床面からの抗力を受けるため、この抗力（接触力）と加速度との関係を運動方程式により表す。典型的な接触力の問題は、次の式のように表すことができる。【００３９】
【数１】
2007094451.tif 000003
【００４０】
ここで、ｆは物体表面の１又は複数の接触点における接触力を表すベクトルであり、ａは各接触点での法線方向及び接戦方向の加速度を表すベクトルである。Ａは接触力と加速度とを関連付ける行列であり、物体の質量に関係する量を表す。また、ａ0 は物体に接触力が印加されていない場合の前記接触点での加速度を表すベクトルである。【００４１】
行列Ａおよびベクトルａ0 の各要素については、例えば、ＳＤＦＡＳＴのような動力学のソフトウェアを用いることにより、解析的に又は実験的に導出することができる。すなわち、行列Ａおよびベクトルａ0 の各要素の値は既知の量と考えることができるため、数式１は、行列Ａを係数行列とした加速度ａおよび接触力ｆに関する連立一次方程式と見ることができ、この連立一次方程式を解く問題に帰着することができる。【００４２】
係数行列を用いて連立一次方程式を解く方法としては、ガウスの消去法、ＬＵ分解法、ＱＲ分解法等が知られている。このうち、ＱＲ分解に基づく方法は、係数行列が正則でありさえすれば解を求めることが可能である。しかし、行列が特異に近い場合には、解の精度を高めようとすると軸列の選択が必要なことが知られており、軸選択を行わない並列解法には適用範囲に限界がある。【００４３】
実際、数式１に示した運動方程式では、多くの接触状態において一次従属の拘束を含むことが知られており、各加速度について独立性を仮定することができない。この場合、ある拘束条件を無視し、全ての拘束条件に適合する解を求める手法がよく採用されているが、接触力自体を求めるのと同様に複雑な計算を要する。また、摩擦力に起因する加速度によっては、任意の加速度の任意の次元において一次従属となり得る。【００４４】
そこで、本実施の形態では、行列Ａから非特異小行列を構築する手法（以下、干渉性利用法という）について説明する。この干渉性利用法では、行列Ａについて消去しないサブセットの任意のインデックスを受付ける。このアルゴリズムでは、ある加速度間の拘束を無視することによって一次独立の接触問題として解を求め、解を求めた後に全ての加速度間の拘束をチェックする。不要な拘束を全て不要セットに置き換えた場合、これらの不要セットのインデックスの１つは保持セットに含まれ、行列Ａの異なる一次独立の小行列を算出することができる。どの拘束が必要であるか、どの拘束が他の拘束に影響を及ぼすかということについては一般的には分からないため、保持する拘束のどの組み合わせについても、全ての拘束を満たす解が見つかるまで線形独立の小行列を計算する。あるいは、元の行列Ａが悪状態又は不十分なランクであるために完全な解を求めることが出来ない場合もあり、そのときは最も拘束を満足する解が見つかるまで全ての小行列について計算を行う。【００４５】
特異小行列の抽出プロセスにはＱＲ分解の理解が不可欠であるため、まず、列交換を保持するプロセスについて説明する。ＱＲ分解では、ｍ行ｎ列の任意の行列Ａを、ｍ行ｍ列の直交行列Ｑとｍ行ｎ列の上三角行列Ｒとに行列分解する。【００４６】
【数２】
2007094451.tif 000004
【００４７】
任意の行列ＡをＱＲ分解することは可能であるが、直交行列Ｑ及び上三角行列Ｒは一意ではない。ＱＲ分解は、元の行列Ａが調整される場合、又は最初から計算をし直す努力を避けたい場合において特に有用である。行または列が追加された場合、ＱＲ分解はアップデートされ、行または列が削除された場合、ＱＲ分解をダウンデートされる。または、ランク１の行列の加算又は減算に続いて再計算が実行される。【００４８】
ＱＲ分解のアップデート及びダウンデートは、行列の任意の列の交換に続いて分解を保持するという標準的な手法が採用される。例えば、第ｎ列と第ｎ＋ｋ列との間の交換を行う場合、第ｎ列および第ｎ＋ｋ列を消去し、その新たな２箇所に列を挿入し、それぞれ２回のアップデート及びダウンデートを行う。しかしながら、これらの演算は単一列の交換演算により統合することができ、演算資源をかなり削減することができる。【００４９】
ＱＲ分解のアップデート及びダウンデートはギブンス回転を用いて実行される。ギブンス行列Ｇｎ（ｉ，ｊ，θ）は、ｎ次元空間のうちの２つの部分空間（１つはｉ次元の部分空間、もう１つはｊ次元の部分空間とする）の間の回転を表している。ギブンス行列Ｇｎ（ｉ，ｊ，θ）は、ｎ×ｎの単位行列のうち、（ｉ，ｉ）、（ｉ，ｊ）、（ｊ，ｉ）、（ｊ，ｊ）の各要素をそれぞれｃｏｓθ、−ｓｉｎθ、ｓｉｎθ、ｃｏｓθにより置き換えた行列である。ＱＲ分解は以下のように与えられる。このとき、Ｑ’の直交性は保持されるが、Ｒは上三角行列でなくなる。【００５０】
【数３】
2007094451.tif 000005
【００５１】
行列ＡのＱＲ分解が与えられた場合、以下のようにして第ｋ列を消去して行列分解を保持することができる。【００５２】
【数４】
2007094451.tif 000006
【００５３】
例えば、６行６列の行列Ｒから第３列の削除を考えた場合、行列Ｒの構造は以下のように影響を受ける。【００５４】
【数５】
2007094451.tif 000007
【００５５】
ここで、「×」のシンボル、及び「＃１ 」〜「＃３ 」のシンボルで表される各要素は一般に非零の値をとる（但し、偶然的に零の値をとり得る）。また、シンボルが付されていない各要素は零の値をとる。行列Ｒ(1) は現時点で上三角行列ではないが、ギブンス回転を３回適用することによって対角成分の直下の要素（すなわち、「＃１ 」〜「＃３ 」のシンボルで表した各要素）を１つずつ零にすることができ、行列Ｒ(1) の上三角性を修復することができる。ここで、ギブンス回転は、インデックスを付した順に隣り合う行同士について適用され、その結果、対角要素の下側に非零の要素が生成されないことが保証される。【００５６】
行列Ａに列を挿入し、ＱＲ分解をアップデートする場合も同様である。行列ＡのＱＲ分解が与えられた場合、以下のようにして、行列Ａに新しい列ｃT を追加し、行列分解を保持することができる。【００５７】
【数６】
2007094451.tif 000008
【００５８】
例えば、５行４列の新たに第３列を挿入することを考えた場合、行列Ｒの構造は以下のように影響を受ける。【００５９】
【数７】
2007094451.tif 000009
【００６０】
上の式においても「×」のシンボル、及び「＃１ 」〜「＃３ 」のシンボルで表される各要素は一般に非零の値をとる（但し、偶然的に零の値をとり得る）。また、「・」のシンボルは、元々は零の要素であるが、ギブンス回転を適用することによって非零の値に変化し得る要素を示している。例えば、「＃１」の要素を零にするためにギブンス回転を適用した場合、「・１」の要素が非零の値になり、「＃２」の要素を零にするためにギブンス回転を適用した場合、「・２」の要素が非零の値になる。したがって、この場合には行列Ｒ(1) を上三角行列に変換するために２回のギブンス回転を行う必要がある。【００６１】
同様の手法は、行列Ｒから２つの列を入れ替えた結果として生成される行列Ｒ(1) の構造を修復する際にも適用される。２つの列の入れ替えは、列の挿入と削除とを同時的に実行することと等価であり、Ｒ(1) の構造を修復する前にアップデートと組み合わせて複数回の列の消去と挿入とを実行する場合と比べた場合、演算資源を削減する効果が高い。行列Ａの第ｉ列と第ｊ列との入れ替えを考えた場合、以下のように行列分解を保持することができる。【００６２】
【数８】
2007094451.tif 000010
【００６３】
行列Ｒ(1) の構造はもはや上三角行列ではない。８行８列の上三角行列を例にとり、その第３列と第６列とを入れ替えた行列Ｒ(1) の構造を修復するプロセスについて以下に説明する。行列Ｒ(1) は以下のように表すことができる。【００６４】
【数９】
2007094451.tif 000011
【００６５】
この例における行列Ｒ(1) は、上三角行列の第３列と第６列とを入れ替えた行列であるから、その第３列には対角要素より下側に３つの非零の要素が存在する。これらの要素を零にするためにギブンス回転を行う。このとき、ギブンス回転の影響を受ける要素の数を最小にするために、隣り合う行同士にギブンス回転を適用する。「＃１ 」のシンボルで示した要素を零にするためにギブンス回転を行った結果、「・１ 」のシンボルで示した要素は零から非零の値に変わる。「・２ 」、「・３ 」のシンボルで示した要素についても同様である。【００６６】
変形した結果の行列をＲ(2) とした場合、行列Ｒ(2) は以下のように表すことができる。【００６７】
【数１０】
2007094451.tif 000012
【００６８】
上の式で示したように、行列Ｒ(2) には、第４列及び第５列の対角要素の下側に「＃４ 」及び「＃５ 」のシンボルで示した非零の要素が存在する。この第２段階での変形では、第１段階の３回のギブンス回転により生成されたこれらの非零の要素を零にするために、２回のギブンス回転を行う。その結果、「＃４ 」及び「＃５ 」で示した要素は零となり、「・４ 」及び「・５ 」で示した要素はそのときのギブンス回転の影響を受けて値が変化する。この第２段階での変形を行った結果、前述の行列Ｒ(2) は上三角行列Ｒ(3) に変形される。対応する直交行列Ｑ(3) は、直交行列Ｑに逆の回転演算を施すことにより得られる。【００６９】
次に、計算コストについて説明する。
Ｍ行Ｎ列の行列Ｒから第ｎ列を消去した場合、その構造を修復するために必要なギブンス回転の数は、ｍａｘ｛ｍｉｎ｛Ｍ−ｎ，Ｎ−ｎ｝，０｝となる。次いで、ｎ番目の位置に列を挿入した場合、修復する際に必要なギブンス回転の数は、ｍａｘ｛Ｍ−ｎ，０｝となる。したがって、Ｎ行Ｎ列の正方行列について、列の消去及び挿入を行うことにより第ｎ列と第ｎ＋ｋ列との入れ替えを行う場合、修復に要するギブンス回転の回数は、４Ｎ−２（２ｎ＋ｋ）−１となる。【００７０】
一方、列交換の手法を用いる場合、前述したように、第１段階でｋ回のギブンス回転を行い、第２段階でｋ−１回のギブンス回転を行うため、修復するために要するギブンス回転の数は２ｋ−１でよい。すなわち、トータルで４（Ｎ−（ｎ＋ｋ））回のギブンス回転を節約することができる。交換すべき２つの列のインデックスのうち、大きい方のインデックスにより節約できるギブンス回転の数が定まり、インデックスが元の行列の最後の列に近づくにつれて減少する。【００７１】
しかしながら、ギブンス回転は非零の要素を含んだ列に対してのみ適用すればよいので、前述した計算は必ずしも真の節約量を反映していない。この点を考慮し、行列回転を用いるよりも列回転を用いて節約量を計算することができる。Ｎ行Ｎ列の行列について第ｎ列と第ｎ＋ｋ列との間の列交換を行う場合、以下の回数だけギブンス列回転が必要となる。【００７２】
【数１１】
2007094451.tif 000013
【００７３】
同様に、Ｍ行Ｎ列の行列から列の消去を行う場合、以下の回数だけギブンス列回転が必要となる。但し、Ｍは、Ｍ∈[Ｎ，Ｎ＋１]を満足する整数である。【００７４】
【数１２】
2007094451.tif 000014
【００７５】
更に、列の挿入を行う場合には、以下の回数だけギブンス列回転が必要となる。但し、Ｍは、Ｍ∈［Ｎ＋１，Ｎ＋２］を満足する整数である。【００７６】
【数１３】
2007094451.tif 000015
【００７７】
したがって、２つの列を消去して２つの列を挿入する場合の計算コストは、以下のように表すことができる。【００７８】
【数１４】
2007094451.tif 000016
【００７９】
図２は２つの手法の計算コストの比較結果を示すグラフである。このグラフでは２４行２４列の行列について計算コストを算出しており、底面の２つの軸はそれぞれ交換対象の列のインデックスを示し、高さ方向の軸は相対コストを示している。このグラフから、消去及び挿入プロセスに比べて列交換プロセスは大部分の条件下で計算コストが良いことが分かる。相対コストが１となる条件をグラフ中の破線により示している。すなわち、交換対象の列のインデックスの何れか一方が２０以下である場合、計算コストは交換プロセスを使用する方が良く、交換対象の列のインデックスが元の行列の最後の列（第２４列）に近づくにつれて計算コストは消去及び挿入プロセスを使用する方が良くなる。【００８０】
図３は列交換プロセスを用いた場合の計算コストを示すグラフであり、図４は消去及び挿入プロセスを用いた場合の計算コストを示すグラフである。何れのグラフについても２４行２４列の行列について計算コストを算出している。何れのプロセスにおいても計算コストは元の行列のサイズに依存する。行列サイズが大きくなるにつれ、列交換プロセスの計算コストは、消去及び挿入プロセスの計算コストの５０％に近づくことが分かった。このファクターは、任意の２つの列の交換の可能性を等確率と仮定し、列回転を実行する回数をカウントすることにより見積もった値である。４行４列の行列、又はそれ以上のサイズを有する行列では、列交換プロセスは消去及び挿入プロセスよりも計算速度が平均的に大きく、３行３列の行列で計算コストが等しくなる。【００８１】
次に、最大の非特異小行列を抽出する手法について説明する。
与えられた行列から最大限に大きな非特異小行列を抽出する手法は、前述したようなＱＲ分解を基にしており、以下の仮定を必要とする。まず、与えられた行列が対象行列、又は行交換した対象行列であることを仮定する。また、正規直交のＱＲ分解において行列Ｒが与えられていることを仮定する。更に、消去することができない行および列の組を示す保持用インデックスのセットが与えられていることを仮定する。更に、保持用インデックスのセットの軽微な変更（典型的には、新たなインデックスの追加）に続いて小行列の抽出を行うことを仮定する。更に、一連の類似の行列について一から小行列の抽出を繰り返すことを仮定する。【００８２】
行列の左上側のブロックの非特異小行列と明確に区別するために元の行列の行および列を再配列することを行う。再配列するインデックスは、続くプロセスの繰り返しの間だけ内部的に保持される。【００８３】
前述の仮定を用いて非特異小行列を抽出するために、対象行列Ａに対するＱＲ分解を以下のように表す。【００８４】
【数１５】
2007094451.tif 000017
【００８５】
ここで、０又は３のインデックスを付した小行列（例えば、Ａ0 、Ａ3 等 ）は正方行列であり、同じインデックスを付した全ての小行列は同じ次元を有する。小行列Ｒ0 の対角要素の全てを非零と仮定したとき、小行列Ａ0 が非特異であり、かつ、小行列Ａ0 の外部に行または列の組を追加することによって拡張した小行列Ａ0 は特異行列となることが証明できる。【００８６】
ＱＲ分解を構築することは、行列Ａの各列に亘って互いに直交するベクトルのセットを見つけることと等価である。また、ＱＲ分解を区分化することは、基を構成するまで直交するベクトルのセットを縮小することと等価である。すなわち、行列Ｒの左上隅から完全なシリーズとなるように、行列Ｒの対角要素にできるだけ多くの非零の要素を配列させるプロセスが要求される。【００８７】
そのため、行列Ｒの対角要素を左上隅から順に調べ、零の要素を探索する。本実施の形態では、微小な値を閾値として予め設定しておき、その閾値より小さい値を見つけた場合、その要素は零であると判定する。零の要素を見つけた場合、その要素のすぐ右隣から列のインデックスが増える方向に非零の要素を探索する。その行に非零の要素が見つからない場合には、行を一段だけ下げて対角要素の右側を探索し、非零の要素が見つかるまで行を一段ずつ下げながら行列Ｒの右下隅に至るまで探索を繰り返す。非零要素が見つからない場合、行列Ｒは区分化された構造を有しているため、本プロセスを終了する。なお、対角要素の下側は零であることが保証されているため、探索を省略できることはいうまでもない。図５は非零要素の探索手法を模式的に説明する説明図である。【００８８】
このような要素が見つかった場合、その要素を含む列は零対角要素を含んだ列と交換され、アップデートされた行列Ｒの次の対角要素が零であるか否かの判定が行われる。列交換は、非零対角要素の上側及び左側には影響を及ぼさないため、行列Ｒの構造は保持される。小行列における零対角要素の下側及び右側に非零要素が存在するということは、その零対角要素を含んだ列と行列Ｒの非零対角要素を含んだ各列とが一次従属でないことを保証する。【００８９】
保持用セットは、行列Ｒの構造を修復するのに先立ち、保持した列を非特異ブロックの最初の列と交換することにより適用することができる。例えば、ある列が保持用セットに存在するが非特異ブロックに存在しない場合、その列はそれ自身が保持用セットに含まれない非特異ブロックの最初の列と交換される。非特異ブロック中の目的の列の対角要素が零になるという結果である場合には、保持セットは一次従属の関係にある列を含み、もはや解が存在しないためプロセスを終了する。【００９０】
この列交換の手続きは、保持用セットの操作は最小の列交換アップデートにより処理することができ、アルゴリズムの次の反復の間で期待された干渉性を使用することができることを確実にする。また、保持用セットが実現可能である場合には速やかに決定することができる。このパターンを用いてオリジナルのマトリックスの順序を入れ替えることにより、最初のＱＲ分解は区分化した形態になるか、又は近づき、必要な列交換の数を減らすことができる。【００９１】
このようにして求めた解は対象行列と同等に扱うことができるが、結果として導出された非正則ブロックはアルゴリズムの実行を繰り返す度にチェックする必要がある。これは、候補となるブロック行列を完全にＱＲ分解することを要求する。Ｑ行列がアルゴリズムを通して保持される場合、分解を再計算する必要はなくなるが、候補となる行列のオリジナルの行列に対する相対サイズに依存することとなり、Ｑ行列の間接的な保持及びＱＲ分解を一から再計算することを避けることが十分可能になる。【００９２】
次に、本発明に係るコンピュータプログラムにより実行される処理の手順を説明する。図６は本発明に係るコンピュータプログラムにより実行される処理の手順を説明するフローチャートである。外部から入力されたパラメータに基づいて物体（例えば、歩行ロボット）の運動解析を行う場合、物体表面上の各点に印加された外力と加速度との関係を定式化する（ステップＳ１）。物体表面上の各点に印加された外力と加速度との関係は、前述の数式１に示したように連立一次方程式を用いることにより、物体表面の１又は複数の接触点における接触力を表すベクトルｆ、各接触点での法線方向及び接線方向の加速度を表すベクトルａ、接触力と加速度とを関連付ける行列Ａにより記述することができる。【００９３】
次いで、行列分解（特に、ＱＲ分解）を用いることにより行列Ａから非特異小行列を抽出し（ステップＳ２）、抽出した非特異小行列を用いて定式化した連立一次方程式の解を算出する（ステップＳ３）。このとき、ある加速度間の拘束を無視することによって一次独立の接触問題として解を求め、解を求めた後に全ての加速度間の拘束をチェックする。不要な拘束を全て不要セットに置き換えた場合、これらの不要セットのインデックスの１つは保持セットに含まれ、行列Ａの異なる一次独立の小行列を算出することができる。どの拘束が必要であるか、どの拘束が他の拘束に影響を及ぼすかということについては一般的には分からないため、保持する拘束のどの組み合わせについても、全ての拘束を満たす解が見つかるまで線形独立の小行列を計算する。あるいは、元の行列Ａが悪状態又は不十分なランクであるために完全な解を求めることが出来ない場合もあり、そのときは最も拘束を満足する解が見つかるまで全ての小行列について計算を行う。【００９４】
このように本発明では、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除して線形独立の関係のみを残すことができ、物体に印加されている外力及び加速度を解析的に速やかに求めることができる。
【図１】
2007094451.tif 000018
【図２】
2007094451.tif 000019
【図３】
2007094451.tif 000020
【図４】
2007094451.tif 000021
【図５】
2007094451.tif 000022
【図６】
2007094451.tif 000023
【手続補正書】
【提出日】平成19年12月17日(2007.12.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析方法において、
各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化し、ＱＲ分解を用いて前記係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて１又は複数回の列交換及びギブンス回転を行うことにより、前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて前記連立一次方程式の解を算出し、前記連立一次方程式の途中結果及び最終結果をメモリに記録することを特徴とする運動解析方法。
【請求項２】
表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析方法において、
各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化し、ＱＲ分解を用いて前記係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換を行う処理と列交換によって対角要素より下側に非零の要素が存在することとなった場合、前記非零の要素を含んだ行ベクトル及び該行ベクトルに隣接する行ベクトルについてギブンス回転を行う処理とを繰り返すことにより、前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて前記連立一次方程式の解を算出し、前記連立一次方程式の途中結果及び最終結果をメモリに記録することを特徴とする運動解析方法。
【請求項３】
（削除）
【請求項４】
前記上三角行列から零である対角要素を探索し、零である対角要素が探索された場合、該対角要素の右隣から順に非零である要素を探索し、非零である要素が探索された場合、該要素を含む列ベクトルと前記対角要素を含む列ベクトルとの間の列交換を行うことを特徴とする請求項１又は請求項２に記載の運動解析方法。
【請求項５】
前記物体は、床面を歩行する歩行ロボットであり、前記外力は前記床面から受ける抗力であることを特徴とする請求項１、２、４の何れか１つに記載の運動解析方法。
【請求項６】
請求項１、２、４、５の何れか１つに記載の運動解析方法を用いて物体の運動を解析することを特徴とする運動解析装置。
【請求項７】
請求項１、２、４、５の何れか１つに記載の運動解析方法を用いて物体の運動を解析させるステップを有することを特徴とするコンピュータプログラム。
【請求項８】
請求項１、２、４、５の何れか１つに記載の運動解析方法を用いて物体の運動を解析させるステップを有するコンピュータプログラムが記録されていることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
グラム、及び記録媒体を提供することを目的とする。
課題を解決するための手段
［０００９］
第１発明に係る運動解析方法は、表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析方法において、各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化し、ＱＲ分解を用いて前記係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて１又は複数回の列交換及びギブンス回転を行うことにより、前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて前記連立一次方程式の解を算出し、前記連立一次方程式の途中結果及び最終結果をメモリに記録することを特徴とする。
［００１０］
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。また、ＱＲ分解により係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換及びギブンス回転を行うようにしているため、計算コストが低減される。
［００１１］
第２発明に係る運動解析方法は、表面上の複数の点に外力が印加された場合の物体の運動を解析する運動解析方法において、各点に印加された外力と、外力が印加された場合の各点での加速度との関係を係数行列を用いた連立一次方程式により定式化し、ＱＲ分解を用いて前記係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換を行う処理と列交換によって対角要素より下側に非零の要素が存在することとなった場合、前記非零の要素を含んだ行ベクトル及び該行ベクトルに隣接する行ベクトルについてギブンス回転を行う処理とを繰り返すことにより、前記係数行列から非特異小行列を抽出し、抽出した非特異小行列を用いて前記連立一次方程式の解を算出し、前記連立一次方程式の途中結果及び最終結果をメモリに記録することを特徴とする。
［００１２］
本発明にあっては、ＱＲ分解を用いて係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換を行う処理と列交換によって対角要素より下側に非零の要素が存在することとなった場合、非零の要素を含んだ行ベクトル及びこの行ベクトルに隣接する行ベクトルについてギブンス回転を行う処理とを繰り返すようにしているため、計算コストが低減される。
［００１３］
［００１４］
［００１５］
第４発明に係る運動解析方法は、前記上三角行列から零である対角要素を探索し、零である対角要素が探索された場合、該対角要素の右隣から順に非零である要素を探索し、非零である要素が探索された場合、該要素を含む列ベクトルと前記対角要素を含む列ベクトルとの間の列交換を行うことを特徴とする。
［００１６］
本発明にあっては、上三角行列から零である対角要素と、その対角要素の右側の列ベクトルに含まれる非零の要素とを探索する。そして、両要素が探索された場合、
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
探索された対角要素及び非零である要素を含む２つの列ベクトルを交換するようにしているため、非特異小行列が速やかに抽出される。
［００１７］
第５発明に係る運動解析方法は、前記物体は、床面を歩行する歩行ロボットであり、前記外力は前記床面から受ける抗力であることを特徴とする。
［００１８］
本発明にあっては、解析対象として歩行ロボットを採用し、歩行ロボットが床面から受ける抗力を接触力問題として解くことができる。
［００１９］
第６発明に係る運動解析装置は、上述した発明の何れか１つに記載の運動解析方法を用いて物体の運動を解析することを特徴とする。
［００２０］
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。また、ＱＲ分解により係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換及びギブンス回転を行うようにしているため、計算コストが低減される。
［００２１］
第７発明に係るコンピュータプログラムは、上述した発明の何れか１つに記載の運動解析方法を用いて物体の運動を解析させるステップを有することを特徴とする。
［００２２］
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。また、ＱＲ分解により係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換及びギブンス回転を行うようにしているため、計算コストが低減される。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
［００２３］
第８発明に係る記録媒体は、上述した発明の何れか１つに記載の運動解析方法を用いて物体の運動を解析させるステップを有するコンピュータプログラムが記録されていることを特徴とする。
［００２４］
本発明にあっては、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしているため、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除することにより線形独立の関係のみが残る。また、ＱＲ分解により係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換及びギブンス回転を行うようにしているため、計算コストが低減される。
発明の効果
［００２５］
第１発明及び第６発明による場合は、外力と加速度との関係を係数行列を用いた連立一次方程式により定式化し、行列分解を用いて係数行列から非特異小行列を抽出するようにしている。したがって、外力及び加速度の関係が一次従属の関係を含む場合であっても、一次従属の関係を排除して線形独立の関係のみを残すことができ、物体に印加されている外力及び加速度を解析的に速やかに求めることができる。
［００２６］
また、本発明による場合は、行列分解として特定のＱＲ分解を用いるため、既知の演算によって非特異小行列を抽出することができる。
［００２７］
第２発明による場合は、ＱＲ分解を用いて係数行列を直交行列と上三角行列との積に分解し、得られた上三角行列を構成する列ベクトルについて列交換を行う処理と列交換によって対角要素より下側に非零の要素が存在することとなった場合、非零の要素を含んだ行ベクトル及びこの行ベクトルに隣接する行ベクトルについてギブンス回転を行う処理とを繰り返すようにしているため、計算コストを低減することができる。
［００２８］
第４発明による場合は、上三角行列から零である対角要素と、その対角要素の右側の列ベクトルに含まれる非零の要素とを探索する。そして、両要素が探索された場合、探索された対角要素及び非零である要素を含む２つの列ベクトルを交換するようにしているため、非特異小行列を速やかに抽出することができる。
【国際調査報告】
2007094451.tif 000024
2007094451.tif 000025
2007094451.tif 000026