こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

経路探索について

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

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

投稿日時 - 2006-12-30 00:56:15

QNo.2633652

困ってます

このQ&Aは役に立ちましたか?

18人が「このQ&Aが役に立った」と投票しています

回答(15)

ANo.15

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

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

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

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

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

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

ANo.14

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

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

最近なかなかまとまって考える時間が取れず,少し考えては中断したり,
行き詰まったりの繰り返しでなかなか先へ進めません.(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

ANo.13

もう話は終わったかな?

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

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

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

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

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

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

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

ANo.12

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

どうぞどうぞ.(^^)


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

> 計算量は最悪,節点数の2乗程度 … かなぁ?

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

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

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

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

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

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

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

ANo.11

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

松下、東芝、日立といった家電メーカから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

ANo.10

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

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

・無向グラフのすべての辺を,同じループに属する辺が同じグループに
 なるようにグループ分けする.
 → どの辺も必ず1つのグループだけに属する.
・1つのグループに含まれるすべての辺と,その各辺の両端の節点からなる
 部分グラフが1つの非可分成分である.
・1つの節点が複数の非可分成分に属する場合がある.そのような節点を
 関節点 (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 のサンプルプログラムが計算している節点ごとの「グループの数」というのは,
その節点が属している非可分成分の数ということになります.
(その数が2以上ならばその節点は関節点です.)

非可分成分を求めるには,#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

投稿日時 - 2007-01-21 02:32:43

ANo.9

途中結果報告

#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┃1┃1┃1┃1┃
┃ ・ ・ ・ ・ ┃
┃2 3 3 3 2┃
┃ ・ ・ ・ ・ ┃
┃1┃1┃1┃1┃1┃
┃ ┣━╋━╋━╋━┫
┃1┃1┃1┃1┃1┃
┃ ・ ・ ・ ・ ┃
┃2 3 3 3 2┃
┃ ・ ・ ・ ・ ┃
┃1┃1┃1┃1┃1┃
┗━┻━┻━┻━┻━┛

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

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


●どこまでできたか?

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

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

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


●これからどうする?

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

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

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

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

計算量は最悪,節点数の2乗程度 … かなぁ?

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

投稿日時 - 2007-01-08 20:21:35

ANo.8

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

それでいいと思います.

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

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

投稿日時 - 2007-01-07 01:34:17

ANo.7

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

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

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

  A
  │
B─V─C
  │
  D

下図のようにC,Dを一つにまとめて1本と数えると,
Vに接続する (互いに合流しない) 辺の数は3本になる.
したがってVは最低2回通らなければならない.

  A
  │
B─V─(C+D)

投稿日時 - 2007-01-06 13:47:52

ANo.6

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

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

下図のような「道幅1」の十字路があり,A~DがX点以外で合流していない場合,
例えばAから入ってDから出て行くとすると経路は
A→X→B→X→C→X→D
となり,Xは3回通らざるをえません.
(図がくずれて見にくいので,テキストファイルに
コピー&ペーストして固定幅フォントでご覧ください.)

   A
  │↓│
 ─┘ └─
B⇔ X ⇔C
 ─┐ ┌─
  │↓│
   D

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

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

投稿日時 - 2007-01-06 12:01:06

お礼

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

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

投稿日時 - 2007-01-07 00:18:38

ANo.5

ちょっと考えてみました.この問題は,グラフ理論でよく知られている
「ハミルトン路問題」を,若干弱めたものになっていると思います.

・ロボットが取り得る位置を,無向グラフの節点とする.
・ロボットが位置Aから,その隣の位置Bに移動可能 (壁がない) ならば,
 節点Aと節点Bを辺で結ぶ.

「一筆書き」は「すべての辺を1回ずつ通る」という問題ですが,
「ハミルトン路問題」は「すべての節点を1回ずつ通る」という問題です.
だから今回の問題で「最大2回まで」という条件ではなく,「必ず1回」
であればハミルトン路問題になります.

ハミルトン路問題は,効率的なアルゴリズムが存在しない (NP完全) であることが
知られています.したがって制約のない一般のハミルトン路問題で,Nがある程度
大きい場合には実用的な時間内でプログラムが終了しなくなります.

今回の問題の場合は,1つの節点に接続する辺が最大4本しかないことを利用すれば,
効率的なプログラムが書けるかもしれません.あと,最適化をどこまで妥協するかも
ポイントでしょうね.

↓の26~27ページを参照
アルゴリズム設計 (9) グラフアルゴリズム (続き)
http://www.logos.t.u-tokyo.ac.jp/www/home/chik/algorithm-design/09%20Graph%20Algorithms.pdf

ハミルトン閉路問題をなぜ始めたか (ほか)
http://www.geocities.com/babalabo/HamiltonJ/DraftIndexJ.html

「+ハミルトン +グラフ +アルゴリズム」で Google 検索
http://www.google.co.jp/search?sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja&q=%2B%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3+%2B%E3%82%B0%E3%83%A9%E3%83%95+%2B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

投稿日時 - 2006-12-31 17:32:39

ANo.4

> できればアドバイスお願いできないでしょうか?

面白そうなので考えてみるつもりです.(笑)
回答には何日か時間をいただくかもしれませんが….

N×Nというサイズは当然,事前に与えられていると思いますが,壁の位置はどうでしょうか?
事前に (「掃除」=移動を始める前に) 知らされているんでしょうか?
それとも移動しながら自分で調べないといけないんでしょうか?
市販のお掃除ロボットのようなものであれば,知らされていないわけですが.

どちらの場合かで,アルゴリズムは全然異なります.
事前に壁の位置がわかっていれば,移動を始める前にコンピュータ内で
シミュレーションして最適経路を求め,それに従って移動することができます.
そうでなければ,移動しながら壁の位置を見つけなければならず,
最適にはなりません (2回通らなければならないマスが増えてしまうかもしれません).

それから,移動終了後の位置に関してリクエストはあるんでしょうか?
例えば,スタート位置に戻れ,とか.

投稿日時 - 2006-12-31 15:39:25

補足

ありがとうございます。

壁の位置は事前に与えられています。移動終了後の位置に指定はありません。ただすべての空間をとおり、その通った順を表示したいのです。ちなみにC言語でやっています。

投稿日時 - 2006-12-31 16:28:14

ANo.3

> お掃除をしてくれるロボットといったとことでしょうか。
> そのためにすべての空間をとおる必要があるのです。

> すべての空間を一回しかとおれない場合、または最大二回まで
> 通れる場合ですべてのマスを通れるかどうか調べたいのです。

ふーむ,「任意図形の塗りつぶし」と「一筆書き」を一緒にしたような
アルゴリズムになりそうですね.「一筆書きによる塗りつぶし」かな?

投稿日時 - 2006-12-31 01:00:40

補足

そんなような感じです。一筆書きでできない条件もよくわからないんです。できればアドバイスお願いできないでしょうか?

投稿日時 - 2006-12-31 14:45:16

ANo.2

No.1の方が仰るところの、マイクロマウス作ってます。
マイクロマウスで使われる迷路探索アルゴリズムの基本は、

http://www.informatics.tuad.ac.jp/tenji/tenji03/shiragami-lab/199970120/3.doc

の解説が秀逸。

マイクロマウスでないのでしたら、

> 広い空間があるのです。

空間はどのように定義しますか?
また、空間の広さの最大はどれくらい?
スタート地点とゴール地点(?)の与え方は?

> その空間をすべて通るかどうかを調べて表示したいのです。

全ての経路を網羅したかどうか確認したいということですか?
スタート地点からゴール地点までの最短経路が求まってしまうと、他の経路は通るだけ無駄ですよね。例えば袋小路とかは、行く意味が無い。

最短経路計画の定番は、数学的にはダイクストラ法とか、A*アルゴリズムとか。
http://research.nii.ac.jp/~uno/MP2/MP2_8shortestpath.ppt
これらは数学的に経路が最短であることを証明できます。

投稿日時 - 2006-12-30 04:57:27

補足

自分のコトバ足らずだったようですいません…マイクロマウスとはまた違うんです。。。迷路という言葉を使った自分が悪いですね。あえて言うならば、お掃除をしてくれるロボットといったとことでしょうか。そのためにすべての空間をとおる必要があるのです。

すべての空間および壁は、二次元配列でN×Nますのフロアとして定義しています。その中に壁を設定します。つまりスタートとゴールがあるというよりは、すべての空間を一回しかとおれない場合、または最大二回まで通れる場合ですべてのマスを通れるかどうか調べたいのです。ただスタートは一番左上のマスからです。

投稿日時 - 2006-12-30 23:56:45

ANo.1

マイクロマウスの話でしょうか?


> 迷路の探索のようなものなのですが、

道は一方通行 (有向グラフ) でしょうか,双方向 (無向グラフ) でしょうか?
普通の迷路探索であれば後者だと思いますが.


> その空間をすべて通るかどうかを調べて表示したいのです。

意味がよくわからないのですが,これは出発点とゴールが指定されていて,
それを結ぶ (1つの) 経路を見つけたいということでしょうか?


> 普通の迷路だったら左手法とかでいけるのだと思うのですが、
> 同じようにやってもうまくいかなくて。。。

合流点またはループがあるということですね?
だとしたら左手法 (右手法) は無限ループします.


ご質問の問題は,典型的な (無向または有向) グラフの深さ優先探索
(縦型探索ともいう) で解決できますが,マイクロマウスであれば色々な
探索法があるようですので,とりあえず↓

迷路を脱出する経路探索プログラムをC言語で作成するには?
http://oshiete1.goo.ne.jp/kotaeru.php3?qid=1553632

「+"左手法" +"迷路"」で Google 検索 (関連する探索法もあります.)
http://www.google.co.jp/search?q=%2B%22%E5%B7%A6%E6%89%8B%E6%B3%95%22+%2B%22%E8%BF%B7%E8%B7%AF%22&hl=ja&lr=&rls=GGGL,GGGL:2006-34,GGGL:ja&start=10&sa=N

投稿日時 - 2006-12-30 03:08:22

あなたにオススメの質問