ゼミ学生研修2006-1

AIBOを使いながらロボットのプログラミングを学んでいきます。

今回の目標は「ポジショニング」です。ポジショニングとは、フィールド上の適当な位置から、自分が与えられた適切な位置に移動するというものです。例えばキーパーならゴールの前で敵ゴール方向を見ますし、フォワードなら試合開始時はフィールド中央に着くといったことです。
いきなりプログラムを作り始めるのではなく、問題の分析を行った上で、アルゴリズムを考えプログラムを作ることにします。

アルゴリズムの作成

アルゴリズムとは、おおざっぱに言って「問題の解き方」を言葉で書き表したものです。公式を使って直接結果が得られるようなものというよりも、何らかの手続きに従って解を見つけるといった、解を導き出す手順のことをアルゴリズムといいます。
アルゴリズムの例として有名なものは、最大公約数を求めるアルゴリズムです。

アルゴリズムの例

2つの非負整数の最大公約数を求めるアルゴリズムの例です。仮に2つの数をx,yとするとき、最大公約数を求めるアルゴリズムは以下のようになります。

手順1. xが0ならば、yが最大公約数である。

手順2. yが0ならば、xが最大公約数である。

手順3. x>yのとき、yとx-yをx,yに置き換えて、手順1からやりなおす。

手順4. y>xのとき、xとy-xをx,yに置き換えて、手順1からやりなおす。

手順にしたがって上から下に計算(処理)を行っていきます。特に指示があれば前の手順に戻ったり、後の手順まで飛んだりします。

これは効率の良いアルゴリズムではありませんが、2つの非負整数の最大公約数を必ず求めることができます。いくつかの例で試してみてください。

アルゴリズムの性質

最大公約数を求めるアルゴリズムのように、アルゴリズムと呼ばれるものはある種の性質を持っています。逆の言い方をすると、そのような性質が満たされていなければアルゴリズムとは呼べません。

アルゴリズムの性質:厳密性

厳密性とは、アルゴリズムの手順が「あいまいではない」ことです。手順として何を行うのかあいまいであったり、いろいろな意味にとれるようなものであってはいけません。各手順が何をするのか明確である必要があります。

アルゴリズムの性質:実際性

実際性とは、手順に示されていることが有限時間内に実行できるような基本的なものでなければならないということです。

アルゴリズムの性質:停止性

停止性とは、アルゴリズムが最終的に何らかの結果を出して停止するということです。手順を無限に繰り返して永遠に終わらないようなものではいけません。

先ほどの最大公約数の例では、2個の正の整数を互いに引きながら手順を繰り返していきます。そこに含まれる行為は引き算や値の入れ替えですから、厳密性や実際性は満たされています。また、手順3か4のどちらも、2つの値のいずれかを減らすので確実に0に近づいていきます。ですから停止性も満たされています。

このアルゴリズムは簡単にプログラム言語で表現することができます。何かの問題を解くプログラムを作る場合、このようにアルゴリズムを考えてから作った方が、適切かつ効率的に作り上げることができるようになります。

ゼミ学生研修2006-1の課題

問題

ロボカップ2006のフィールド上に適当に置かれたAIBOが、あらかじめ指定された位置へ制限時間内に移動するようにしたい。

問題の分析

この問題を解くために、フィールドのサイズや構成、AIBOができることなどをきちんと理解する必要があります。

フィールドサイズ

ロボカップ2006のフィールドは、4m×6mのシート上で3.6m×5.4mの大きさに設定されています。
フィールドには位置を確認する目印として2つのゴールと4つのビーコンが置かれています。(※この課題ではゴールは使いません)
その他、センターラインやセンターサークル、ペナルティエリアが定められています。

AIBOにできること

AIBOには鼻先にカメラがついており、周囲の状況を把握することができます。ただし、物体として認識できるのは、ボール、ゴール、ビーコンだけです。物体といっても色(オレンジ、ピンク、黄色、青色)を認識するだけなので、似たような色が見えれば他の物体と勘違いしてしまいます。

