読者です 読者をやめる 読者になる 読者になる

drilldripper’s blog

機械学習とソフトウェア開発を頑張ってます

ETロボコンの走行を支える技術

What is ETロボコン

ETロボコンは統一規格のロボット(Mindsorms EV3)を使い、指定されたコースを走行する精度とタイムを競う競技です。UML等で書かれた仕様とアピールポイントをまとめたモデルシートを作成する必要があり、モデルシートも評価の対象となります。

ETロボコン2016公式サイト

統一規格のロボットを使うというルールから分かる通り、ソフトウェアデザインとアルゴリズムに重きが置かれたロボコンと言えます。*1珍しい特徴として、ETロボコンは学生チームと企業チームが同じ土俵で戦います。*2車両開発系や組込系のIT企業も参加するとても熱い競技です。

今回はロボットの走行を支える一般的な技術について書きたいと思います。UMLなどのソフトウェア設計技術も順位決定の重要な要素ですが、今回は触れません。

ライントレース

ロボットは基本的にコースに引かれた黒い線を追いかけて走行します。原始的な手法として、白を検知したら右に旋回し、黒を検知したら左に旋回するという手法があります。下の図ようなイメージです。 f:id:drilldripper:20160925192150p:plain

これは一般にON/OFF制御として知られている手法です。この手法では右と左にしか動作することができないので、ロボットがジグザグな動きとなります。当然安定性が低く速度も遅くなります。これを改善するためにPID制御が用いられます。

PID制御

PID制御(Proportional-Integral-Differential Controller)は古くから使われるフィードバックループの制御手法の一つです。名前の通りフィードバッグの要素として比例値P、微分値I、積分値Dを使います。PID制御は以下の式で表されます。

{  K_pe(t) + K_i \int_0^t e(\tau) \: d\tau + K_d\frac{de(t)}{dt} }  (tを時間、eを入力と目標値の誤差とする)

各項の意味を簡単に説明します。(そのため正確性は少し欠いているかもしれません)

  • Kp値(比例制御):

    • 入力値と目標値(出力したい値)の偏差を計算し、偏差の大きさによって操作量(出力に近づけるための値)を変化させます。
  • Ki値(積分制御):

    • 入力値の目標値の偏差を積分をします。偏差がある状態が長く続くほどこの項は大きくなり、目標値に近づいていきます。
  • Kd値(微分制御)

    • 積分制御の項が大きくなりすぎると、目標値を超えて制御不能になる場合や、目標値の前後を振動してしまう場合があります。そこで微分制御では偏差の微分値を計算することで、急激な変化を捉えて動作を押さえ込みます。

PIDの各パラメータを適切に設定できれば、ロボットを滑らかに走行させることができます。

探索アルゴリズム

走行エリアには難所と呼ばれるアトラクションがあり、クリアするとボーナスポイントを取得できます。難所の一部は探索問題に帰着させることができる場合があります。問題をよく考察してグラフなどのデータ構造に落とし込めば、以下のアルゴリズムが使用できます。*3

計算量や実装難度と相談して、攻略に最適なアルゴリズムを選びましょう。

データ分類(機械学習)

ロボットからは様々なセンサ情報を取得することが出来ます。EV3であればジャイロセンサ、超音波センサ、光センサなどから情報が取得できます。取得したセンサ情報から状況を把握することで、ロボットの次の動作を決定できます。

人間が手動で分類の閾値を決定することもできますが、うまく教師データを作ることができればRandom ForestやSupport Vector Machineなどの機械学習アルゴリズムを活用できる可能性があります。

デッドレコニング(自己位置推定)

競技ではロボットの位置によって動作を変更しなければならないので、ロボットの自己位置を推定する必要があります。センサ情報とロボットの仕様から自己位置を推定する手法を、一般的にデッドレコニングと呼びます。

デッドレコニングは走行距離が長くなると、蓄積した誤差によって自己位置の推定に失敗してしまいます。そのため何らかの工夫で誤差の蓄積をリセットする必要があります。

タスクの制御

ロボットの上で複数の処理を同時に動作させるさせることで、柔軟な処理が可能になります。リアルタイムOSでは処理をタスクと呼ばれる単位に分割して、優先度を決めて動作させるさせることができます。

一般的な並列プログラミングと同様に、排他制御に気を使う必要があります。

おわりに

いろいろ技術を学ぶことができる熱い競技なので、課題*4をクリアできるのであれば参加してみると楽しいと思います。

*1:ETロボコンの正式名称はEmbedded Technology Software Design Robot Contestです。名前からもソフトウェアに重きを置いていることがわかります。

*2:ISUCONなどと同じですね

*3:一瞬「競技プログラミングは役に立たない」の反例かと思ったが、競技の攻略に競技が役立ったと主張するのはだめな気がします

*4:時間、予算、練習場の確保、チームメンバ集めなど