高速且つ正確な経路プランニングのための方法及びシステム
システム（２００）は、あらゆる種類の経路プランニングアプリケーションについて最適な経路を生成する方法（１３０〜１８０）を実行する。動作において、システム（２００）は、１又はそれ以上のパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造を構成し、配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により及び／又は離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値により、配置空間ノード構造を増補する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、障害物回避を有して最適な経路をプランニングする方法及びシステムに関する。
【背景技術】
【０００２】
経路プランニングアプリケーションの例には、（１）患者の体内における器具の外科的経路のプランニング、（２）特定の環境内におけるロボット、車両、飛行機、船舶等の動作／移動経路のプランニング、（３）経済システム、緊急システム等の様々な条件付きの及び無条件の状態を通るフロー経路のプランニング、及び（４）陸上及び／又は水上の特定の部分を通る道、高速道路、水路等のルート経路のプランニングがあるが、これらに限られない。
【０００３】
このような経路プランニングアプリケーションは、Ｋａｒｅｎ Ｉ． Ｔｒｏｖａｔｏ著、Ａ＊Ｐｌａｎｎｉｎｇ ｉｎ Ｄｉｓｃｒｅｔｅ Ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓｐａｃｅｓ ｏｆ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ、アムステルダム大、１９９６年（非特許文献１）によって教示されているフレームワークを用いて実行されてよい。
【０００４】
具体的に、経路プランニングアプリケーションは、離散パラメータに関して記載可能でなければならならい。すなわち、経路プランニングアプリケーションは、１又はそれ以上の範囲の有効な離散パラメータ値を夫々が有するキーパラメータによって特徴付けられる。全てのとり得るパラメータ範囲の組合せは配置空間と呼ばれ、配置空間の夫々の状態はこれらのパラメータの夫々について一意の設定を与える。
【０００５】
ある範囲内で配置空間における１つ状態から他の状態への変化又は遷移を引き起こす許容動作は、「近傍（neighborhood）」として包含される。言い換えると、近傍は、配置空間の一部又は全体内の核となる状態遷移を表す許容される後続の集合である。配置空間は離散化された空間であるから、配置空間の夫々の状態は、２次元又は３次元グラフにおける「ノード（nodes）」として考えられてよく、２又はそれ以上の状態の間の変化を引き起こしうる配置空間におけるあらゆるイベント又は動きはノード間の「遷移（transitions）」と見なされてもよい。
【０００６】
「近傍」は、また、「ゲームのルール（rules of the game）」に基づいて決定されてよく、従って、タスク空間自体の特定の属性又はタスク空間内の対象物／状態フローによって選択される少数の近傍が存在してよい。遷移は、例えば一方通行の道等の環境に基づいてよい。夫々の遷移には、元の状態とそれに隣接する状態との間の変化のために課されるコストが割り当てられる。従って、配置空間における状態間の隣接遷移と配置空間における状態との組合せは、ノードとしての状態と、方向付けられたエッジとしての遷移とを有するグラフとして考えられてよい。
【０００７】
多くの経路プランニングアプリケーションに関して、しばしば機械的な制限、障害物との相互作用、又は課されたルールのために、違法状態を定義する制約が存在する。従って、配置空間におけるノードの識別可能な禁止領域が存在してよい。幾つかのグラフにおいて、これらのノードへの遷移は、そのノード自体とともに取り除かれる。代替的に、ノードは、違法であるとして印を付されてよく、あるいは、そのようなノードへの遷移は、無限の（達成不可能な高い）コストを有して、∞によって表されてよい。このような技術は夫々、制約ノードを回避する探索をもたらす。
【０００８】
経路プランニングによれば、「目標（goal）」位置は、離散化された配置空間における１又はそれ以上の等価な「目標」ノードにマッピングされてよい。システムを表すパラメータの式がそのシステムの「目標」を記述する１よりも多い解を有してよいことから、多くの「目標」ノードが存在してよい。例えば、腕の左利き設定及び右利き設定はいずれも同じ場所に達することができる。システムの「開始（start）」は単純に特定の開始ノードに変換される。
【０００９】
現在のシステムノードから所望の「目標」へ通ずる最も望ましい一連のイベントを見つけることは、全ての違法ノードを回避しながらコストが最小である、現在のノードから「目標」ノードへの遷移の最適な経路を見つけることと似ている。経路プラニングの目的は、しばしば、空間変形行列、コスト行列、又はオブジェクト関数（例えば、最速、最短、最安）と時々よばれる成功の判断基準を有する。多くの場合に、これは、直接に、ノード間の特定の遷移のために課されるコストに変形されてよい。従って、望ましい一連のイベントは、配置空間ノード、遷移、コスト、禁止領域及び「目標」を用いて経路をプランニングすることによって、更に、「開始ノード」を定義又は設定することによって、見つけることができる。Ａ＊に記載されるグラフ探索方法は、最適な経路を決定するための有効なメカニズムを提供する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Ｋａｒｅｎ Ｉ． Ｔｒｏｖａｔｏ著、Ａ＊Ｐｌａｎｎｉｎｇ ｉｎ Ｄｉｓｃｒｅｔｅ Ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓｐａｃｅｓ ｏｆ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ、アムステルダム大、１９９６年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値の使用を容易にすることによって、障害物回避を有して最適な経路をプランニングすることにおいて、非特許文献１で教示されるような主題フレームワークの利用を拡張する。
【課題を解決するための手段】
【００１２】
本発明の１つの形態は、経路プランニングアプリケーションに従って経路のプランニングを行う方法である。当該方法は、１又はそれ以上のパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造をデータ記憶媒体内に構成する段階を有する。当該方法は、更に、前記データ記憶媒体内に構成された前記配置空間ノード構造を、該配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により増補する段階を有する。
【００１３】
本発明の第２の形態は、データ記憶媒体（すなわち、データを記憶するためのあらゆる媒体）及びデータ処理デバイス（すなわち、記憶されているデータを必要とする動作を実行して情報を得るためのあらゆるデバイス）を有し、経路プランニングアプリケーションに従って経路のプランニングを行うシステムである。動作において、前記データ処理デバイスは、少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造を前記データ記憶媒体内に構成する。前記データ処理デバイスは、更に、前記配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により、前記データ記憶媒体内の前記配置空間ノード構造の構成を増補する。
【００１４】
本発明の上記の形態及び他の形態並びに本発明の様々な特徴及び利点は、添付の図面に関連して読まれる本発明の様々な実施形態に係る以下の詳細な記載から、更に明らかになるであろう。詳細な記載及び図面は、限定ではなく本発明の単なる例示にすぎない。本発明の適用範囲は、添付の特許請求の範囲及びその均等によって定義される。
【図面の簡単な説明】
【００１５】
【図１】本発明に従う離散パラメータ値モード及びヒューリスティック値モードのブロック図を表す。
【図２】本発明の離散パラメータ値モードを表示する離散化された配置空間の例を表す。
【図３】本発明のヒューリスティック値モードを表示する離散化された配置空間の例を表す。
【図４】本発明に従う離散パラメータ値取得方法を表すフローチャートである。
【図５】当該技術で知られている非ホロノミックな近傍の例を表す。
【図６】本発明に従う近傍スレッドのサンプリングの例を表す。
【図７】本発明に従う離散パラメータ値管理方法を表すフローチャートである。
【図８】本発明に従う基線構成方法を表すフローチャートである。
【図９】本発明に従う、明示的な離散状態パラメータを用いてシードノードから目標への最適な経路の決定のためのＡ＊アルゴリズムを表すフローチャートである。
【図１０】自由空間ノードの疎表現を有する離散化された配置空間の例を表す。
【図１１】本発明に従う疎な自由空間構成方法を表すフローチャートである。
【図１２】障害ノードの疎表現を有する離散化された配置空間の例を表す。
【図１３】本発明に従う疎な障害物構成方法を表すフローチャートである。
【図１４】本発明に従うヒューリスティック値生成及び回復方法のフローチャートである。
【図１５】本発明に従う完全接続された近傍の例を表す。
【図１６】本発明に従う、気管支樹における全ての自由空間点についての計算されたヒューリスティックの例を表す。
【図１７】本発明に従うヒューリスティック及び当該技術で知られているサンプル・ユークリッド・ヒューリスティックの夫々でプランニングされた経路の例を表す。
【図１８】本発明に従うシステムのブロック図を表す。
【発明を実施するための形態】
【００１６】
本発明は、３つの主な発明原理を前提としている。
【００１７】
第１に、経路プランニングアプリケーションのための離散化された配置空間は、当該技術でよく知られている離散化された配置空間のインデックスから推測される離散パラメータに依存するのではなく、配置空間ノード構造内の各ノードに配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値を持たせることによって、より正確に行うことができる。これは、経路の高分解能の計算が、粗く離散化された配置空間においてさえ、正確に計算可能であることを暗示する。これは、更に、分解能がより低い配置空間が、メモリをセーブし、又は従前不可能であった経路プランニングアプリケーションを時間及びメモリにおいて扱いやすくするために使用されてよいことを暗示する。
【００１８】
第２に、配置空間記憶は、障害物表現と計算された状態及び方向との間で分離され、要求に応じて割り当てられてよく、それにより、拡大されたノードのみが、例えば、全てのＮ個の次元におけるトラバース状態の浮動小数点（floating point）精度等の状態の全詳細を有する。拡大は通常、配置空間全体よりもずっと小さい範囲にわたるので、この節約率は公称の配置空間の約２０％であってよい。そのようなものとして、６４ビットマシンを必要とする多くの経路プランニングアプリケーションは現在、３２ビットマシンを使用することができる。
【００１９】
第３に、Ａ＊アルゴリズムによれば、ヒューリスティック値は、離散化された配置空間の自由空間（非障害）エリアを通る探索を導くために使用されてよい。経路プランニングアプリケーションに関し、最も速い非ホロノミックなＡ＊アルゴリズムの実行は、ヒューリスティック値が、最初に、障害物の周辺の距離を計算に入れた自由空間を通る目標からの正確な距離を推定する場合に、達成され得る。
【００２０】
当業者には当然ながら、図１乃至１８に係る以下の記載は、具体的な今のところ率直な例を用いて一般論として本発明の上記の発明原理を説明するために与えられるのであり、このような発明原理の実施を制限するために与えられるのではない。特に、従来の機能及び動作に係る不必要な詳細は、本発明を不明りょうにしないように本願における発明原理の記載からは省略されることがある。とはいえ、あらゆるタイプの経路プランニングアプリケーション（すなわち、手術道具経路プランニング、車両経路プランニング、経済システム経路プランニング、等）に対して本発明の発明原理をどのように実施すべきか、更に、本発明の主旨及び添付の特許請求の範囲の適用範囲の中にある変形例が多数存在することは、当業者に明らかである。
【００２１】
図１は、（１）患者の体内における器具の外科的経路のプランニング、（２）特定の環境内におけるロボット、車両、飛行機、船舶等の動作／移動経路のプランニング、（３）経済システム、緊急システム等の様々な条件付きの及び無条件の状態を通るフロー経路のプランニング、及び（４）陸上及び／又は水上の特定の部分を通る道、高速道路、水路等のルート経路のプランニングを含むが、これらに限られないあらゆるタイプの経路プランニングアプリケーションのためのセットアップ相１００及び経路プランニング相１０１を表す。
【００２２】
一般論として、セットアップ相１００は、最低限、（１）１又はそれ以上のパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造の構成、（２）離散化された配置空間における状態間の変化又は遷移を引き起こす許容動作の全てを包含する近傍の識別、及び（３）離散化された配置空間を通る経路のプランニングにおける成功の判断基準を表す行列式、を有してよい。更に、一般論として、経路プランニング相１０１は、最低限、（１）離散化された配置空間内のシードノードの識別又は定義、及び（２）開始ノードと目標ノードとの間で最も望ましい一連のイベントを見つけるよう行列に基づいて配置空間ノード構造を通るコスト波の伝播を開始するためのシードノードの使用、を有してよい。
【００２３】
本発明は、経路プランニングアプリケーションのセットアップ相１００及び／又は経路プランニング相１０１に組み込まれる離散パラメータ値モード１０３を導入する。一般論として、配置空間ノード構造は複数のノードを有し、各ノードは、パラメータによって特徴付けられる離散化された配置空間において異なる離散的位置、フロー点等にある。離散パラメータ値モード１０３は、当該技術でよく知られている離散化された配置空間のインデックスから推測される離散パラメータとは対照的に、配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値の使用を提供する。本発明のために、語「明示的に定量化する」は、特定の配置空間ノード構造におけるノードに関連する数値、指標、数量、又は他の何らかの利用可能なパラメータの的確な表現として本願では幅広く定義される。
【００２４】
例えば、図２は、ｘ及びｙの位置パラメータによって特徴付けられる状態の１０×１０の２次元配置を有する離散化された配置空間１１０内の経路１１１を表す。当該技術で知られるように、ｉ、ｊインデックスから推測される離散パラメータ値への依存は、直接隣り合っているものの間の妨げられない遷移による１単位コストと、対角で隣り合っているものの間の妨げられない遷移による１．４単位コストとをもたらす。しかし、ライン１１２によって例示されるような、離散化された配置空間１１０のｉ、ｊインデックスから推測される離散パラメータ値への依存に代えて、離散パラメータ値モード１０３は、本願で更に説明されるような、配置空間ノード構造に係る経路１１１のｘ及びｙ位置パラメータを明示的に定量化する離散パラメータ値を用いる。この結果は、配置空間ノード構造内のあらゆるタイプのノード遷移からの正確なコスト計算である。
【００２５】
本発明は、更に、経路プランニングアプリケーションのセットアップ相１００及び／又は経路プランニング相１０１に組み込まれるヒューリスティック値モード１０４を導入する。一般論として、ヒューリスティック値モード１０４は、離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値の使用を提供する。特に、ヒューリスティック値は、障害物の周辺の距離を計算に入れた自由空間領域を通る目標からの正確な距離を推定して、配置空間ノード構造のために好ましい許容ヒューリスティック値を得る。例えば、図３は、非ホロノミックな経路を導くために使用される場合にそのような経路には障害物が存在するために好ましくないシードノードＳと目標ノードＧとの間の直線ユークリッド距離に基づく例となる許容ヒューリスティック１１３を表す。比較すると、許容ヒューリスティック１１４は、障害物の周辺の距離を計算に入れるので、非ホロノミックな経路プランニングのための好ましい許容ヒューリスティックである。
【００２６】
図４乃至１８に示される離散パラメータ値モード１０３及びヒューリスティック値モード１０４の様々な実施例は、本発明の発明原理の更なる理解を助けるために記載され、それによって、離散パラメータ値モード１０３によって達成される配置空間ノード構造の固有の離散化誤差（discretization error）の改善や、ヒューリスティック値モード１０４によって達成される最適な経路の探索中の時間効率の改善を含むが、それらに限られない本発明の様々な利点が、当業者に明らかになるであろう。
【００２７】
Ａ．離散パラメータモード（データ取得）
図４は、本発明の離散パラメータ値取得方法を表すフローチャート１２０である。この方法の目的は、経路プランニングアプリケーションの経路プランニング相１０１（図１）の間の最適な探索を容易にするよう、経路プランニングアプリケーションのセットアップ相１００（図１）の間に、離散化された配置空間の状態に係る実効離散パラメータ値の実際上の組を取得することである。
【００２８】
フローチャート１２０の段階Ｓ１２１は、離散化された配置空間において状態間の変化又は遷移を引き起こす許容動作の全てを包含する近傍のサンプリングを有する。例えば、図５は、気管支鏡又はアクティブ若しくは入れ子式カニューレ（cannula）のためのスレッドの例となる非ホロノミックな近傍１２３を表す。段階Ｓ１２１は、近傍１２３の連続するスレッドを各ノードのｘ、ｙ、ｚ位置パラメータを明示的に定量化する離散パラメータ値の数列に変換するためのサンプリング処理（例えば、各ノードごとに離散的なｘ、ｙ、ｚ値を与える‘ｘ’、‘ｙ’又は‘ｚ’の最小単位指定に基づくスレッドのナイキスト−シャノン・サンプリング等）を用いてよい。図６は、ｘ単位指定に基づくスレッド１２４の例となるサンプリングを表す。
【００２９】
フローチャート１２０の段階Ｓ１２２は、段階Ｓ１２１の間に取得される明示的な離散パラメータ値の関数としての選択された行列の定式化を有する。例えば、図１に示される離散化された配置空間を用いると、行列は局所的にユークリッド行列であってよく、これにより、夫々の状態（ｉ，ｊ）で、方向矢印バー（ｄｉ，ｄｊ）によって状態（ｉ，ｊ）から除かれる近隣の状態への遷移のコストは、√（ｄｘ２＋ｄｙ２）によって与えられる。ここで、ｄｘ及びｄｙは、状態（ｉ，ｊ）に対応するノードについてのｘ，ｙ位置に関する明示的な離散パラメータ値である。
【００３０】
図１乃至４を参照して、フローチャート１２０は、特定の経路プランニングアプリケーションのために必要に応じてセットアップ相１００及び／又は経路プランニング相１０１の間に実施されてよい。
【００３１】
Ｂ．離散パラメータ値モード（データ管理）
図７は、本発明の離散パラメータ値管理方法を表すフローチャート１３０である。この方法の目的は、方法を実行するシステムの速度及びメモリ能力に如何なる悪影響も与えることなく、配置空間ノード構造を離散パラメータ値により増補（augmentation）することである。フローチャート１３０の段階Ｓ１３１は、あらゆるタイプのデータ記憶媒体内における配置空間ノード構造の構成を有し、それによって、構成された配置空間ノード構造は、フローチャート１３０の段階Ｓ１３２の間に、ノードを明示的に定量化する離散パラメータ値により増補されてよい。実際に、段階Ｓ１３１のために選択される配置空間ノード構造のための構成スキームは、多くの因子、特に、所与の経路プランニングアプリケーションで必要とされる精度や、所望の精度を達成するために明示的な離散パラメータ値を必要とする自由空間ノードの実際の数及び相対数等の配置空間要件に依存する。フローチャート１３０の理解を容易にするよう、３つの例となる構成スキームについて以下に記載する。
【００３２】
［１．基線構成］
「基線構成（baseline construction）」として本願でのみ知られる第１の構成スキームは、例えば、図２に示される離散化された配置空間１１０のような、おおよそ等しい数の障害ノード及び自由空間ノードの公平な分布を有する離散化された配置空間に適する。これは、障害ノードに対して自由空間ノードの数を決定するよう障害物マップを読むことで、又は経路プランニングアプリケーションの固有の性質によって、決定されてよい。
【００３３】
例えば、図８は、本発明の基線構成方法を表すフローチャート１４０である。フローチャート１４０の段階Ｓ１４０は、自由空間ノードの全てを保持するようインデックス付きテーブルの生成を有し、フローチャート１４０の段階Ｓ１４２は、対応する離散パラメータ値を指し示す各自由空間ノードごとの詳細ポインタと、自由空間ノードについての他の何らかの関連する詳細情報とを有する配置空間ノード構造の構成を有する。下記は、詳細ポインタによる配置空間ノード構造の基線構成の一例である。
【００３４】
【数１】
この基線構成の例において、１つの配置空間情報（ＣＳＮＯＤＥ）は、最も近い目標に到達するための残りのコストを示すcost_to_goalと、最も近い目標へ向かう途中で到達される次のノードを指し示すvectorと、ソート中に使用されるheap_locationと、詳細配置空間情報（ＣＳＤＥＴＡＩＬＮＯＤＥ）を指し示すdetailポインタとを有する。比較すると、詳細な位置空間情報（ＣＳＤＥＴＡＩＬＮＯＤＥ）は、ヒューリスティック・フロート値ｈ１と、３次元におけるノード座標alpha、theta、phi（すなわち、α、θ、φ）と、離散化された配置空間内のノードの実際のｘ、ｙ、ｚ位置を示す明示的な離散パラメータ値（ＸＹＺＭＭ）Xmm、Ymm、Zmmと、核となる配置空間情報（ＣＳＮＯＤＥ）に戻るポインタmyCSNODEとを有する。
【００３５】
例えば、気管支鏡の操縦又はアクティブカニューレの設定等の、肺の配置空間のための経路プランニングアプリケーションの例で、上述されるような５１２×５１２×６００の配置空間ノード構造が使用される。この例で、プログラムはオプションの比較を発生させることができる。それは、夫々の場所における全ての変数を有するフル装備の配置空間に必要とされるメモリと、上述されるような核となる配置空間情報及び詳細な配置空間情報に分けられるフル装備の配置空間に必要とされるメモリとを計算する。下記は、プログラムの出力例である：
#CSnodes：157,286,400
元のＣＳノードの夫々のサイズ：80バイト
総計：12,582,912,000バイト
現在：
新しいＣＳノードの夫々のサイズ：24バイト
総ＣＳバイト：3,774,873,600バイト
自由空間要素の数：毎725,083バイト
詳細用：64
詳細総バイト：46,402,432バイト
総計：3,821,276,032バイト
より良くＣＳを詳細に分けるためのセービング：8,761,635,968バイト
結果として、公称の（元の）配置空間は、１２ギガバイトから４ギガバイト未満にサイズが低減され得る。配置空間ノード構造全体がページングによらずにメモリに適合することができる場合にアルゴリズムは動的により速く実行されるので、この高分解能プログラムは難なく現在の６４ビットマシンで実行可能である。プログラム自体はソートに必要とされるヒープスペース及びメモリを必要とすることに留意すべきである。
【００３６】
図７及び８を参照して、フローチャート１３０（図７）の段階Ｓ１３２は、フローチャート１４０（図８）に従って構成される配置空間ノード構造の全体又は一部を選択された行列に従ってコスト値（cost value）により満たすよう、配置空間ノード構造におけるコスト波伝播（cost wave propagation）を実施することができる。この場合に、コスト値は、明示的な離散状態パラメータの関数であり、これによって、配置空間ノード構造は、シード自由空間ノード又は改善された自由空間ノードの詳細な配置空間情報が本願で更に説明されるようにコスト波伝播の間にのみ割り当てられる場合に、明示的な離散状態パラメータにより増補される。
【００３７】
例えば、図９は、図２に示される近傍１２３に基づいて本発明に従って明示的な離散パラメータ値を用いてシードノードから目標への最適な経路を決定するためのＡ＊アルゴリズムを表すフローチャート１５０である。具体的に、シードノードは、コスト波伝播、すなわちＡ＊を開始するために、ヒープに置かれる。ヒープは、ルートにおいて最小コスト値を保つ均衡の取れた二分木である。フローチャート１５０の段階Ｓ１５１で、最小コストノードがヒープから取り出される。ヒープから取り出されたノードは「ホーム」と呼ばれる。ヒープが正確なままであることを確かにするよう従来のアルゴリズムが用いられるとする。
【００３８】
段階Ｓ１５１で、更に、シードの詳細（detail）ポインタが、ホームノードにＣＳＤＥＴＡＩＬＮＯＤＥを割り当てて、ホームノードの詳細な配置空間情報、特に、ホームノードの明示的な離散パラメータ値（ＸＹＺＭＭ）を得るために使用される。これは、フローチャート１５０を実行するシステムの速度及びメモリ能力に如何なる悪影響も与えることなくコスト波伝播に望まれる前進運動（precession）を与える。
【００３９】
フローチャート１５０の段階Ｓ１５２で、収束判定条件（stopping criterion）の試験が行われる。処理が終了するかどうかを決定するために実行される多くの試験が存在する。収束判定条件は、（１）ヒープが空であるかどうかの試験、及び（２）現在の（ホーム）ノードのcost_to_goal値が（目的の）開始又は目標よりも大きいかどうかの試験を含んでよいが、これらに限られない。これは、空間全体が満たされる前に探索が終了することを可能にするが、それでもなお、それは、開始と目標との間の最適な経路を与える。
【００４０】
収束判定条件が満足される場合、フローチャート１５０は終了する。そうではなく、収束判定条件が満足されない場合、フローチャート１５０の段階Ｓ１５３は、許容される遷移の近傍の発生を有する。ホームノードの隣接ノードは、そのホームのｘ、ｙ、ｚ位置に加えてα、θ及びφによって与えられるホームノード座標に基づいて計算される。近傍は、α、θ及びφによって公称の近傍を回転させて、既に回転された近傍をホームノードのｘ、ｙ、ｚ位置に対して移動させることから得られる。点の回転及び移動のための方法は当該技術において知られている。
【００４１】
画素が段階Ｓ１５４の間完全には正方形でない場合（例えば、ＣＴ画像において、ｘ：ｙ：ｚの比が１：１：１．３である場合）、回転が行われ、値が増減される。次いで、結果として得られた近傍は、現在の拡大ノードの位置に移動される。
【００４２】
現在のホームノード隣接ノードが計算されると、フローチャート１５０は段階Ｓ１５４に進み、必要に応じて、近傍の次のスレッド（Ｆ）が選択される。もはやスレッドがない場合には、フローチャート１５０は段階Ｓ１５１に戻る。そうではなく、スレッド（Ｆ）がある場合、フローチャート１５０は、必要に応じてスレッド（Ｆ）に沿って次の隣接ノード（ｎ）を選択するために段階Ｓ１５５に進む。
【００４３】
このスレッド（Ｆ）沿いにもはや隣接ノードがない場合には、フローチャート１５０は段階Ｓ１５１に戻る。隣接ノード（ｎ）が他にある場合には、フローチャート１５０は、その隣接ノードのコスト値を試験するために段階Ｓ１５６に進む。それが無限である場合、又は当該隣接ノードが通行可能でないとの他の表示がある場合、フローチャートは段階Ｓ１５１に戻る。他の表示は、その隣接ノードが無限大よりも小さい何らかの所定の閾値よりも高いコスト値を有するが、高すぎて通れないことを示す。この閾値は、例えば、（ホームノードで）移動される現在の距離の関数であってよい。
【００４４】
隣接ノードが無限なコストを有さない場合、フローチャート１５０は、その新しい隣接ノードについて提案される新しいコストＦ（ｎ’）を計算するために段階Ｓ１５７に進む。隣接ノードは予めコストを有することがあるので、それはＦ（ｎ’）で表される。Ａ＊アルゴリズムにおいて、ヒューリスティックｈ（ｎ）は探索を導くために使用されてよい。なお、完全に有効な値はｈ＝０であり、収束判定条件が満たされる／真であるまで、空間に全てのシードノードから埋めさせる。望ましくは、ヒューリスティック値は、本願で後述されるように図１４に従う。
【００４５】
その後、フローチャート１５０は、計算されたコスト値Ｆ（ｎ’）をｎでの既存のコストＦ（ｎ）と比較するために段階Ｓ１５８に進む。計算されたＦ（ｎ’）が既存のコストＦ（ｎ）よりも大きい場合、ホームノードを介してｎに到達することは、以前に決定されたあらゆるものよりもコストがかかる（すなわち、改善はない。）。フローチャート１５０は段階Ｓ１５３に戻る。計算されたコストＦ（ｎ’）が既存のコストＦ（ｎ）よりも小さい場合、この値は従前の方向に対する改善であり、これによって、フローチャート１５０は、当該隣接ノードをヒープに加えるために段階Ｓ１５９に進む。あるいは、既に隣接ノードがヒープにある場合には、かかるノードの値は更新され、ヒープは調整される。改善する隣接ノードがヒープに加えられる場合に、ＣＳＤＥＴＡＩＬＮＯＤＥはその隣接ノードに割り当てられて、隣接ノードの詳細な配置空間情報、特に、隣接ノードの明示的な離散パラメータ（ＸＹＺＭＭ）を得る。先と同じく、これは、フローチャート１５０を実行するシステムの速度及びメモリ能力に如何なる悪影響も与えることなくコスト波伝播に望まれる前進運動を与える。
【００４６】
段階Ｓ１５９で、更に、新しいcost_to_goalが、新しいα、θ及びφであるように、ｎに、割り当てられる。α、θ及びφの値は、現在のスレッドから計算されるαの値により親ノードのθ及びφに対して公称ノードのθ及びφを回転させることによって計算される。シードノードへの最良の道のりを導く修正ベクトルは、ポインタをホームに割り当てられる。任意に、しかし望ましくは、スレッドの数が記憶される。これは、スレッドの数が制御パラメータ（すなわち、例えば、気管支鏡が上下及び左右に回転される量、又は入れ子式カニューレの形状及び相対位置、又は車の操舵及び前進／後進）に直接にマッピングするので、後に、すなわち続く経路の間、計算を最小限とする。
【００４７】
収束判定条件が満足されると、結果として得られるプランニングされた経路は、当該技術に従来達成されていたよりも正確且つ高速に得られる。
【００４８】
［２．疎な自由空間構成］
「疎な自由空間構成（sparse free space construction）」として本願でのみ知られる第２の構成スキームは、自由空間ノードよりも多い相当程度の障害ノードを有する配置空間（例えば、図１０に示されるような離散化された配置空間１１５）に適している。これは、障害ノードに対して自由空間ノードの数を決定するための障害物マップの読み出しから、又は経路プランニングアプリケーション（例えば、駐車プランニング又は肺ナビゲーションプランニング等）の固有特性によって、決定されてよい。所与の経路プランニングアプリケーションに必要とされる精度に係る配置空間要件を満たす疎な自由空間構成のために、全てのデータセットが、各自由空間ノードごとに詳細セクションに実際に記憶されてよく、一方、障害ノードは同じＮＵＬＬ位置を指し示してよい。
【００４９】
例えば、図１１は、本発明の疎な自由空間の構成方法を表すフローチャート１６０である。フローチャート１６０の段階Ｓ１６１はＮＵＬＬ位置の生成を有し、各障害ノードはＮＵＬＬ位置を指し示す。あるいは、代替的に、ＮＵＬＬを示すデフォルトの障害ノードが生成されてよい。フローチャート１６０の段階Ｓ１６２は、全ての詳細な配置空間情報、特に、明示的な離散パラメータ値を各自由空間ノードに含めることを有する。下記は、配置空間ノード構造のための事前に割り振られた詳細な自由空間ノードの疎な自由空間構成の一例である。
【００５０】
【数２】
この疎な自由空間構成は、３次元の配置空間の疎性質と、あらゆる禁止（障害）状態が通行不可能であるという事実を除いて方向、cost_to_goal又は何らかの情報を記憶する必要がないという事実とを使用する。同様に、全てのデータセットは、配置空間における詳細インデックス（detailIndex）のみを残して、実際に詳細セクションに記憶されてよい。
【００５１】
最初に、これは、インデックスが過剰であり且つデータの全ての組が詳細に記憶されるので、必要とされるメモリを増大させるにすぎないと考えられるかもしれない。しかし、障害物であるノードは、詳細のオーバーヘッドをセーブするために、同じ位置（例えば、ＮＵＬＬ）を指し示してよい。多くの障害物が存在する場合に、これは多くの空間をセーブすることができる。このような技術を用いることで、ギガバイトのメモリは約半分しか必要とされない。
【００５２】
例えば、５１２×５１２×６００＝１５７，２８６，４００個の配置状態が存在し、各配置状態は１つのインデックスしか有さない。４２０万個よりも少ない自由空間状態に関し、４バイト整数又はポインタは、トータルで６２９，１４５，６００バイトを必要とするインデックスを与えることができる。６５５３６個よりも少ない状態が存在する場合、２バイト整数で明らかに十分である。このアプリケーションに関し、７２５，０３８個の自由空間ノードが存在し、各ノードは８０バイトを必要とする。全部で、この必要メモリは６８７，１４８，６４０バイトであり、アプリケーションを３２ビットマシンにおいて極めて扱いやすくする。
【００５３】
しかし、このようなメモリの節約は、変数が詳細へと動かされるアクセス時間を増大させる。第１の優先事項は、このアプリケーションでのページングが異常に遅くされうることから、配置空間が局所（高速）メモリ（ＲＡＭ）内に適合することを確かにすることである。
【００５４】
図７及び１１を参照して、フローチャート１３０（図７）の段階Ｓ１３２は、フローチャート１６０（図１１）に従って構成される配置空間ノード構造の全体又は一部を選択された行列に従うコスト値により満たすよう配置空間ノード構造においてコスト波伝播を実施してよい。この場合に、コスト値は明示的な離散状態パラメータの関数であり、これによって、配置空間ノード構造は、コスト波伝播より前に明示的な離散状態パラメータにより増補される。例えば、全ての詳細な自由空間ノードは、図９に示されているフローチャート１５０に従ってシードノードから目標への最適な経路の決定のために、Ａ＊アルゴリズムの実行より前に、予め割り振られる。
【００５５】
［３．疎な障害物構成］
「疎な障害物構成（sparse obstacle construction）」として本願でのみ知られる第３の構成スキームは、障害ノードよりも多い相当程度の自由空間ノードを有する配置空間（例えば、図１２に示されるような離散化された配置空間１１６）に適している。これは、障害ノードに対して自由空間ノードの数を決定するための障害物マップの読み出しから、又は経路プランニングアプリケーション（例えば、開放型屋内競技場、領空、又は腹腔鏡手術等）の固有特性によって、決定されてよい。所与の経路プランニングアプリケーションに必要とされる精度に係る配置空間要件を満たす疎な障害物構成のために、全てのデータセットが、各自由空間ノードごとに、要求に応じて割り振られた詳細セクションに実際に記憶されてよく、一方、障害ノードは同じＮＵＬＬ位置を指し示してよい。
【００５６】
例えば、図１３は、本発明の疎な障害物の構成方法を表すフローチャート１７０である。フローチャート１７０の段階Ｓ１７１は、自由空間ノードのためのコストがかからない（Uncosted）空間変数と、障害ノードのための無限の（Infinity）空間変数との生成を有し、フローチャート１７０の段階Ｓ１７２は、全ての詳細な配置空間情報、特に、明示的な離散パラメータ値を有する各自由空間ノードが要求に応じて割り振られることを有する。下記は、配置空間ノード構造のための詳細な自由空間ノードの疎な障害物構成の一例である。
【００５７】
【数３】
疎な障害表現との関連で、空間が、各次元ごとに２つの隣り合った隣接ノードを含むとともに対角を含む３次元近傍である場合に、近傍の全径（overall diameter）は３と推定されてよい。ユークリッド行列及び無障害物によれば、拡大経路は、連続する空間においてπ×D×長さの体積である。しかし、連続空間でない場合、それは離散化される。より適切には、長さにわたって８個の隣接ノードが存在する。配置空間が上記のようなもの、すなわち、５１２×５１２×６００＝１５７，２８６，４００個の配置状態を有するものであるならば、４バイト整数は基本配置空間についてトータルで６２９，１４５，６００バイトを必要とする。１つの角から対角に相対する角への経路に関し、１：１：１の長さ比（立方体）を有するとすれば、経路の中心は約９４０＝√（５１２２＋５１２２＋６００２）である。起こり得る最悪の場合は、選択される経路がほとんど対角である場合である。各インクリメントにおいて８個の隣接ノードが存在する場合に、全体の必要メモリは、約７５２０個の詳細状態のためでしかない。これは、全ての問題が、６２９バイトの基本配置空間にたった６２０Ｋを足したもので解消され得ることを意味する。配置空間の先の使用と比べて、同じ空間は１２．５ギガバイトを必要としうる。
【００５８】
図７及び１３を参照して、フローチャート１３０（図７）の段階Ｓ１３２は、フローチャート１７０（図１３）に従って構成される配置空間ノード構造の全体又は一部を選択された行列に従うコスト値により満たすよう配置空間ノード構造においてコスト波伝播を実施してよい。この場合に、コスト値は明示的な離散状態パラメータの関数であり、これによって、配置空間ノード構造は、シード自由空間ノード又は改善された自由空間ノードの全データセットが、例えば、図９に示され且つ本願で上述されるようなフローチャート１５０のＳ１５１及びＳ１５９の夫々の段階に従って、コスト波伝播の間に必要に応じて割り振られる場合に、明示的な離散状態パラメータにより増補される。
【００５９】
Ｃ．ヒューリスティック値モード
再び図１を参照して、実際的な許容ヒューリスティックは、障害物を有する空間におけるＡ＊探索のガイダンスのために、ヒューリスティック値モード１０４によって与えられる。具体的に、ヒューリスティック値モード１０４は、セットアップ相１００の間に自由空間の全てのノードについてヒューリスティック値を予め計算して記憶し、それらの値を経路プランニング相１０１の間に、特に非ホロノミックな６Ｄプランニングのために、使用する。示されるように、ヒューリスティック値モード１０４は時間を節約し、複数の経路が効率的にプランニングされることを可能にする。
【００６０】
図１４は、本発明に従うヒューリスティック値生成及び回復方法を表すフローチャート１８０である。概して、ヒューリスティックは、図３に示される直接ユークリッド距離とは対照的に、障害物の周辺の距離において計算する自由空間を通る目標からの距離を表す。更に、ヒューリスティックは、自由空間及び障害物の配置空間から一度だけ予め計算されても、又は必要に応じて再計算されてもよく、これによって、ヒューリスティックは、異なる経路をプランニングするために同じ配置空間についてその後に繰り返し使用されてよい。
【００６１】
具体的に、フローチャート１８０の段階Ｓ１８２は、アルゴリズムが配置空間において全ての自由空間点を訪れること、従って、自由空間の全ての状態においてヒューリスティックを計算することを可能にする完全接続された近傍の配置を有する。近傍の中心にあるノードは、自由空間領域において完全接続された近傍を容易にする最良のノードである。図１５は、近傍の中心にあるノードに接続された２６個のノードから成るヒューリスティック計算のための完全接続された近傍１９０の一例を表す。
【００６２】
フローチャート１８０の段階Ｓ１８３は、段階Ｓ１８２の完全接続された近傍に基づくヒューリスティックの生成を有する。例えば、本願で上述されるフローチャート１５０（図９）の実施は、適切なヒューリスティックが完全接続された近傍に基づいて生成されることを確かにするよう二通りに変形されてよい。第１の変形はアルゴリズム初期化の変更であり、これによって、１又は複数のシードはＡ＊アルゴリズムの開始のために定義されなければならない。これは、単一の状態、又は状態の組（例えば、気管における面全体）であってよい。第２の変形は収束判定条件の変更であり、これによって、アルゴリズムは、自由空間における全てのノードが訪ねられる場合（例えば、気管の面に沿った全ての自由空間ノードが到達される場合）に終了される。
【００６３】
フローチャート１８０の段階Ｓ１８６は、セットアップの間、段階Ｓ１８３の結果（例えば、図１６に示される気管支樹における全ての自由点についての例となる計算されたヒューリスティック等の、自由空間の全ての状態における計算されたヒューリスティック値を有する配置空間）をセーブする。この情報は、３次元画像でメモリに又はハードドライブ（ＨＤ）でセーブされてよい。例えば、データは、未加工フォーマットで又は分析画像フォーマットであってよい。これらは、浮動小数点が、例えば、ＤＩＣＯＭに共通するたった１２ビット整数よりもむしろ、それらのフォーマットで記憶されてよいことから、好ましい。全ての画像要素（配置状態）における、すなわち、自由空間の全ての位置における情報は、経路プランニングの間、段階Ｓ１８５で取り出される。ヒューリスティックの事前計算は、単一のヒューリスティック計算により複数の経路プランニング（同じシードからの異なった目標点）を可能にする。
【００６４】
フローチャート１８０の段階Ｓ１８４は、配置空間における探索を導くためのヒューリスティックの使用を有する。ヒューリスティックが零（ｈ（ｎ）＝０）である場合に、ガイダンスは提供されず、アルゴリズムは自由空間における全ての点を訪れる。障害物を回避するヒューリスティックによれば、純粋なユークリッド指標よりも良い近似が、非ホロノミックな近傍を導くために使用されてよい。入れ子式カニューレ配置において、これはまた、目標に到達するのに必要とされる管の数に影響する。例えば、図１７は、フローチャート１８０に従って生成されたヒューリスティックによる入れ子式カニューレ配置における経路プランニングの例１９２と、当該技術で知られる純粋なユークリッド指標において生成されたヒューリスティックによる入れ子式カニューレ配置における経路プランニングの例１９３とを示す。左側に示されているように本発明のヒューリスティックを使用することは、ユークリッド・ヒューリスティック１９３に比べて、計算時間を５０％以上も減少させ且つ管の数を４０％以上も減少させる。更に、ヒューリスティックは、０．５秒未満の正味の時間節約で計算可能であることが証明されている。
【００６５】
Ｄ．経路プランニングシステム
ここで図１８を参照して、本発明に従う経路プランニングアプリケーションのためのシステム２００が表されている。システム２００は、データ処理デバイス２１０及びデータ記憶媒体２２０を有する。データ処理デバイス２１０は、図１乃至１７に関連して本願で上述された本発明の様々な発明原理を実施するためにセットアップユニット２１１及びプランニングユニット２１２を用いる。一般論として、セットアップユニット２１１は、データ記憶媒体２２０内の特定の経路プランニングアプリケーションに適した配置空間ノード構造（ＣＳＮＳ）を構成するのに必要な全てのタスクを実行し、プランニングユニット２１２は、特定の経路プランニングアプリケーションに望まれるように本発明に従って明示的な離散パラメータ値及び／又はヒューリスティック値の関数としてのコスト値により配置空間ノード構造を満たすのに必要とされるコスト波を伝播する。その結果、特定の経路プランニングアプリケーションに適し多フォーマットで最適な経路２４０が得られる。
【００６６】
本発明の様々な実施形態が図示及び記載をされてきたが、本願で記載される方法及びシステムは例示であり、様々な変更及び修正が行われてよく、等価なものが本発明の技術的範囲を外れることなくそれらの要素に代用されて良いことが当業者に理解される。更に、多くの変形例が、本発明の技術的範囲を外れることなく本発明の教示をエンティティ経路プランニングに適合させるために行われてよい。従って、本発明は、本発明を実施するために考えられている最良モードとして開示される具体的な実施例に限られず、本発明は添付の特許請求の範囲の適用範囲内にある全ての実施形態を包含する。
【技術分野】
【０００１】
本発明は、障害物回避を有して最適な経路をプランニングする方法及びシステムに関する。
【背景技術】
【０００２】
経路プランニングアプリケーションの例には、（１）患者の体内における器具の外科的経路のプランニング、（２）特定の環境内におけるロボット、車両、飛行機、船舶等の動作／移動経路のプランニング、（３）経済システム、緊急システム等の様々な条件付きの及び無条件の状態を通るフロー経路のプランニング、及び（４）陸上及び／又は水上の特定の部分を通る道、高速道路、水路等のルート経路のプランニングがあるが、これらに限られない。
【０００３】
このような経路プランニングアプリケーションは、Ｋａｒｅｎ Ｉ． Ｔｒｏｖａｔｏ著、Ａ＊Ｐｌａｎｎｉｎｇ ｉｎ Ｄｉｓｃｒｅｔｅ Ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓｐａｃｅｓ ｏｆ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ、アムステルダム大、１９９６年（非特許文献１）によって教示されているフレームワークを用いて実行されてよい。
【０００４】
具体的に、経路プランニングアプリケーションは、離散パラメータに関して記載可能でなければならならい。すなわち、経路プランニングアプリケーションは、１又はそれ以上の範囲の有効な離散パラメータ値を夫々が有するキーパラメータによって特徴付けられる。全てのとり得るパラメータ範囲の組合せは配置空間と呼ばれ、配置空間の夫々の状態はこれらのパラメータの夫々について一意の設定を与える。
【０００５】
ある範囲内で配置空間における１つ状態から他の状態への変化又は遷移を引き起こす許容動作は、「近傍（neighborhood）」として包含される。言い換えると、近傍は、配置空間の一部又は全体内の核となる状態遷移を表す許容される後続の集合である。配置空間は離散化された空間であるから、配置空間の夫々の状態は、２次元又は３次元グラフにおける「ノード（nodes）」として考えられてよく、２又はそれ以上の状態の間の変化を引き起こしうる配置空間におけるあらゆるイベント又は動きはノード間の「遷移（transitions）」と見なされてもよい。
【０００６】
「近傍」は、また、「ゲームのルール（rules of the game）」に基づいて決定されてよく、従って、タスク空間自体の特定の属性又はタスク空間内の対象物／状態フローによって選択される少数の近傍が存在してよい。遷移は、例えば一方通行の道等の環境に基づいてよい。夫々の遷移には、元の状態とそれに隣接する状態との間の変化のために課されるコストが割り当てられる。従って、配置空間における状態間の隣接遷移と配置空間における状態との組合せは、ノードとしての状態と、方向付けられたエッジとしての遷移とを有するグラフとして考えられてよい。
【０００７】
多くの経路プランニングアプリケーションに関して、しばしば機械的な制限、障害物との相互作用、又は課されたルールのために、違法状態を定義する制約が存在する。従って、配置空間におけるノードの識別可能な禁止領域が存在してよい。幾つかのグラフにおいて、これらのノードへの遷移は、そのノード自体とともに取り除かれる。代替的に、ノードは、違法であるとして印を付されてよく、あるいは、そのようなノードへの遷移は、無限の（達成不可能な高い）コストを有して、∞によって表されてよい。このような技術は夫々、制約ノードを回避する探索をもたらす。
【０００８】
経路プランニングによれば、「目標（goal）」位置は、離散化された配置空間における１又はそれ以上の等価な「目標」ノードにマッピングされてよい。システムを表すパラメータの式がそのシステムの「目標」を記述する１よりも多い解を有してよいことから、多くの「目標」ノードが存在してよい。例えば、腕の左利き設定及び右利き設定はいずれも同じ場所に達することができる。システムの「開始（start）」は単純に特定の開始ノードに変換される。
【０００９】
現在のシステムノードから所望の「目標」へ通ずる最も望ましい一連のイベントを見つけることは、全ての違法ノードを回避しながらコストが最小である、現在のノードから「目標」ノードへの遷移の最適な経路を見つけることと似ている。経路プラニングの目的は、しばしば、空間変形行列、コスト行列、又はオブジェクト関数（例えば、最速、最短、最安）と時々よばれる成功の判断基準を有する。多くの場合に、これは、直接に、ノード間の特定の遷移のために課されるコストに変形されてよい。従って、望ましい一連のイベントは、配置空間ノード、遷移、コスト、禁止領域及び「目標」を用いて経路をプランニングすることによって、更に、「開始ノード」を定義又は設定することによって、見つけることができる。Ａ＊に記載されるグラフ探索方法は、最適な経路を決定するための有効なメカニズムを提供する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Ｋａｒｅｎ Ｉ． Ｔｒｏｖａｔｏ著、Ａ＊Ｐｌａｎｎｉｎｇ ｉｎ Ｄｉｓｃｒｅｔｅ Ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓｐａｃｅｓ ｏｆ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ、アムステルダム大、１９９６年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値の使用を容易にすることによって、障害物回避を有して最適な経路をプランニングすることにおいて、非特許文献１で教示されるような主題フレームワークの利用を拡張する。
【課題を解決するための手段】
【００１２】
本発明の１つの形態は、経路プランニングアプリケーションに従って経路のプランニングを行う方法である。当該方法は、１又はそれ以上のパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造をデータ記憶媒体内に構成する段階を有する。当該方法は、更に、前記データ記憶媒体内に構成された前記配置空間ノード構造を、該配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により増補する段階を有する。
【００１３】
本発明の第２の形態は、データ記憶媒体（すなわち、データを記憶するためのあらゆる媒体）及びデータ処理デバイス（すなわち、記憶されているデータを必要とする動作を実行して情報を得るためのあらゆるデバイス）を有し、経路プランニングアプリケーションに従って経路のプランニングを行うシステムである。動作において、前記データ処理デバイスは、少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造を前記データ記憶媒体内に構成する。前記データ処理デバイスは、更に、前記配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により、前記データ記憶媒体内の前記配置空間ノード構造の構成を増補する。
【００１４】
本発明の上記の形態及び他の形態並びに本発明の様々な特徴及び利点は、添付の図面に関連して読まれる本発明の様々な実施形態に係る以下の詳細な記載から、更に明らかになるであろう。詳細な記載及び図面は、限定ではなく本発明の単なる例示にすぎない。本発明の適用範囲は、添付の特許請求の範囲及びその均等によって定義される。
【図面の簡単な説明】
【００１５】
【図１】本発明に従う離散パラメータ値モード及びヒューリスティック値モードのブロック図を表す。
【図２】本発明の離散パラメータ値モードを表示する離散化された配置空間の例を表す。
【図３】本発明のヒューリスティック値モードを表示する離散化された配置空間の例を表す。
【図４】本発明に従う離散パラメータ値取得方法を表すフローチャートである。
【図５】当該技術で知られている非ホロノミックな近傍の例を表す。
【図６】本発明に従う近傍スレッドのサンプリングの例を表す。
【図７】本発明に従う離散パラメータ値管理方法を表すフローチャートである。
【図８】本発明に従う基線構成方法を表すフローチャートである。
【図９】本発明に従う、明示的な離散状態パラメータを用いてシードノードから目標への最適な経路の決定のためのＡ＊アルゴリズムを表すフローチャートである。
【図１０】自由空間ノードの疎表現を有する離散化された配置空間の例を表す。
【図１１】本発明に従う疎な自由空間構成方法を表すフローチャートである。
【図１２】障害ノードの疎表現を有する離散化された配置空間の例を表す。
【図１３】本発明に従う疎な障害物構成方法を表すフローチャートである。
【図１４】本発明に従うヒューリスティック値生成及び回復方法のフローチャートである。
【図１５】本発明に従う完全接続された近傍の例を表す。
【図１６】本発明に従う、気管支樹における全ての自由空間点についての計算されたヒューリスティックの例を表す。
【図１７】本発明に従うヒューリスティック及び当該技術で知られているサンプル・ユークリッド・ヒューリスティックの夫々でプランニングされた経路の例を表す。
【図１８】本発明に従うシステムのブロック図を表す。
【発明を実施するための形態】
【００１６】
本発明は、３つの主な発明原理を前提としている。
【００１７】
第１に、経路プランニングアプリケーションのための離散化された配置空間は、当該技術でよく知られている離散化された配置空間のインデックスから推測される離散パラメータに依存するのではなく、配置空間ノード構造内の各ノードに配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値を持たせることによって、より正確に行うことができる。これは、経路の高分解能の計算が、粗く離散化された配置空間においてさえ、正確に計算可能であることを暗示する。これは、更に、分解能がより低い配置空間が、メモリをセーブし、又は従前不可能であった経路プランニングアプリケーションを時間及びメモリにおいて扱いやすくするために使用されてよいことを暗示する。
【００１８】
第２に、配置空間記憶は、障害物表現と計算された状態及び方向との間で分離され、要求に応じて割り当てられてよく、それにより、拡大されたノードのみが、例えば、全てのＮ個の次元におけるトラバース状態の浮動小数点（floating point）精度等の状態の全詳細を有する。拡大は通常、配置空間全体よりもずっと小さい範囲にわたるので、この節約率は公称の配置空間の約２０％であってよい。そのようなものとして、６４ビットマシンを必要とする多くの経路プランニングアプリケーションは現在、３２ビットマシンを使用することができる。
【００１９】
第３に、Ａ＊アルゴリズムによれば、ヒューリスティック値は、離散化された配置空間の自由空間（非障害）エリアを通る探索を導くために使用されてよい。経路プランニングアプリケーションに関し、最も速い非ホロノミックなＡ＊アルゴリズムの実行は、ヒューリスティック値が、最初に、障害物の周辺の距離を計算に入れた自由空間を通る目標からの正確な距離を推定する場合に、達成され得る。
【００２０】
当業者には当然ながら、図１乃至１８に係る以下の記載は、具体的な今のところ率直な例を用いて一般論として本発明の上記の発明原理を説明するために与えられるのであり、このような発明原理の実施を制限するために与えられるのではない。特に、従来の機能及び動作に係る不必要な詳細は、本発明を不明りょうにしないように本願における発明原理の記載からは省略されることがある。とはいえ、あらゆるタイプの経路プランニングアプリケーション（すなわち、手術道具経路プランニング、車両経路プランニング、経済システム経路プランニング、等）に対して本発明の発明原理をどのように実施すべきか、更に、本発明の主旨及び添付の特許請求の範囲の適用範囲の中にある変形例が多数存在することは、当業者に明らかである。
【００２１】
図１は、（１）患者の体内における器具の外科的経路のプランニング、（２）特定の環境内におけるロボット、車両、飛行機、船舶等の動作／移動経路のプランニング、（３）経済システム、緊急システム等の様々な条件付きの及び無条件の状態を通るフロー経路のプランニング、及び（４）陸上及び／又は水上の特定の部分を通る道、高速道路、水路等のルート経路のプランニングを含むが、これらに限られないあらゆるタイプの経路プランニングアプリケーションのためのセットアップ相１００及び経路プランニング相１０１を表す。
【００２２】
一般論として、セットアップ相１００は、最低限、（１）１又はそれ以上のパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造の構成、（２）離散化された配置空間における状態間の変化又は遷移を引き起こす許容動作の全てを包含する近傍の識別、及び（３）離散化された配置空間を通る経路のプランニングにおける成功の判断基準を表す行列式、を有してよい。更に、一般論として、経路プランニング相１０１は、最低限、（１）離散化された配置空間内のシードノードの識別又は定義、及び（２）開始ノードと目標ノードとの間で最も望ましい一連のイベントを見つけるよう行列に基づいて配置空間ノード構造を通るコスト波の伝播を開始するためのシードノードの使用、を有してよい。
【００２３】
本発明は、経路プランニングアプリケーションのセットアップ相１００及び／又は経路プランニング相１０１に組み込まれる離散パラメータ値モード１０３を導入する。一般論として、配置空間ノード構造は複数のノードを有し、各ノードは、パラメータによって特徴付けられる離散化された配置空間において異なる離散的位置、フロー点等にある。離散パラメータ値モード１０３は、当該技術でよく知られている離散化された配置空間のインデックスから推測される離散パラメータとは対照的に、配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値の使用を提供する。本発明のために、語「明示的に定量化する」は、特定の配置空間ノード構造におけるノードに関連する数値、指標、数量、又は他の何らかの利用可能なパラメータの的確な表現として本願では幅広く定義される。
【００２４】
例えば、図２は、ｘ及びｙの位置パラメータによって特徴付けられる状態の１０×１０の２次元配置を有する離散化された配置空間１１０内の経路１１１を表す。当該技術で知られるように、ｉ、ｊインデックスから推測される離散パラメータ値への依存は、直接隣り合っているものの間の妨げられない遷移による１単位コストと、対角で隣り合っているものの間の妨げられない遷移による１．４単位コストとをもたらす。しかし、ライン１１２によって例示されるような、離散化された配置空間１１０のｉ、ｊインデックスから推測される離散パラメータ値への依存に代えて、離散パラメータ値モード１０３は、本願で更に説明されるような、配置空間ノード構造に係る経路１１１のｘ及びｙ位置パラメータを明示的に定量化する離散パラメータ値を用いる。この結果は、配置空間ノード構造内のあらゆるタイプのノード遷移からの正確なコスト計算である。
【００２５】
本発明は、更に、経路プランニングアプリケーションのセットアップ相１００及び／又は経路プランニング相１０１に組み込まれるヒューリスティック値モード１０４を導入する。一般論として、ヒューリスティック値モード１０４は、離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値の使用を提供する。特に、ヒューリスティック値は、障害物の周辺の距離を計算に入れた自由空間領域を通る目標からの正確な距離を推定して、配置空間ノード構造のために好ましい許容ヒューリスティック値を得る。例えば、図３は、非ホロノミックな経路を導くために使用される場合にそのような経路には障害物が存在するために好ましくないシードノードＳと目標ノードＧとの間の直線ユークリッド距離に基づく例となる許容ヒューリスティック１１３を表す。比較すると、許容ヒューリスティック１１４は、障害物の周辺の距離を計算に入れるので、非ホロノミックな経路プランニングのための好ましい許容ヒューリスティックである。
【００２６】
図４乃至１８に示される離散パラメータ値モード１０３及びヒューリスティック値モード１０４の様々な実施例は、本発明の発明原理の更なる理解を助けるために記載され、それによって、離散パラメータ値モード１０３によって達成される配置空間ノード構造の固有の離散化誤差（discretization error）の改善や、ヒューリスティック値モード１０４によって達成される最適な経路の探索中の時間効率の改善を含むが、それらに限られない本発明の様々な利点が、当業者に明らかになるであろう。
【００２７】
Ａ．離散パラメータモード（データ取得）
図４は、本発明の離散パラメータ値取得方法を表すフローチャート１２０である。この方法の目的は、経路プランニングアプリケーションの経路プランニング相１０１（図１）の間の最適な探索を容易にするよう、経路プランニングアプリケーションのセットアップ相１００（図１）の間に、離散化された配置空間の状態に係る実効離散パラメータ値の実際上の組を取得することである。
【００２８】
フローチャート１２０の段階Ｓ１２１は、離散化された配置空間において状態間の変化又は遷移を引き起こす許容動作の全てを包含する近傍のサンプリングを有する。例えば、図５は、気管支鏡又はアクティブ若しくは入れ子式カニューレ（cannula）のためのスレッドの例となる非ホロノミックな近傍１２３を表す。段階Ｓ１２１は、近傍１２３の連続するスレッドを各ノードのｘ、ｙ、ｚ位置パラメータを明示的に定量化する離散パラメータ値の数列に変換するためのサンプリング処理（例えば、各ノードごとに離散的なｘ、ｙ、ｚ値を与える‘ｘ’、‘ｙ’又は‘ｚ’の最小単位指定に基づくスレッドのナイキスト−シャノン・サンプリング等）を用いてよい。図６は、ｘ単位指定に基づくスレッド１２４の例となるサンプリングを表す。
【００２９】
フローチャート１２０の段階Ｓ１２２は、段階Ｓ１２１の間に取得される明示的な離散パラメータ値の関数としての選択された行列の定式化を有する。例えば、図１に示される離散化された配置空間を用いると、行列は局所的にユークリッド行列であってよく、これにより、夫々の状態（ｉ，ｊ）で、方向矢印バー（ｄｉ，ｄｊ）によって状態（ｉ，ｊ）から除かれる近隣の状態への遷移のコストは、√（ｄｘ２＋ｄｙ２）によって与えられる。ここで、ｄｘ及びｄｙは、状態（ｉ，ｊ）に対応するノードについてのｘ，ｙ位置に関する明示的な離散パラメータ値である。
【００３０】
図１乃至４を参照して、フローチャート１２０は、特定の経路プランニングアプリケーションのために必要に応じてセットアップ相１００及び／又は経路プランニング相１０１の間に実施されてよい。
【００３１】
Ｂ．離散パラメータ値モード（データ管理）
図７は、本発明の離散パラメータ値管理方法を表すフローチャート１３０である。この方法の目的は、方法を実行するシステムの速度及びメモリ能力に如何なる悪影響も与えることなく、配置空間ノード構造を離散パラメータ値により増補（augmentation）することである。フローチャート１３０の段階Ｓ１３１は、あらゆるタイプのデータ記憶媒体内における配置空間ノード構造の構成を有し、それによって、構成された配置空間ノード構造は、フローチャート１３０の段階Ｓ１３２の間に、ノードを明示的に定量化する離散パラメータ値により増補されてよい。実際に、段階Ｓ１３１のために選択される配置空間ノード構造のための構成スキームは、多くの因子、特に、所与の経路プランニングアプリケーションで必要とされる精度や、所望の精度を達成するために明示的な離散パラメータ値を必要とする自由空間ノードの実際の数及び相対数等の配置空間要件に依存する。フローチャート１３０の理解を容易にするよう、３つの例となる構成スキームについて以下に記載する。
【００３２】
［１．基線構成］
「基線構成（baseline construction）」として本願でのみ知られる第１の構成スキームは、例えば、図２に示される離散化された配置空間１１０のような、おおよそ等しい数の障害ノード及び自由空間ノードの公平な分布を有する離散化された配置空間に適する。これは、障害ノードに対して自由空間ノードの数を決定するよう障害物マップを読むことで、又は経路プランニングアプリケーションの固有の性質によって、決定されてよい。
【００３３】
例えば、図８は、本発明の基線構成方法を表すフローチャート１４０である。フローチャート１４０の段階Ｓ１４０は、自由空間ノードの全てを保持するようインデックス付きテーブルの生成を有し、フローチャート１４０の段階Ｓ１４２は、対応する離散パラメータ値を指し示す各自由空間ノードごとの詳細ポインタと、自由空間ノードについての他の何らかの関連する詳細情報とを有する配置空間ノード構造の構成を有する。下記は、詳細ポインタによる配置空間ノード構造の基線構成の一例である。
【００３４】
【数１】
この基線構成の例において、１つの配置空間情報（ＣＳＮＯＤＥ）は、最も近い目標に到達するための残りのコストを示すcost_to_goalと、最も近い目標へ向かう途中で到達される次のノードを指し示すvectorと、ソート中に使用されるheap_locationと、詳細配置空間情報（ＣＳＤＥＴＡＩＬＮＯＤＥ）を指し示すdetailポインタとを有する。比較すると、詳細な位置空間情報（ＣＳＤＥＴＡＩＬＮＯＤＥ）は、ヒューリスティック・フロート値ｈ１と、３次元におけるノード座標alpha、theta、phi（すなわち、α、θ、φ）と、離散化された配置空間内のノードの実際のｘ、ｙ、ｚ位置を示す明示的な離散パラメータ値（ＸＹＺＭＭ）Xmm、Ymm、Zmmと、核となる配置空間情報（ＣＳＮＯＤＥ）に戻るポインタmyCSNODEとを有する。
【００３５】
例えば、気管支鏡の操縦又はアクティブカニューレの設定等の、肺の配置空間のための経路プランニングアプリケーションの例で、上述されるような５１２×５１２×６００の配置空間ノード構造が使用される。この例で、プログラムはオプションの比較を発生させることができる。それは、夫々の場所における全ての変数を有するフル装備の配置空間に必要とされるメモリと、上述されるような核となる配置空間情報及び詳細な配置空間情報に分けられるフル装備の配置空間に必要とされるメモリとを計算する。下記は、プログラムの出力例である：
#CSnodes：157,286,400
元のＣＳノードの夫々のサイズ：80バイト
総計：12,582,912,000バイト
現在：
新しいＣＳノードの夫々のサイズ：24バイト
総ＣＳバイト：3,774,873,600バイト
自由空間要素の数：毎725,083バイト
詳細用：64
詳細総バイト：46,402,432バイト
総計：3,821,276,032バイト
より良くＣＳを詳細に分けるためのセービング：8,761,635,968バイト
結果として、公称の（元の）配置空間は、１２ギガバイトから４ギガバイト未満にサイズが低減され得る。配置空間ノード構造全体がページングによらずにメモリに適合することができる場合にアルゴリズムは動的により速く実行されるので、この高分解能プログラムは難なく現在の６４ビットマシンで実行可能である。プログラム自体はソートに必要とされるヒープスペース及びメモリを必要とすることに留意すべきである。
【００３６】
図７及び８を参照して、フローチャート１３０（図７）の段階Ｓ１３２は、フローチャート１４０（図８）に従って構成される配置空間ノード構造の全体又は一部を選択された行列に従ってコスト値（cost value）により満たすよう、配置空間ノード構造におけるコスト波伝播（cost wave propagation）を実施することができる。この場合に、コスト値は、明示的な離散状態パラメータの関数であり、これによって、配置空間ノード構造は、シード自由空間ノード又は改善された自由空間ノードの詳細な配置空間情報が本願で更に説明されるようにコスト波伝播の間にのみ割り当てられる場合に、明示的な離散状態パラメータにより増補される。
【００３７】
例えば、図９は、図２に示される近傍１２３に基づいて本発明に従って明示的な離散パラメータ値を用いてシードノードから目標への最適な経路を決定するためのＡ＊アルゴリズムを表すフローチャート１５０である。具体的に、シードノードは、コスト波伝播、すなわちＡ＊を開始するために、ヒープに置かれる。ヒープは、ルートにおいて最小コスト値を保つ均衡の取れた二分木である。フローチャート１５０の段階Ｓ１５１で、最小コストノードがヒープから取り出される。ヒープから取り出されたノードは「ホーム」と呼ばれる。ヒープが正確なままであることを確かにするよう従来のアルゴリズムが用いられるとする。
【００３８】
段階Ｓ１５１で、更に、シードの詳細（detail）ポインタが、ホームノードにＣＳＤＥＴＡＩＬＮＯＤＥを割り当てて、ホームノードの詳細な配置空間情報、特に、ホームノードの明示的な離散パラメータ値（ＸＹＺＭＭ）を得るために使用される。これは、フローチャート１５０を実行するシステムの速度及びメモリ能力に如何なる悪影響も与えることなくコスト波伝播に望まれる前進運動（precession）を与える。
【００３９】
フローチャート１５０の段階Ｓ１５２で、収束判定条件（stopping criterion）の試験が行われる。処理が終了するかどうかを決定するために実行される多くの試験が存在する。収束判定条件は、（１）ヒープが空であるかどうかの試験、及び（２）現在の（ホーム）ノードのcost_to_goal値が（目的の）開始又は目標よりも大きいかどうかの試験を含んでよいが、これらに限られない。これは、空間全体が満たされる前に探索が終了することを可能にするが、それでもなお、それは、開始と目標との間の最適な経路を与える。
【００４０】
収束判定条件が満足される場合、フローチャート１５０は終了する。そうではなく、収束判定条件が満足されない場合、フローチャート１５０の段階Ｓ１５３は、許容される遷移の近傍の発生を有する。ホームノードの隣接ノードは、そのホームのｘ、ｙ、ｚ位置に加えてα、θ及びφによって与えられるホームノード座標に基づいて計算される。近傍は、α、θ及びφによって公称の近傍を回転させて、既に回転された近傍をホームノードのｘ、ｙ、ｚ位置に対して移動させることから得られる。点の回転及び移動のための方法は当該技術において知られている。
【００４１】
画素が段階Ｓ１５４の間完全には正方形でない場合（例えば、ＣＴ画像において、ｘ：ｙ：ｚの比が１：１：１．３である場合）、回転が行われ、値が増減される。次いで、結果として得られた近傍は、現在の拡大ノードの位置に移動される。
【００４２】
現在のホームノード隣接ノードが計算されると、フローチャート１５０は段階Ｓ１５４に進み、必要に応じて、近傍の次のスレッド（Ｆ）が選択される。もはやスレッドがない場合には、フローチャート１５０は段階Ｓ１５１に戻る。そうではなく、スレッド（Ｆ）がある場合、フローチャート１５０は、必要に応じてスレッド（Ｆ）に沿って次の隣接ノード（ｎ）を選択するために段階Ｓ１５５に進む。
【００４３】
このスレッド（Ｆ）沿いにもはや隣接ノードがない場合には、フローチャート１５０は段階Ｓ１５１に戻る。隣接ノード（ｎ）が他にある場合には、フローチャート１５０は、その隣接ノードのコスト値を試験するために段階Ｓ１５６に進む。それが無限である場合、又は当該隣接ノードが通行可能でないとの他の表示がある場合、フローチャートは段階Ｓ１５１に戻る。他の表示は、その隣接ノードが無限大よりも小さい何らかの所定の閾値よりも高いコスト値を有するが、高すぎて通れないことを示す。この閾値は、例えば、（ホームノードで）移動される現在の距離の関数であってよい。
【００４４】
隣接ノードが無限なコストを有さない場合、フローチャート１５０は、その新しい隣接ノードについて提案される新しいコストＦ（ｎ’）を計算するために段階Ｓ１５７に進む。隣接ノードは予めコストを有することがあるので、それはＦ（ｎ’）で表される。Ａ＊アルゴリズムにおいて、ヒューリスティックｈ（ｎ）は探索を導くために使用されてよい。なお、完全に有効な値はｈ＝０であり、収束判定条件が満たされる／真であるまで、空間に全てのシードノードから埋めさせる。望ましくは、ヒューリスティック値は、本願で後述されるように図１４に従う。
【００４５】
その後、フローチャート１５０は、計算されたコスト値Ｆ（ｎ’）をｎでの既存のコストＦ（ｎ）と比較するために段階Ｓ１５８に進む。計算されたＦ（ｎ’）が既存のコストＦ（ｎ）よりも大きい場合、ホームノードを介してｎに到達することは、以前に決定されたあらゆるものよりもコストがかかる（すなわち、改善はない。）。フローチャート１５０は段階Ｓ１５３に戻る。計算されたコストＦ（ｎ’）が既存のコストＦ（ｎ）よりも小さい場合、この値は従前の方向に対する改善であり、これによって、フローチャート１５０は、当該隣接ノードをヒープに加えるために段階Ｓ１５９に進む。あるいは、既に隣接ノードがヒープにある場合には、かかるノードの値は更新され、ヒープは調整される。改善する隣接ノードがヒープに加えられる場合に、ＣＳＤＥＴＡＩＬＮＯＤＥはその隣接ノードに割り当てられて、隣接ノードの詳細な配置空間情報、特に、隣接ノードの明示的な離散パラメータ（ＸＹＺＭＭ）を得る。先と同じく、これは、フローチャート１５０を実行するシステムの速度及びメモリ能力に如何なる悪影響も与えることなくコスト波伝播に望まれる前進運動を与える。
【００４６】
段階Ｓ１５９で、更に、新しいcost_to_goalが、新しいα、θ及びφであるように、ｎに、割り当てられる。α、θ及びφの値は、現在のスレッドから計算されるαの値により親ノードのθ及びφに対して公称ノードのθ及びφを回転させることによって計算される。シードノードへの最良の道のりを導く修正ベクトルは、ポインタをホームに割り当てられる。任意に、しかし望ましくは、スレッドの数が記憶される。これは、スレッドの数が制御パラメータ（すなわち、例えば、気管支鏡が上下及び左右に回転される量、又は入れ子式カニューレの形状及び相対位置、又は車の操舵及び前進／後進）に直接にマッピングするので、後に、すなわち続く経路の間、計算を最小限とする。
【００４７】
収束判定条件が満足されると、結果として得られるプランニングされた経路は、当該技術に従来達成されていたよりも正確且つ高速に得られる。
【００４８】
［２．疎な自由空間構成］
「疎な自由空間構成（sparse free space construction）」として本願でのみ知られる第２の構成スキームは、自由空間ノードよりも多い相当程度の障害ノードを有する配置空間（例えば、図１０に示されるような離散化された配置空間１１５）に適している。これは、障害ノードに対して自由空間ノードの数を決定するための障害物マップの読み出しから、又は経路プランニングアプリケーション（例えば、駐車プランニング又は肺ナビゲーションプランニング等）の固有特性によって、決定されてよい。所与の経路プランニングアプリケーションに必要とされる精度に係る配置空間要件を満たす疎な自由空間構成のために、全てのデータセットが、各自由空間ノードごとに詳細セクションに実際に記憶されてよく、一方、障害ノードは同じＮＵＬＬ位置を指し示してよい。
【００４９】
例えば、図１１は、本発明の疎な自由空間の構成方法を表すフローチャート１６０である。フローチャート１６０の段階Ｓ１６１はＮＵＬＬ位置の生成を有し、各障害ノードはＮＵＬＬ位置を指し示す。あるいは、代替的に、ＮＵＬＬを示すデフォルトの障害ノードが生成されてよい。フローチャート１６０の段階Ｓ１６２は、全ての詳細な配置空間情報、特に、明示的な離散パラメータ値を各自由空間ノードに含めることを有する。下記は、配置空間ノード構造のための事前に割り振られた詳細な自由空間ノードの疎な自由空間構成の一例である。
【００５０】
【数２】
この疎な自由空間構成は、３次元の配置空間の疎性質と、あらゆる禁止（障害）状態が通行不可能であるという事実を除いて方向、cost_to_goal又は何らかの情報を記憶する必要がないという事実とを使用する。同様に、全てのデータセットは、配置空間における詳細インデックス（detailIndex）のみを残して、実際に詳細セクションに記憶されてよい。
【００５１】
最初に、これは、インデックスが過剰であり且つデータの全ての組が詳細に記憶されるので、必要とされるメモリを増大させるにすぎないと考えられるかもしれない。しかし、障害物であるノードは、詳細のオーバーヘッドをセーブするために、同じ位置（例えば、ＮＵＬＬ）を指し示してよい。多くの障害物が存在する場合に、これは多くの空間をセーブすることができる。このような技術を用いることで、ギガバイトのメモリは約半分しか必要とされない。
【００５２】
例えば、５１２×５１２×６００＝１５７，２８６，４００個の配置状態が存在し、各配置状態は１つのインデックスしか有さない。４２０万個よりも少ない自由空間状態に関し、４バイト整数又はポインタは、トータルで６２９，１４５，６００バイトを必要とするインデックスを与えることができる。６５５３６個よりも少ない状態が存在する場合、２バイト整数で明らかに十分である。このアプリケーションに関し、７２５，０３８個の自由空間ノードが存在し、各ノードは８０バイトを必要とする。全部で、この必要メモリは６８７，１４８，６４０バイトであり、アプリケーションを３２ビットマシンにおいて極めて扱いやすくする。
【００５３】
しかし、このようなメモリの節約は、変数が詳細へと動かされるアクセス時間を増大させる。第１の優先事項は、このアプリケーションでのページングが異常に遅くされうることから、配置空間が局所（高速）メモリ（ＲＡＭ）内に適合することを確かにすることである。
【００５４】
図７及び１１を参照して、フローチャート１３０（図７）の段階Ｓ１３２は、フローチャート１６０（図１１）に従って構成される配置空間ノード構造の全体又は一部を選択された行列に従うコスト値により満たすよう配置空間ノード構造においてコスト波伝播を実施してよい。この場合に、コスト値は明示的な離散状態パラメータの関数であり、これによって、配置空間ノード構造は、コスト波伝播より前に明示的な離散状態パラメータにより増補される。例えば、全ての詳細な自由空間ノードは、図９に示されているフローチャート１５０に従ってシードノードから目標への最適な経路の決定のために、Ａ＊アルゴリズムの実行より前に、予め割り振られる。
【００５５】
［３．疎な障害物構成］
「疎な障害物構成（sparse obstacle construction）」として本願でのみ知られる第３の構成スキームは、障害ノードよりも多い相当程度の自由空間ノードを有する配置空間（例えば、図１２に示されるような離散化された配置空間１１６）に適している。これは、障害ノードに対して自由空間ノードの数を決定するための障害物マップの読み出しから、又は経路プランニングアプリケーション（例えば、開放型屋内競技場、領空、又は腹腔鏡手術等）の固有特性によって、決定されてよい。所与の経路プランニングアプリケーションに必要とされる精度に係る配置空間要件を満たす疎な障害物構成のために、全てのデータセットが、各自由空間ノードごとに、要求に応じて割り振られた詳細セクションに実際に記憶されてよく、一方、障害ノードは同じＮＵＬＬ位置を指し示してよい。
【００５６】
例えば、図１３は、本発明の疎な障害物の構成方法を表すフローチャート１７０である。フローチャート１７０の段階Ｓ１７１は、自由空間ノードのためのコストがかからない（Uncosted）空間変数と、障害ノードのための無限の（Infinity）空間変数との生成を有し、フローチャート１７０の段階Ｓ１７２は、全ての詳細な配置空間情報、特に、明示的な離散パラメータ値を有する各自由空間ノードが要求に応じて割り振られることを有する。下記は、配置空間ノード構造のための詳細な自由空間ノードの疎な障害物構成の一例である。
【００５７】
【数３】
疎な障害表現との関連で、空間が、各次元ごとに２つの隣り合った隣接ノードを含むとともに対角を含む３次元近傍である場合に、近傍の全径（overall diameter）は３と推定されてよい。ユークリッド行列及び無障害物によれば、拡大経路は、連続する空間においてπ×D×長さの体積である。しかし、連続空間でない場合、それは離散化される。より適切には、長さにわたって８個の隣接ノードが存在する。配置空間が上記のようなもの、すなわち、５１２×５１２×６００＝１５７，２８６，４００個の配置状態を有するものであるならば、４バイト整数は基本配置空間についてトータルで６２９，１４５，６００バイトを必要とする。１つの角から対角に相対する角への経路に関し、１：１：１の長さ比（立方体）を有するとすれば、経路の中心は約９４０＝√（５１２２＋５１２２＋６００２）である。起こり得る最悪の場合は、選択される経路がほとんど対角である場合である。各インクリメントにおいて８個の隣接ノードが存在する場合に、全体の必要メモリは、約７５２０個の詳細状態のためでしかない。これは、全ての問題が、６２９バイトの基本配置空間にたった６２０Ｋを足したもので解消され得ることを意味する。配置空間の先の使用と比べて、同じ空間は１２．５ギガバイトを必要としうる。
【００５８】
図７及び１３を参照して、フローチャート１３０（図７）の段階Ｓ１３２は、フローチャート１７０（図１３）に従って構成される配置空間ノード構造の全体又は一部を選択された行列に従うコスト値により満たすよう配置空間ノード構造においてコスト波伝播を実施してよい。この場合に、コスト値は明示的な離散状態パラメータの関数であり、これによって、配置空間ノード構造は、シード自由空間ノード又は改善された自由空間ノードの全データセットが、例えば、図９に示され且つ本願で上述されるようなフローチャート１５０のＳ１５１及びＳ１５９の夫々の段階に従って、コスト波伝播の間に必要に応じて割り振られる場合に、明示的な離散状態パラメータにより増補される。
【００５９】
Ｃ．ヒューリスティック値モード
再び図１を参照して、実際的な許容ヒューリスティックは、障害物を有する空間におけるＡ＊探索のガイダンスのために、ヒューリスティック値モード１０４によって与えられる。具体的に、ヒューリスティック値モード１０４は、セットアップ相１００の間に自由空間の全てのノードについてヒューリスティック値を予め計算して記憶し、それらの値を経路プランニング相１０１の間に、特に非ホロノミックな６Ｄプランニングのために、使用する。示されるように、ヒューリスティック値モード１０４は時間を節約し、複数の経路が効率的にプランニングされることを可能にする。
【００６０】
図１４は、本発明に従うヒューリスティック値生成及び回復方法を表すフローチャート１８０である。概して、ヒューリスティックは、図３に示される直接ユークリッド距離とは対照的に、障害物の周辺の距離において計算する自由空間を通る目標からの距離を表す。更に、ヒューリスティックは、自由空間及び障害物の配置空間から一度だけ予め計算されても、又は必要に応じて再計算されてもよく、これによって、ヒューリスティックは、異なる経路をプランニングするために同じ配置空間についてその後に繰り返し使用されてよい。
【００６１】
具体的に、フローチャート１８０の段階Ｓ１８２は、アルゴリズムが配置空間において全ての自由空間点を訪れること、従って、自由空間の全ての状態においてヒューリスティックを計算することを可能にする完全接続された近傍の配置を有する。近傍の中心にあるノードは、自由空間領域において完全接続された近傍を容易にする最良のノードである。図１５は、近傍の中心にあるノードに接続された２６個のノードから成るヒューリスティック計算のための完全接続された近傍１９０の一例を表す。
【００６２】
フローチャート１８０の段階Ｓ１８３は、段階Ｓ１８２の完全接続された近傍に基づくヒューリスティックの生成を有する。例えば、本願で上述されるフローチャート１５０（図９）の実施は、適切なヒューリスティックが完全接続された近傍に基づいて生成されることを確かにするよう二通りに変形されてよい。第１の変形はアルゴリズム初期化の変更であり、これによって、１又は複数のシードはＡ＊アルゴリズムの開始のために定義されなければならない。これは、単一の状態、又は状態の組（例えば、気管における面全体）であってよい。第２の変形は収束判定条件の変更であり、これによって、アルゴリズムは、自由空間における全てのノードが訪ねられる場合（例えば、気管の面に沿った全ての自由空間ノードが到達される場合）に終了される。
【００６３】
フローチャート１８０の段階Ｓ１８６は、セットアップの間、段階Ｓ１８３の結果（例えば、図１６に示される気管支樹における全ての自由点についての例となる計算されたヒューリスティック等の、自由空間の全ての状態における計算されたヒューリスティック値を有する配置空間）をセーブする。この情報は、３次元画像でメモリに又はハードドライブ（ＨＤ）でセーブされてよい。例えば、データは、未加工フォーマットで又は分析画像フォーマットであってよい。これらは、浮動小数点が、例えば、ＤＩＣＯＭに共通するたった１２ビット整数よりもむしろ、それらのフォーマットで記憶されてよいことから、好ましい。全ての画像要素（配置状態）における、すなわち、自由空間の全ての位置における情報は、経路プランニングの間、段階Ｓ１８５で取り出される。ヒューリスティックの事前計算は、単一のヒューリスティック計算により複数の経路プランニング（同じシードからの異なった目標点）を可能にする。
【００６４】
フローチャート１８０の段階Ｓ１８４は、配置空間における探索を導くためのヒューリスティックの使用を有する。ヒューリスティックが零（ｈ（ｎ）＝０）である場合に、ガイダンスは提供されず、アルゴリズムは自由空間における全ての点を訪れる。障害物を回避するヒューリスティックによれば、純粋なユークリッド指標よりも良い近似が、非ホロノミックな近傍を導くために使用されてよい。入れ子式カニューレ配置において、これはまた、目標に到達するのに必要とされる管の数に影響する。例えば、図１７は、フローチャート１８０に従って生成されたヒューリスティックによる入れ子式カニューレ配置における経路プランニングの例１９２と、当該技術で知られる純粋なユークリッド指標において生成されたヒューリスティックによる入れ子式カニューレ配置における経路プランニングの例１９３とを示す。左側に示されているように本発明のヒューリスティックを使用することは、ユークリッド・ヒューリスティック１９３に比べて、計算時間を５０％以上も減少させ且つ管の数を４０％以上も減少させる。更に、ヒューリスティックは、０．５秒未満の正味の時間節約で計算可能であることが証明されている。
【００６５】
Ｄ．経路プランニングシステム
ここで図１８を参照して、本発明に従う経路プランニングアプリケーションのためのシステム２００が表されている。システム２００は、データ処理デバイス２１０及びデータ記憶媒体２２０を有する。データ処理デバイス２１０は、図１乃至１７に関連して本願で上述された本発明の様々な発明原理を実施するためにセットアップユニット２１１及びプランニングユニット２１２を用いる。一般論として、セットアップユニット２１１は、データ記憶媒体２２０内の特定の経路プランニングアプリケーションに適した配置空間ノード構造（ＣＳＮＳ）を構成するのに必要な全てのタスクを実行し、プランニングユニット２１２は、特定の経路プランニングアプリケーションに望まれるように本発明に従って明示的な離散パラメータ値及び／又はヒューリスティック値の関数としてのコスト値により配置空間ノード構造を満たすのに必要とされるコスト波を伝播する。その結果、特定の経路プランニングアプリケーションに適し多フォーマットで最適な経路２４０が得られる。
【００６６】
本発明の様々な実施形態が図示及び記載をされてきたが、本願で記載される方法及びシステムは例示であり、様々な変更及び修正が行われてよく、等価なものが本発明の技術的範囲を外れることなくそれらの要素に代用されて良いことが当業者に理解される。更に、多くの変形例が、本発明の技術的範囲を外れることなく本発明の教示をエンティティ経路プランニングに適合させるために行われてよい。従って、本発明は、本発明を実施するために考えられている最良モードとして開示される具体的な実施例に限られず、本発明は添付の特許請求の範囲の適用範囲内にある全ての実施形態を包含する。
【特許請求の範囲】
【請求項１】
経路プランニングアプリケーションに従って経路のプランニングを行う方法であって、
少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造をデータ記憶媒体内に構成する段階と、
前記データ記憶媒体内に構成された前記配置空間ノード構造を、該配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により増補する段階と
を有する方法。
【請求項２】
前記離散パラメータ値は、前記離散化された配置空間に対応する近傍の離散サンプリングから得られる、
請求項１に記載の方法。
【請求項３】
前記離散パラメータ値の関数としてのコスト値により前記配置空間ノード構造の少なくとも一部を満たすよう、前記配置空間ノード構造においてコスト波を伝播する段階
を更に有する、請求項１に記載の方法。
【請求項４】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播の前に前記離散パラメータ値により増補される、
請求項３に記載の方法。
【請求項５】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播に応答して前記離散パラメータ値により増補される、
請求項３に記載の方法。
【請求項６】
前記離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値により前記配置空間ノード構造の少なくとも一部を満たすよう、前記配置空間ノード構造においてコスト波を伝播する段階
を更に有する、請求項１に記載の方法。
【請求項７】
前記ヒューリスティック値は、前記離散化された配置空間の自由空間領域に対応する前記配置空間ノード構造の各ノードを接続する近隣配置から得られる、
請求項６に記載の方法。
【請求項８】
経路プランニングアプリケーションに従って最適な経路をプランニングするデータ処理デバイス及びデータ記憶媒体を有し、
前記データ処理デバイスは、少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造を前記データ記憶媒体内に構成するよう動作し、
前記データ処理デバイスは、更に、前記配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により、前記データ記憶媒体内の前記配置空間ノード構造の構成を増補するよう動作する、
システム。
【請求項９】
前記データ処理デバイスは、更に、前記離散化された配置空間に対応する近傍の離散サンプリングから前記離散パラメータ値を得るよう動作する、
請求項８に記載のシステム。
【請求項１０】
前記データ処理デバイスは、更に、前記離散パラメータ値の関数としてのコスト値により前記配置空間ノード構造の少なくも一部を満たすよう前記配置空間ノード構造においてコスト波を伝播するよう動作する、
請求項８に記載のシステム。
【請求項１１】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播の前に前記離散パラメータ値により増補される、
請求項１０に記載のシステム。
【請求項１２】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播に応答して前記離散パラメータ値により増補される、
請求項１０に記載のシステム。
【請求項１３】
前記データ処理デバイスは、更に、前記離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値により前記配置空間ノード構造の少なくとも一部を満たすよう前記配置空間ノード構造においてコスト波を伝播するよう動作する、
請求項８に記載のシステム。
【請求項１４】
前記ヒューリスティック値は、前記離散化された配置空間の自由空間領域に対応する前記配置空間ノード構造の各ノードを接続する近隣配置から得られる、
請求項１３に記載のシステム。
【請求項１５】
経路プランニングアプリケーションに従って最適な経路をプランニングする経路プランニングユニット及びセットアップユニットを有し、
前記セットアップユニットは、少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造をデータ記憶媒体内に構成するよう動作し、
前記セットアップユニット及び前記経路プランニングユニットの少なくとも一方は、前記配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により、前記データ記憶媒体内の前記配置空間ノード構造の構成を増補するよう動作する、
データ処理デバイス。
【請求項１】
経路プランニングアプリケーションに従って経路のプランニングを行う方法であって、
少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造をデータ記憶媒体内に構成する段階と、
前記データ記憶媒体内に構成された前記配置空間ノード構造を、該配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により増補する段階と
を有する方法。
【請求項２】
前記離散パラメータ値は、前記離散化された配置空間に対応する近傍の離散サンプリングから得られる、
請求項１に記載の方法。
【請求項３】
前記離散パラメータ値の関数としてのコスト値により前記配置空間ノード構造の少なくとも一部を満たすよう、前記配置空間ノード構造においてコスト波を伝播する段階
を更に有する、請求項１に記載の方法。
【請求項４】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播の前に前記離散パラメータ値により増補される、
請求項３に記載の方法。
【請求項５】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播に応答して前記離散パラメータ値により増補される、
請求項３に記載の方法。
【請求項６】
前記離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値により前記配置空間ノード構造の少なくとも一部を満たすよう、前記配置空間ノード構造においてコスト波を伝播する段階
を更に有する、請求項１に記載の方法。
【請求項７】
前記ヒューリスティック値は、前記離散化された配置空間の自由空間領域に対応する前記配置空間ノード構造の各ノードを接続する近隣配置から得られる、
請求項６に記載の方法。
【請求項８】
経路プランニングアプリケーションに従って最適な経路をプランニングするデータ処理デバイス及びデータ記憶媒体を有し、
前記データ処理デバイスは、少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造を前記データ記憶媒体内に構成するよう動作し、
前記データ処理デバイスは、更に、前記配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により、前記データ記憶媒体内の前記配置空間ノード構造の構成を増補するよう動作する、
システム。
【請求項９】
前記データ処理デバイスは、更に、前記離散化された配置空間に対応する近傍の離散サンプリングから前記離散パラメータ値を得るよう動作する、
請求項８に記載のシステム。
【請求項１０】
前記データ処理デバイスは、更に、前記離散パラメータ値の関数としてのコスト値により前記配置空間ノード構造の少なくも一部を満たすよう前記配置空間ノード構造においてコスト波を伝播するよう動作する、
請求項８に記載のシステム。
【請求項１１】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播の前に前記離散パラメータ値により増補される、
請求項１０に記載のシステム。
【請求項１２】
前記配置空間ノード構造は、該配置空間ノード構造における前記コスト波の伝播に応答して前記離散パラメータ値により増補される、
請求項１０に記載のシステム。
【請求項１３】
前記データ処理デバイスは、更に、前記離散化された配置空間の自由空間領域を通る探索ガイドを表すヒューリスティック値により前記配置空間ノード構造の少なくとも一部を満たすよう前記配置空間ノード構造においてコスト波を伝播するよう動作する、
請求項８に記載のシステム。
【請求項１４】
前記ヒューリスティック値は、前記離散化された配置空間の自由空間領域に対応する前記配置空間ノード構造の各ノードを接続する近隣配置から得られる、
請求項１３に記載のシステム。
【請求項１５】
経路プランニングアプリケーションに従って最適な経路をプランニングする経路プランニングユニット及びセットアップユニットを有し、
前記セットアップユニットは、少なくとも１つのパラメータによって特徴付けられる複数の状態を有する離散化された配置空間を表す配置空間ノード構造をデータ記憶媒体内に構成するよう動作し、
前記セットアップユニット及び前記経路プランニングユニットの少なくとも一方は、前記配置空間ノード構造の各ノードを明示的に定量化する離散パラメータ値により、前記データ記憶媒体内の前記配置空間ノード構造の構成を増補するよう動作する、
データ処理デバイス。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公表番号】特表２０１１−５２５９８４（Ｐ２０１１−５２５９８４Ａ）
【公表日】平成２３年９月２９日（２０１１．９．２９）
【国際特許分類】
【出願番号】特願２０１１−５１５６９５（Ｐ２０１１−５１５６９５）
【出願日】平成２１年６月１９日（２００９．６．１９）
【国際出願番号】ＰＣＴ／ＩＢ２００９／０５２６５０
【国際公開番号】ＷＯ２００９／１５６９３１
【国際公開日】平成２１年１２月３０日（２００９．１２．３０）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
【公表日】平成２３年９月２９日（２０１１．９．２９）
【国際特許分類】
【出願日】平成２１年６月１９日（２００９．６．１９）
【国際出願番号】ＰＣＴ／ＩＢ２００９／０５２６５０
【国際公開番号】ＷＯ２００９／１５６９３１
【国際公開日】平成２１年１２月３０日（２００９．１２．３０）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
[ Back to top ]