なお、カメラには視野角があり、カメラの向いている方向で左右30度程度の範囲しか一度に見ることはできません。また4m以上離れた箇所を見ることもできませんし、首の角度に限度があるため、近くて高いところにあるものを見ることもできません。
AIBOは4足を使って歩き回ることができますが、歩く速度には上限があります。フィールドの材質も均一ではないので、微妙な動作や正確な動作もあまりできません。
私たちのシステムでは、AIBOは一度に7cm進む、12cm進む、18cm進むことと、10度回転する、30度回転する、60度回転するということしかできません。

ポジショニングの実際

ロボカップでは試合直前に、人間の審判によって適当な位置(適当な向き)にAIBOが置かれます。ゲームコントローラというシステムの指示によって、一斉にAIBOへポジショニングの指示が送られます。この指示を受けたら、AIBOは攻撃側、守備側として適切な位置に自動的に移動しなければなりません。
ポジショニングに使える時間は30秒となっており、30秒以内に適切な位置につけなかったAIBOは、罰として不利な位置に強制的に配置されます。

アルゴリズムを作る

これらの前提条件に基づいて、AIBOを適切な位置に移動するポジショニングのアルゴリズムを作るのが今回の課題です。

アルゴリズムですから、プログラムを作るのではなく、手順を日本語で表現すれば良いのです。もちろん先に示した3つの性質は満たさなければなりません。今回の場合、30秒で強制的に止められるので停止性は気にしなくてかまいません。
厳密性や実際性については、きちんと考えておかないと後でプログラムを作れなくなってしまいます。気をつけてください。

解決目標のレベル

解決するといってもそれほど簡単な問題ではありません。そこでいろいろなレベルを用意しました。最低限のレベルクリアを目標にし、できればより高度なレベルをクリアするようがんばってほしいと思います。
レベルごとにポイントをもうけ、最終的に得たポイントの多かった人にはご褒美をプレゼントすることにします。

レベル1:1ポイント

フィールド内の味方陣地側にいること。

レベル2:2ポイント

フィールド内の味方陣地側で、かつ2つのビーコンよりゴール側に完全に入っていること。

レベル3:3ポイント

レベル2と同様だが、頭が敵陣地側を向いていること。

レベル4:4ポイント

味方陣地のペナルティエリア内に完全に入っていること。ゴール内は不可。

レベル5:5ポイント

レベル4と同様だが、頭が敵陣地側を向いていること。

レベル6:6ポイント

センターサークルの内側に入らずに、かつ中心から鼻先までが20cm以内にあること。

手順例

日本語で表現してかまわないのですが、厳密性や実際性を保つために、書き方のサンプルを示しておきます。

手順の例:
青ピンクビーコンが前方に見えたら18cm前進する。

ピンク黄ビーコンが、左30?50度、50cm?1.5mの範囲に見えたら手順xxに進む。
黄ピンクビーコンを目で追い続ける。
5秒間、18cm前進を繰り返す。
60度左回転を3回行う。

アルゴリズム例

(今回は使いませんが)ボールのところに行って止まるアルゴリズムの例です。完全でも最適でもありませんが、書き方を参考にしてください。

手順1. ボールが見えないなら、60度左回転して手順1へ戻る。

手順2. ボールが前方20cm以内に見えたら停止して終了する。

手順3. ボールが左に見えたら30度左回転して手順1へ戻る。

手順4. ボールが右に見えたら30度右回転して手順1へ戻る。

手順5. それ以外なら18cm前進して手順1へ戻る。

4/18までにすること

達成目標とするレベルを決め、そのアルゴリズムを考えてください。
なお、どのレベルを選んだ場合でも、ランダムな位置(と方向)から始めて3回中3回とも成功するようなものでなければなりません。
アルゴリズムは手書きではなく、このwikiシステムの自分のページに書いてください。

4/18のゼミで行うこと

4/18のゼミでは各自に自分のアルゴリズムについて説明(3分)してもらいます。説明ではオリジナリティとともに厳密性、実際性が充分に守られていることがチェックされます。自分のアルゴリズムの良さを充分説明できるように準備しておいてください。
次の課題は作成したアルゴリズムに基づいてプログラムを作ります。

その他

ゼミ学生同士で議論したり相談するのはかまいませんが、最終的には各自オリジナリティのある考え方でアルゴリズムを作成してください。

資料

figure1.png

図1. フィールド全体の図解(単位=mm)