経路探索について(1/3)

まだ終わってなかったようで安心しました（笑）
質問者さんそっちのけで申し訳ないです。

"掃引計画"という言葉は、コロナ社からでているロボット工学ハンドブックの目次に出ているところを見ると、専門用語なんじゃないかと思います。
http://www.coronasha.co.jp/np/detail.do?goods_id=2056
英語では sweep algorithm で探すと沢山出てきました。

> 事前に探索空間の情報が与えられているか否かでアルゴリズムは全然変わってきますよね．

探索空間の情報が与えらていない場合の常套手段は、「最初に壁沿いを1周して部屋の外形を把握すること」で、ほとんどの掃除ロボットはこれやってますし、特許調査すると沢山出てきます。掃除ロボット以外でも、床のワックスがけをするロボットで同様の「一筆書き」経路計画が必要になるそうです。

誤差が無い、環境が変化しない理想的な世界で経路計画だけを考えても、探索空間の広さ、グリッドの細かさ等々考えると、恐ろしい計算量になりそうです。この計算量を如何に減らすか考えるのが楽しそうです。

投稿日時 - 2007-03-06 00:44:51

> もう話は終わったかな？

まだ考え中です．(^^;

最近なかなかまとまって考える時間が取れず，少し考えては中断したり，
行き詰まったりの繰り返しでなかなか先へ進めません．(ToT)

質問者さんには，長い間待たせてしまって大変申し訳ないです．m(_ _)m
(それとも，とっくに待ちくたびれて帰っちゃったかな？)


> そこの研究室の発表論文を漁れば、学術的にちゃんとした参考になりそうな
> 論文が見つかるんじゃないでしょうか。（特に2002年前後にありそう）

まだ一部しか探してませんが，見つけにくそうなのでとりあえず "掃引計画"
で検索してみたところ，別のサイトばかりが数件ヒットしました．
ロボット工学で普通に使われている用語なんでしょうか？
http://www.google.co.jp/search?sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja&q=%22%E6%8E%83%E5%BC%95%E8%A8%88%E7%94%BB%22


> 実際人間が生活している空間を自律移動ロボットが動き回るとなると
> 問題がえらく複雑化します。(以下略)

実際に移動するロボットには，経路探索以外にもさまざまな技術課題が山積
していることは承知していますが，私の興味はもっぱらグラフアルゴリズム
なので，経路探索に限定して考えています．それでも，事前に探索空間の
情報が与えられているか否かでアルゴリズムは全然変わってきますよね．


> いいアイデアなら一般公開する前に特許出願ですよね～。

個人で出願するとなるとなると，かなり費用もかかりますよね～．

＃ アナログシンセサイザーがまだ珍しかった30年ほど前に考えていた
＃ 電子楽器のアイディアのいくつかを特許にしていたら，さぞかし
＃ もうかっていただろうな～～．(当時高校生)

投稿日時 - 2007-03-06 00:03:09

もう話は終わったかな？

ロボットで領域を隅々まで塗りつぶすように走行する計画（掃引計画）の研究、東大工学部の太田先生のところで研究されてた記憶があります。＜一時期交流があったので覚えています
http://www.arai.pe.u-tokyo.ac.jp/~ota/index-j.html

なので、そこの研究室の発表論文を漁れば、学術的にちゃんとした参考になりそうな論文が見つかるんじゃないでしょうか。（特に2002年前後にありそう）

しかし。実際人間が生活している空間を自律移動ロボットが動き回るとなると問題がえらく複雑化します。まず、部屋の形状や家具のレイアウトをどのように教示するか。ドアが開いていたら？　教示されていないものが置かれていたら？　人が前を横切ったら？　床にケーブル類や雑誌があったら？　考えるだけでもゾッとします。

もっと現実として厳しいのは、ロボットが自分の位置を正確に計測し続けることが大変難しいということ。そのためのデバイスもいろいろ考え出されていますが、非常に高価です。なので、ヒューリスティクス的なやり方をしているRoombaは非常にシンプルな考え方で安く仕上げていて評価に値すると思います。

ANo.12では
> この欠点を補うため，#6 を思いつく以前に考えていたアイディアを併用する
> ことも検討しています．それは，探索領域を「壁のない矩形領域」に分割する
> 方法で，これを１つのマクロな節点と考えたグラフを探索する方法です．

と書かれていますが、いいアイデアなら一般公開する前に特許出願ですよね～。

投稿日時 - 2007-03-05 22:02:51

> noocyteさんのグラフ表現を無断でいただいて、
> なにかヒュリスティックを見つける方向で、
> 私も考えてみたいと思っています。

どうぞどうぞ．(^^)


相変わらず #9 の「これからどうする？」で書いたアルゴリズムを
考えていますが，当初予想していたよりも厄介です．その上，

> 計算量は最悪，節点数の２乗程度 … かなぁ？

なんて書きましたが，やっぱりそんなもんじゃすみそうにありません．(甘かった．orz)
そもそもこの問題は NP 完全な Hamilton 路問題とほぼ同じなので，
どんな場合にも効率よく解けるアルゴリズムなんて存在しないんでしょうね．
やはり特定の条件下でのみ効率よく解ける，ヒューリスティックな
アルゴリズムを見つけるしかなさそうです．

今考えているアルゴリズムは，既に書いたとおり非可分成分への分割を
元にしているので，ほぼ同じ大きさの複数の非可分成分に分割できるとき
最も効率が良くなる思います．

逆に最悪なのは，(奇妙に思われるかもしれませんが) 壁が全くない場合です．
この場合は制約が全くないため可能な経路の数が最大で，グラフ全体が
１個の非可分成分なので，最も探索に (膨大な) 時間がかかるはずです．

この欠点を補うため，#6 を思いつく以前に考えていたアイディアを併用する
ことも検討しています．それは，探索領域を「壁のない矩形領域」に分割する
方法で，これを１つのマクロな節点と考えたグラフを探索する方法です．

これだと，壁が少ないスカスカの場合にはうまくいきそうな気もしますが，
矩形領域のサイズや，隣接する矩形領域同士の道幅などに関する場合分けが
ひどく面倒になりそうです．なので現在考えている方法と併用するのは当面
見送ることにしました．

興味のある方，試してみませんか？
(ただしうまくいくという保証は全くできません．(笑))

投稿日時 - 2007-02-07 18:54:12

おもしろいはなしなので、「回答」というより「まぜて～」という感じなんですが.....

松下、東芝、日立といった家電メーカから2002年ごろにそれぞれ出ていますね。
http://itpro.nikkeibp.co.jp/article/COLUMN/20061012/250605/?ST=develop&P=4

iRobot社のルンバというお掃除ロボは、なかなかいい動きをしてます。
（ただし米国の広いお部屋向け）

NP完全問題らしいので、noocyteさんのグラフ表現を無断でいただいて、なにかヒュリスティックを見つける方向で、
私も考えてみたいと思っています。

参考URL：http://www.irobot-jp.com/

投稿日時 - 2007-02-06 14:37:06