【手続補正書】
【提出日】令和1年10月23日(2019.10.23)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
本発明を、例示的な設計を有するものとして説明したが、本発明は本開示の精神及び範囲内で更に修正してよい。従って本出願は、本発明の一般原理を用いた本発明のいずれの変形、使用又は改造を包含することを意図している。更に本出願は、本発明が属する技術分野の公知の又は慣例的な実施の範囲内にあるような、本開示からの発展形態を包含することを意図している。
以下、本発明の好ましい実施形態を項分け記載する。
実施形態１
ルート生成器を操作する方法であって、前記方法は：
第１のグループ内の複数のブロックに関して、ルートトラバーサル値を同時に計算するステップであって、各前記ブロックは複数のセルを含み、前記トラバーサル値は、地形移動コストデータと、ルート終点への進行を示すデータとを、セル毎に検討した値である、ステップ
を含み、
前記複数のブロックは、前記第１のグループ内の前記ブロックが、前記第１のグループ内の他のグループと、いずれのエッジを共有できないように選択される、方法。
実施形態２
前記複数のブロックに関する前記ルートトラバーサル値は、グラフィック処理ユニットによって同時に計算される、実施形態１に記載の方法。
実施形態３
前記ブロックはマップの一部であり、
各前記ブロックは、２つの極性の値のうちの一方が割り当てられる、実施形態１又は２に記載の方法。
実施形態４
第１の前記極性を有する各前記ブロックは、第２の前記極性のみを有する他の前記ブロックに対して側方に隣接する、実施形態３に記載の方法。
実施形態５
前記第１の極性を有する各前記ブロックは、前記第１の極性のみを有する他の前記ブロックに対して対角線方向に隣接する、実施形態３又は４に記載の方法。
実施形態６
前記第１のグループ内の前記ブロックは、共通の前記極性を共有する、実施形態３〜５のいずれか１項に記載の方法。
実施形態７
いずれの前記ブロック内のいずれの前記セルに関する前記トラバーサル値を計算する際、前記ブロック内の全ての前記セルに関する前記トラバーサル値を計算する必要がある、実施形態１〜６のいずれか１項に記載の方法。
実施形態８
ルート生成器を操作する方法であって、前記方法は：
コストマップのセルの第１のブロックに関するデータを、グラフィック処理ユニットのキャッシュメモリにロードするステップであって、前記第１のブロック内の１つの前記セルに関するデータのロードは、前記第１のブロック内の全ての前記セルに関するデータのロードを必要とする、ステップ；及び
前記セルの第２のセットをロードするステップであって、前記第２のセット内の各前記セルは、前記第１のブロック内にはなく、前記第１のブロック内のあるセルとエッジを共有するか、又は対角線方向に隣接する、ステップ
を含み、
前記第１のブロック内の前記セルの数と、前記第２のセット内の前記セルの数との比は、１：８未満であり、
前記セルの第１のブロックと前記セルの第２のセットとの組み合わせは、前記第１のブロックの全ての前記セルに関するトラバーサル値を生成するために必要な全てのマップデータを提供し、
前記トラバーサル値は、コストデータと、ルート終点への進行を示すデータとを検討した値である、方法。
実施形態９
前記第１のブロックに関する前記コストデータを処理することによって、前記第１のブロックに関する前記トラバーサル値を生成するステップを更に含む、実施形態８に記載の方法。
実施形態１０
前記第１のブロックは少なくとも１０２４個のセルを含み、前記第２のセットは２７２個以下のセルを含む、実施形態８又は９に記載の方法。
実施形態１１
いずれの前記ブロック内のいずれの前記セルに関する前記トラバーサル値を計算する際、前記ブロック内の全ての前記セルに関する前記トラバーサル値を計算する必要がある、実施形態８〜１０のいずれか１項に記載の方法。
実施形態１２
前記セルの前記第１のブロックに関する前記トラバーサル値を生成するステップを更に含み、
前記セルの前記第１のブロックに関する前記トラバーサル値を生成するために使用されるコスト値のみが、前記セルの第１のセット及び前記第２のセットのコスト値である、実施形態８〜１１のいずれか１項に記載の方法。
実施形態１３
生成された前記トラバーサル値に応答して、開始位置から目的位置までのルートを生成するステップを更に含む、実施形態８〜１２のいずれか１項に記載の方法。
実施形態１４
各前記セルは、各前記セルに関連付けられた単一の前記コスト値及び単一の前記トラバーサル値のみを有する、実施形態８〜１３のいずれか１項に記載の方法。
実施形態１５
ルート生成器を操作する方法であって、前記方法は：
ルートの決定の一部として第１のセルが処理されることになることを決定するステップ；
前記第１のセルが、少なくとも２つのセルを内包する第１のブロック内にあることを決定するステップ；
前記第１のブロック内の全ての前記セルを分析するために必要なデータを、第１の不揮発性メモリから、プロセッサによってアクセス可能な揮発性メモリにロードするステップであって、前記第１のブロック内の全ての前記セルを分析するために必要な前記データは、前記第１のブロック内のある１つの前記セルとエッジ及びコーナーのうちの少なくとも１つを共有する全てのセルを含む、ステップ；及び
前記第１のブロック内の全ての前記セルを分析するために必要な前記データを全て前記揮発性メモリにロードした後、前記第１のブロック内の全ての前記セルを分析するステップ
を含む、方法。
実施形態１６
ロードされる各前記セルは、各前記セルに割り当てられた単一のコスト値及び単一のトラバーサル値のみを有する、実施形態１５に記載の方法。
実施形態１７
前記第１のセルが処理されることになることを決定する前記ステップは、前記第１のセルを内包しない第２のブロックを処理するステップを含み、
前記処理は、前記第１のブロックが前記第２のブロックに隣接することを示す、実施形態１５又は１６に記載の方法。
実施形態１８
前記プロセッサはグラフィック処理ユニットであり、
複数の前記ブロックが同時に処理される、実施形態１５〜１７のいずれか１項に記載の方法。
実施形態１９
各前記ブロックは、２のべき乗の個数の前記セルを含む、実施形態１５〜１８のいずれか１項に記載の方法。
実施形態２０
前記揮発性メモリは、前記プロセッサ上のキャッシュメモリである、実施形態１５〜１９のいずれか１項に記載の方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ルート計画計算システム（１０）のルート生成器を操作する方法であって、改善が：
物理的地形の異なる部分に対応するブロックをマップ内で識別するステップと、
第１のグループ内の複数のブロックに関して、ルートトラバーサル値を同時に計算するステップであって、各前記ブロックは複数のセルを含み、前記トラバーサル値は、地形移動コストデータと、ルート終点への進行を示すデータとを、セル毎に検討した値である、ステップと
を含み、
前記複数のブロックは、前記第１のグループ内の前記ブロックが、前記第１のグループ内の他のグループと、いずれのエッジを共有できないように選択される、方法。
【請求項２】
前記複数のブロックに関する前記ルートトラバーサル値は、グラフィック処理ユニットによって同時に計算される、請求項１に記載の方法。
【請求項３】
各前記ブロックは、２つのパリティの値のうちの一方が割り当てられる、請求項１又は２に記載の方法。
【請求項４】
第１のパリティを有する各前記ブロックは、第２のパリティのみを有する他のブロックに対して側方に隣接する、請求項３に記載の方法。
【請求項５】
第１のパリティを有する各前記ブロックは、前記第１のパリティのみを有する他のブロックに対して対角線方向に隣接する、請求項３又は４に記載の方法。
【請求項６】
前記第１のグループ内の前記ブロックは、共通のパリティを共有する、請求項３〜５のいずれか１項に記載の方法。
【請求項７】
いずれの前記ブロック内のいずれの前記セルに関する前記トラバーサル値を計算する際、前記ブロック内の全ての前記セルに関する前記トラバーサル値を計算する必要がある、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
ルート生成器を操作する方法であって、前記方法は：
コストマップのセルの第１のブロックに関するデータを、グラフィック処理ユニットのキャッシュメモリにロードするステップであって、前記第１のブロック内の１つの前記セルに関するデータのロードは、前記第１のブロック内の全ての前記セルに関するデータのロードを必要とする、ステップ；及び
前記セルの第２のセットをロードするステップであって、前記第２のセット内の各前記セルは、前記第１のブロック内にはなく、前記第１のブロック内のあるセルとエッジを共有するか、又は対角線方向に隣接する、ステップ
を含み、
前記第１のブロック内の前記セルの数と、前記第２のセット内の前記セルの数との比は、１：８未満であり、
前記セルの第１のブロックと前記セルの第２のセットとの組み合わせは、前記第１のブロックの全ての前記セルに関するトラバーサル値を生成するために必要な全てのマップデータを提供し、
前記トラバーサル値は、コストデータと、ルート終点への進行を示すデータとを検討した値である、方法。
【請求項９】
前記第１のブロックに関する前記コストデータを処理することによって、前記第１のブロックに関する前記トラバーサル値を生成するステップを更に含む、請求項８に記載の方法。
【請求項１０】
前記第１のブロックは少なくとも１０２４個のセルを含み、前記第２のセットは２７２個以下のセルを含む、請求項８又は９に記載の方法。
【請求項１１】
いずれの前記ブロック内のいずれの前記セルに関する前記トラバーサル値を計算する際、前記ブロック内の全ての前記セルに関する前記トラバーサル値を計算する必要がある、請求項８〜１０のいずれか１項に記載の方法。
【請求項１２】
前記セルの前記第１のブロックに関する前記トラバーサル値を生成するステップを更に含み、
前記セルの前記第１のブロックに関する前記トラバーサル値を生成するために使用されるコスト値のみが、前記セルの第１のセット及び前記第２のセットのコスト値である、請求項８〜１１のいずれか１項に記載の方法。
【請求項１３】
生成された前記トラバーサル値に応答して、開始位置から目的位置までのルートを生成するステップを更に含む、請求項８〜１２のいずれか１項に記載の方法。
【請求項１４】
各前記セルは、各前記セルに関連付けられた単一の前記コスト値及び単一の前記トラバーサル値のみを有する、請求項８〜１３のいずれか１項に記載の方法。
【請求項１５】
ルート生成器を操作する方法であって、前記方法は：
ルートの決定の一部として第１のセルが処理されることになることを決定するステップ；
前記第１のセルが、少なくとも２つのセルを内包する第１のブロック内にあることを決定するステップ；
前記第１のブロック内の全ての前記セルを分析するために必要なデータを、第１の不揮発性メモリから、プロセッサによってアクセス可能な揮発性メモリにロードするステップであって、前記第１のブロック内の全ての前記セルを分析するために必要な前記データは、前記第１のブロック内のある１つの前記セルとエッジ及びコーナーのうちの少なくとも１つを共有する全てのセルを含む、ステップ；及び
前記第１のブロック内の全ての前記セルを分析するために必要な前記データを全て前記揮発性メモリにロードした後、前記第１のブロック内の全ての前記セルを分析するステップ
を含む、方法。
【請求項１６】
ロードされる各前記セルは、各前記セルに割り当てられた単一のコスト値及び単一のトラバーサル値のみを有する、請求項１５に記載の方法。
【請求項１７】
前記第１のセルが処理されることになることを決定する前記ステップは、前記第１のセルを内包しない第２のブロックを処理するステップを含み、
前記処理は、前記第１のブロックが前記第２のブロックに隣接することを示す、請求項１５又は１６に記載の方法。
【請求項１８】
前記プロセッサはグラフィック処理ユニットであり、
複数の前記ブロックが同時に処理される、請求項１５〜１７のいずれか１項に記載の方法。
【請求項１９】
各前記ブロックは、２のべき乗の個数の前記セルを含む、請求項１５〜１８のいずれか１項に記載の方法。
【請求項２０】
前記揮発性メモリは、前記プロセッサ上のキャッシュメモリである、請求項１５〜１９のいずれか１項に記載の方法。