経路探索について

質問

基本的には迷路の探索のようなものなのですが、広い空間があるのです。その空間をすべて通るかどうかを調べて表示したいのです。

普通の迷路だったら左手法とかでいけるのだと思うのですが、同じようにやってもうまくいかなくて。。。通ったとこを壁にしていって、行けなくなればバックトラックするようにしようとしてもうまくいかなかったんです。何かヒントいただければと思いました。よろしくお願いします。

回答No.15

Interest

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

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

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

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

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

回答No.14

noocyte

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

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

最近なかなかまとまって考える時間が取れず，少し考えては中断したり，
行き詰まったりの繰り返しでなかなか先へ進めません．(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年ほど前に考えていた
＃ 電子楽器のアイディアのいくつかを特許にしていたら，さぞかし
＃ もうかっていただろうな～～．(当時高校生)

回答No.13

Interest

もう話は終わったかな？

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

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

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

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

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

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

回答No.12

noocyte

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

どうぞどうぞ．(^^)

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

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

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

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

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

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

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

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

回答No.11

ykkw_2001

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

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

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

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

参考URL：

http://www.irobot-jp.com/

回答No.10

noocyte

最適経路探索プログラムはまだ作成中ですが
(週末ぐらいしか落ち着いて考えられないので orz)，
久しぶりにグラフ理論の教科書を見直していて
気付いたことがあるので報告しておきます．

#7，#9 で書いた「辺のグループ分け」というのは結局，グラフ理論で
言うところの「非可分成分」への分割を行っていることになります．
無向グラフの非可分成分 (nonseparable component) とは，
大雑把にいうと次のようなものです．

・無向グラフのすべての辺を，同じループに属する辺が同じグループに
　なるようにグループ分けする．
　→ どの辺も必ず１つのグループだけに属する．
・１つのグループに含まれるすべての辺と，その各辺の両端の節点からなる
　部分グラフが１つの非可分成分である．
・１つの節点が複数の非可分成分に属する場合がある．そのような節点を
　関節点 (articulation point) または切断点 (cut-vertex) という．

「非可分成分」で Google 検索 (日本語だとわずかしかヒットしない．)
http://www.google.co.jp/search?hl=ja&rls=GGGL%2CGGGL%3A2006-34%2CGGGL%3Aja&q=%22%E9%9D%9E%E5%8F%AF%E5%88%86%E6%88%90%E5%88%86%22&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=

#9 のサンプルプログラムが計算している節点ごとの「グループの数」というのは，
その節点が属している非可分成分の数ということになります．
(その数が２以上ならばその節点は関節点です．)

非可分成分を求めるには，#9 のサンプルプログラムよりも効率的な
アルゴリズムが知られています．
(ただし，このアルゴリズムの効率を落とさずに上記の「グループの数」
を計算できるかどうかはまだ考えていません．まあそれは，経路探索
プログラムの後ということで…．)

↓非可分成分を求めるアルゴリズムを検索 (日本語のサイトでは見つからなかった．)
「+graph +nonseparable +algorithm +search」
http://www.google.co.jp/search?hl=ja&rls=GGGL%2CGGGL%3A2006-34%2CGGGL%3Aja&q=%2Bgraph+%2Bnonseparable+%2Balgorithm+%2Bsearch&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=

↑で見つけたページの一つ↓ (PostScript なので Acrobat がないと見れないかも．)
http://www.cs.technion.ac.il/~cs234141/Material/EvenBooks/Graph-Algorithms-2003/chapter3.ps
10ページの Table 3 にプログラムリストがあります．
縦型探索ですが再帰呼び出しではなく，スタックを明示的に使ったアルゴリズムです．
(元の論文が1970年頃なので．)

日本語で読みたい方は，グラフアルゴリズムの本を買うしかなさそうです．
私のネタ本は↓です (古いですが)．

伊理ほか，「演習グラフ理論 ―基礎と応用―」，コロナ社，1983．
http://www.coronasha.co.jp/np/detail.do?goods_id=30

回答No.9

noocyte

途中結果報告

#6，#7 で書いた方法で，各節点を最低何回通らなければならないかを計算する
サンプルプログラムを作成しました．下記 URL からダウンロードできます．

http://www.uploda.net/cgi/uploader3/index.php?file_id=0000000153.html

ソース，実行ファイル (Win32)，地図定義ファイル，解析結果ファイル付です．

●実行例

例えば次のような地図 (上記に含まれる地図定義ファイル Map1.txt 参照) が
あるとします．

節点の座標 (XXYY) 始点：(0, 0)
┏━━┳━━┳━━┳━━┳━━┓
┃0000┃0100┃0200┃0300┃0400┃
┃　　・　　・　　・　　・　　┃
┃0001　0101　0201　0301　0401┃
┃　　・　　・　　・　　・　　┃
┃0002┃0102┃0202┃0302┃0402┃
┃　　┣━━╋━━╋━━╋━━┫
┃0003┃0103┃0203┃0303┃0403┃
┃　　・　　・　　・　　・　　┃
┃0004　0104　0204　0304　0404┃
┃　　・　　・　　・　　・　　┃
┃0005┃0105┃0205┃0305┃0405┃
┗━━┻━━┻━━┻━━┻━━┛

これを解析すると，次のように各節点の必要通過回数が表示されます．

各節点の必要通過回数 (始点：(0, 0))
┏━┳━┳━┳━┳━┓
┃１┃１┃１┃１┃１┃
┃　・　・　・　・　┃
┃２　３　３　３　２┃
┃　・　・　・　・　┃
┃１┃１┃１┃１┃１┃
┃　┣━╋━╋━╋━┫
┃１┃１┃１┃１┃１┃
┃　・　・　・　・　┃
┃２　３　３　３　２┃
┃　・　・　・　・　┃
┃１┃１┃１┃１┃１┃
┗━┻━┻━┻━┻━┛

注意：この数字は，最少この回数で通過できるという十分条件ではなく，
少なくともこれ以上の回数必要という意味です．
実際の最適経路では，これより回数が増える可能性がありますが，
減る可能性はないということです．(減らすとすべての節点には到達できない．)

例えば上の迷路では，「行き止まりの魚の骨」が２つあり，それぞれの中央部には
「３」が表示されています．しかしこの迷路全体を巡るには，例えば先に上の
「魚の骨」に入った後引き返し，下の「魚の骨」に入る必要があります．
すると上側の「３」と書かれた節点は，実際には４回通らなければならなくなります．

●どこまでできたか？

ロボットの探索領域を無向グラフで表現し，始点からの到達可能性を分析することにより，

(1) 各節点について，それから出る辺同士がその節点以外で合流するか否かを調べ，
　　合流するもの同士をグループにまとめ，グループ分けする．

(2) 各節点の辺のグループがいくつあるかを数えることにより，その節点を最低何回
　　通らなければならないかを判定する．

●これからどうする？

次の方法で最適経路が求められるのではないかと思うので試してみる．

(1) 始点について上記のグループ分けを行う．

(2) 始点を開放除去 (始点に接続する辺および始点自身を削除) した無向グラフを
　　考えると，上記の各グループの接続先は，互いに連結していない部分グラフと
　　なる．このように分割された各部分グラフについて (再帰的に) 最適経路を求
　　める．

(3) (2) で求めた部分グラフごとの最適経路を合成して全体の最適経路を求める．

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

参考URL：

http://www.uploda.net/cgi/uploader3/index.php?file_id=0000000153.html

回答No.8

noocyte

> 二次元配列を使っているのですが、
> 深さ優先探索でやろうと思ったのですがどう思いますか？

それでいいと思います．

実は，おとといまでは別の方法を考えていましたが，昨日，#6，#7 で
書いたことに気付いたため，これらを基本に問題を考え直しているところです．
深さ優先探索を基本にしたアルゴリズムでできそうな気がしています．

ただし，木構造の深さ優先探索のように単純ではなく，
深さ優先探索をしながらグラフの構造に関する情報を色々と抽出する必要があります．
(#6，#7 で書いた，節点Ｖのどの辺とどの辺が合流しているか，といったことなど．)

回答No.7

noocyte

#6 で書いたことを一般化し，ある節点Ｖを最低何回通らなければならないかを
考えてみると，次のように言えると思います．

節点Ｖに接続する辺を Ｅ1，…，Ｅn とする (１≦ｎ≦４)．
これらの辺のうち複数のもの (につながる経路) が頂点Ｖ以外で合流していれば，
それらの辺をまとめて１つと数える．
こうして数えた辺の数をｍとすると，Ｖは最低 max(m-1, 1) 回通らなければならない．

例えば下図の頂点Ｖから出る辺Ｃ，Ｄ (の先につながる経路) が，
Ｖ以外で合流しているとすると，

　　Ａ
　　│
Ｂ─Ｖ─Ｃ
　　│
　　Ｄ

下図のようにＣ，Ｄを一つにまとめて１本と数えると，
Ｖに接続する (互いに合流しない) 辺の数は３本になる．
したがってＶは最低２回通らなければならない．

　　Ａ
　　│
Ｂ─Ｖ─(Ｃ＋Ｄ)

回答No.6

noocyte

> 最大二回まで通れる場合ですべてのマスを通れるかどうか

これは不可能な場合がありますね．

下図のような「道幅１」の十字路があり，Ａ～ＤがＸ点以外で合流していない場合，
例えばＡから入ってＤから出て行くとすると経路は
Ａ→Ｘ→Ｂ→Ｘ→Ｃ→Ｘ→Ｄ
となり，Ｘは３回通らざるをえません．
(図がくずれて見にくいので，テキストファイルに
コピー＆ペーストして固定幅フォントでご覧ください．)

　　　Ａ
　　│↓│
　─┘　└─
Ｂ⇔　Ｘ　⇔Ｃ
　─┐　┌─
　　│↓│
　　　Ｄ

このＸのように「３回通らざるを得ない点」が連続することもありえます．
例えば下図のような「道幅１の魚の背骨」のＸの部分．

　┌─┬─┬─┬─┬─┬─┐
　│　│　│　│　│　│　│
　│　│　│　│　│　│　│
─┘　│　│　│　│　│　└─
　　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ　Ｘ
─┐　│　│　│　│　│　┌─
　│　│　│　│　│　│　│
　│　│　│　│　│　│　│
　└─┴─┴─┴─┴─┴─┘

お礼

ありがとうございます。確かに二回だけでは不可能なマップもありました。それは無視していいと思います。

自分でもやってみたのですが、二回通れるますをできるだけ少なくするというのがとても難しく感じています。二回通れるマスが多ければできるのですが…二次元配列を使っているのですが、深さ優先探索でやろうと思ったのですがどう思いますか？