障害物を回避してみよう

続・周囲情報 gSurTiles[]

マップ a25x70_level05.txt は経路上に障害物があります。

そのため コード 8.2を使うと障害物に当たって前に進まなくなります。

これをなんとかするには障害物を見つけて回避する処理を入れるしかありません。 障害物を見つけるには前回でも使った周囲情報 gSurTiles[] を使います。 あの時は「今目指している場所か」を知るため & NEXTFLAG_TILE という文字を添えましたが、今回は「障害物かどうか」を知りたいので & OBSTACLE_TILE という文字を添えます。 とりあえず真正面が障害物なら右回転する処理を追加してみましょう。

上手く動きません。 ここでプログラムがどう動いているか考えてみましょう。

Loop() の中に入りました。 最初にチェックするのは右斜め前に目標かどうかです。

そこには目標はありません。

そこで次の if 文に入ります。 そこでは目標が前にあるかどうかチェックしてます。

ばっちり前ですね。

そのためロボットは前に進もうと NaviCmd(1,0) を実行します。 前方に障害物があるかどうかなんて関係ないのです。

つまりきちんと障害物を回避するためには「目標が前方にある」よりも「前方が障害物である」ことを優先して処理しなければならないのです。 優先度を上げるには前に書けばいいです。

無事に障害物を回避してゴールできるようになりました。

シンプルなアルゴリズムですが結構強いです。 次の図はマップ a25x70_level06.txt で試走した結果ですが きちんとゴールできてます。

障害物にハマる可能性

コード 9.2 は強いですが万能ではありません。 その分かり易い例がマップ a25x70_level07.txt です。

へこんだ所でくるくる回って脱出できなくなってしまいます。

なぜこんなことが起こるのでしょうか。

まず前面にぶつかります。 真正面が障害物なら右旋回するというルールなので右旋回します。

真正面に障害物が無く、かつ目標は前方向なので前進します。

また正面が障害物になりました。右旋回します。

右旋回した結果目標が後方になってしまいました。 しかたないので右旋回します。

まだ後方なので右回転します。

まだ後方です。右回転します。

旋回した結果、前面が障害物になりました。 右旋回します。

まだ前面が障害物です。 右旋回します。

振り出しに戻りました。

以降これが永遠と続き脱出できなくなったのです。

障害物回避モード

このような問題を解決する方法の一つに 障害物にあたると障害物を回避することに専念する「障害物回避モード」に移行することです。

グローバル変数で AvoidMode という今のモードを表現するものが必要なので、 全体を示します。 RESET ボタンを押すと実行される Init() の中身で通常モードの意味を表す 0 を 代入します。 そして Loop() の中身でこの値が 1 なら障害物回避モードの動作を、 0 なら通常の動作をするのです。 通常モードの動作は、前面に障害物があれば AvoidMode に 1 を代入する処理を 追加したこと以外はコード 9.2 と同じです。

さて、この「障害物回避時の動作」としてどのような動きが望ましいでしょうか。 シンプルに前に行けたら前に、行けなかったら右旋回としてみましょうか。 次のようなコードで実現できます。

動きは変わりましたが望む動きではありません。

障害物回避モードに入る時、右旋回しているので左側に障害物があるはずです。 左前に進めるなら前進より優先してそっちに進むべきでしょう。 そうしてみましょう。

障害物に張り付きだしました。

張り付いた理由は簡単です。 障害物回避モードから通常モードに戻る処理を入れてないからです。 この通常モードに戻るきっかけですが何がいいでしょうか。 とりあえず「目標が前にあって、かつ真正面が障害物でない」にしてみましょうか。

なんか上手く動くようになりました。

壁伝いによる失敗

上手く動いたと喜んだのもつかの間、コード 9.6 には致命的な欠点があります。 壁にあたっても右方向に回頭してしまうのです。 運が悪いと同じ所を回ってしまいます。 作為的にそれを起すマップが a25x70_level08.txt です。 このマップに対しコード 9.6 を動かしてみると次のようになります。

