歩数マップ更新

この記事を書く背景

皆さんはマイクロマウス、ひいては、他のプログラムにおいて、計算コストというのを気にしたことがありますか。
ここでは、コストが高い=時間がかかるとし、そのためには多少のメモリを使うという思想で話します。

前提1:速い処理と遅い処理について

処理の速さとは、今回注目する、歩数マップ更新の更新においては、
ループの回数が少ない=速い処理であること意味します。
厳密には、加減乗除もコストに入るわけですが、今回に限っては、四則演算は求められないので、関係ありません。
その他、CPUの性能やメモリ等のリソースに関して、ここでは触れません。

前提2:必要な知識

この記事では以下の知識を要求します。

  • 基礎的な歩数マップ更新のプログラムが理解できること。
  • ビット演算を理解していること。

実装例

  
void updateDist(int x, int y, int mode) { //(x,y)ゴール座標
    unsigned char distPositionList[257];
    char head=0, tail=1;
    distPositionList[0] = x * 16 + y;
    clearMap(x, y); //歩数マップ初期化
    while (head != tail) { //head = tail なら更新する区画がない
        char Y = distPositionList[head] & 0x0f;
        char X = (distPositionList[head] & 0xf0) >> 4;
        head++;
        int distPoint= dist[X][Y] + 1;//歩数値
        char D = 1;//方向用の変数
        while (D <= 8) {
            char i = 0, j = 0;
            if (D == North) {//North=1
                j = 1;
            } else if (D == East) {//East=2
                i = 1;
            } else if (D == West) {//West=4
                i = -1;
            } else if (D == South) {//South=8
                j = -1;
            }
            //更新対象か確認 mode = 1(最短)のとき、既探索かを内部でチェック
            char isUpdateTarget = (mode==1) ? proceedEnable(X, Y, D) : !existWall(X, Y, D);
            if (isUpdateTarget  && getDistance(X + i, Y + j) == ILLEGAL_ARGUMENT) {
                if (X + i < 0 || X + i >= MAZE_SIZE || Y + j < 0
                        || Y + j >= MAZE_SIZE) {
                } else {
                    dist[X + i][Y + j] = distPoint;
                    distPositionList[tail] = ((X + i) << 4) | (Y + j);
                    tail++;
                }
            }
            D *= 2;
        }
    }
}

説明・解説

アルゴリズム解説

更新座標格納用配列qに初期値として、ゴール座標を格納、
隣接する座標に歩数を割り振り、
その座標を配列に格納、次の隣接する座標を探します。
無理やり1次元配列としている理由は、データ節約のためです。
ハーフでは2次元配列としてもよいと思います。
while(D<=8)としているのは、ソースの再利用性を考慮した結果です。

更新する座標情報の格納について

更新座標格納用配列qの各値には以下の法則で値を格納します。

  • 上位4ビットをX座標
  • 下位4ビットをY座標

headがインクリメントされ、値を参照したとき、上記のソースコードのようにX,Yに複合化します。

32*32の場合でも、同様の手法が使えます。

計算コストについて

今回紹介したアルゴリズムは、最大O(n)です。
ちなみに簡単に思いつく手法として

  
char looping = true;
while(looping){
    looping = false; //全座標を参照後更新がなければ、breakする仕掛け。
    for(int i=0;i<16;i++){
        for(int j=0;j<16;j++){
            if(dist[i][j]==targetDist){
                if((map[i][j+1]&0x11)==0x10){ 
                    dist[i][j+1]=dist[i][j]+1;
                    looping = true; //更新が続く可能性があるのでフラグをtrueにする
                }
                // 以下略
            }
        }
    }
}

上記のような感じになりますが、for文が3段階にネストしています。
この場合、計算コストはO(n^3)となります。
これがハーフサイズ決勝のサイズになったときの計算時間を想定した場合、恐ろしいことになります。

まとめ

計算コストについて意識する場合、ループ数を気にする
これだけです。

Exiaのスペック紹介

Exia

This is a my micromouse in MM2016.
Robot name is Exia that originate from Gundam00.
It has a suction design.

f:id:nao1288stusj:20161014013833j:plain

Spec

