(57)【要約】【課題】始点から終点までの経路を探索する際のインタラクティブ性能が向上する。【解決手段】三次元空間を直交格子に分割し、始点として設定された前記直交格子の第１格子点、または経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、障害物を検知するまで直進して前記経路を探索する直進探索を行ない、前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する。【選択図】図３
2016212627.tif 000002
【特許請求の範囲】
【請求項１】
障害物が存在する三次元空間内で始点から終点までの経路を探索するコンピュータに、
前記三次元空間を直交格子に分割し、
前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行ない、
前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する
処理を実行させる、経路探索プログラム。
【請求項２】
前記直進探索を行なった結果、前記終点として設定された前記直交格子の第４格子点を通過する軸と交わる位置の第５格子点を検知した場合、検知した第５格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる、請求項１に記載の経路探索プログラム。
【請求項３】
前記次の方向変更点から、前記障害物を検知した位置における障害物面の法線と直交する方向へ、前記障害物面と前記経路との最短距離が所定距離以上になるまで、前記直進探索を行ない、
前記障害物面と前記経路との最短距離が前記所定距離以上になった位置の近傍において前記障害物面との最短距離が前記所定距離以上の位置に存在する前記直交格子の第６格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる請求項１または請求項２に記載の経路探索プログラム。
【請求項４】
前記直進探索を行なっても前記障害物面と前記経路との最短距離が前記所定距離以上にならない場合、前記直進探索によって前記経路が到達した位置の近傍における前記直交格子の第７格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる、請求項３に記載の経路探索プログラム。
【請求項５】
前記始点または前記方向変更点からの前記直進探索一回当たりの最小直進距離を、前記経路に沿って配設されるハーネスの最小曲率半径に応じて設定する、
処理を実行させる、請求項１〜請求項４のいずれか一項に記載の経路探索プログラム。
【請求項６】
前記直進探索を行なっても前記経路が前記終点に到達しない場合、前記直進探索を完了した直進探索済み空間を認識し、
認識した直進探索済み空間内における前記始点から移動可能な隣接格子点を一つずつ探索し、探索した隣接格子点が前記直進探索済み空間内であるか否かを判定することで、前記直進探索済み空間外であると判定された前記隣接格子点を、前記直進探索済み空間内から前記直進探索済み空間外へ到る前記経路上の第８格子点として設定し、
設定した第８格子点から前記直進探索を再開する、
処理を実行させる、請求項１〜請求項５のいずれか一項に記載の経路探索プログラム。
【請求項７】
障害物が存在する三次元空間内で始点から終点までの経路を探索する処理部と、
前記障害物に関する情報を記憶する記憶部と、を有し、
前記処理部は、
前記三次元空間を直交格子に分割し、
前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行ない、
前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する、情報処理装置。
【請求項８】
コンピュータにより、障害物が存在する三次元空間内で始点から終点までの経路を探索する経路探索方法であって、
前記三次元空間を直交格子に分割し、
前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行ない、
前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する、経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本件明細書に開示の発明は、経路探索プログラム、情報処理装置、及び経路探索方法に関する。
【背景技術】
【０００２】
近年、三次元ＣＡＤ（Computer Aided Design）によって得られる三次元モデルを使用して設計開発を効率化する設計支援装置（ＶＰＳ：Virtual Product Simulator）が開発されている。当該設計支援装置は、例えば、設計対象装置（ノートＰＣ（Personal Computer）等）の設計工程におけるバーチャル検証、より具体的には設計対象装置内のハーネスの配線経路の設計・検証に用いられる。
【０００３】
このとき、ユーザは、三次元ＣＡＤを用いて製品（設計対象装置）の部品モデルを生成する。上記設計支援装置は、生成された部品モデル上に、ハーネスの三次元モデル（以下、ハーネスモデルという）を生成しディスプレイに表示する。例えば、ユーザは、ディスプレイに表示される三次元モデル上で、ハーネスとしてのコネクタの始点，終点，通過点などを指定し、ハーネス配線経路を設定する。そして、上記設計支援装置は、設定されたハーネス配線経路に沿うハーネスモデルを部品モデル上に生成して表示する。そして、ユーザは、ディスプレイを参照し、部品モデルとハーネスモデルとの配置関係つまり部品とハーネスとの干渉状態や、ハーネスの長さや曲率半径などを確認しながら、上記設計支援装置を用いてハーネスの配線経路を設計する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平０９−０５０４５４号公報
【特許文献２】特開２００９−１９９３４８号公報
【特許文献３】特開平０３−０６２９４９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述のようにユーザが設計支援装置を用いて手動操作による配線経路の設定検証作業を行なう際には、以下のような工数や手間がかかり、経路設定検証作業に多大な時間を要する。例えば、ハーネスの通過点をマウスクリック操作によって指定する際、通過点が製品の内側にある場合、通過点をユーザに見えるようにすべく、例えば、設計支援装置は、製品の断面図を作成表示したり部品モデルを非表示化したりする。また、狭い空間内に通過点を指定する際、誤クリックを避けるべく、設計支援装置は、部品モデルの要部を拡大表示したり、通過点が見えるように表示されている部品モデルを回転させたりする。
【０００６】
そこで、設計支援装置は、三次元空間内の部品モデル上において始点から終点に到るハーネスの配線経路であって、障害物と干渉しない配線経路を自動的に生成する機能を備えてもよい。当該機能では、基本経路の探索処理（図１０参照）と、ハーネス配線経路の生成処理（図１１参照）とが実行される。
【０００７】
基本経路の探索処理では、図１０に示すように、ハーネスを配線する三次元空間に直交格子（グリッド）が配置される。このとき、ハーネスの始点および終点は、前記直交格子の格子点（グリッド点）になっている。そして、経路探索技術によって、始点から終点に到る配線経路であって、障害物と干渉しない配線経路が、直交格子に沿う基本経路として探索され生成される。
【０００８】
また、ハーネス配線経路の生成処理では、上述のごとく生成された基本経路をハーネスモデルに変換することで、図１１に示すように、滑らかなハーネス配線経路が生成される。なお、経路探索技術では、例えば図１２や図１３に示すように、始点から移動可能な隣接格子点を一つずつ探索し始点から終点まで障害物と干渉しない格子点をつなぐことで、基本経路が探索され生成される。
【０００９】
しかし、上述の経路探索技術では、図１２に示すように配線対象の三次元空間内に狭い空間が存在する場合、図１３に示すようにグリッド間隔（格子点間隔）を狭くすることで当該狭い空間内に格子点を配置する。このため、経路探索の対象になる格子点の数が増大し、経路探索の処理量が増大する。
【００１０】
そこで、図１４に示すように、直交格子において障害物近傍の位置だけにグリッド点を配置設定しておき、経路探索の対象になる格子点の数を削減し、経路探索の処理量を削減することも行なわれている。
【００１１】
しかしながら、図１５に示すように、一般に障害物の表面はグリッドと平行でない場合が多く、この場合、図１４と図１５とを比較しても明らかなように、直交格子において障害物近傍の位置に配置設定されるグリッド点の数を削減することができない。また、障害物の境界を検出する処理が容易でなく、その処理量が大きい。
【００１２】
したがって、上述のようにグリッド間隔が狭い場合や障害物の表面がグリッドと平行でない場合、経路探索等の処理量を削減することができず、多大な処理時間を要することになり、設計支援装置でのインタラクティブ性能（ユーザからの指示に対する応答性能）が低下する。
【００１３】
一つの側面で、本件明細書に開示の発明は、始点から終点までの経路探索に要する処理量を削減することを目的とする。
【課題を解決するための手段】
【００１４】
本件の経路探索プログラムは、障害物が存在する三次元空間内で始点から終点までの経路を探索するコンピュータに、以下の処理（１）〜（３）を実行させる。
（１）前記三次元空間を直交格子に分割する処理。
（２）前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行なう処理。
（３）前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する処理。
【発明の効果】
【００１５】
一実施形態によれば、始点から終点までの経路探索に要する処理量を削減することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態としての経路探索機能を有する情報処理装置の機能構成の一例を示すブロック図である。
【図２】本発明の一実施形態としての経路探索機能を実現する情報処理装置のハードウェア構成の一例を示すブロック図である。
【図３】本実施形態の経路探索手法の概要を説明する図である。
【図４】本実施形態の経路探索処理の手順を説明するフローチャートである。
【図５】図４に示す経路探索処理において処理対象格子点毎に実行される、移動可能な格子点の確認処理の手順を説明するフローチャートである。
【図６】本実施形態の経路探索処理に際して終点に辿り着けない場合に実行される例外処理の手順を説明するフローチャートである。
【図７】図６に示す例外処理において処理対象格子点毎に実行される、移動可能な格子点の確認処理の手順を説明するフローチャートである。
【図８】（Ａ）〜（Ｃ）は本実施形態の第１チェックキューにおける調査候補の保存内容を説明する図である。
【図９】本実施形態の経路探索処理に際して終点に辿り着けない状態と、当該状態が発生した場合に実行される例外処理とを説明する図である。
【図１０】基本経路の探索処理を説明する図である。
【図１１】ハーネス配線経路の生成処理を説明する図である。
【図１２】グリッドを用いた経路探索を説明する図である。
【図１３】間隔の狭いグリッドを用いた経路探索を説明する図である。
【図１４】障害物近傍に配置したグリッド点を用いた経路探索を説明する図である。
【図１５】障害物表面がグリッドと平行でない場合に障害物近傍に配置設定されるグリッド点位置を示す図である。
【発明を実施するための形態】
【００１７】
以下に、図面を参照し、本願の開示する経路探索プログラム、情報処理装置、及び経路探索方法の実施形態について、詳細に説明する。ただし、以下に示す実施形態は、あくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。また、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能を含むことができる。そして、各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００１８】
〔１〕経路探索機能を実現する本実施形態の情報処理装置のハードウェア構成
まず、図２を参照しながら、本実施形態の経路探索機能を実現する情報処理装置（コンピュータ）１０のハードウェア構成について説明する。図２は、当該ハードウェア構成の一例を示すブロック図である。
【００１９】
コンピュータ１０は、例えば、プロセッサ１１，ＲＡＭ（Random Access Memory）１２，ＨＤＤ（Hard Disk Drive）１３，グラフィック処理装置１４，入力インタフェース１５，光学ドライブ装置１６，機器接続インタフェース１７およびネットワークインタフェース１８を構成要素として有する。これらの構成要素１１〜１８は、バス１９を介して相互に通信可能に構成される。
【００２０】
プロセッサ（処理部）１１は、コンピュータ１０全体を制御する。プロセッサ１１は、マルチプロセッサであってもよい。プロセッサ１１は、例えばＣＰＵ（Central Processing Unit），ＭＰＵ（Micro Processing Unit），ＤＳＰ（Digital Signal Processor），ＡＳＩＣ（Application Specific Integrated Circuit），ＰＬＤ（Programmable Logic Device），ＦＰＧＡ（Field Programmable Gate Array）のいずれか一つであってもよい。また、プロセッサ１１は、ＣＰＵ，ＭＰＵ，ＤＳＰ，ＡＳＩＣ，ＰＬＤ，ＦＰＧＡのうちの２種類以上の要素の組み合わせであってもよい。
【００２１】
ＲＡＭ（記憶部）１２は、コンピュータ１０の主記憶装置として使用される。ＲＡＭ１２には、プロセッサ１１に実行させるＯＳ（Operating System）プログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１２には、プロセッサ１１による処理に必要な各種データが格納される。アプリケーションプログラムには、コンピュータ１０によって本実施形態の経路探索機能を実現するためにプロセッサ１１によって実行される経路探索プログラム（図１の符号３１参照）が含まれてもよい。
【００２２】
ＨＤＤ（記憶部）１３は、内蔵したディスクに対して、磁気的にデータの書き込み及び読み出しを行なう。ＨＤＤ１３は、コンピュータ１０の補助記憶装置として使用される。ＨＤＤ１３には、ＯＳプログラム，アプリケーションプログラム、及び各種データが格納される。なお、補助記憶装置としては、フラッシュメモリ等の半導体記憶装置（ＳＳＤ：Solid State Drive）を使用することもできる。
【００２３】
グラフィック処理装置１４には、モニタ１４ａが接続されている。グラフィック処理装置１４は、プロセッサ１１からの命令に従って、画像をモニタ１４ａの画面に表示させる。モニタ１４ａとしては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置等が挙げられる。
【００２４】
入力インタフェース１５には、キーボード１５ａおよびマウス１５ｂが接続されている。入力インタフェース１５は、キーボード１５ａやマウス１５ｂから送られてくる信号をプロセッサ１１に送信する。なお、マウス１５ｂは、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル，タブレット，タッチパッド，トラックボール等が挙げられる。
【００２５】
光学ドライブ装置１６は、レーザ光等を利用して、光ディスク１６ａに記録されたデータの読み取りを行なう。光ディスク１６ａは、光の反射によって読み取り可能にデータを記録された可搬型の非一時的な記録媒体である。光ディスク１６ａには、ＤＶＤ（Digital Versatile Disc），ＤＶＤ−ＲＡＭ，ＣＤ−ＲＯＭ（Compact Disc Read Only Memory），ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。
【００２６】
機器接続インタフェース１７は、コンピュータ１０に周辺機器を接続するための通信インタフェースである。例えば、機器接続インタフェース１７には、メモリ装置１７ａやメモリリーダライタ１７ｂを接続することができる。メモリ装置１７ａは、機器接続インタフェース１７との通信機能を搭載した非一時的な記録媒体、例えばＵＳＢ（Universal Serial Bus）メモリである。メモリリーダライタ１７ｂは、メモリカード１７ｃへのデータの書き込み、またはメモリカード１７ｃからのデータの読み出しを行なう。メモリカード１７ｃは、カード型の非一時的な記録媒体である。
【００２７】
ネットワークインタフェース１８は、ネットワーク１８ａに接続される。ネットワークインタフェース１８は、ネットワーク１８ａを介して、他のコンピュータまたは通信機器との間でデータの送受信を行なう。
【００２８】
以上のようなハードウェア構成を有するコンピュータ１０によって、図３〜図９を参照しながら後述する本実施形態の経路探索機能を実現することができる。
【００２９】
なお、コンピュータ１０は、例えばコンピュータ読み取り可能な非一時的な記録媒体に記録されたプログラム（経路探索プログラム等）を実行することにより、本実施形態の経路探索機能を実現する。コンピュータ１０に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、コンピュータ１０に実行させるプログラムをＨＤＤ１３に格納しておくことができる。プロセッサ１１は、ＨＤＤ１３内のプログラムの少なくとも一部をＲＡＭ１２にロードし、ロードしたプログラムを実行する。
【００３０】
また、コンピュータ１０（プロセッサ１１）に実行させるプログラムを、光ディスク１６ａ，メモリ装置１７ａ，メモリカード１７ｃ等の非一時的な可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１１からの制御により、ＨＤＤ１３にインストールされた後、実行可能になる。また、プロセッサ１１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００３１】
〔２〕経路探索機能を有する本実施形態の情報処理装置の機能構成
次に、図１を参照しながら、本実施形態の経路探索機能を有する情報処理装置（コンピュータ）１０の機能構成について説明する。図１は、当該機能構成の一例を示すブロック図である。
【００３２】
コンピュータ１０は、上述した基本経路の探索処理（図１０参照）を行なうもので、境界面および障害物が存在する三次元空間内で始点から終点までの配線経路であって、障害物と干渉しない配線経路を、基本経路として探索生成する機能を果たす。上記境界面は、例えば、本実施形態では例えば図３を参照しながら後述するごとく配置設定される直交格子の境界面に対応する。上記機能を果たすため、コンピュータ１０は、図１に示すように、少なくとも処理部２０，記憶部３０，入力部４０および表示部５０としての機能を有している。
【００３３】
処理部２０は、例えば図２に示すようなプロセッサ１１であり、上述した経路探索プログラム３１を実行することで、後述する直交格子配置部２１，直進探索部２２，直進探索済み空間認識部２３，直進探索済み空間内経路探索部２４としての機能を果たす。
【００３４】
記憶部３０は、例えば図２に示すようなＲＡＭ１２，ＨＤＤ１３であり、経路探索機能を実現するための各種情報を記憶し保存する。当該各種情報としては、上述した経路探索プログラム３１のほか、部品モデル３２，ハーネスモデル３３，ハーネス情報３４，直交格子情報３５，グリッド点情報３６，第１チェックキュー３７，第２チェックキュー３８などが含まれる。
【００３５】
部品モデル３２は、三次元ＣＡＤを用いて生成された製品（設計対象装置）の三次元モデル（３Ｄモデル）であり、本実施形態のコンピュータ１０は、当該部品モデル３２上において、ユーザによって指定された始点から終点までハーネスを配線する。
【００３６】
ハーネスモデル３３は、部品モデル３２上において、本実施形態のコンピュータ１０によって配線されたハーネスの三次元モデルである。当該ハーネスモデル３３は、本実施形態のコンピュータ１０の経路探索機能によって探索生成された基本経路を変換して生成されるもので、滑らかなハーネス配線経路（図１１参照）に対応する。
【００３７】
ハーネス情報３４は、部品モデル３２上に配線されるべき配線対象ハーネスに関する情報である。ハーネス情報３４は、例えば、当該配線対象ハーネスの長さや最小曲率半径のほか、ユーザによって指定される当該配線対象ハーネスの始点（第１格子点）および終点（第４格子点）の位置情報などを含む。なお、配線対象ハーネスの最小曲率半径は、後述する直進探索一回当たりの最小直進距離として用いられる。
【００３８】
直交格子情報（境界面情報）３５は、例えば図３を参照しながら後述するごとく配置設定される直交格子に関する情報で、例えば、グリッド分割数（格子分割数），グリッド間隔（格子間隔），直交格子の配置方向，直交格子の境界面の位置を含む。
【００３９】
グリッド点情報３６は、コンピュータ１０によって探索される各グリッド点に関する情報で、各グリッド点を特定するグリッド点ＩＤ（identification）に対応付けられている。グリッド点情報３６は、例えば、各グリッド点の位置情報（座標）や、親グリッド点ＩＤ（以下、単に親という場合がある）や、基本経路が各グリッド点に到るまでのコスト値や、衝突フラグを含む。
【００４０】
親グリッド点ＩＤは、各グリッド点に到る基本経路が各グリッド点に到る直前に設定された親グリッド点を特定する情報である。
【００４１】
コスト値は、小さいほど始点からの移動距離が短くなるように設定されている。例えば、コスト値は、始点から各グリッド点に到るまでの基本経路の距離（移動グリッド数）Ｄ１や、各グリッド点から終点までの予想距離（例えばマンハッタン距離）Ｄ２に基づいて算出される。このとき、コスト値としては、距離Ｄ１を用いてもよいし、距離Ｄ１＋Ｄ２を用いてもよい。
【００４２】
衝突フラグは、各グリッド点が、直進探索によって障害物を検知する直前（障害物と衝突する直前）のグリッド点（第３格子点）である場合に“１”を設定され、それ以外の場合は“０”を設定される（図５，図８参照）。
【００４３】
第１チェックキュー３７は、後述する直進探索部２２による直進探索に用いられ、当該直進探索部２２による調査候補のグリッド点に関する情報（グリッド点ＩＤ，親，コスト値，衝突フラグ）を投入され一時的に保存する（図４，図５，図８参照）。
【００４４】
第２チェックキュー３８は、後述する直進探索済み空間内経路探索部２４による経路探索に用いられ、当該経路探索部２４による調査候補になるグリッド点に関する情報（グリッド点ＩＤ，親，コスト値）を投入され保存する（図６，図７参照）。なお、第２チェックキュー３８を用いて当該経路探索部２４が経路探索を行なう際、当該経路探索部２４によって探索される各グリッド点の位置や、各グリッド点の親や、探索経路が各グリッド点に到るまでのコスト値が、グリッド点情報３６として記憶部３０に保存される。
【００４５】
入力部４０は、例えば図２に示すようなキーボード１５ａおよびマウス１５ｂであり、ユーザによって操作され、ホットスポットの有無を判定するための各種指示を行なう。なお、マウス１５ｂに代え、タッチパネル，タブレット，タッチパッド，トラックボール等が用いられてもよい。ユーザは、入力部４０を操作することにより、例えば、部品モデル３２上に配線されるハーネスの始点や終点（図３参照）を指定入力してもよい。
【００４６】
表示部５０は、例えば図２に示すようなモニタ１４ａであり、ユーザが本実施形態のコンピュータ１０を用いて部品モデル３２上にハーネスを配線する際に、当該ハーネスの配線経過に伴う各種状況を表示する。当該各種状況としては、例えば、基本経路の探索過程の状況（図３，図１０参照）や、基本経路をハーネスモデル３３に変換するハーネス化過程の状況（図１１参照）が挙げられる。
【００４７】
経路探索プログラム３１は、上述のごとく、処理部２０（プロセッサ１１）に、後述する直交格子配置部２１，直進探索部２２，直進探索済み空間認識部２３，直進探索済み空間内経路探索部２４による処理を実行させるものである。
【００４８】
次に、処理部２０（プロセッサ１１）によって実現される、直交格子配置部２１，直進探索部２２，直進探索済み空間認識部２３，直進探索済み空間内経路探索部２４としての機能について説明する。
【００４９】
直交格子配置部（分割部）２１は、直交格子情報３５に基づいて、ハーネスを配線する三次元空間（部品モデル３２上）に直交格子（グリッド）を配置することで、前記三次元空間を直交格子に分割する。このとき、図３や図１０に示すように、ユーザによって指定される配線対象ハーネスの始点および終点は、直交格子の格子点（グリッド点）になっている。
【００５０】
直進探索部２２は、始点（直交格子の第１格子点；図３のＰ１参照）、または、探索中の経路が進行方向を変える方向変更点として探索され設定された格子点（直交格子の第２格子点；図３のＰ２，Ｐ４，Ｐ５，Ｐ７参照）から、直交格子の一軸方向（全部で６つの方向のそれぞれ）へ、直交格子の境界面または障害物を検知するまで直進して経路を探索する直進探索を行なう。
【００５１】
直進探索部２２は、直交格子の境界面または障害物を検知する直前に通過した直交格子の格子点（第３格子点；図３のＰ２，Ｐ３，Ｐ５，Ｐ６参照）を、探索中の経路の次の方向変更点として、記憶部３０のグリッド点情報３６に設定する。このとき、グリッド点情報３６には、当該次の方向変更点の情報として、当該次の方向変更点の位置，親，コスト値，衝突フラグ“１”が設定される。
【００５２】
直進探索部２２は、直進探索を行なった結果、終点（直交格子の第４格子点；図３のＰ８参照）を通過する軸（直交格子の一軸）と交わる位置の格子点（直交格子の第５格子点；図３のＰ７参照）を検知した場合、検知した第５格子点を、探索中の経路の次の方向変更点として、記憶部３０のグリッド点情報３６に設定する。このとき、グリッド点情報３６には、当該次の方向変更点の情報として、当該次の方向変更点の位置，親，コスト値，衝突フラグ“０”が設定される。
【００５３】
直進探索部２２は、方向変更点（図３のＰ３，Ｐ６参照）から、障害物を検知した位置における障害物面の法線方向（図３の矢印Ｈ１，Ｈ２方向参照）と直交する４つの探索方向へ、障害物面と探索中の経路との最短距離（図３のｄ参照）が所定距離以上になるまで、直進探索を行なう。前記４つの探索方向は、前記法線方向と前記方向変更点を検知するまでの直進探索方向とが成す面上で前記法線方向と直交する２つの方向（例えば図３の矢印Ａ３方向及びその反対方向、または、矢印Ａ６方向及びその反対方向参照）を含む。また、前記４つの探索方向は、前記法線方向と前記方向変更点を検知するまでの直進探索方向とが成す面と直交する２つの方向（例えば図３の紙面と直交する２つの方向）を含む。
【００５４】
そして、直進探索部２２は、障害物面と探索中の経路との最短距離が所定距離以上になった位置の近傍において障害物面との最短距離が所定距離以上の位置に存在する直交格子の格子点（第６格子点；図３のＰ４参照）を、探索中の経路の次の方向変更点として、記憶部３０のグリッド点情報３６に設定する。このとき、グリッド点情報３６には、当該次の方向変更点の情報として、当該次の方向変更点の位置，親，コスト値，衝突フラグ“０”が設定される。
【００５５】
直進探索を行なっても障害物面と探索中の経路との最短距離が所定距離以上にならない場合、直進探索部２２は、直進探索によって探索中の経路が到達した位置の近傍における直交格子の格子点（第７格子点；図３のＰ７参照）を、探索中の経路の次の方向変更点として、記憶部３０のグリッド点情報３６に設定する。このとき、グリッド点情報３６には、当該次の方向変更点の情報として、当該次の方向変更点の位置，親，コスト値，衝突フラグ“０”が設定される。
【００５６】
直進探索部２２は、始点（図３のＰ１参照）または方向変更点（図３のＰ２〜Ｐ７）からの直進探索一回当たりの最小直進距離を、探索中の経路に沿って配設されるハーネスの最小曲率半径に応じて設定する。例えば、直進探索部２２によって探索された基本経路に沿ってハーネスを配線することができるように、直進探索一回当たりの最小直進距離は、ハーネスの最小曲率半径以上に設定される（図５を参照しながら後述）。
【００５７】
上述した直進探索部２２が第１チェックキュー３７を用いて行なう具体的な直進探索動作については、図４，図５，図８，図９を参照しながら後述する。
【００５８】
直進探索済み空間認識部（認識部）２３は、直進探索を行なっても探索中の経路が終点に到達しない場合（図９を参照しながら後述するような場合）、直進探索を完了した直進探索済み空間（図９の直方体空間参照）を認識する。
【００５９】
直進探索済み空間内経路探索部（経路探索部）２４は、認識部２３が認識した直進探索済み空間内における始点から移動可能な隣接格子点を一つずつ探索する。そして、経路探索部２４は、探索した隣接格子点が直進探索済み空間内であるか否かを判定する。経路探索部２４は、直進探索済み空間外であると判定された隣接格子点を、直進探索済み空間内から同空間外へ到る経路上の格子点（第８格子点；図９のＰ９参照）として、記憶部３０のグリッド点情報３６に設定する。このとき、グリッド点情報３６には、当該隣接格子点（第８格子点）の情報として、当該隣接格子点の位置，親，コスト値が設定される。そして、直進探索部２２は、当該隣接格子点（第８格子点）から直進探索を再開する。
【００６０】
なお、直進探索済み空間内から同空間外へ到る経路上の格子点（第８格子点）が探索できない場合、または当該格子点（第８格子点）が存在しない場合、経路探索部２４は、直進探索済み空間内から同空間外へ到る経路が無いと判断し、その旨を、表示部５０等によってユーザに通知することができる。
【００６１】
上述した直進探索済み空間内経路探索部２４が第１チェックキュー３７および第２チェックキュー３８を用いて行なう具体的な経路探索動作については、図６，図７，図９を参照しながら後述する。
【００６２】
〔３〕本実施形態の経路探索手法の概要
次に、図３を参照しながら、本実施形態の経路探索手法の概要について説明する。図３は、本実施形態の経路探索手法の概要を説明する図である。なお、図３においては、ハーネスを配線すべき三次元空間に配置された直交格子（グリッド）や、当該三次元空間内の障害物，始点，終点および探索経路や、探索時の移動方向などが、二次元で表現されている。
【００６３】
本実施形態の経路探索手法では、始点または探索格子点から経路（次の格子点）の探索が開始されると、開始点から６方向のうちの一つが、経路の進行方向として選択される。そして、図３に示すように、選択された進行方向のみに経路探索を行なって、直交格子の境界面または障害物の検知が行なわれる。境界面が検知された場合、境界面が検知される直前に通過した格子点が次の方向変更点として設定される（このとき衝突フラグは“０”に設定される）。また、障害物が検知された場合、障害物が検知される直前に通過した格子点が次の方向変更点として設定される（このとき衝突フラグは“１”に設定される）。このとき、ハーネスの曲率を考慮した経路（基本経路）を生成するため、一回の経路探索による探索位置は、少なくともハーネスの最小曲率半径の距離だけ、直進移動する。
【００６４】
また、本実施形態の経路探索手法では、障害物が検知された場合、図３に示すように、障害物検知直前の格子点から、障害物検知位置における障害物面の法線と垂直な方向へ、障害物面の端部と探索中の経路との最短距離が所定距離以上になるまで、直進探索が行なわれる。そして、図３に示すように、障害物面と探索中の経路との最短距離が所定距離以上になった位置の近傍において障害物面との最短距離が所定距離以上の位置に存在する格子点が、探索中経路の次の方向変更点として設定される（このとき衝突フラグは“０”に設定される）。
【００６５】
これにより、本実施形態の経路探索手法では、一方向のみへ連続移動する直進探索を６つの方向に対して行なって、境界面や障害物面を検知した場合に探索点が設定される。また、グリッドと平行でない障害物面（曲面や斜面）を検知した場合には障害物面の法線と垂直な方向へ障害物面から所定距離だけ離れるまで経路探索が行なわれ、障害物が回避される。
【００６６】
したがって、隣接格子点を一つずつ探索設定しながら経路を探索する手法に比べ、始点から終点までの経路探索に要する処理量を大幅に削減することができる。また、障害物近傍に存在するが障害物を確実に回避可能な格子点のみを選択設定しながら経路探索を行なうことができるので、グリッド間隔が狭い場合や障害物面がグリッドと平行でない場合においても、始点から終点までの経路探索に要する処理量を削減することができる。
【００６７】
ついで、本実施形態の経路探索手法によって、図３において始点（第１格子点）Ｐ１から終点（第４格子点）Ｐ８へ到る、一つの基本経路を探索する手順について、具体的に説明する。
【００６８】
まず、図３に示す例では、始点Ｐ１から図３の上方向（矢印Ａ１方向）へ向かう直進探索が開始される。矢印Ａ１方向への直進探索は、図３に示す直交格子の上側境界面を検知するまで行なわれ、上側境界面を検知すると、上側境界面検知直前に通過した格子点（第３格子点）Ｐ２が、始点Ｐ１の次の方向変更点として設定される。
【００６９】
次に、格子点（第２格子点）Ｐ２から、上側境界面と平行な右方向（矢印Ａ２方向）へ向かう直進探索が実行される。矢印Ａ２方向への直進探索は、図３に示す上側障害物の面を検知するまで行なわれ、上側障害物面を検知すると、上側障害物面検知直前に通過した格子点（第３格子点）Ｐ３が、格子点Ｐ２の次の方向変更点として設定される。
【００７０】
次に、格子点Ｐ３から、上側障害物を検知した位置における障害物面の法線Ｈ１と垂直な方向（矢印Ａ３方向）へ向かう直進探索が実行される。矢印Ａ３方向への直進探索は、上側障害物面と探索中経路との最短距離ｄが所定距離以上になるまで行なわれる。当該最短距離ｄが所定距離以上になると、当該最短距離が所定距離３以上になった位置の近傍において上側障害物面との最短距離が所定距離ｄ以上の位置に存在する直交格子の格子点（第６格子点）Ｐ４が、格子点Ｐ３の次の方向変更点として設定される。
【００７１】
次に、格子点（第２格子点）Ｐ４から図３の下方向（矢印Ａ４方向）へ向かう直進探索が実行される。矢印Ａ４方向への直進探索は、図３に示す直交格子の下側境界面を検知するまで行なわれ、下側境界面を検知すると、下側境界面検知直前に通過した格子点（第３格子点）Ｐ５が、格子点Ｐ４の次の方向変更点として設定される。
【００７２】
次に、格子点（第２格子点）Ｐ５から、下側境界面と平行な右方向（矢印Ａ５方向）へ向かう直進探索が実行される。矢印Ａ５方向への直進探索は、図３に示す右下障害物の面を検知するまで行なわれる。右下障害物面を検知すると、つまり格子点を示す黒丸と右下障害物の面とが干渉すると、右下障害物面干渉直前に通過した格子点（第３格子点）Ｐ６が、格子点Ｐ５の次の方向変更点として設定される。
【００７３】
次に、格子点Ｐ６から、右下障害物を検知した位置における障害物面の法線Ｈ２と垂直な方向（矢印Ａ６方向）へ向かう直進探索が実行される。ここで、矢印Ａ６方向への直進探索を行なっても、右下障害物面と探索中の経路との最短距離ｄは所定距離以上にならない。このとき、直進探索によって探索中の経路は直交格子の右側境界面に到達し、到達した右側境界面の位置近傍における格子点（第７格子点）Ｐ７が、格子点Ｐ６の次の方向変更点として設定される。
【００７４】
なお、格子点Ｐ７は、格子点Ｐ６から、以下のように探索されてもよい。つまり、格子点Ｐ６から矢印Ａ６方向へ向かう直進探索を行なうことにより、終点（第４格子点）Ｐ８を通過する軸（直交格子の一軸）と交わる位置の格子点（第５格子点）として、格子点Ｐ７が検知されてもよい。
【００７５】
最後に、格子点（第２格子点）Ｐ７から図３の上方向へ向かう直進探索が実行され、終点Ｐ８が検知され、一つの基本経路の探索が完了する。同様にして、複数の異なる基本経路が探索される場合には、各基本経路について算出されるコスト値が最小になる基本経路が選択される。ここで、コスト値は、例えば、始点から終点に到るまでの各基本経路の距離（移動グリッド数）とすることができる。
【００７６】
〔４〕本実施形態の経路探索処理
次に、図４〜図９を参照しながら、本実施形態の情報処理装置１０による具体的な経路探索処理の手順について説明する。
【００７７】
〔４−１〕経路探索処理の手順
まず、図４に示すフローチャート（ステップＳ１１〜Ｓ２０）に従って、本実施形態の情報処理装置１０による経路探索処理の手順について説明する。情報処理装置１０は、三次元モデル（部品モデル）３２，グリッド分割数，始点，終点，ハーネスの最小曲率半径などを入力されると、分割部２１によって、ハーネスを配線すべき三次元空間（部品モデル３２）を、グリッド分割数に従ってグリッド状（直交格子）に分割する（ステップＳ１１）。
【００７８】
また、直進探索部２２は、ステップＳ１１で分割された直行格子の各グリッド点に設定されるグリッド点情報３６を初期化する（ステップＳ１２）。つまり、各グリッド点のＩＤに対応付けられて保存されるコスト値および衝突フラグが、それぞれ∞（最大値）および“０”に設定されるとともに、各グリッド点のＩＤに対応付けられて保存される位置や親が未定状態に設定される。
【００７９】
さらに、直進探索部２２は、当該直進探索部２２による調査候補になるグリッド点を投入される第１チェックキュー３７を初期化（空状態に）するとともに（ステップＳ１３）、始点を第１チェックキュー３７に投入する（ステップＳ１４）。ここで、始点についてのグリッド点情報３６には、コスト値＝∞，衝突フラグ＝“０”，親＝「無し」が設定される。
【００８０】
この後、直進探索部２２は、第１チェックキュー３７が空状態か否かを判断し（ステップＳ１５）、空状態でない場合（ステップＳ１５のＮＯルート）、第１チェックキュー３７からグリッド点を一つ取り出す（ステップＳ１６）。そして、直進探索部２２は、取り出したグリッド点が終点であるか否かを判断する（ステップＳ１７）。
【００８１】
取り出したグリッド点が終点でない場合（ステップＳ１７のＮＯルート）、直進探索部２２は、取り出したグリッド点の周囲を確認し、取り出したグリッド点から移動可能なグリッド点を第１グリッドキュー３７に投入する（ステップＳ１８）。移動可能なグリッド点が存在しなければ、第１グリッドキュー３７に対するグリッド点の投入は行なわれない。この後、直進探索部２２は、ステップＳ１５の処理へ移行する。なお、ステップＳ１８の確認処理の詳細については、図５を参照しながら後述する。
【００８２】
取り出したグリッド点が終点である場合（ステップＳ１７のＹＥＳルート）、直進探索部２２は、終点からグリッド点情報３６の親を辿って基本経路をバックトレースすることにより、始点から終点に到る基本経路を取得して出力し（ステップＳ１９）、経路探索処理を「経路あり」として終了する。なお、ステップＳ１９では、必要に応じて、ユーザが、取得した基本経路に対し手動による調整を行なってもよい。
【００８３】
一方、第１チェックキュー３７が空状態の場合（ステップＳ１５のＹＥＳルート）、図９を参照しながら後述するごとく、情報処理装置１０は、終点に辿り付けない状態に陥っていると考えられる。そこで、このような状態に陥った場合、情報処理装置１０は、直進探索部２２による処理から、認識部２３および経路探索部２４による例外処理（終点に辿り付けない状態に対応する処理；ステップＳ２０）へ移行する。
【００８４】
ステップＳ２０の例外処理によって第１チェックキュー３７に直進探索部２２による調査候補のグリッド点が投入されると、情報処理装置１０は、認識部２３および経路探索部２４による例外処理から直進探索部２２によるステップＳ１５の処理へ移行する。また、情報処理装置１０は、図６を参照しながら後述するごとく、ステップＳ２０の例外処理の結果によって「経路あり」として経路探索処理を終了、または、「経路無し」として経路探索処理を終了する。なお、ステップＳ２０の例外処理の詳細については、図６および図７を参照しながら後述する。
【００８５】
〔４−２〕移動可能な格子点の確認処理の手順
次に、図５に示すフローチャート（ステップＳ２１〜Ｓ３２）に従って、図４のステップＳ１８において処理対象格子点（調査候補）毎に実行される、移動可能な格子点の確認処理の手順について説明する。
【００８６】
図４のステップＳ１６で取り出された終点でない一グリッド点（即ち処理対象格子点）が、入力グリッド点として入力されると、まず、直進探索部２２は、当該入力グリッド点から直進移動する方向として、直交格子の６軸方向（前後左右上下）の中から一軸方向を選択する（ステップＳ２１）。
【００８７】
直進探索部２２は、グリッド点情報３６を参照し、入力グリッド点の衝突フラグが“０”であるか否かを判断する（ステップＳ２２）。入力グリッド点が、後述するごとく直進探索によって直交格子の境界面または終点通過軸との交差を検知することによって設定されている場合、入力グリッド点の衝突フラグは“０”である（ステップＳ２２のＹＥＳルート）。この場合、直進探索部２２は、入力グリッド点から、ステップＳ２１で選択した一軸方向へ直進探索を行なう（ステップＳ２３）。つまり、直進探索部２２は、直交格子の境界面または障害物の面を検知するか、終点を通過する軸と交わる位置の格子点を検知するまで、選択した一軸方向への直進探索を行なう。
【００８８】
直交格子の境界面または障害物の面を検知するか、終点を通過する軸と交わる位置の格子点を検知すると、直進探索部２２は、移動距離が配線対象ハーネスの最小曲率半径以上であるか否かを判断する（ステップＳ２４）。ここで、移動距離は、入力グリッド点から、ステップＳ２３の直進探索によって最後に通過または到達したグリッド点（次の方向変更点）までの距離である。
【００８９】
移動距離が最小曲率半径未満の場合（ステップＳ２４のＮＯルート）、入力グリッドと次の方向変更点との距離が短いため、直進探索部２２によって探索される基本経路に沿ってハーネスを曲げてハーネスの配線方向を変更することができないものと考えられる。したがって、直進探索部２２は、当該基本経路に沿ってハーネスを配線することができない可能性が高いと判断する。そのため、直進探索部２２は、今回選択した一軸方向への直進探索を採用せず、ステップＳ２８の処理へ移行し、６軸方向の全ての方向を選択したか否かを判断する。
【００９０】
まだ全ての方向を選択していない場合（ステップＳ２８のＮＯルート）、直進探索部２２は、ステップＳ２１の処理に戻る。一方、全ての方向を選択している場合（ステップＳ２８のＹＥＳルート）、直進探索部２２は、図４のステップＳ１５の処理に戻る。
【００９１】
移動距離が最小曲率半径以上の場合（ステップＳ２４のＹＥＳルート）、入力グリッドと次の方向変更点との間にはハーネスを曲げながら配線するのに十分な距離があるため、直進探索部２２によって探索される基本経路に沿ってハーネスを曲げハーネスの配線方向を変更することができるものと考えられる。したがって、直進探索部２２は、当該基本経路に沿ってハーネスを配線することができると判断する。
【００９２】
そして、直進探索部２２は、ステップＳ２３において最後に通過または到達したグリッド点であって、障害物面の検知に伴って得られたグリッド点について、衝突フラグ＝“１”と親＝入力グリッド点ＩＤとを設定する。また、直進探索部２２は、ステップＳ２３において最後に通過または到達したグリッド点であって、境界面の検知、または、終点通過軸との交差の検知に伴って得られたグリッド点について、衝突フラグ＝“０”と親＝入力グリッド点ＩＤとを設定する。さらに、直進探索部２２は、ステップＳ２３において最後に通過または到達したグリッド点について、当該グリッド点でのコスト値を算出する（ステップＳ２５）。
【００９３】
この後、ステップＳ２３で直進探索されたグリッド点について以前に算出したコスト値が保存されている場合、直進探索部２２は、今回算出したコスト値が、保存されているコスト値よりも低いか否かを判断する（ステップＳ２６）。
【００９４】
今回算出したコスト値が、保存されているコスト値よりも低い場合（ステップＳ２６のＹＥＳルート）、直進探索部２２は、ステップＳ２５で設定又は算出された衝突フラグ，親，コスト値を、ステップＳ２３で直進探索されたグリッド点のグリッド点情報３６として保存する。また、直進探索部２２は、ステップＳ２３で直進探索されたグリッド点（グリッド点ＩＤ）を第１チェックキュー３７に投入する（ステップＳ２７）。この後、直進探索部２２は、ステップＳ２８の処理へ移行する。
【００９５】
なお、ステップＳ２３の直進探索で検知されたグリッド点について以前に算出したコスト値が保存されていない場合、直進探索部２２は、ステップＳ２６での比較処理を行なうことなく、ステップＳ２７の処理へ移行する。
【００９６】
今回算出したコスト値が、保存されているコスト値以上の場合（ステップＳ２６のＮＯルート）、直進探索部２２は、ステップＳ２５で設定又は算出された衝突フラグ，親，コスト値を、保存することなく、ステップＳ２５の処理前の状態に戻す（ステップＳ２９）。この後、直進探索部２２は、ステップＳ２８の処理へ移行する。
【００９７】
一方、入力グリッド点が、直進探索によって障害物面を検知することによって設定されている場合、入力グリッド点の衝突フラグは“１”である（ステップＳ２２のＮＯルート）。この場合、直進探索部２２は、入力グリッド点から、障害物を検知した位置における障害物面の法線方向と直交する４つの方向への直進探索を行なう（ステップＳ３０）。なお、当該４つの探索方向は、当該法線方向と当該入力グリッド点を検知するまでの直進探索方向とが成す面上で当該法線方向と直交する２つの方向と、当該法線方向と当該入力グリッド点を検知するまでの直進探索方向とが成す面と直交する２つの方向とを含む。このとき、直進探索部２２は、障害物面と探索中の経路との最短距離ｄが所定距離以上になるまで、もしくは、障害物面の端に到るまで、もしくは、終点を通過する軸と交わる位置の格子点を検知するまで、直進探索を行なう。
【００９８】
検知した障害物面から所定距離離れる、又は障害物面の端に到る、又は終点通過軸と交差すると、直進探索部２２は、移動距離が配線対象ハーネスの最小曲率半径以上であるか否かを判断する（ステップＳ３１）。ここで、移動距離は、入力グリッド点から、ステップＳ３０の直進探索によって到達した直進移動先のグリッド点（次の方向変更点）までの距離である。
【００９９】
移動距離が最小曲率半径未満の場合（ステップＳ３１のＮＯルート）、前述と同様の理由により、直進探索部２２は、当該基本経路に沿ってハーネスを配線することができない可能性が高いと判断する。そのため、直進探索部２２は、今回の直進探索を採用せず、ステップＳ２８の処理へ移行し、６軸方向の全ての方向を選択したか否かを判断する。
【０１００】
移動距離が最小曲率半径以上の場合（ステップＳ３１のＹＥＳルート）、前述と同様の理由により、直進探索部２２は、当該基本経路に沿ってハーネスの配線方向を変更することができると判断する。
【０１０１】
そして、直進探索部２２は、直進移動先のグリッド点について、衝突フラグ＝“０”と親＝入力グリッド点ＩＤとを設定する。また、直進探索部２２は、ステップＳ２３において最後に通過または到達したグリッド点であって、境界面の検知、または、終点通過軸との交差の検知に伴って得られたグリッド点について、衝突フラグ＝“０”と親＝入力グリッド点ＩＤとを設定する。さらに、直進探索部２２は、直進移動先のグリッド点について、当該グリッド点でのコスト値を算出する（ステップＳ３２）。この後、直進探索部２２は、ステップＳ２６の処理に移行する。
【０１０２】
〔４−３〕例外処理の手順
次に、図６に示すフローチャート（ステップＳ４１〜Ｓ４９）に従って、図４のステップＳ２０において終点に辿り着けない場合に実行される例外処理の手順について説明する。情報処理装置１０は、配線対象ハーネスの始点および終点と、第１チェックキュー３７とを入力されると、認識部２３によって、直進探索を完了した直進探索済み空間、換言するとコスト値を設定されたグリッド点を全て含む空間を認識し作成する（ステップＳ４１）。図９を参照しながら後述する例において、当該直進探索済み空間は直方体空間になる。
【０１０３】
また、経路探索部２４は、当該経路探索部２４による調査候補になるグリッド点を投入される第２チェックキュー３８を初期化（空状態に）するとともに（ステップＳ４２）、始点を第２チェックキュー３８に投入する（ステップＳ４３）。ここで、始点についてのグリッド点情報３６には、コスト値＝∞，親＝「無し」が設定される。
【０１０４】
この後、経路探索部２４は、第２チェックキュー３８が空状態か否かを判断し（ステップＳ４４）、空状態である場合（ステップＳ４４のＹＥＳルート）、第１チェックキュー３７が空状態か否かを判断する（ステップＳ４５）。第１チェックキュー３７が空状態である場合（ステップＳ４５のＹＥＳルート）、情報処理装置１０は、「経路無し」として経路探索処理を終了する。
【０１０５】
一方、第１チェックキュー３７が空状態でない場合（ステップＳ４５のＮＯルート）、後述するごとく直進探索済み空間内から同空間外へ到る経路上の格子点が第１チェックキュー３７に投入された状態である。この場合、情報処理装置１０は、直進探索部２２による図４のステップＳ１５の処理に戻る。
【０１０６】
第２チェックキュー３８が空状態でない場合（ステップＳ４４のＮＯルート）、経路探索部２４は、第２チェックキュー３８からグリッド点を一つ取り出す（ステップＳ４６）。そして、経路探索部２４は、取り出したグリッド点が終点であるか否かを判断する（ステップＳ４７）。
【０１０７】
取り出したグリッド点が終点でない場合（ステップＳ４７のＮＯルート）、経路探索部２４は、取り出したグリッド点の周囲を確認し、取り出したグリッド点から移動可能なグリッド点を第１グリッドキュー３７または第２チェックキュー３８に投入する（ステップＳ４８）。移動可能なグリッド点が存在しなければ、グリッドキュー３７，３８に対するグリッド点の投入は行なわれない。この後、経路探索部２４は、ステップＳ４４の処理へ移行する。なお、ステップＳ４８の確認処理（例外処理）の詳細については、図７を参照しながら後述する。
【０１０８】
取り出したグリッド点が終点である場合（ステップＳ４７のＹＥＳルート）、経路探索部２４は、終点からグリッド点情報３６の親を辿って基本経路をバックトレースすることにより、始点から終点に到る基本経路を取得して出力し（ステップＳ４９）、経路探索処理を「経路あり」として終了する。なお、ステップＳ４９では、必要に応じて、ユーザが、取得した基本経路に対し手動による調整を行なってもよい。
【０１０９】
〔４−４〕移動可能な格子点の確認処理（例外処理）の手順
次に、図７に示すフローチャート（ステップＳ５１〜Ｓ６０）に従って、図６のステップＳ４８において処理対象格子点（調査候補）毎に実行される、移動可能な格子点の確認処理（例外処理）の手順について説明する。
【０１１０】
図６のステップＳ４６で取り出された終点でない一グリッド点（即ち処理対象格子点）が、入力グリッド点として入力されると、まず、経路探索部２４は、当該入力グリッド点から移動する方向として、直交格子の６軸方向（前後左右上下）の中から一軸方向を選択する（ステップＳ５１）。
【０１１１】
経路探索部２４は、入力グリッド点から、ステップＳ５１で選択した方向に隣接するグリッド点に移動可能であるか否かを判断する（ステップＳ５２）。移動不可である場合（ステップＳ５２のＮＯルート）、経路探索部２４は、ステップＳ５７の処理へ移行し、６軸方向の全ての方向を選択したか否かを判断する。まだ全ての方向を選択していない場合（ステップＳ５７のＮＯルート）、経路探索部２４は、ステップＳ５１の処理に戻る。一方、全ての方向を選択している場合（ステップＳ５７のＹＥＳルート）、経路探索部２４は、図６のステップＳ４４の処理に戻る。
【０１１２】
入力グリッド点から、ステップＳ５１で選択した方向に隣接するグリッド点に移動可能である場合（ステップＳ５２のＹＥＳルート）、経路探索部２４は、移動先のグリッド点がステップＳ４１で作成された直進探索済み空間内であるか否かを判断する（ステップＳ５３）。つまり、入力グリッド点から移動可能な隣接格子点が、直進探索済み空間（直方体空間）内に存在するか否かを判断する。
【０１１３】
隣接格子点が直進探索済み空間内に存在する場合（ステップＳ５３のＹＥＳルート）、経路探索部２４は、移動先のグリッド点について、当該グリッド点でのコスト値を算出するとともに、親＝入力グリッド点ＩＤを設定する（ステップＳ５４）。
【０１１４】
この後、移動先のグリッド点について以前に算出したコスト値が保存されている場合、経路探索部２４は、今回算出したコスト値が、保存されているコスト値よりも低いか否かを判断する（ステップＳ５５）。
【０１１５】
今回算出したコスト値が、保存されているコスト値よりも低い場合（ステップＳ５５のＹＥＳルート）、経路探索部２４は、ステップＳ５４で設定又は算出された親，コスト値を、移動先のグリッド点のグリッド点情報３６として保存する。また、経路探索部２４は、移動先のグリッド点（グリッド点ＩＤ）を、経路探索部２４の調査候補として第２チェックキュー３８に投入する（ステップＳ５６）。この後、経路探索部２４は、ステップＳ５７の処理へ移行する。
【０１１６】
なお、移動先のグリッド点について以前に算出したコスト値が保存されていない場合、経路探索部２４は、ステップＳ５５での比較処理を行なうことなく、ステップＳ５６の処理へ移行する。
【０１１７】
今回算出したコスト値が、保存されているコスト値以上の場合（ステップＳ５５のＮＯルート）、経路探索部２４は、ステップＳ５４で設定又は算出された親，コスト値を、保存することなく、ステップＳ５４の処理前の状態に戻す（ステップＳ５８）。この後、経路探索部２４は、ステップＳ５７の処理へ移行する。
【０１１８】
一方、隣接格子点が直進探索済み空間内に存在しない場合（ステップＳ５３のＮＯルート）、つまり隣接格子点が直進探索済み空間外に存在する場合、経路探索部２４は、移動先のグリッド点について、当該グリッド点でのコスト値を算出するとともに、親＝入力グリッド点ＩＤを設定する（ステップＳ５９）。
【０１１９】
そして、経路探索部２４は、ステップＳ５９で設定又は算出された親，コスト値を、移動先のグリッド点のグリッド点情報３６として保存する。また、経路探索部２４は、移動先のグリッド点（グリッド点ＩＤ）を、直進探索部２２の調査候補として第１チェックキュー３７に投入する（ステップＳ６０）。この後、経路探索部２４は、ステップＳ５７の処理へ移行する。
【０１２０】
なお、直進探索済み空間内から同空間外へ到る経路上の格子点、つまり直進探索済み空間外の隣接格子点（第８格子点）を探索することができなかった場合、第１チェックキュー３７も第２チェックキュー３８は空状態となる。したがって、図６のステップＳ４４およびＳ４５において第２チェックキュー３８も第１チェックキュー３７も空状態であると判断され、情報処理装置１０は、「経路無し」として経路探索処理を終了する。このとき、直進探索済み空間内から同空間外へ到る経路が無い旨が、表示部５０等によってユーザに通知されてもよい。
【０１２１】
〔４−５〕第１チェックキューの保存内容
次に、図８（Ａ）〜図８（Ｃ）を参照しながら、本実施形態の第１チェックキュー３７における調査候補（処理対象格子点）の保存内容について具体的に説明する。図８（Ａ）〜図８（Ｃ）に示す例では、二つの障害物の間において４×４の直交格子が配置され、１６個のグリッド点にはそれぞれＡ〜Ｐのグリッド点ＩＤが付与され、三次元空間内の直交格子が二次元で表現されている。
【０１２２】
以下では、図８（Ａ）に示すように、第１チェックキュー３７に調査候補のグリッド点Ｆ，Ｃが保存されている状態で、第１チェックキュー３７から調査候補のグリッド点Ｆを選択した場合について説明する。なお、図８（Ａ）において、調査候補グリッド点Ｆについては、グリッド点情報３６として、親＝グリッド点Ｂ、コスト値＝３、衝突フラグ＝０が設定されている。同様に、調査候補グリッド点Ｃについては、グリッド点情報３６として、親＝グリッド点Ｂ、コスト値＝４、衝突フラグ＝０が設定されている。
【０１２３】
図８（Ａ）に示す状態で第１チェックキュー３７から調査候補のグリッド点Ｆが選択されると（図４のステップＳ１６およびステップＳ１７のＮＯルート参照）、図８（Ｂ）に示すように、当該調査候補グリッド点Ｆの周囲が確認される（図４のステップＳ１８および図５参照）。つまり、グリッド点Ｆの親はグリッド点Ｂであるので、グリッド点Ｆから、上方向（Ｂ方向）以外の三方向（Ｅ，Ｇ，Ｊ方向）への直進探索がそれぞれ実行される。
【０１２４】
このとき、左方向（Ｅ方向）への直進探索を行なうと、隣接点Ｅに到達する前に障害物が検知されるため、左方向への移動は不可であると判断される。
【０１２５】
また、右方向（Ｇ方向）への直進探索を行なうと、グリッド点Ｇを通過した後に障害物が検知されるため、障害物検知直前に通過したグリッド点Ｇが、グリッド点Ｆから移動可能なグリッド点（方向変更点）の一つとして認識される。
【０１２６】
さらに、下方向（Ｊ方向）への直進探索を行なうと、グリッド点Ｎを通過した後に直交格子の境界面が検知されるため、境界面検知直前に通過したグリッド点Ｎが、グリッド点Ｆから移動可能なグリッド点（次の方向変更点）の一つとして認識される。
【０１２７】
このように認識されたグリッド点Ｎ，Ｇは、図８（Ｃ）に示すように、第１チェックキュー３７に調査候補として投入される。このとき、グリッド点Ｎについては、グリッド点情報３６として、親＝グリッド点Ｆ、コスト値＝５、衝突フラグ＝０が設定され、グリッド点Ｇについては、グリッド点情報３６として、親＝グリッド点Ｆ、コスト値＝４、衝突フラグ＝１が設定される。
【０１２８】
なお、グリッド点Ｎ，Ｇについてのグリッド点情報（コスト値等）３６が既に保存されている場合、保存されているコスト値と今回得られたコスト値とが比較される（図５のステップＳ２６参照）。そして、今回得られたコスト値の方が小さい場合のみ、新たなグリッド点情報３６が保存される。
【０１２９】
〔４−６〕終点に辿り着けない状態と当該状態に対応する例外処理とについて
次に、図９を参照しながら、本実施形態の経路探索処理に際して終点に辿り着けない状態と、当該状態が発生した場合に実行される例外処理とについて説明する。
【０１３０】
図９に示す障害物は、開口部（グリッド点Ｐ９の周囲近傍参照）を通じて外部空間につながる内部空間を有する。このような障害物の内部空間に始点が存在し外部空間に終点が存在する状態で、始点から、図４および図５で説明した直進探索を行なう場合について考える。
【０１３１】
この場合、始点から直進探索を行なうと障害物内面が検知され、グリッド点Ａ，Ｂ，Ｃが次の方向変更点として検知され第１チェックキュー３７に投入される。ついで、グリッド点Ａ，Ｂ，Ｃから直進探索を行なうと障害物内面が検知され、グリッド点Ｄ，Ｅが次の方向変更点として検知され第１チェックキュー３７に投入される。この後、グリッド点Ｄ，Ｅから直進探索を行なうと障害物内面が検知される。しかし、この場合、検知される各グリッド点のコスト値（移動距離）が、当該グリッド点について既に保存されているコスト値を超えるため、グリッド点Ｄ，Ｅは第１チェックキュー３７に投入されず、第１チェックキュー３７は空状態になる。つまり、情報処理装置１０（直進探索部２２）は、直進路探索処理では、終点に辿り着けない状態に陥る。
【０１３２】
このように第１チェックキュー３７が空状態になると（図４のステップＳ１５のＮＯルート参照）、図６および図７を参照しながら説明した、認識部２３および経路探索部２４による例外処理が実行される（図４のステップＳ２０参照）。
【０１３３】
例えば、図９に示す障害物では、まず、コスト値を設定されたグリッド点（図９の始点およびＡ〜Ｅ）を全て含む空間が、認識部２３によって、直進探索を完了した直進探索済み空間（直方体空間）として認識され作成される（図６のステップＳ４１参照）。
【０１３４】
この後、経路探索部２４によって、認識部２３が認識した直進探索済み空間内における始点から移動可能な隣接格子点が、第２チェックキュー３８を用いて、一つずつ探索され（図６，図７参照）、探索された隣接格子点が直進探索済み空間内であるか否かが判定される（図７のステップＳ５３参照）。
【０１３５】
そして、直進探索済み空間外であると判定された隣接格子点（図９に示す例ではグリッド点Ｐ９）が、直進探索済み空間内から同空間外へ到る経路上の格子点として設定され、直進探索部２２による調査候補として第１チェックキュー３７に投入される（図７のステップＳ５９，Ｓ６０参照）。これにより、第１チェックキュー３７は空状態でなくなる。
【０１３６】
そして、第２チェックキュー３８が空状態になるとともに第１チェックキュー３７が空状態でなくなった場合、図９に示す例では、直進探索済み空間内から同空間外へ到る経路上のグリッド点Ｐ９が、第１チェックキュー３７に投入されている。これに伴い、直進探索部２２によって、グリッド点Ｐ９から外部空間での直進探索が再開され、図４のステップＳ１５〜Ｓ１９および図５の処理によって、終点に到る基本経路が探索される。
【０１３７】
なお、図９において、始点と終点とが逆である状態、つまり障害物の内部空間に終点が存在し外部空間に始点が存在する状態で、始点から、図４および図５で説明した直進探索を行なう場合について考える。この場合も、グリッド点Ｐ９を検知することができず、情報処理装置１０（直進探索部２２）は、終点に辿り着けない状態に陥る。これに伴い、認識部２３および経路探索部２４による例外処理が実行され、障害物の外部空間が直進探索済み空間内の始点からグリッド点Ｐ９へ到る経路が探索される。そして、直進探索部２２によって、グリッド点Ｐ９から内部空間での直進探索が再開され、終点に到る基本経路が探索される。
【０１３８】
〔５〕本実施形態の効果
以上のように、経路探索機能を有する本実施形態の情報処理装置１０によれば、三次元ＣＡＤにおいて、障害物が存在する空間内で始点から終点までの経路を探索するために空間が直交格子に分割される。そして、障害物または境界面を検知するまで直進して経路を探索する直進探索を行なって障害物近傍の格子点や障害物を回避する格子点を検知しながら、始点から終点までの経路が探索される。
【０１３９】
つまり、障害物や境界面を検知するまで一気に経路探索を行なって検知された一の格子点が方向変更点として設定される。このため、本実施形態では、方向変更点の探索のみを行なえばよく、隣接格子点を一つずつ探索設定しながら経路を探索する手法に比べ、格子点の探索回数が大幅に削減され、始点から終点までの経路探索に要する処理量を大幅に削減することができる。
【０１４０】
また、グリッドと平行でない障害物面（曲面や斜面）を検知した場合には障害物面の法線と垂直な方向へ障害物面から所定距離だけ離れるまで経路探索が行なわれる。このようにして、障害物近傍に存在するが障害物を確実に回避可能な格子点のみを選択設定しながら経路探索を行なうことができる。つまり、障害物面の周囲の点を動的に方向変更点に設定することができる。このため、本実施形態では、グリッド間隔が狭い場合や障害物面がグリッドと平行でない場合においても、始点から終点までの経路探索に要する処理量を削減することができる。
【０１４１】
したがって、本実施形態によれば、始点から終点までの経路を探索する際のインタラクティブ性能、特に、グリッド間隔が狭い場合や障害物面がグリッドと平行でない場合におけるインタラクティブ性能が大幅に向上する。つまり、本実施形態の経路探索技術を用いることで、狭い空間を有するノートＰＣや電子機器における配線経路設定において、処理時間が大幅に削減されインタラクティブ性能が大幅に向上するという顕著な効果を得ることができる。
【０１４２】
一方、本実施形態では、図９に示すごとく直進探索によって探索中の経路が終点に到達しない場合、例外処理によって、直進探索を完了した直進探索済み空間が認識され、当該直進探索済み空間内における始点から移動可能な隣接格子点が一つずつ探索される。そして、探索された隣接格子点が直進探索済み空間内であるか否かを判定することで、直進探索済み空間内から同空間外へ到る経路上の格子点が探索される。このように探索された格子点から直進探索が再開される。
【０１４３】
これにより、情報処理装置１０は、直進探索を採用することで生じる可能性のある、終点に辿り付けない状態から抜け出すことができる。したがって、直進探索を採用しても、始点から終点までの経路探索を確実に行なうことができる。
【０１４４】
また、本実施形態では、直進探索を採用することで、一度の直進探索で移動する距離が直進探索毎に変化する。このため、移動距離が短いと、探索された基本経路に沿ってハーネスを曲げてハーネスの配線方向を変更することができない場合がある。そこで、本実施形態では、一度の直進探索で移動する距離がハーネスの最小曲率半径以上であるか否かが判断される。
【０１４５】
移動距離が最小曲率半径未満である場合には、基本経路に沿ってハーネスを配線することができない可能性が高いと判断され、移動距離が最小曲率半径未満になった直進探索は採用されない。一方、移動距離が最小曲率半径以上である場合、ハーネスを曲げながら配線するのに十分な距離が確保されており、基本経路に沿ってハーネスを配線することができると判断される。このようにして、本実施形態によれば、ハーネスを確実に配線可能な基本経路が探索される。
【０１４６】
〔６〕その他
以上、本発明の好ましい実施形態について詳述したが、本発明は、係る特定の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変形、変更して実施することができる。
【０１４７】
例えば、上述した実施形態では、三次元空間内の直交格子を二次元で表現した例についてのみ図示して説明したが、直交格子を三次元で表現した場合にも本発明の経路探索技術は上述した実施形態と同様に適用され、上述した実施形態と同様の作用効果を得ることができる。
【０１４８】
〔７〕付記
以上の各実施形態を含む実施形態に関し、さらに以下の付記を開示する。
【０１４９】
（付記１）
障害物が存在する三次元空間内で始点から終点までの経路を探索するコンピュータに、
前記三次元空間を直交格子に分割し、
前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行ない、
前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる、経路探索プログラム。
【０１５０】
（付記２）
前記直進探索を行なった結果、前記終点として設定された前記直交格子の第４格子点を通過する軸と交わる位置の第５格子点を検知した場合、検知した第５格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる、付記１に記載の経路探索プログラム。
【０１５１】
（付記３）
前記次の方向変更点から、前記障害物を検知した位置における障害物面の法線と直交する方向へ、前記障害物面と前記経路との最短距離が所定距離以上になるまで、前記直進探索を行ない、
前記障害物面と前記経路との最短距離が前記所定距離以上になった位置の近傍において前記障害物面との最短距離が前記所定距離以上の位置に存在する前記直交格子の第６格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる、付記１または付記２に記載の経路探索プログラム。
【０１５２】
（付記４）
前記直進探索を行なっても前記障害物面と前記経路との最短距離が前記所定距離以上にならない場合、前記直進探索によって前記経路が到達した位置の近傍における前記直交格子の第７格子点を、前記経路の次の方向変更点として設定する、
処理を実行させる、付記３に記載の経路探索プログラム。
【０１５３】
（付記５）
前記始点または前記方向変更点からの前記直進探索一回当たりの最小直進距離を、前記経路に沿って配設されるハーネスの最小曲率半径に応じて設定する、
処理を実行させる、付記１〜付記４のいずれか一項に記載の経路探索プログラム。
【０１５４】
（付記６）
前記直進探索を行なっても前記経路が前記終点に到達しない場合、前記直進探索を完了した直進探索済み空間を認識し、
認識した直進探索済み空間内における前記始点から移動可能な隣接格子点を一つずつ探索し、探索した隣接格子点が前記直進探索済み空間内であるか否かを判定することで、前記直進探索済み空間外であると判定された前記隣接格子点を、前記直進探索済み空間内から前記直進探索済み空間外へ到る前記経路上の第８格子点として設定し、
設定した第８格子点から前記直進探索を再開する、
処理を実行させる、付記１〜付記５のいずれか一項に記載の経路探索プログラム。
【０１５５】
（付記７）
障害物が存在する三次元空間内で始点から終点までの経路を探索する処理部と、
前記障害物に関する情報を記憶する記憶部と、を有し、
前記処理部は、
前記三次元空間を直交格子に分割し、
前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行ない、
前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する、情報処理装置。
【０１５６】
（付記８）
前記処理部は、
前記直進探索を行なった結果、前記終点として設定された前記直交格子の第４格子点を通過する軸と交わる位置の第５格子点を検知した場合、検知した第５格子点を、前記経路の次の方向変更点として設定する、付記７に記載の情報処理装置。
【０１５７】
（付記９）
前記処理部は、
前記次の方向変更点から、前記障害物を検知した位置における障害物面の法線と直交する方向へ、前記障害物面と前記経路との最短距離が所定距離以上になるまで、前記直進探索を行ない、
前記障害物面と前記経路との最短距離が前記所定距離以上になった位置の近傍において前記障害物面との最短距離が前記所定距離以上の位置に存在する前記直交格子の第６格子点を、前記経路の次の方向変更点として設定する、付記７または付記８に記載の情報処理装置。
【０１５８】
（付記１０）
前記処理部は、
前記直進探索を行なっても前記障害物面と前記経路との最短距離が前記所定距離以上にならない場合、前記直進探索によって前記経路が到達した位置の近傍における前記直交格子の第７格子点を、前記経路の次の方向変更点として設定する、付記９に記載の情報処理装置。
【０１５９】
（付記１１）
前記処理部は、
前記始点または前記方向変更点からの前記直進探索一回当たりの最小直進距離を、前記経路に沿って配設されるハーネスの最小曲率半径に応じて設定する、付記７〜付記１０のいずれか一項に記載の情報処理装置。
【０１６０】
（付記１２）
前記処理部は、
前記直進探索を行なっても前記経路が前記終点に到達しない場合、前記直進探索を完了した直進探索済み空間を認識し、
認識した直進探索済み空間内における前記始点から移動可能な隣接格子点を一つずつ探索し、探索した隣接格子点が前記直進探索済み空間内であるか否かを判定することで、前記直進探索済み空間外であると判定された前記隣接格子点を、前記直進探索済み空間内から前記直進探索済み空間外へ到る前記経路上の第８格子点として設定し、
設定した第８格子点から前記直進探索を再開する、付記７〜付記１１のいずれか一項に記載の情報処理装置。
【０１６１】
（付記１３）
コンピュータにより、障害物が存在する三次元空間内で始点から終点までの経路を探索する経路探索方法であって、
前記三次元空間を直交格子に分割し、
前記始点として設定された前記直交格子の第１格子点、または前記経路が進行方向を変える方向変更点として探索され設定された前記直交格子の第２格子点から、一方向へ、前記障害物を検知するまで直進して前記経路を探索する直進探索を行ない、
前記障害物を検知する直前に通過した前記直交格子の第３格子点を、前記経路の次の方向変更点として設定する、経路探索方法。
【０１６２】
（付記１４）
前記直進探索を行なった結果、前記終点として設定された前記直交格子の第４格子点を通過する軸と交わる位置の第５格子点を検知した場合、検知した第５格子点を、前記経路の次の方向変更点として設定する、付記１３に記載の経路探索方法。
【０１６３】
（付記１５）
前記次の方向変更点から、前記障害物を検知した位置における障害物面の法線と直交する方向へ、前記障害物面と前記経路との最短距離が所定距離以上になるまで、前記直進探索を行ない、
前記障害物面と前記経路との最短距離が前記所定距離以上になった位置の近傍において前記障害物面との最短距離が前記所定距離以上の位置に存在する前記直交格子の第６格子点を、前記経路の次の方向変更点として設定する、付記１３または付記１４に記載の経路探索方法。
【０１６４】
（付記１６）
前記直進探索を行なっても前記障害物面と前記経路との最短距離が前記所定距離以上にならない場合、前記直進探索によって前記経路が到達した位置の近傍における前記直交格子の第７格子点を、前記経路の次の方向変更点として設定する、付記１５に記載の経路探索方法。
【０１６５】
（付記１７）
前記始点または前記方向変更点からの前記直進探索一回当たりの最小直進距離を、前記経路に沿って配設されるハーネスの最小曲率半径に応じて設定する、付記１３〜付記１６のいずれか一項に記載の経路探索方法。
【０１６６】
（付記１８）
前記直進探索を行なっても前記経路が前記終点に到達しない場合、前記直進探索を完了した直進探索済み空間を認識し、
認識した直進探索済み空間内における前記始点から移動可能な隣接格子点を一つずつ探索し、探索した隣接格子点が前記直進探索済み空間内であるか否かを判定することで、前記直進探索済み空間外であると判定された前記隣接格子点を、前記直進探索済み空間内から前記直進探索済み空間外へ到る前記経路上の第８格子点として設定し、
設定した第８格子点から前記直進探索を再開する、付記１３〜付記１７のいずれか一項に記載の経路探索方法。
【符号の説明】
【０１６７】
１０    コンピュータ（経路探索機能を有する情報処理装置）
１１    プロセッサ（処理部）
１２    ＲＡＭ（記憶部）
１３    ＨＤＤ（記憶部）
１４    グラフィック処理装置
１４ａ    モニタ（表示部）
１５    入力インタフェース
１５ａ    キーボード（入力部）
１５ｂ    マウス（入力部）
１６    光学ドライブ装置
１６ａ    光ディスク
１７    機器接続インタフェース
１７ａ    メモリ装置
１７ｂ    メモリリーダライタ
１７ｃ    メモリカード
１８    ネットワークインタフェース
１８ａ    ネットワーク
１９    バス
２０    処理部
２１    直交格子配置部（分割部）
２２    直進探索部
２３    直進探索済み空間認識部（認識部）
２４    直進探索済み空間内経路探索部（経路探索部）
３０    記憶部
３１    経路探索プログラム
３２    部品モデル（三次元モデル）
３３    ハーネスモデル（三次元モデル）
３４    ハーネス情報
３５    直交格子情報（境界面情報）
３６    グリッド点情報
３７    第１チェックキュー
３８    第２チェックキュー
４０    入力部
５０    表示部
【図１】
2016212627.tif 000003
【図２】
2016212627.tif 000004
【図３】
2016212627.tif 000005
【図４】
2016212627.tif 000006
【図５】
2016212627.tif 000007
【図６】
2016212627.tif 000008
【図７】
2016212627.tif 000009
【図８】
2016212627.tif 000010
【図９】
2016212627.tif 000011
【図１０】
2016212627.tif 000012
【図１１】
2016212627.tif 000013
【図１２】
2016212627.tif 000014
【図１３】
2016212627.tif 000015
【図１４】
2016212627.tif 000016
【図１５】
2016212627.tif 000017