目標つかずひたすら壁をつたってしまいます。 これもなんとかしたいです。

根源はここです。 右に回る、前は壁、右に回る、前は壁と 180°回って前が空いた時、 目標が後ろにあるためです。 対策方法はいろいろ考えられますが、 初めて障害物に当たったら左回転してみるのはどうでしょうか。

だめです。左回頭をし続けて同じ状態になってしまいます。

どういう風になっているかを知るには、コード 9.6 がどういう処理なのか きちんと確認しておく必要があります。 あのコードの動きをフローチャートにしてみましょう。

前に進めるより左前が空いていたらそちらを向くことを優先していたのです。 最初に壁にぶつかるので左に旋回します。

この状態で先ほどのフローチャートに入ります。 左前に進めるので左旋回します。

まだ左前に進めるので左旋回します。

ここで左前に進めなくなったので前進します。 目的地は後ろにあるので回避モードのまま前進してしまったのです。

こういった動作を防ぐには

1. 回避モード時で前進できる時に目的地が前面にあったら回避モードを終了する
2. 最初左に旋回した後、目的地が前面にあったら回避モードを終了する

という二つの方法が思いつきます。 1. はまず前進できるかどうかを判定し、その中で目的地が前にあるかチェックするように書き換えればいいでしょう。 いい練習問題になると思います。

ここでは 2. の方法について紹介します。 「通常モード」「左旋回モード」「障害物回避モード」の三つを作るのです。

コード 9.8 では通常モード中、前面に障害物があれば左旋回しつつ AvoidMode を 1 にして「左旋回モード」に入ります。 左旋回モードでは、前面に障害物があるか目的地が後方にあれば、 右旋回しつつ AvoidMode を 2 にして「障害物回避モード」に入ります。 逆にそうでなければ (障害物が前面になく、かつ目的地が前方にあれば) 前進すると共に AvoidMode を 0 にして通常モードに戻ります。

無事マップ a25x70_level08.txt もゴールできるようになりました。

自然に見る障害物回避

コード 9.8 まで来て、それなりに障害物が回避できるようになりましたが、 それでもハマッてしまうパターンがあります。 障害物をこう配置されていたら、ああ配置されていたらと想定し、 その場合どのようにすれば脱出できるか工夫してみるのは面白いでしょう。 その際、自然界の動物の戦略を見てみるのもいいかもしれません。

ダンゴムシという生き物がいます。 あれは「交替性転向反応」と呼ばれる動きをします。 障害物に当たり右に避けたとします。 すると次に障害物に当たると左に避けるのです。 左右必ず交互に避けるのです。 一方でミミズやハエ等は時間によって障害物に当たったときの避ける方向を 変えています。 そういう動きを取り入れるとハマるパターンの種類を減らせるかもしれません。

一方であれこれ回避策を組み込んでも、 なんか上手く脱出できるようにならないパターンがあるかもしれません。 例えば次のようなパターンです。

流石にコンテストではこんな鬼畜なトラップをしかけるつもりはありませんが、 このトラップを脱出するプログラムを作るのはかなり難しいと言っておきましょう。 そしてそれは自然界でもいっしょです。 小学校ででしょうか、定置網と呼ばれる漁法を習ったことがあると思います。 海に真上から見て次のような形になる網を仕掛けるのです。

魚は右端の箱網と呼ばれる部分に入りやすく、 かつ一度入ると脱出が難しくなります。 漁師さんはここから逃げ出せなくなった魚を獲るのです。 似たようなものに、セルビンとかビンドウとか呼ばれる漁具があります。 断面が次のようになっている透明な瓶です。

あまりにも容易に魚が獲れるので、生態系を守るために国内では 正式には使用が禁止されています。 この仕組みも同じです。

なぜ魚が入りやすいのか、そして脱出しにくいのか、プログラムを通して感じてもらえたらと思います。