(57)【要約】【課題】３次元空間内で複数の経路を探索する場合に、経路探索の順番に依存せず、複数の経路を自動的に得られるような経路探索装置及び方法を提供する。【解決手段】３次元空間内の始点と終点とを結ぶ複数の経路を探索する複数経路の探索装置であって、前記３次元空間の形状データを取り込む外部入力インターフェイスと、複数の前記経路の探索に必要な条件を設定する初期設定部と、最適経路を求めるための評価指標に基づき複数の前記経路の探索を実行する経路演算部と、前記初期設定部が設定した探索条件を保存する探索条件データベースと、前記形状データと前記経路演算部による経路探索結果とを保存する探索結果データベースと、前記経路探索結果を外部に出力するための外部出力インターフェイスとを備え、前記経路演算部は、前記３次元空間内に、前記経路を通すことができない仮想禁止区域を設ける。【選択図】図１
2011013708.tif 000002
【特許請求の範囲】
【請求項１】
３次元空間内の始点と終点とを結ぶ複数の経路を探索する複数経路の探索装置であって、
前記３次元空間の形状データを取り込む外部入力インターフェイスと、
複数の前記経路の探索に必要な条件を設定する初期設定部と、
最適経路を求めるための評価指標に基づき複数の前記経路の探索を実行する経路演算部と、
前記初期設定部が設定した探索条件を保存する探索条件データベースと、
前記形状データと前記経路演算部による経路探索結果とを保存する探索結果データベースと、
前記経路探索結果を外部に出力するための外部出力インターフェイスとを備え、
前記経路演算部は、前記３次元空間内に、前記経路を通すことができない仮想禁止区域を設けることを特徴とする複数経路の探索装置。
【請求項２】
請求項１記載の複数経路の探索装置において、
前記経路演算部は、経路探索の順番を設定し、この経路探索の順番に応じて前記仮想禁止区域の位置を変化させる複数経路の探索装置。
【請求項３】
請求項２記載の複数経路の探索装置において、
複数の前記経路の探索により得られた経路のパターンの数に応じて前記評価指標の値を補正する複数経路の探索装置。
【請求項４】
請求項２記載の複数経路の探索装置において、
複数の前記経路の探索により得られた経路のパターンの一致度に応じて前記評価指標の値を補正する複数経路の探索装置。
【請求項５】
請求項１〜４のいずれか１項記載の複数経路の探索装置において、
入力装置と接続され、
前記入力装置を介して、前記仮想禁止区域の個数と前記評価指標の値の補正方法とのうち、少なくとも１つを入力する複数経路の探索装置。
【請求項６】
請求項１〜５のいずれか１項記載の複数経路の探索装置において、
画像表示装置と接続され、
前記評価指標の値と複数の前記経路の探索により得られた経路のパターンとのうち、少なくとも１つを前記画像表示装置に表示する複数経路の探索装置。
【請求項７】
複数経路の探索装置により、３次元空間内の始点と終点とを結ぶ複数の経路を、最適経路を求めるための評価指標に基づき遺伝的アルゴリズムを用いて探索する複数経路の探索方法であって、
前記３次元空間内に、前記経路を通すことができない仮想禁止区域を配置する工程と、
前記仮想禁止区域の配置位置をパラメータで表し、探索により得られる複数の前記経路に対して同じ経路パターンを解に持つ個体数が少なくなるように前記パラメータを補正し、この補正パラメータにより新たな仮想禁止区域の配置を決定する工程と、
を有して複数の前記経路を探索することを特徴とする複数経路の探索方法。
【請求項８】
請求項７記載の複数経路の探索方法において、
前記仮想禁止区域の配置位置と複数の前記経路の探索順番とをパラメータで表し、探索により得られる複数の前記経路に対して同じ経路パターンを解に持つ個体数が少なくなるように前記パラメータを補正し、この補正パラメータにより新たな仮想禁止区域の配置を決定する工程、
を有して複数の前記経路を探索する複数経路の探索方法。
【請求項９】
請求項８記載の複数経路の探索方法において、
複数の前記経路の探索により得られた経路のパターンの数に応じて前記評価指標の値を補正する工程、
を有して複数の前記経路を探索する複数経路の探索方法。
【請求項１０】
請求項８記載の複数経路の探索方法において、
複数の前記経路の探索により得られた経路のパターンの一致度に応じて前記評価指標の値を補正する工程、
を有して複数の前記経路を探索する複数経路の探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、空間内に複数の経路を設ける際、制約条件を満たした経路を探索するための装置及び方法に関する。
【背景技術】
【０００２】
２次元平面や３次元空間内に始点と終点を与え、この２点を結ぶ経路を探索する問題は、最短経路問題として非常に良く知られた問題であり、産業界での適用事例も多数ある。例えば、２次元平面の場合、カーナビゲーションシステムへの適用が良く知られている。３次元空間内の場合、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）の配線設計、発電用プラントや一般産業プラントなどの配管や電気ケーブルの設計などへの適用例がある。
【０００３】
どちらの場合でも、制約条件や所望の経路を得るための指標（評価指標）が設定される。制約条件は、適用対象によって異なるが、多くの場合、与えられた２次元平面あるいは３次元空間内で経路を通してはいけない箇所（禁止区域）などが代表的である。評価指標としては、経路の長さが最短となるように設定したり、コストが最小となるように設定する場合が多い。経路の探索対象となる２次元平面や３次元空間の規模が大きくなり、決定しなければならない経路の数が多くなると、組合せの数が多くなり、最短経路問題の解を求めることが困難になる。
【０００４】
従来、２次元平面及び３次元空間での最短経路問題を解く手法として、バックトラック法や幅優先探索がある。バックトラック法は、与えられた始点から経路を選択し、行き詰ると後戻りして別の経路を選択するという試行錯誤的な探索手法である。従って、最初に見つかる経路が最短経路であるという保証はない。幅優先探索は、すべての経路について、平行に探索を進めるため、最初に見つかる経路が最短経路となる。どちらの手法も、始点から終点までの経路を１つずつ進めながら求めるため、計算量が多くなる。
【０００５】
そこで、ベルマンが提案した最適性の原理をもとにした探索手法が考案されている。最適性の原理とは、全体問題の最適解の部分解はその部分問題の最適解に一致するというものである。これをもとにした動的計画法は、対象となる問題を複数の部分問題に分割し、同じ部分問題を繰り返し解かないようその部分問題の解を保存しておく手法である。最短経路問題をコンピュータで解析する場合、途中のある点までの経路を保存しておけば、その点を含んだ経路探索時に、保存してある経路を用いると、その点までの計算は不要となり、計算量を節約できる。
【０００６】
最適性の原理を用いた他の手法としてダイクストラ法がある。ダイクストラ法は、主にグラフ理論で用いられる手法である。グラフとは、複数の点とそれを接続するパスで構成されたものである。ダイクストラ法は、最適な経路として最短経路を求める場合、最短経路長の定まった点から、さらに経路１つで到達可能な点のうち、経路長が最短の点を、最短経路と決定するという手法である。
【０００７】
複数の経路を求める場合も、一本目の経路の始点と終点を与え、上述した手法を用いて経路を決定する。次に、２本目の経路の始点と終点を与え、同様に経路を求める。この手順を必要な経路本数分繰り返すことで、複数の経路を求める。ただし、これらの場合、得られる経路は一種類であり、多数の異なった経路の組合せを得るためには、各経路に与える制約条件を変更しながら、上述した手順を繰り返し実施しなければならない。条件設定などはユーザの人手によって行うため、網羅的な経路の組合せを得ることが困難である。
【０００８】
そこで、制約条件の幾つかをパラメータ化し、遺伝的アルゴリズムを用いることで複数の経路を得る手法がある。
【０００９】
遺伝的アルゴリズムは、１９７５年、Ｊ．Ｈｏｌｌａｎｄによる適応システムの研究に端を発し、１９８９年、Ｄ．Ｇｏｌｄｂｅｒｇによりアルゴリズムの枠組みが体系化された手法である。具体的には、問題の解を記号列として表現した個体を用い、生物の持つ遺伝機構と自然選択を模擬することで、複数の個体による離散的な探索空間での最適化をする。また、個体間でお互いの遺伝情報を交換する交叉演算にて、新しい探索点を生成することを特徴としている。各個体の優劣を判断するため、適応度関数と呼ばれる指標を設定する。適応度関数は、通常は、最適化問題における評価指標と同様である。遺伝的アルゴリズムは、他の手法と異なり、複数の個体による探索が可能となるため、組合せ問題やスケジューリング問題への適用事例が多数ある。体系化されたアルゴリズムや簡単な事例については、非特許文献１に記載されている。また、産業界への適用事例などについては、非特許文献２に記載されている。
【００１０】
また、特許文献１では、発電プラントの配管経路を探索する手法として、配管経路方向の優先度をパラメータとし遺伝的アルゴリズムを適用することで、複数の経路パターンを得るための手法が記載されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００２−２８８２５０号公報
【非特許文献】
【００１２】
【非特許文献１】Ｄ．Ｅ．Ｇｏｌｄｂｅｒｇ，“Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ  ｉｎ  Ｓｅａｒｃｈ，Ｏｐｔｉｍｉｚａｔｉｏｎ，ａｎｄ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ”，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ（１９８９）
【非特許文献２】三宮信夫、喜多一、玉置久、岩本貴司、「遺伝アルゴリズムと最適化」、朝倉書店（１９９８）
【発明の概要】
【発明が解決しようとする課題】
【００１３】
２次元平面または３次元空間内に複数の経路を設定する場合、経路は、経路探索の順番に大きく依存して設定されるという問題がある。３次元空間内で２本の経路を決定する問題を例とし、図２と図３を用いて、経路決定の順番に関する問題を詳しく説明する。
【００１４】
まず、図２と図３に示すように、対象とする空間を格子状のメッシュに分割する。対象空間は、６×６×３の格子数からなり、ハッチングした箇所は、障害物を模擬しており、経路を通すことができない禁止区域を示している。Ｓ１とＳ２を始点とし、それぞれＧ１とＧ２を終点とする２本の経路Ｐ１、Ｐ２を求める。接続点は、経路Ｐ２が必ず通る経由点である。発電用プラントや一般産業プラントなどの配管の場合には、配管と機器とが接続する位置に相当する。
【００１５】
図２では、Ｐ１を始めに経路探索し、次にＰ２を経路探索した場合の一例を示している。この場合、Ｐ１は空間内での最適な経路（最短経路）を選択することが出来るが、Ｐ２は、すでに確保されたＰ１の経路を避ける必要があるため、最適な経路にはならない。
【００１６】
一方、図３は、Ｐ２を始めに経路探索し、次にＰ１を経路探索した場合の一例である。この場合は、図２の場合とは反対に、Ｐ２が最適な経路（最短経路）となるが、Ｐ１は、Ｐ２の経路を避ける必要があるため、最適な経路とはならない。
【００１７】
この２例に対し、設定された経路を、直線部の長さと曲部（曲がり角）の数の合計を評価指標として評価する。評価指標の値が小さいほど経路が短くなり、評価指標の値が最小となる経路が最適な経路（最短経路）である。始点Ｓ１とＳ２、及び終点Ｇ１とＧ２は、ともに該当メッシュの中心に位置するとし、直線部の長さは格子数で表現する。
【００１８】
図２の場合は、Ｐ１の経路の長さと曲部の合計数は９であり、Ｐ２は２０となる。図３の場合は、Ｐ１が１５、Ｐ２が１４である。どちらの場合も、Ｐ１とＰ２の評価指標の合計は２９である。このように、図２の場合はＰ１、図３の場合はＰ２が最適な経路であり、先に探索した方の経路が最適な経路として求められる。
【００１９】
しかし、Ｐ１とＰ２がいずれも最適な経路でなくても、上述した評価指標の合計が、Ｐ１とＰ２のうち一方が最適な経路である場合（図２、３の場合）と同じ値になる場合も存在する。図４に、この一例を示す。図４では、Ｐ１の経路の長さと曲部の合計は１３、Ｐ２は１６である。従って、この場合のＰ１とＰ２は、Ｐ１が最適となる場合（図２）のＰ１やＰ２が最適となる場合（図３）のＰ２とそれぞれ比べて、ともに評価指標の値は大きい。すなわち、図４の場合は、Ｐ１とＰ２の両方とも最適な経路ではない。ところが、Ｐ１とＰ２の評価指標の合計は２９であり、図２と図３の場合と同じ値になっている。
【００２０】
このように、個々の経路がいずれも最適でない場合であっても、評価指標の合計が最小となり、全体としては最適となる場合が存在する。このような場合の経路は、従来の手法では探索することができない。
【００２１】
従って、上述した非特許文献１、２及び特許文献１に記載の技術は、経路探索の順番に依存しないで、多数の異なった経路、特に最適な経路を得ることが困難である。
【００２２】
本発明の目的は、３次元空間内で複数の経路を探索する場合に、経路探索の順番に依存せず、複数の経路を自動的に得られるような経路探索装置及び方法を提供することである。
【課題を解決するための手段】
【００２３】
前述の課題を解決するため、本発明による複数経路の探索装置及び方法は以下の機能で構成される。
【００２４】
本発明による第１の複数経路の探索装置は、３次元空間内の始点と終点とを結ぶ複数の経路を探索する複数経路の探索装置であって、前記３次元空間の形状データを取り込む外部入力インターフェイスと、複数の前記経路の探索に必要な条件を設定する初期設定部と、最適経路を求めるための評価指標に基づき複数の前記経路の探索を実行する経路演算部と、前記初期設定部が設定した探索条件を保存する探索条件データベースと、前記形状データと前記経路演算部による経路探索結果とを保存する探索結果データベースと、前記経路探索結果を外部に出力するための外部出力インターフェイスとを備え、前記経路演算部は、前記３次元空間内に、前記経路を通すことができない仮想禁止区域を設けることを特徴とする。
【００２５】
本発明による第２の複数経路の探索装置は、本発明による第１の複数経路の探索装置において、前記経路演算部は、経路探索の順番を設定し、この経路探索の順番に応じて前記仮想禁止区域の位置を変化させる。
【００２６】
本発明による第３の複数経路の探索装置は、本発明による第２の複数経路の探索装置において、複数の前記経路の探索により得られた経路のパターンの数に応じて前記評価指標の値を補正する。
【００２７】
本発明による第４の複数経路の探索装置は、本発明による第２の複数経路の探索装置において、複数の前記経路の探索により得られた経路のパターンの一致度に応じて前記評価指標の値を補正する。
【００２８】
本発明による第５の複数経路の探索装置は、本発明による第１〜第４の複数経路の探索装置において、入力装置と接続され、前記入力装置を介して、前記仮想禁止区域の個数と前記評価指標の値の補正方法とのうち、少なくとも１つを入力する。
【００２９】
本発明による第６の複数経路の探索装置は、本発明による第１〜第５の複数経路の探索装置において、画像表示装置と接続され、前記評価指標の値と複数の前記経路の探索により得られた経路のパターンとのうち、少なくとも１つを前記画像表示装置に表示する。
【００３０】
本発明による第１の複数経路の探索方法は、複数経路の探索装置により、３次元空間内の始点と終点とを結ぶ複数の経路を、最適経路を求めるための評価指標に基づき遺伝的アルゴリズムを用いて探索する複数経路の探索方法であって、前記３次元空間内に、前記経路を通すことができない仮想禁止区域を配置する工程と、前記仮想禁止区域の配置位置をパラメータで表し、探索により得られる複数の前記経路に対して同じ経路パターンを解に持つ個体数が少なくなるように前記パラメータを補正し、この補正パラメータにより新たな仮想禁止区域の配置を決定する工程とを有して複数の前記経路を探索することを特徴とする。
【００３１】
本発明による第２の複数経路の探索方法は、本発明による第１の複数経路の探索方法において、前記仮想禁止区域の配置位置と複数の前記経路の探索順番とをパラメータで表し、探索により得られる複数の前記経路に対して同じ経路パターンを解に持つ個体数が少なくなるように前記パラメータを補正し、この補正パラメータにより新たな仮想禁止区域の配置を決定する工程を有して複数の前記経路を探索する。
【００３２】
本発明による第３の複数経路の探索方法は、本発明による第２の複数経路の探索方法において、複数の前記経路の探索により得られた経路のパターンの数に応じて前記評価指標の値を補正する工程を有して複数の前記経路を探索する。
【００３３】
本発明による第４の複数経路の探索方法は、本発明による第２の複数経路の探索方法において、複数の前記経路の探索により得られた経路のパターンの一致度に応じて前記評価指標の値を補正する工程を有して複数の前記経路を探索する。
【発明の効果】
【００３４】
本発明による経路の探索装置及び方法では、所定の始点・終点間について経路を探索する場合に、人手によって条件設定を変えることなく自動的に複数経路の探索の結果を得ることができるため、従来の試行錯誤的な作業を大幅に減らすことが可能となる。また、網羅的な探索が可能であるため、見落としや探索漏れなどを防止することが可能である。
【図面の簡単な説明】
【００３５】
【図１】本発明の１実施形態による複数経路の探索装置の構成を示すブロック図である。
【図２】従来手法による経路探索（Ｐ１が最適な経路）を説明する図である。
【図３】従来手法による経路探索（Ｐ２が最適な経路）を説明する図である。
【図４】従来手法では探索できない経路（Ｐ１、Ｐ２がともに最適な経路でない）を説明する図である。
【図５】本発明の１実施形態による経路探索装置の対象となる３次元空間内に配置された機器の形状データを示す図である。
【図６】本発明の１実施形態による経路探索装置の対象となる３次元空間内に配置される配管の形状データを示す図である。
【図７】本発明の１実施形態による経路探索装置の探索結果データベースに記憶されるデータの態様を示す図である。
【図８】本発明の１実施形態による経路探索装置の探索条件データベースに記憶されるデータの態様を示す図である。
【図９】本発明の１実施形態による経路探索装置の経路演算部で適用される仮想禁止セルを説明する図である。
【図１０】本発明の１実施形態による経路探索装置の経路演算部で適用される経路探索パラメータの遺伝子列の一例を示す図である。
【図１１】本発明の１実施形態による経路探索装置の経路演算部で適用される評価関数の補正に用いる演算係数を説明する図である。
【図１２】本発明の１実施形態による経路探索装置の経路演算部が行う処理のフローチャートである。
【図１３】本発明の１実施形態による画像表示装置に表示される初期画面である。
【図１４】本発明の１実施形態による画像表示装置に表示される探索条件設定画面である。
【図１５】本発明の１実施形態による画像表示装置に表示される探索結果情報の表示画面である。
【図１６】本発明の１実施形態による画像表示装置に表示される、探索の結果得られた経路の３次元の経路情報表示画面である。
【発明を実施するための形態】
【００３６】
以下、本発明による複数経路の探索装置及び方法の実施形態の例について、添付図面を参照しながら説明する。図１は、本発明による複数経路の探索装置の構成を示すブロック図である。本実施例では、複数経路の探索装置及び方法を、発電用プラントや一般産業プラントなどの配管に適用した例について説明する。本実施形態において、求めるべき最適な経路とは、配管の直線部の長さと曲部（曲がり角）の数の合計が最も少ない最短経路のことである。本発明による複数経路の探索装置及び方法は、このような最適経路を求めるにあたって、探索の順番に依存せずに多数の経路を自動的に求めることが可能である。
【００３７】
経路探索（配管）の対象となる３次元空間１００は、記憶装置１１０に保存されているデータであり、例えば、汎用的な３次元ＣＡＤで作成される。この３次元空間１００内には、複数の機器が配置されており、これらの機器を配管で接続する場合について説明する。機器についても、ユーザが汎用的な３次元ＣＡＤを用いて配置するものとし、これらの機器を接続する配管の始点と終点もユーザが与えるものとする。
【００３８】
記憶装置１１０に保存された３次元空間１００のデータを処理するシステムは、経路探索装置２００、入力装置９００、支援ツール９１０、及び画像表示装置９５０で構成される。
【００３９】
経路探索装置２００は、外部入力インターフェイス２１０を介して記憶装置１１０から、３次元空間１００の３次元形状を特徴づける形状データ１を取り込む。形状データ１は、３次元空間１００内の機器や配管の形状に関するデータである。また、経路探索装置２００では、外部出力インターフェイス２６０を介して、支援ツール９１０に探索結果５を送信する。
【００４０】
図５に、形状データ１のうち、機器に関するデータの様式を示す。図５に示すように、形状データ１の機器に関するデータは、対象機器のＩＤ、その対象機器を包含する最小の直方体または立方体Ｖの中心線Ｌの両端座標、及びその直方体または立方体Ｖの最小と最大の点座標を含む。
【００４１】
図６は、形状データ１のうち、配管の形状に関するデータの様式を示す。配管のＩＤ、名称、種別、口径、肉厚、保温材厚み、及び他の機器または配管とのクリアランスが記載されている。さらに、ユーザにより指定された配管（経路）の始点と終点の座標も含む。
【００４２】
外部入力インターフェイス２１０で取り込んだ形状データ１は、入力データ２として初期設定部２２０及び探索結果データベース（探索結果ＤＢ）２４０に伝送される。
【００４３】
初期設定部２２０は、ユーザからの指定値またはデフォルト値を、経路演算部２３０での経路探索に必要となる演算入力値３として設定し、経路演算部２３０へ出力する。また、設定した演算入力値３は、探索条件データベース（探索条件ＤＢ）２５０に格納される。演算入力値３については、探索条件データベース２５０のテーブルの説明にて詳しく述べる。
【００４４】
経路演算部２３０では、探索結果データベース２４０に格納されている入力データ２のうち経路の始点・終点データ６と、初期設定部２２０からの演算入力値３とをもとに、経路探索を実施し、経路演算結果４を外部出力インターフェイス２６０と探索結果データベース２４０に伝送する。経路の演算に関する詳細な処理については、詳しく後述する。
【００４５】
探索結果データベース２４０では、外部入力インターフェイス２１０からの入力データ２と経路演算部２３０からの経路演算結果４とを受け取り、それぞれを決められた形式で保存する。また、経路演算部２３０に、処理に必要となる経路の始点・終点データ６を伝送する。探索結果データベース２４０に格納するデータの形式については、詳しく後述する。
【００４６】
外部出力インターフェイス２６０では、経路演算部２３０での経路演算結果４を受け取り、探索結果５として支援ツール９１０へ伝送する。また、探索結果５を保存するために記憶装置１１０に伝送し、３次元空間１００とともに可視化できるようにする。
【００４７】
ユーザは、キーボード９０１とマウス９０２で構成される入力装置９００、及び画像表示装置９５０に接続されている支援ツール９１０を用いることにより、３次元空間１００に対して、新規形状の生成や、既に配置されている形状データの修正・削除が可能である。また、ユーザは、入力装置９００、支援ツール９１０、及び画像表示装置９５０を用い、初期設定部２２０に探索条件を設定したり、探索条件データベース２５０や探索結果データベース２４０に保存されている情報にアクセスしたりすることができる。
【００４８】
支援ツール９１０は、外部入力インターフェイス９２０、データ送受信処理部９３０、及び外部出力インターフェイス９４０で構成される。
【００４９】
入力装置９００で生成した入力信号３１は、支援ツール９１０の外部入力インターフェイス９２０を介して支援ツール９１０に取り込まれ、入力信号３２としてデータ送受信処理部９３０に伝送される。
【００５０】
データ送受信処理部９３０は、入力信号３２の情報に従って、経路探索装置２００から探索情報１０を取得したり、経路探索装置２００の初期設定部２２０の設定値を参照または設定したりする。また、データ送受信処理部９３０では、探索情報１０や探索結果５を出力信号３３として、外部出力インターフェイス９４０に送信する。
【００５１】
外部出力インターフェイス９４０に送信された出力信号３３は、出力信号３４として画像表示装置９５０に送信され、画像表示装置９５０に表示される。
【００５２】
尚、本実施形態ではデータベースが全て経路探索装置２００の内部に配置されているが、これらを経路探索装置２００の外部に配置することもできる。また、本実施形態では記憶装置１１０が経路探索装置２００の外部に配置されているが、内部に配置してもよい。
【００５３】
以下では、データベースに保存されている情報、及び経路演算部２３０の機能について説明する。
【００５４】
図７を用いて、探索結果データベース２４０に保存される情報について説明する。図７は、探索結果データベース２４０に保存されている情報の態様を説明する図である。
【００５５】
探索結果データベース２４０には、外部入力インターフェイス２１０からの入力データ２と、経路演算部２３０からの経路演算結果４とが格納される。入力データ２からは配管の形状に関する情報（配管のＩＤ、種別、口径、肉厚、保温材厚み、及び名称）が、経路演算結果４からは経路情報（経路の頂点数、各頂点の座標、及び経路の曲部の角度）がそれぞれ反映される。
【００５６】
例えば、図７に示すような始点と終点とを持った経路が１番目の経路パターンとして得られたとする。この時、パターン番号は１、頂点数は４として格納される。ＩＤ、配管種別、口径、肉厚、保温材厚み、配管名称は、入力データ２の値が格納される。その次に、経路の頂点座標（０，０，０）、（ｘ２，ｙ２，ｚ２）、（ｘ３，ｙ３，ｚ３）、及び（１００，５００，２００）が１点ごとに格納される。最後に、曲部の角度が格納される。始点と終点は、端部であり、曲部が存在しないので、曲部の角度は０となる。端部以外の点は、例えば曲部の角度が９０度の場合、９０という値が格納される。図７の場合は、０、ａ、ｂ、及び０が格納される。このような形式で、全ての配管の情報と経路情報が格納される。
【００５７】
次に、図８を用いて、探索条件データベース２５０に保存される情報について説明する。図８は、探索条件データベース２５０に保存されている情報の態様を説明する図である。
【００５８】
探索条件データベース２５０には、初期設定部２２０から出力された演算入力値３が格納される。演算入力値３には、対象配管を区別するＩＤと、遺伝的アルゴリズムに必要となるパラメータである世代数、個体数、選択演算子、交叉演算子、交叉確率、及び突然変異率とが含まれる。さらに、仮想禁止セル数、補正関数、及び重み係数が格納される。それぞれの項目の意味については、経路演算部２３０の機能の説明にて述べる。
【００５９】
また、演算入力値３には、経路探索の順番の決定に用いる経路のリストＣが含まれ、このリストＣも探索条件データベース２５０に格納される。経路のリストＣについても、経路演算部２３０の機能の説明にて述べる。
【００６０】
次に、経路演算部２３０の動作について説明する。経路演算部２３０は、評価指標（経路の直線部の長さと曲部の数の合計）の値が最小となる経路（最短経路）を最適な経路として探索する。
【００６１】
従来手法での経路探索の問題点として、多数のさまざまな経路を生み出せないという問題がある。そこで、本発明では、対象空間内に仮想の障害物を配置し、この障害物の配置位置をさまざまに変えることで、多数の異なる経路を生み出すこととした。
【００６２】
図９に、対象空間内に仮想の障害物を配置し、始点と終点間の経路を求めた例を示す。２点間の経路を求める手法は、従来手法である動的計画法を用いている。しかしながら、障害物があるため、これを避けるようなルートが生成されている。この仮想の障害物を仮想禁止セルと呼ぶことにする。すなわち、仮想禁止セルは、経路を通すことができない仮想の禁止区域のことである。従って、この仮想禁止セルの配置位置と経路の探索順番をパラメータとした最適化計算をすることで、従来手法での経路探索の問題点を解決することが可能である。
【００６３】
このパラメータを、遺伝的アルゴリズムの計算手法を用いて求める。遺伝的アルゴリズムでは、対象となるパラメータを遺伝子列の状態に変換する必要がある。これをコーディングと呼んでいる。遺伝子列の状態に変換する前の状態を表現型と呼ぶ。
【００６４】
図１０に、本発明における経路探索のパラメータを遺伝子列にコーディングした例を示す。図１０では、２本の経路に対し、空間内に３つの仮想禁止セルを配置するという初期設定を表している。遺伝子列の先頭部分は、経路の探索順序を示しており、残りの部分は、仮想禁止セルの配置位置を示している。
【００６５】
経路探索の順番は、前述した経路のリストＣを用いて、次のようにして決定する。経路のリストＣは、空間内に引く経路の数で決定され、例えば、経路のリストをＣ＝（ｐ，ｑ）とする。このリストＣは、空間内に経路を２本引き、リストの１番目が経路ｐ、２番目が経路ｑであることを表している。経路ｐの始点をＳｐ、終点をＧｐとすると、経路ｐは、始点Ｓｐと終点Ｇｐとを結ぶ経路候補（複数の経路候補がある場合は、これらを全て含む）を意味している。経路ｑについても同様に、始点Ｓｑと終点Ｇｑとを結ぶ経路候補を意味している。
【００６６】
図１０の遺伝子列の１番目は「１」であるため、リストＣの１番目にある経路ｐを１番目の探索候補とする。その後、経路ｐが選択されたため、Ｃ＝（ｑ）とリストを更新する（２番目の経路ｑを１番目に繰り上げる）。図１０の遺伝子列の２番目は「１」であるため、やはり、リストＣの１番目にある経路ｑを２番目の探索候補とする。以上のような方法で、経路探索の順番を決定する。
【００６７】
仮想禁止セルの配置位置については、それぞれｘ、ｙ、ｚの３方向の座標が必要となるため、１つのセルに対して、遺伝子列の３つ分を用いる。遺伝子列のそれぞれの数値は、対象空間をメッシュ状に分割した際の、ｘ、ｙ、ｚ軸の格子点の数を表している。
【００６８】
リストＣと図１０に示した遺伝子列とを用いて、経路ｐ（始点Ｓｐと終点Ｇｐ間の経路候補）や経路ｑ（始点Ｓｑと終点Ｇｑ間の経路候補）が、配置された仮想禁止セルに対していくつあり、それはどのような経路であるかを探索する。この経路探索は、仮想禁止セルの配置位置を変化させて、繰り返し行う。
【００６９】
これまでの設定で、遺伝的アルゴリズムを使ってパラメータを探索することが可能となった。しかし、このままでは、多数の異なる経路を生み出すために仮想禁止セルを経路パターンが増加するような位置に配置する仕組みがないため、初期値に依存する結果が得られる。そこで、本発明では、遺伝的アルゴリズムに必要となる評価関数を補正する手法を導入する。
【００７０】
本発明では、経路の長さと曲部の個数の合計が最少となるような多数の最短経路（最適経路）を求めることが目的である。従って、評価指標（経路の直線部の長さと曲部の数の合計）を評価関数ｆで表現し、評価関数ｆが最小となる経路（最短経路）を複数求める。評価関数ｆは、次の式（１）で表すことができる。
【００７１】
【数１】
2011013708.tif 000003
【００７２】
ｉはｉ番目の経路を表す添え字、Ｉは経路の集合、ｘｉはｉ番目の配管長さ、ｙｉはｉ番目の曲部の個数を示し、αとβは重み係数を示している。この重み係数は、対象配管のコストや仕様などをもとに、ユーザによって指定される。
【００７３】
この評価関数ｆをもとに、繰り返し計算を実施し、得られた経路のパターン数とそのパターンに属する個体数とを求め、パターンに属する個体数に応じて、式（２）と式（３）を用いて評価関数ｆを補正する。
【００７４】
【数２】
2011013708.tif 000004
【００７５】
【数３】
2011013708.tif 000005
【００７６】
ｄｉはｉ番目のパターンに占める個体数、Ｎは得られた経路に属する全個体数を表す。ｆｓは補正された評価関数を示す。
【００７７】
式（２）のｄｉについては、図１１を用いて説明する。図１１では、全個体数Ｎが１０個あり、このうち、１番目の配管パターンを解に持つ個体数が５個、２番目の配管パターンを解に持つ個体数が３個、３番目の配管パターンを解に持つ個体数が２個となっている。この場合、ｄｉの値は、ぞれぞれ、ｄ１＝５、ｄ２＝３、ｄ３＝２となる。
【００７８】
式（２）では、ｄｉの値が大きい程、ｓ（ｄｉ）の値は小さくなる。ｓ（ｄｉ）の値が小さければ、式（３）より評価関数ｆｓの値が大きくなるよう補正される。つまり、同じ経路パターンを多くもつ個体集団に対する評価関数ｆｓは大きくなり、同じ経路パターンが少ない個体集団に対する評価関数ｆｓは小さくなる。図１１の場合、１番目の配管パターンを解に持つ固体の評価関数ｆｓに比べて、３番目の配管パターンを解に持つ個体の評価関数ｆｓが小さくなる。
【００７９】
【数４】
2011013708.tif 000006
【００８０】
また、式（２）の代わりに、式（４）を用いてもよい。式（４）は、ｊ番目の配管とｋ番目の配管の経路の差を示している。すなわち、式（４）の値の逆数は、経路のパターンの一致度を示す。２つの配管経路の差が小さいと、式（４）の値、すなわちｓ（ｄｉ）の値は小さくなる。つまり、評価関数ｆｓの値は大きくなる。経路のパターンの一致度（ｓ（ｄｉ）の逆数）も、大きくなる。逆に、２つの配管経路の差が大きくなれば、つまり、２つの配管経路が大きく異なっていれば、ｓ（ｄｉ）の値は大きくなり、評価関数ｆｓの値は小さくなる。経路のパターンの一致度も小さくなる。
【００８１】
本発明による経路探索装置２００の初期設定部２２０では、探索条件データベース２５０に保存される補正関数の情報（図８参照）として、式（２）を用いる場合は補正関数を「１」、式（４）を用いる場合は補正関数を「２」としている。
【００８２】
図１２は、上述した手法をもとにした経路演算部２３０の処理のフローチャートである。尚、本フローチャートの実行に必要なパラメータについては、支援ツール９１０よりユーザが値を設定することができる。この値の設定については後述する。
【００８３】
図１２において、ステップ３０１では、経路探索演算に必要な初期設定を初期設定部２２０から読込む。この初期設定には、前述した経路のリストＣも含まれる。
【００８４】
次に、ステップ３０２で、ランダムにＮ個の個体を生成し、ｔ＝０として初期個体集団Ｐ（ｔ）を生成する。尚、世代をｔ、最終世代をＴで表す。
【００８５】
ステップ３０３では、生成した個体集団Ｐ（ｔ）を表現型に変換する。表現型への変換は、従来知られている一般的な遺伝的アルゴリズムの手法に基づく。
【００８６】
ステップ３０４で、一般的な遺伝的アルゴリズムの手法に従い、各個体の適応度を計算する。遺伝的アルゴリズムでは、この適応度が高い個体ほど、次世代に引き継がれやすくなるため、通常は、評価指標の最大化問題として、適応度関数と評価指標を等価にする。本発明では、評価指標（評価関数）の最小化問題であるため、本演算では、評価指標をマイナスとしたもの（評価指標の負号を変えたもの）を適応度関数とすることで、通常の方法と整合を取る。
【００８７】
ステップ３０５では、得られた適応度をもとに、選択演算子を適用して、新たな固体集団Ｐ’（ｔ）を生成する。選択演算子とは、次世代に残す個体を選択する操作のことである。選択演算子には、幾つかの方法が考案されている。例えば、個体の適応度に応じた確率で次世代の個体を選択するルーレット選択法、固体を適応度の高い順番に並べ、この順番に応じて次世代の個体を選択するランキング法、Ｎ個の個体からｓ個の個体を組とし、その中で最も適応度の高いものを選択した後、ｓ個分コピーして次世代の個体とするトーナメント法などがある。
【００８８】
本発明による経路探索装置２００の初期設定部２２０では、探索条件データベース２５０に保存される選択演算子の情報（図８参照）として、ルーレット選択法を用いる場合は「１」、ランキング法を用いる場合は「２」、トーナメント法を用いる場合は「３」としている。また、全ての個体の中で、最も適応度が高い個体を優先的に残すエリート保存法を組み合わせることも可能である。
【００８９】
次に、ステップ３０６にて、ステップ３０５で生成された新たな個体集団Ｐ’（ｔ）内からランダムに２個ずつのペアを作り、交叉演算子を適用して、ある確率でこの２個体の遺伝子型の一部を交換し、新たな個体集団Ｐ’’（ｔ）を生成する。ここで適用する確率を交叉率と呼ぶ。この交叉演算子にも、複数の方法が考案されている。遺伝子型で表現された個体の１点を境にして、お互いの記号列を交換する１点交叉、２点を境にする２点交叉、０と１からなる固体と同じ長さの記号列を持ったテンプレートを生成し、テンプレート内で１となっている箇所と同じ位置の記号列を交換する一様交叉などがある。
【００９０】
本発明による経路探索装置２００の初期設定部２２０では、探索条件データベース２５０に保存される交叉演算子の情報（図８参照）として、１点交叉を「１」、２点交叉を「２」、一様交叉を「３」とする。探索条件データベース２５０には、交叉率も保存されている（図８参照）。
【００９１】
ステップ３０７では、交叉によって得られた個体集団Ｐ’’（ｔ）に対し、突然変異演算子を適用して、最終的に次世代の個体集団Ｐ（ｔ＋１）を生成する。突然変異は、遺伝子型で表現された個体の一部を、ある確率で別の記号列に変える操作である。例えば、０、１を用いた遺伝子型では、０を１に、または１を０に変えることを指す。ここで用いている確率を、突然変異率と呼ぶ。突然変異率についての情報は、探索条件データベース２５０に保存されている（図８参照）。
【００９２】
ステップ３０８にて、世代ｔが最終世代Ｔに達していない（ｔ＜Ｔ）場合は、ステップ３０９に進む。世代ｔが最終世代Ｔに達した場合（ｔ＝Ｔ）は、終了となる。
【００９３】
ステップ３０９では、世代ｔを次世代ｔ＋１にする。そして、ステップ３０３以後の操作を、世代ｔが最終世代Ｔになるまで繰り返す。
【００９４】
次に、ユーザが支援ツール９１０を用いて、画像表示装置９５０に探索結果５や、初期設定部２２０、探索結果データベース２４０、探索条件データベース２５０の情報を表示させる方法について説明する。
【００９５】
図１３〜図１６は、画像表示装置９５０に表示される画面の実施例である。ユーザは、キーボード９０１やマウス９０２を用いて、これらの画面に表示されている欄にパラメータ値を入力するなどの操作を実行する。
【００９６】
図１３は、画像表示装置９５０に表示される初期画面である。ユーザは、探索条件設定ボタン９５１、探索結果情報表示ボタン９５２、及び経路情報表示ボタン９５３の中から必要なボタンを選択し、マウス９０２を用いてカーソル９５４を移動させ、マウス９０２をクリックすることによりボタンを押す。
【００９７】
図１４は、探索条件設定画面を説明する図である。図１３において探索条件設定ボタン９５１をクリックすることにより、図１４に示した画面が表示される。
【００９８】
設定情報欄９７１には、ＩＤ、配管名称、世代数、個体数、選択演算子、交叉演算子、交叉率、突然変異率、仮想禁止セル数、補正関数、及び重み係数が表示される。選択演算子、交叉演算子、及び補正関数については、予め設定されている項目をプルダウンメニューより選択する。また、画面上のボックスにＩＤまたは配管の名称のいずれか一方を入力し、検索ボタン９７２をクリックすると、検索結果のみを表示することができる。これは、対象配管数が多い大規模なプラントに本装置を適用する場合に便利な機能である。
【００９９】
転送ボタン９７３をクリックすることにより、設定情報欄９７１に表示されている情報が、経路探索装置２００にある初期設定部２２０と探索条件データベース２５０に設定される。
【０１００】
キャンセルボタン９７４をクリックすると、設定情報欄９７１に入力された情報がキャンセルされる。また、戻るボタン９７５をクリックすることにより、図１３に示した初期画面に戻ることができる。
【０１０１】
図１５は、探索結果情報の表示画面であり、探索結果データベース２４０に保存されている情報を画像表示装置９５０に表示したものである。図１３において、探索結果情報表示ボタン９５２をクリックすることにより、図１５に示した画面が表示される。
【０１０２】
ユーザは、画像表示装置９５０に表示させたい配管を、ＩＤまたは配管名称を入力して検索ボタン９８５をクリックすることにより、検索することができる。また、表示ボタン９８３をクリックすることで、表示対象の配管に対する探索情報の１つである評価指標値（評価関数値）の世代数ごとの変化を、表示欄９８１に表示することができる。この時、評価指標値の最小値、平均値、最大値についても表示する。尚、検索や表示は、複数の配管を指定することが可能である。
【０１０３】
また、ユーザは、求めた経路パターン数の世代数ごとの変化を表示欄９８２に表示することができる。表示形式は、表示欄９８２の下部にあるラジオボタン９８６によって選択することが可能である。例えば、探索対象となった配管全てのパターン数を表示する場合には、ラジオボタン９８６のうち、総数の表示部をクリックする。また、配管の個別パターンを表示する場合には、プルダウンメニュー９８７より、各配管の表示または非表示を選択する。その後、表示ボタン９８３をクリックすることで、選択した表示形式に従って、経路パターン数の世代数による変化を表示欄９８２に表示することができる。
【０１０４】
ユーザは、戻るボタン９８４をクリックすることにより、図１３の初期画面に戻ることができる。
【０１０５】
図１６は、探索の結果得られた経路を画像表示装置９５０に３次元空間表示した経路情報表示画面である。図１３において、経路情報表示ボタン９５３をクリックすることにより、図１６に示した経路情報表示画面が表示される。
【０１０６】
ユーザは、表示対象となる配管をＩＤまたは配管名称を入力して検索ボタン９９１をクリックすることによって検索した後、表示させたい経路パターンを選択する。対象配管の全てのパターンを表示するか非表示にするかはラジオボタン９９２で選択し、対象配管を個別に指定する場合は、プルダウンメニュー９９３から選択する。表示させる経路が決定したら、表示ボタン９９４をクリックすると、選択した経路の上面図、正面図、側面図、アイソメ図（等角投影図）がそれぞれ表示される。
【０１０７】
また、戻るボタン９９５をクリックすることにより、図１３の初期画面に戻ることができる。
【０１０８】
尚、以上で述べた情報以外にも、経路探索装置２００内の探索結果データベース２４０や探索条件データベース２５０に保存されている任意の情報を、所定の態様で画像表示装置９５０に表示することもできる。
【０１０９】
以上、本発明による複数経路の探索装置及び方法を、発電用プラントや一般産業プラントなどの配管に適用した例について説明してきた。本発明によると、多数の異なる配管経路が１度の探索で得られるため、多角的な設計が可能となる。従来手法のような繰り返し作業が無いため、煩雑な操作が不要となり、より詳細な設計検討に時間を割くことが可能となる。
【０１１０】
尚、本発明の適用先は、発電用プラントや一般産業プラントなどの配管に限られるものではなく、３次元空間内の経路探索問題であれば、対象とする空間の規模や経路の長短によらず、幅広い分野に応用可能である。
【符号の説明】
【０１１１】
１００…３次元空間、１１０…記憶装置、２００…経路探索装置、２１０…外部入力インターフェイス、２２０…初期設定部、２３０…経路演算部、２４０…探索結果データベース、２５０…探索条件データベース、２６０…外部出力インターフェイス、９００…入力装置、９０１…キーボード、９０２…マウス、９１０…支援ツール、９２０…外部入力インターフェイス、９３０…データ送受信処理部、９４０…外部出力インターフェイス、９５０…画像表示装置。
【図１】
2011013708.tif 000007
【図２】
2011013708.tif 000008
【図３】
2011013708.tif 000009
【図４】
2011013708.tif 000010
【図５】
2011013708.tif 000011
【図６】
2011013708.tif 000012
【図７】
2011013708.tif 000013
【図８】
2011013708.tif 000014
【図９】
2011013708.tif 000015
【図１０】
2011013708.tif 000016
【図１１】
2011013708.tif 000017
【図１２】
2011013708.tif 000018
【図１３】
2011013708.tif 000019
【図１４】
2011013708.tif 000020
【図１５】
2011013708.tif 000021
【図１６】
2011013708.tif 000022