min max
MaxSpeed 3.5[m/s] 5.1[m/s]
MaxSpeed(diagonal) 3.2[m/s] 4.8[m/s]
Acceleration 18[m/s/s] 21[m/s/s]
Deceleration 22[m/s/s]
Turn 90 1.2[m/s] 1.9[m/s]
Turn 180 1.2[m/s] 2.0[m/s]
Turn 45 1.2[m/s] 1.9[m/s]
Turn 135 1.2[m/s] 1.9[m/s]
Turn 90(diagonal) 1.2[m/s] 1.9[m/s]
Hard
Size L 96mm,W 74mm,H 32?mm
Weight 108g
CPU RX631(64pin) IDE is e2studio
Motor 1717-003SR+IEH2-4096
Motor(for suction) DCX10S
Mortor Driver TB6614FNG
LED SFH4550 *4
Sensor (Photodiode) ST-1KL3A *4
Battery Nano-Tech 200mah×2 ⇒ 2Cell(7.4V)

Result of Cotest

Qualifying round

NoRecord(Seeded)

Final round 

Try 1 2 3 4 5 Best
Time 30.041 R 4.924 R R 4.924

2nd try is best run. at that time, turn velocity is 1.7m/s all.so Exia shoud run more fast.

全日本大会

結果

3位!!!!! やりました。 f:id:nao1288stusj:20161121014138j:plain

今までで一番の成績です。

後輩全員バスターしたので、今シーズンのバスターズのクラシックの防御率は0.00で終えることができました。

個人としては、最短が1度しか成功できなかったため、金沢草の根大会のときと比べると、かなり安定性に課題が残るものであったこと。
ちゃんと走れていたと仮定すると、かなりいいタイムが出せていたことがわかりきっているので、悔しいです。

走行詳細

  1. 探索(無事全面探索終了、約2分半を消費)
  2. (最短)一番下 失敗!?
  3. 下から2番目 4.924
  4. 上から2番目 失敗
  5. 一番上 失敗

という構成でやっていました。

中部支部での試走では一度も失敗していない速度で減速に失敗していたことから、グリップの感触が良すぎるのかと予想。今後のオーバーホールで改善させます。

ターンについては、上位のパラメータ群のほうが作りこめていたので、それを使えなかったことが残念でした。

来年について

多方面からハーフに出ないのかというコメントをもらいましたので、どっかのO氏が以前反対されていたが、これで彼の意見はマイノリティとなったので、作ろうかなと思います。

作らない理由も特になくなったことと。
作るための要素技術の情報収集もある程度終えられたかな?と思います。

テーマについて

ハセシュマウスの飼い主からは、毎度私のマウスをみて、つまらないと言っていますが。
今後も、彼の眼を楽しませるマウスは作らないでしょう。

理由は、ハードウェアの革新はテーマとして持たないとしているからです。
ついでに言うと、制御を極めることでも、処理速度を追求することも違います。

調整の自動化というのをテーマにしようかなと思います。 詳細やどうやるかはそのうち。

さすがに、眠いです。

データフラッシュの運用

データフラッシュについて

まずは、以下のブログをご覧ください。

ここ数週間、一番ホットなブログですね。

データフラッシュを運用することで、以下のことが可能になります。

  1. 既存のRAM領域以上の領域を扱える
  2. 電源を落としても迷路情報を保持できる
  3. プログラムを書き換えても継続できる

上記のリンクから、1と2の実現が可能だと思います。

が、しかし。 一部トラップ(事故設置型)の回避と、
3のを行うためには、 リンク先には含まれていない情報があるため、それを補完します。

RX631のFCK指定

RX631では、外部クロックの利用のため、いくつかのコードを記述する必要があります。
クロックの起動後、CMTやMTUのタイマーで使用する分周比を設定するのですが、ここで引っかかりました。

SYSTEM.SCKCR.BIT.PCKB = 1;
SYSTEM.SCKCR.BIT.PCKA = 1;
SYSTEM.SCKCR.BIT.BCK = 1;
SYSTEM.SCKCR.BIT.FCK = 1  //ここ
SYSTEM.SCKCR.BIT.ICK = 1;

ノリと勢いで、とりあえず1にしてしまったせいで、誤動作し、

  • 書き込みが不安定
  • 削除が不安定
  • 読み取りした値にffが混じる。

といったことがありました。

