Skip to content

第一回マスターズ選手権-決勝-

問題概要

  • 2次元平面上で飛行ドローンを操作し、N箇所の目的地をすべて訪れたい
    • 操作は、「加速」と「計測」が行える
  • いくつか壁があったり、風による影響で速度が変化したり、計測には誤差がのる
    • 壁にぶつかる場合、ぶつかる前のターンの位置のままで、速度は0にリセットされる
  • スコア0から開始し、5000ターン経つか、すべての目的地を訪れた時点までの最大スコアを得点としたとき、得点を最大化せよ
    • 毎ターンスコアが2減少する
    • 壁に衝突したら100減少する(同時に複数の壁に衝突しても100減少)
    • 初めて到達した目的地にある場合は、1つにつき1000点得られる
  • 問題ごとの違い
    • A問題(60ケース): 壁なし＋風の影響あり＋計測誤差あり
    • B問題(60ケース): 壁10個＋風の影響小＋計測誤差小
    • C問題(80ケース): 壁あり＋風の影響あり＋計測誤差あり

時間

  • 360 分

個人的メモ

  • 幾何＋推定＋制御＋インタラクティブ＋オンサイト＋短期(6時間)＋チーム戦と、いろんな要素・状況が詰まっていた

チームでの分担

  • 今回の問題は、A問題+B問題=C問題のような感じで、チームでの分担がやや難しかった
    • 予選の問題は、傾向の違う入力ごとに分担とかができた
  • うまく「全員で各モジュールを開発して1つのソルバーを作る」みたいなチームプレイができればよいが、連携も難しいので練習が必要そうかも
  • 1位チームはうまくチームプレイができていたみたい(どういう分担だろう？)

自己位置推定

  • ロボットなどでの自己位置推定手法が使える
  • 今回の場合、1位はパーティクルフィルタで自己位置推定していた模様

計測のタイミング

  • 何ターンかに1回ずつ計測
  • 推定精度が低いときに計測(ただし、計測ばかりにならないように調整)
  • など

計測値とのズレをそのまま位置にフィードバック

  • 計測した値には誤差があるが、そのまま扱っても誤差が小さいケースなどではうまく動く
  • 誤差があることも想定して、計測のたびに、その差分の何%分かだけを現在の位置に加える、なども
    • (平均的には実際の値なので、ある程度うまくいくみたい)

パーティクルフィルタ(粒子フィルタ)

  • 今回の場合、いろんな状態(位置、速度)のドローンを粒子として何個か用意し、測定結果などで各粒子の尤度を計算して可能性の高い粒子を作り直すことを繰り返すことで、その粒子から自己位置推定を行える
    • 粒子の平均や分散を推定値として使う
  • パーティクルフィルタの手続き
    • 初期位置で粒子をK個用意する
    • 各ターンについて以下を繰り返す
      • 加速操作の場合は、各粒子に対してその加速および速度・風の影響を適用する
      • 計測操作の場合は、計測値に対して、各粒子で尤度を計算し、その尤度を重みとして、重み付きサンプリングをしてK個の粒子を作り直し(リサンプリング)、速度・風の影響を適用する
  • リサンプリングのタイミング
    • 計測操作以外にも、壁にぶつかった場合、目的地に到達した場合も、おおよその位置が確定するので、尤度計算＆リサンプリングできる
  • 尤度の計算
    • 真の距離がdとして、得られる値はd*α倍になっている
    • したがって、dで割ったものは、α〜N(1.0,δ^2)になるので、αをこの正規分布の確率密度関数にいれた値が尤度になる
    • 各粒子に対して、その位置から計測した場合に得られる距離で割ってあげたもので尤度計算する
    • (または、正規分布のパラメータが変わるだけだと思うので、d倍されたものをそのまま扱うでも)
  • 計測方向
    • A問題の場合は外壁しかないので、一番近い外壁に対して距離を取得し、各粒子の位置での距離
      • x軸、y軸に並行な方向に測定する
    • 壁がある場合は、現在位置から壁(半直線)に直角になるようなものなどを列挙して、一番近い位置ものを採用
      • または、各粒子の方向の偏りなども考慮して、列挙した方向の中で、各粒子での計測距離がバラけそうな(粒子を選別できそうな)方向を選ぶとかもありっぽい(writer解)
  • 粒子が全滅した場合
    • 全滅前の粒子に対して、再度速度などを適用しなおす
    • または、その付近を広めにリサンプリングする、一様にばらまいてリサンプリングする

カルマンフィルタ

  • 自己位置推定の別の方法として、カルマンフィルタの適用なども考えられる
    • システムの状態に対して、次の状態の予測と観測値からの最適カルマンゲインを計算し状態の推定値を更新する
  • しかし、今回、壁などがあったりもするので、パーティクルフィルタの方が扱いやすかったかも

ドローン制御

  • 理想的には、速度を落とさずに目的地をスムーズに通り過ぎる、途中経路は曲線的に動く、などができれば良さそうかもしれないが、とても短期では難しいので、速度制限ありで、目的地に向かうように速度制御するだけでも十分

目的地に向かうようにだけ速度制御

  • 現在位置から目的位置までのベクトル上に速度ベクトルがのるように加速度ベクトルを決める
  • 速度上限は決めておく
  • 推定誤差や風の影響で、目的位置を通り過ぎる場合があるが、目的地に向かうのを繰り返すので、(推定位置がある程度妥当なら)多少ターン数がかかってもたどり着ける

PID制御

  • 1つの目的地に一直線に向かうことを考えると、これは、1次元で制御対象を目標値にする古典的なフィードバック制御の問題と考えられる
    • A問題1位はPID制御していたらしい
  • PID制御は、P(比例)制御、I(積分)制御、D(微分)制御からなる制御方法
  • P制御
    • 目的位置と現在位置の差(偏差)に対して、K_p倍したものを制御入力にする
    • 速度が出すぎていたり、目的地で速度が0になるように制御していないと、オーバーシュートや振動が起きたりしている
  • D制御
    • 目標位置での速度と、現在の速度の差に対して、K_d倍したものを制御入力にする
      • 目標速度で目的位置に移動できるように制御
  • I制御
    • 目的位置と現在位置の差を積分したもの(誤差の蓄積)に対して、K_i倍したものを制御入力にする
      • P制御だけだと最終的な定常値が目標値にならない場合で、その差分を埋めるように制御
  • 今回の場合、目的地点付近で速度0にする必要性はあまりなく、I制御もあまりいらないようで、P制御、PD制御だけで十分っぽい
    • なので、「位置の目標値との差分」と「現在の速度と目的地での速度との差分」に対していい感じの速度になるように制御してあげればよい

その他

パーティクルフィルタ関連

解説

(発言を見つけられた方のみ)