2/13 MITの安定化制御則(3)


前回に引き続き[1]の内容を見ていく. ページで言うと, 8/47~14/47
3.1.1 Convex Decomposition
・足跡を凸安全領域に割り当てるという組み合わせの問題を単純化するために, 安全地形セットが分解される凸部分の数を最小限に抑える.
・計算上の問題から, 障害物のない空間全てをカバーするのでなく, 代わりにいくつかの大きな凸形領域を作成する. これらの領域を計算するために, IRISを使う. これは単一の大きな障害物のない凸領域を貪欲に計算するためのアルゴリズムである[2].
・IRISアルゴリズムは, 2つの凸最適化を交互に行う. 最初のステップでは, 一連の小さな2次計画法を解いて, 楕円体を一連の障害物から分離する一連の超平面を見つける. 各超平面は, 障害物のない半空間を定義し, それらの半空間の交差点は(凸)ポリトープである.  2番目のステップでは, 単一の半正定値計画を解いて, そのポリトープに内接する最大体積楕円体を見つける. 局所的な固定点が見つかるまでこれら2つのステップを繰り返し, 楕円体を成長させる.
ロボットを開発なのに, 幾何学だったり線形代数学だったりと数学の問題を考える所が面白いですね.

3.1.2 Representing Reachability
・足跡の配置を計画するときは, ロボットの運動学的な到達可能性, つまり, 四肢の寸法と関節の限界によって課せられる制約を考慮して達成できる足の配置のセットを表す必要がある. ロボットの全身運動学モデルを使用してこの到達可能な集合を直接推論することは理想的だが, そのような推論はロボットの関節角の三角関数の多項式を導入し, 凸公式とは両立しない. 代わりに, ロボットの到達可能集合の単純化された内部近似を使用する. これは, 混合整数凸2次制約で表すことができる.
・到達可能な足跡位置のおおよその集合を, 前の足跡の参照フレーム内に固定された円の交点として表す. 各円は半径\(d_k\)を持ち, 前の足跡の枠内に, ある一定のオフセット\(\mathbf{o}_k\)で配置される. これらの円で定義された到達可能領域を下図に示す.

左足の位置(p1)が与えられたときの右足の中心の到達可能な位置の集合の近似. 上からの眺め. 2つの円は半径d1とd2を持ち, それぞれp1からo1o2の位置にある. 灰色部分は, xy平面における右足の中心の到達可能な姿勢のセットを示す. 右足に対する単一の実行可能な姿勢は, p2として示される.

各足跡jについて, 次式が成り立つ.

cosとsinは非凸関数なので, これはまだ凸制約ではない. これを軽減するために, \( \sin\theta_j\)と\(\cos\theta_j\)を追加の決定変数に置き換える. これをそれぞれ\(s_j\)と\(c_j\)とすると, 次式のようになる.

これは凸2次制約である. もちろん, \(s_j\)と\(c_j\)がsinとcosのように振る舞うようにしなければいけない, これを行うには, sinとcosの区分的線形近似を作成し, 追加の整数変数を使用して, 与えられた\(\theta_j\)の値に対するアクティブな線形近似を示す. 近似に使用する区分的線形セグメントの数を選択することにより, 精度と計算速度のtrade-offが可能[3].

3.1.3 Determining the Number of Footsteps
一般的に, 目標位置に到達するのに必要な足跡数を事前に知ることはできない. そのため, 足跡計画担当者がこの数字の決定に責任を負う必要がある. 足跡のセット全体が同時に最適化されるため, 足跡の数を変更すると, 最適化問題のサイズが変わる. もちろん, 毎回別々の最適化を実行して, さまざまな数の足跡を試すことができるが, これは大量の無駄な計算になる. 代わりに, 特定のステップが未使用であることを示すために, 各足跡にバイナリフラグを追加する. このフラグに\(\rho_j\)というラベルを付け, \(\rho_j\)が真であれば, 足跡jがその足の開始姿勢に固定されることを要求する.

ここで, p1p2は足の固定された初期姿勢. 最適化の目的に各\(\rho_j\)に負のコストを追加すると, 事前に必要な数を知らなくても, 足跡を減らすことができる. 最適化が完了した後, \(\rho_j\)が1に等しい足跡は計画から削除できる.

定式化を完成させるために, 1つの足跡から次の足跡へのzおよびヨー値の変化に対して線形制約を追加し, それはロボットが単一ステップであまりにも遠くに旋回または上昇することを防ぐ. また, 転倒を引き起こす可能性が高い非常に大きなステップにペナルティを科すために, 隣接する足跡間の変位に2次コストを追加する. その結果, 単一の混合整数2次制約付き2次計画法 mixed-integer quadratically-constrained quadratic program(MIQCQP)が得られる. これは, 最適性を解くときに, 各足跡の位置と方向, 足跡の合計数, および凸安全領域への足跡の割り当てを選択する. 以上より, 足跡計画の最適化全体を次のように定式化できる.


このような2次計画問題はロボット工学のみならず, 経営工学にも顔を出す(ポートフォリオ選択問題).
ここで, \(\boldsymbol{p}_g\in R^4\)は目標姿勢\(x,y,z,\theta\), \(\boldsymbol{Q}_g\in S^4, \boldsymbol{Q}_r\in S^4\)は目標までの距離とステップ間の客観的な重み, \(q_t\in R\)は未使用のステップのトリミングに関する客観的な重み, そしてpmin, pmax, ∆pmin, ∆pmax\(\in R^4\)は絶対的な足跡位置とその差の範囲である. また, p1p2をロボットの足の初期姿勢に固定する. \(g_{s,l}, h_{s,l}, g_{c,l}, h_{x,l}\)の項は, 正弦関数と余弦関数の事前に選択された区分的線形化を表す. 詳細は[3].

・足跡計画問題を最適に解くことに含まれる非常に多くの個別の決定にもかかわらず, 上の定式化は典型的な場合に非常に効率的な解決策を導く. N = 12ステップの足跡計画の場合, 各ステップはR = 10の安全領域, L = 8のsinとcosの区分的線形化, および各\(\rho_j\)の2つの値のいずれかに割り当てる必要があり, 単純に, \(10^{12}×8^{12}×2^{12}≒3×10^{26}\)の可能な離散的組み合わせ探索する. しかし, 凸型のobjectiveと制約により, ソルバー(解く人)は最適性を犠牲にすることなく, その検索空間の大部分を探索することを回避できる.
[3]では, そのようなサイズの問題に対する1~10秒の典型的な解決時間を示す. 地形全体が平らで安全な地域ではない場合, 割り当てが必要で, 解決時間は最大16フットステップの計画では通常1秒未満である.
所望の足跡の軌跡が与えられると、足跡を通る区分的多項式の圧力中心(COP)軌跡を使用して動的な歩行運動を定義することができる(この考えは2/15でさらに説明). しかし, ランニングや地面からの起床など, より複雑で全身的な動作を実現するには, 2/14で説明するより充実した計画策定が必要である.

【参考文献】
[1]https://dspace.mit.edu/openaccess-disseminate/1721.1/110533
[2]http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B17CF6E1CDF0773950D1863805FEE7D?doi=10.1.1.716.7266&rep=rep1&type=pdf
[3]https://groups.csail.mit.edu/robotics-center/public_papers/Deits14a.pdf