SYSTEM.SCKCR.BIT.PCKB = 1;
SYSTEM.SCKCR.BIT.PCKA = 1;
SYSTEM.SCKCR.BIT.BCK = 1;
SYSTEM.SCKCR.BIT.FCK = 4;  //今は4で運用してます。2でもいけるはず?
SYSTEM.SCKCR.BIT.ICK = 1;

どうやら、FCKが早すぎたらしいです。
細かいことは各自よろしく。とりあえず、お気を付けください。

書き込み後にデータフラッシュ領域の値が書き換わる

以下の記事は、検証が雑です。
皆さん頑張ってください。

皆さんmotファイルをマイコンに書き込み時には、ツールから、指定した領域に対して書き込むことになります。
このとき、データフラッシュ格納領域にも改変が行わる場合があります。

そのため、ログは取ったけど、出力するコードがないため、全部やり直しということになります。
そんなことは嫌ですよね? このとき必要なものが、IDコードプロテクトです。

詳しくは各自!

RX631のデータシートでIDコードで検索してもらえれば、どんなものかわかると思います。
自分の用途では、p.1908に書いてあるコードをvecttbl.cで修正するだけでした。

さて、コードも書いた。書き込んだ。これでいける!!
と、思うじゃないですか。
先ほどのIDコードが書き込みツール上で必要になります。 値はデータシート丸コピです。

const unsigned long id_code[4] = {
    0x45010203,
    0x04050607,
    0x08090A0B,
    0x0C0D0E0F
};
//  上位8byte = 0x4501020304050607
//  下位8byte = 0x08090A0B0C0D0E0F
//  全体連結  = 0x450102030405060708090A0B0C0D0E0F

書き込みツール(Resesas Flash Prgrammer)で以下の操作が必要になります。

  • 操作設定タブ > ベリファイのチェックを外す。
  • ブロック設定タブ > DataFlash 1 のEraseチェックを外す。
  • 接続設定 > IDコードの設定 で連結したIDコードを入れる。

以上です。
Renesas Flash ProgrammerFDT2倍の速さで書き込みができることと、 IDコードの保存できるため、おすすめです。

昔は操作しにくかったのですが、V3にもなり、使い勝手がFDT以上になったと思います。
Windows10環境でFDTを使うとIDコードあたりの動作がかなり不安定でした。
アプリ落ちるし、毎回IDコードを問われるし。イラついたため、消えてもらいました。

それでは、自分に合った運用を見つけて快適なマウスライフを。

中部地区大会本番

Buster完了

ExiaRepairⅡで、中部地区大会のクラシック競技、サーキット競技に出場しました。
結果は、どちらも準優勝。とても満足です。

f:id:nao1288stusj:20161024083344j:plain

Busterできたことで、YI氏を焚きつけることができたと思います。

こいよベネット!銃なんか捨ててかかって来い!

1位は赤い彗星でしたが、最高速については、もう少しExiaでもなんとかお近づきになれそうなので、全日本大会では日本人の選手層の厚さに貢献できればと思います。

サーキットでは、6.347秒という記録なのですが、1位の紫電改5.680秒0.667秒差
最高パラメータで滑空をやって見せたので、Exiaの中では中位のパラメータで走らせた分にしては、検討できたと思います。

大会後にU氏から、4点接地が崩れているとの指摘から、家具すべーるを少しつけることで、全体的な底上げになりそうだということが確信できました。
前作Cobaltでも先端と、後ろにそれぞれ、カグスベールをつけて、急加速しても4点接地を維持することで、安定性と高加速度を得られたことから、それの再現をするだけかなと。見積もっています。

以下に、今回の大会から個人的なポイントをまとめました。(完全自分用の備忘録です)

速度

実際に走ったのが4.5m/sです。 しかし、5.0m/sも減速時に低滑空状態にさえならなければ、使い物になりそうということが分かりました。

ターン

1.5~1.7m/s 壁をぶち破ったときには2m/s~2.3m/sを入れていました。

加速度

18m/s 前作のCobaltが22m/sが(怪しいですが)できていたので、まだ伸ばせるところ

制御

壁制御が非常に安定した。 東日本の時点で壁制御がろくにかかっていない(非常に限られた条件下でのみ、発動)という状態だった。

これを正しい状態に持って行けたことが大きい。

経路導出

やはり、南ルートからの、最後の斜め+斜めを選択した。 斜めの制御ができてきたのか、斜め中はこけなかったことも大きい
前提として、非斜め時の直進が安定することにより、続く斜めへの入りに安定性が増した。

