« もうしばらくかかります (^-^) | トップページ | 旅人 (^-^) »

2006年5月 3日 (水)

迷路探索シミュレーション(3)

5/1(月)からCATV経由でインターネットにつなげるようになりました。ぼちぼち日記をアップしていきます。

4月末から迷路探索アルゴリズムのシミュレーションを行ってきました。単純な左手法、仮想壁を利用した拡張左手法、距離マップを利用したポテンシャル法(足立法?)の3通りのアルゴリズムを実装して、探索走行、自動帰還、最速走行(タイムアタック)、自動帰還までできるようになりました。使用しているシミュレータの都合上、1区画ずつ移動しては停止して壁を記録する走り方になっていますが、拡張左手法、ポテンシャル法どちらでも第1回~第20回大会の迷路をクリアできているので、(バグがないとはいいませんが)正常系に対して正しく動作することは verify できたものと思っています。

拡張左手法を実装して動かしてみた感想ですが、無駄な動きがかなり多いですね。仮想壁を利用しているせいで、経路の分岐点まで戻るときに余計にグルグル回って戻ってきます。これは俗に「枝刈り」と呼ばれる袋小路に仮想的に蓋をする処理を追加すれば、少しはましになるのではないかと思います。大会で使われた迷路自体が拡張左手法を意識して作られているのか、拡張左手法を使うとほぼ迷路を全面探索することになる迷路が多かった気がします。

一方、ポテンシャル法(と私が勝手に呼んでいる距離のマップを利用した手法)では「枝刈り」自体必要ない処理です。私は目的位置から迷路全体への距離マップを作り、マウスの現在位置から距離が短くなる方向を選択して移動する方法をとっているため、スタート地点からゴール地点に向かうときはゴール地点(x4つ)を目的地点に、ゴール地点からスタート地点に移動するときはスタート地点を目的地にすることで、一つのアルゴリズムでスタートからゴール、ゴールからスタートまでの処理を扱うことができます。ゴール地点からスタート地点に戻る際にも探索を行っていますが、最速走行(タイムアタック、第2走行ともいう)時でも未探索区画の壁がないものとして扱っているため、1回目のタイムアタックでは未探索区画に入ってしまいます。迷路はクリアできるので、とりあえずそれでいいかなと思っています。

今シミュレーションプログラムの実装はC言語なのですが、設計はオブジェクト指向的にやっているのでC++を使いたい、けれど、YellowSoftのコンパイラはCコンパイラしかないし、でも、(評価版の)ルネサスのコンパイラやGCCならC++が使える・・・といろいろ迷っています。

« もうしばらくかかります (^-^) | トップページ | 旅人 (^-^) »

コメント

こんにちは

 早速、改良版のスケジューラを実装させてもらいました。
 こちらも前回同様、うまく動作しました。
 #ARM-60MHzなので、前回のでも問題なしです。

 ありがとうございました。
 取り急ぎ、ご報告とお礼です。

では

コメントありがとうございます。

TeamKNOxさんのホームページ/Blogを見せていただきましたが、私よりずっと経験が豊富な方のようですね。

さて、私が公開した簡易スケジューラについてですが、http://homepage1.nifty.com/BROKEN/project/humanoid2003/exp_scheduler.htm
は動くは動くのですが微妙な設計ミスがあり、どうしても処理タイミングのずれが出てしまいます。これは割り込み処理の中でタスクの wakeup count を更新していることが原因で、改良版がhttp://homepage1.nifty.com/BROKEN/project/humanoid2003/exp_multi_servo.htm にあります。

コントローラ設計の一助になれば幸いです。

こんにちは

 PICを用いたロボのコントローラのスケジューラ、参考にさせていただきました。
 http://www.teamknox.com/mt/archives/2006/05/post_137.html
 ありがとうございました。

これからもよろしくお願いいたします。

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/167990/9875632

この記事へのトラックバック一覧です: 迷路探索シミュレーション(3):

« もうしばらくかかります (^-^) | トップページ | 旅人 (^-^) »

最近の写真