(57)【要約】【目的】ビットマップ上の障害物がある場合の経路探索において、中継点を組合せによる点のばらまきにより与え、中継点の接続の順序を順列によりつなぎかえて、最短経路を発見する。【構成】公平な中継点のばらまきと、順列を用いたつなぎ変えにより障害物を横切らない経路のみについて距離計算を行い、出力をうる。常に最短となる経路のデータのみが出力として保存される、経路探索問題の解法。【選択図】　　　　　図１
2004145837.tif 000002
【特許請求の範囲】
【請求項１】
ビットマップ上に障害物が配置され、出発点と到着点が与えられ、障害物をさけて出発点から到着点に到る経路を探索するにあたって、中継点をロジスティック写像（Ｃ＝４．０）のカオスが生成する擬似乱数またはＰＮ信号の組合せを使って与え、中継点を結ぶ経路をロジスティック写像（Ｃ＝４．０）のカオスが生成する擬似乱数またはＰＮ信号の順列を使って変え、障害物にかからない経路の探索をすることを特徴とする経路探索問題の解法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
人が見れば何でもなく答えがみつけられる。しかし、その問題をデジタルコンピュータにやらせようとすると、複雑な組合せ問題の迷路にはまってしまう。デジタルコンピュータがそういう問題に答えられるようになったときに、私達の社会生活や経済活動にとってデジタルコンピュータはさらに有用な道具となる。
【０００２】
簡単なはずの問題が複雑になってしまい、産業技術としては使いものにならないという例は多い。たとえば、連立方程式を解けばいいという線形計画法に属する問題は多い。しかし、実際にデジタルコンピュータで数値計算をしようとすると、さまざまな条件が加えられ、どうにも身動きがとれなくなってしまうという例にしばしば出会う。
【０００３】
デジタルコンピュータの逐次処理に、論理演算以外の数値演算処理を期待してはいけないともいわれる。デジタルコンピュータの逐次処理で数値計算による問題解決が困難な理由として、周期に入らない、良質の擬似乱数またはＰＮ信号がないことが指摘される。一方、ロジスティック写像のカオスが生成する擬似乱数またはＰＮ信号を浮動小数点６４ビット倍精度、有効数字５２ビットで数値計算したとき、ある程度の周期に入らない擬似乱数が取り出され、複雑な組合せ問題の問題解決能力をもつことが知られるようになった。そして、この延長線上で、周期を気にしないで擬似乱数やＰＮ信号を使える時代が近づいている。
【０００４】
【従来の技術】
ロジスティック写像Ｘｔ＋１＝４Ｘｔ（１−Ｘｔ），Ｘｔ＝Ｘｔ＋１がリャプノフ指数λ＝Ｉｎ２＝０．６９３…をもつカオスを生成することは、すでによく知られている。同相変換量子化観察し、Ｙｔ，ｎ＝［２／π＊ａｒｃｓｉｎ（√Ｘｔ）＊２ｎ］、量子分解能ｎ＝１のとき、擬似乱数Ｙｔ，１が良質であり、０と１の連なりの分布が確率分布を示す。デジタルコンピュータのＯＳ上で、浮動小数点６４ビット倍精度、有効数字５２ビットで写像の計算を実行し、有効数字５２ビットを整数として逐次出力したＰＮ信号も、０と１の連なりの分布が確率分布を示す。両者とも、複雑な組合せ問題の問題解決に利用することができる。
【０００５】
集積回路での擬似乱数Ｙｔ，１またはＰＮ信号の取得は、Ｘｔ（１−Ｘｔ）の固定小数点乗算器により実現できる。ＯＳ上の数値計算が１μｓ／写像であるのに対し、ＦＰＧＡ（ｆｉｅｌｄ　ｐｒｏｇｒａｍｍａｂｌｅ　ｇａｔｅ　ａｒｒａｙ）固定小数点乗算器は２０〜５０ｎｓ／写像と高速である。
【０００６】
ロジスティック写像は初期値からタイムシリーズを生成する。有効数字５２ビットのとき、タイムシリーズのどこかで周期に入ることはさけられない。そこには初期値敏感性があるが、周期に入る目安はｔ＝２２６＝１０８（ｔは離散時間）である。問題解決能力としては未だ十分とはいえないが、擬似乱数Ｙｔ，１もＰＮ信号も初期値に固有のタイムシリーズである。また、初期値からの繰り返し生成の再現性が保証されている。
【０００７】
【発明が解決しようとする課題】
複雑な組合せ問題を複雑にしないで説明するには、具体例を用いることである。具体的に限定されることにより一般性を失うが、抽象化して考えることによりおぎなうことができる。図１は経路探索を行うビットマップ（グラフ用紙、地図）である。ビットマップサイズは０〜６３、すなわち、６ビット・２６＝６４の場合である。Ｓ（出発点、ｓｔａｒｔ）とＧ（ゴール，ｇｏａｌ）は６ビットコード２ヶ（ｘ軸、ｙ軸）で与えられる。Ａ，Ｂ，Ｃはビットマップ上に与えられた障害物である。ＳからＧに到るとき、この領域を横切ることは禁止される。
【０００８】
図１において、ＳからＧへ直線で結ぶと、障害物Ｂを横切ることになる。こういう経路のとり方は禁止される。この図１の例では、中継点を経由しないでＳからＧに到る経路はない。障害物をさけて回り道をしなければならない。回り道を発見するためには、たとえば、図１の例では，中継点０，１をおき、まず順番にＳ−０−１−Ｇと結んでみる。やはり障害物Ｂを横切ってしまう。そこで順列を用いてＳ−１−０−Ｇとつなぎかえる。このときには、障害物を横切らない。１本の経路が発見されたことになる。
【０００９】
図１の場合、中継点を１点与えても、Ｓ−Ｇを結ぶことができる。すなわち、障害物Ａ，Ｂの中間に中継点をおく、あるいはＢ，Ｃの中間に中継点をおくとよい。人が図形を見たときには、人は容易に図形の特徴を認識できるから、このような経路探索は容易である。デジタルコンピュータがこのような解を見逃さずにもとめることができるようにならねばならない。
【００１０】
中継点は、何個でも、公平にビットマップ上にばらまかれねばならない。そのためには、ロジスティック写像が生成する擬似乱数Ｙｔ，１、タイムシリーズＹｔ，ｎ（１≦ｎ≦２６）、あるいはＰＮ信号から組合せ６ビットコードで取り出す。ｘ座標の１点（６ビットコード）とｙ座標の１点（６ビットコード）のペアが組み合わされて中継点１点を指定する。公平にビットマップを埋めつくすように点がばらまかれる機能がそなえられていなければならない。
【００１１】
障害物Ａ，Ｂ，Ｃ内の点も組合せでは生成されるが、その中の点は中継点とはみなさない。捨てられる。中継点なしで接続可能かどうか最初にチェックされる。直接接続する経路があれば、それは最短経路である。それがなければ、中継点を１点与えて経路をもとめる。中継点を２つ与える。中継点を３つ与える。・・・このような操作を繰り返し行い、最短経路を発見する。
【００１２】
【課題を解決するための手段】
２次元平面上の経路探索問題は、連立方程式と条件文からなる幾何学の問題である。原理的には、連立方程式をきちんと立てて、解をもとめれば、時間さえかければ解けることはわかっている。障害物の数がふえたり、形状がかわったりしたとき、連立方程式の組合せが膨大な数となり、手に負えなくなってしまう。
【００１３】
人が図形を見て判断するようには、コンピュータは図形、あるいは図形と図形の間の関係を知ることができない。そのかわりに、失敗することをおそれずに、公平に点をばらまき、点と点のつなぎかえを繰り返えし変えていくと、そのうちに障害物を横切らずに接続できる経路が必ず発見される。コンピュータ自身は考えることをしないが、プログラム化されたルーチンワークを丹念に繰り返すことはできる。コンピュータのこの性質と乱数の公平さとを組み合わせて問題の解決を計る。
【００１４】
【作用・実施例】
図２に、ビットマップ６４×６４▲１▼上の、障害物がある場合の、経路探索のフローチャートを示す。ビットマップ６４×６４▲１▼は図１と同じである。まず、障害物の数および形状は任意に与えてよい。任意の形状の障害物であっても、矩形に分解し角の２点の座標値として入力するとよい。
【００１５】
出発点Ｓと到着点Ｇを与える▲３▼．ＳおよびＧの座標値は６ビットコードの組合せを手動で与えてもよい。あるいはＳおよびＧのいろいろな組合せについて実験する必要があるときには、障害物をさけた、制限をもうけた組合せにより自動で与えることもできる。▲１▼、▲２▼、▲３▼で課題の設定を終了する。
【００１６】
問題を解いていくフローチャートは▲４▼〜▲９▼のループである。まず、中継点０，１，２，・・・を、障害物内には与えられないように、制限した６ビットコードの組合せで与える。中継点０は、中継点を与えない場合のことで、ＳとＧを直接接続してみることを意味する。中継点の順序を変える▲５▼を必要しないので、障害物がさけられたかどうかの判断をもとめ、Ｎｏ（さけられない）なら、▲４▼にもどる。Ｙｅｓ（さけられる）なら、ＳＧ間の距離の計算▲６▼をし、その結果をメモリに残す▲７▼、再びあらたな中継点を与える▲４▼にもどる。
【００１７】
ＳＧを直接接続できたとき、それは最短距離となっている。そのときには、それ以上の仕事をする必要がないから、コンピュータに終了命令を与えるようにしておく。そのことは、図２を複雑にしないために、書かれていない。
【００１８】
中継点１、すなわち１点を与えるときも、中継点の順序を変える▲５▼をパスして障害物がさけられるかの判断へ進む。障害物がさけられない（Ｎｏ）のときは、▲４▼にもどる。障害物がさけられる（Ｙｅｓ）のときは、距離の計算▲６▼をし、その結果をメモリに残す▲７▼、再びあらたな中継点を与える▲４▼にもどる。
【００１９】
中継点を２ヶ与えた場合は、図１の例である。Ｓ−０−１−Ｇと順番に接続し、（０１）の順列により順番を入れ替え、Ｓ−１−０−Ｇの２つの場合について、障害物がさけられるかの判断を行う。前者は障害物がさけられないので、そのデータは残さない。一方、後者は障害物がさけられているから、距離計算▲６▼を行い、出力▲７▼としてデータがのこされる。出力としてメモリにのこされるデータは、経路Ｓ−１−０−Ｇ（座標のデータも含む）と距離の値である。
【００２０】
このような処理を高速に繰り返すことにより、課題は解かれていく。すべての組合せを調べつくしたときには、当然のことながら、課題に対する最短距離がもとめられている。この手法の優れた点は、必ずしも最短距離がもとめられなくてても、確率的に期待できる、ほどほどの良い答えが早く出力▲７▼に現れる点にある。
【００２１】
出力▲７▼を、図１のように図にして示すと、どれぐらいの解がえられていて、仕事をしてしまうに十分であるかどうか、最後は人間が判断できるようにしておくのは、合理的な手法である。ただし、図形の出力には時間がかかる。
【００２２】
高速に組合せと順列を生成、あるいは取り出すには、ロジスティック写像の５２ビット固定小数点乗算器を活用するのが実際的である。そこで生成される擬似乱数Ｙｔ，１、タイムシリーズＹｔ，ｎ（１≦ｎ≦２６）またはＰＮ信号は１０８回の写像を行なっても周期に入らない。それでも、ビットマップサイズを大きくすると、十分な数の組合せと順列を取り出せないこともある。これらの擬似乱数やＰＮ信号は、５２ビットコードで与える初期値に固有である。初期値を変えて、取り出す組合せや順列を増やすとよい。
【００２３】
【発明の効果】
障害物がある場合のロボットの経路探索を、組合せと順列を用いて解く合理的な手法を示した。５２ビット固定小数点乗算器が生成するカオスの擬似乱数やＰＮ信号の複雑な組合せ問題解法能力は、１６都市のＴＳＰ（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ）程度であるといえよう。それぐらいの問題解決能力で、６４×６４ビットマップ上の障害物をさける経路探索問題で、ほどほどのいい解が、コンピュータの待ち時間約１秒以内にみつけられる。
【００２４】
取り扱うことのできる地図のサイズを大きくし、地図の分解能をより細かくしたいというニーズに応えていくためには、５２ビット固定小数点乗算器のビット幅を６４ビットや１２８ビットに拡張し、１回あたりの写像時間を短くすることである。そのためには、集積回路の最小寸法（０．２〜０．４μｍ）を有効に活用した専用ＬＳＩのプロセッサーが必要とされる。
【図面の簡単な説明】
【図１】ビットマップ６４×６４上の経路探索の例である。
【図２】ビットマップ上の経路探索のフローチャートである。
【符号の説明】
Ａ，Ｂ，Ｃ：障害物：
Ｓ：出発点
Ｇ：到着点
０、１：中継点
【図１】
2004145837.tif 000003
【図２】
2004145837.tif 000004