探索

1か所怪しい動きをしましたが、位置座標がなぜか狂わず、続行。経路が正しく出ることに。(危ない)
もう少し工夫すべきことがある。

今後の課題

以下を北信越までに何とかしたい。

  1. データフラッシュの実装と運用慣れ
  2. 急加速への対応
  3. 探索が乱れた時の補助プログラム

中部地区大会前日試走会

中部地区大会前日試走会レビュー

投稿2こ目です。
最寄りの地区大会である、中部地区大会前日の試走会に行ってきました。

後輩たちは例によって、17時過ぎに来て確認や調整を一切せずといった余裕ぶり。
なんと途中で割り込みで秋葉神社に行ってきたこと。
その旅行の剛性低くないですか??
飲み会には二人ほど足りないような気がしました。
この一行、ばらけてしまうとは、やはり剛性に不安がありますね。

懇親会での話ですが、明日の迷路を楽しみにしてろとのこと。
楽しみにですね。

昨日にも、大きなバグをつぶせたのですが、それでも不安事項というのは多いです。
東日本大会以降につぶしたバグは

  1. 最短で減速しない
  2. 割込みが16kHzでまわる
  3. 姿勢制御が限られた条件下でしか働ない
  4. 壁切れが不安定

です。

いずれも安定走行には不可欠で、(何でそれで東日本に動いていた)
ターンの調整だけでは解決しない、本番で浮き彫りになるバグです。

探索中の補正

皆さんはどれぐらいやってますか?
いくら最短が早いと言え、 経路導出以前に探索がしっかりしないと、勝負にならないのですが、どうもしっくりくる方法がないですね。

今のところ以下の、補正を入れています。

  1. 直進時の壁切れ補正
  2. スラローム時に前壁があるとき、前壁のセンサー値が一定以上になるまで待つ、前壁補正。

いずれも強力な補正ですが、明確に壁・柱があることが前提なので、頼りにならない場面が当然あります。

スラロームの直進区間(前距離・後ろ距離)中になんとかならないのか今探しているところです。

壁切れ、前壁補正は、理想の状態に近づける補正ですが、 スラローム中の補正というのは、それが難しいので、それ以上悪化させないといった、別の方法をとることも考えるべきなのかもしれませんね。

何か良い案があったら、教えてほしいです。

ブログ移転します。

ブログ移転

前のブログから移転します。

Visual Studio Code のmarkdownプレビュー機能のおかげで、きれいに書けるようになったので、思い切って新しいブログを作ってみました。(そして、はてなブログ上のエディタにもプレビューあることに驚愕しました。)

自分は活字だけのブログは基本飛ばし読みをするので、見出しとか、画像とかをざっと見て、ほしい情報ならじっくり読むというスタンスですので、見出しとか、いろいろ小細工ができるのがうれしいわけです。この文は記事をあらかた書いた後に、付け加えているのですが、当然自分なら、この段落は最後に読むことになると思って、文章の密度をわざと上げています。ね?ここだけ読みにくいでしょう?

markdownの作法も勉強中なので、慣れてくればもう少しビジュアルに凝って書いていきたいと思います。

参考URL

マウスの進捗について

Exiaのが突然の死を遂げました。

静電気なのか、余計な埃で導通したのかわかりませんが、ヤツは死にました。

というわけで

ExiaRepairⅡ 始動です。

部品の在庫は確保しておいたので、計6時間の作業ですべてを復旧\ 1度目の作成で得た知見から、半田付けの手順を一新。 ホットプレートを買ったので、リフローも考えたのですが、 やはり一度さっちゃんと一緒にお好み焼きを食べてからでないと と思いとどまりました。

もう動いています。 f:id:nao1288stusj:20161014013833j:plain
赤は3倍速いので、壁切れセンサー2つを取っ払い。LEDを新たに付け加えました。
制御にも大きなバグがいて、複数使用する割り込みのうち、SPIを使用している割り込みが16kHzで動いていました・・・そりゃぁ動きがおかしくなる。

そして、
東日本がなぜ動いていたのかがわからない。
謎です。

吸引のスカートも素材を変えました。
現在、duty50%程度で前回と同じぐらい160g程度を出しています。
そのうち技術的なネタをこの場にフィードバックできたらなと思ってます。