対象は、障害物を含む8近傍グリッドマップ上で、始点から目標までの経路を高速に求める問題である。直交移動と斜め移動を許すが、斜め移動では角を切り抜けないという制約を課す。グリッド経路計画はゲームだけでなく、ロボットの動作計画やマルチエージェント経路探索の簡略モデルとしても利用されるため、探索速度と経路品質の両立が重要になる。従来のTree Cacheは根から全セルへの最短経路木を前計算し、始点と目標から根へ向かう木をたどって共通祖先で接続するが、品質保証を持たない。
第一の貢献は、Tree Cacheの木構築にJPSの対称性削減規則を組み込んだJSTSである。JSTSでは通常のセルではなく、ジャンプ点を親とするジャンプ全域木を作り、オンライン時に木をたどることで経路上のセグメント数を減らす。第二の貢献は、JSTSを上界としてJPS+型探索に組み込んだBJSTSであり、指定した係数wに対して最適経路長のw倍以内という有界劣化を保証する。提示された抜粋は、これらがすべての既存手法を常に上回ることや、任意の地図・クエリで同じ性能を示すことまでは確立していない。
まず、根から各セルへの最短経路木を構築し、JPSの後継判定を用いて、自然後継に当たる中間セルを親のジャンプ点へスキップする。オンライン探索では、始点と目標からそれぞれ木を根方向へたどり、最初の共通セルを見つけて二つの部分経路を連結する。始点と目標の順序に応じて経路を反転・連結し、JSTSの解を得る。BJSTSはJSTSの経路長を初期上界として保持し、ジャンプ点後継を探索しながら下界と上界を比較し、指定係数の条件を満たした時点で保証付き経路を返す。
実装はRustのmkpathライブラリを用い、Ubuntu 22.04、AMD Ryzen 9 5950X（4.5GHz）、16GB DDR4メモリの環境で評価された。データセットにはMoving AIの標準グリッドベンチマークとIron Harvestグリッドベンチマークを使用し、Game、Street、Maze、Random、Room、Iron Harvestとして分類している。主な指標は木構築時間、1経路あたりの探索時間、劣化率であり、探索時間は地図上の全問題を解く実時間を問題数で割り、100回繰り返して測定した。JSTSはJPS+、重み付きヒューリスティックを使うJPS+、JPS+BB+、Tree Cache、理想化された最適経路オラクルなどと比較されたが、抜粋には全ての個別測定値は含まれていない。
JSTSの速度は、ジャンプにより返却経路のセグメント数を減らし、オンライン処理をほぼ木の読み出しに近づけることで得られる。その代償は、経路が最適である保証も、一定の有限係数以内に収まる保証もないことであり、結論では実アプリケーション領域のグリッドで平均約20パーセント、99パーセンタイルで最適値の3〜5倍悪化し得ると報告される。性能と品質の関係は地図構造に依存し、Game、Street、Iron Harvestではジャンプが有効だった一方、Randomでは効果が小さく、狭い通路のMazeではサブマイクロ秒を外れる場合がある。階段状の中間ノードを迂回する最適化はセグメント数を減らしても、メモリ配置とCPUキャッシュの影響でMaze、Room、Randomの実行時間を悪化させることがある。将来課題は、複数の木などを用いて速度を大きく失わずに経路品質を改善することである。
JPSは前処理なしでグリッド上の対称な経路を削減する最適探索であり、通常のA*より大幅に高速だと説明されている。より高速にするには前処理が必要で、JPS+は各方向の次のジャンプ点までの距離を記録するクリアランステーブルを利用する。Tree Cacheは、根からの最短経路木を前処理し、クエリ時に二つの木上経路を共通祖先でつなぐ単純な方式である。JSTSはこの方式とJPSの対称性削減を結合したものとして位置づけられる。
地図はW×H個のセルからなり、各セルは通行可能または不通行である。移動は隣接する直交・斜めセルへの遷移で、斜め移動では両側の直交セルも通行可能でなければならない。経路長は各移動ベクトルのユークリッド長の合計で、JSTSはこの問題に対して非常に短い計算時間を目指す。抜粋だけでは、動的障害物、複数エージェントの衝突回避、オンライン地図更新を直接評価したかどうかは確定できない。
Tree Cacheでは各セルが直近の親セルを持つのに対し、JSTSではJPSの規則に基づく親ジャンプ点を持つため、木の深さと経路セグメント数を減らせる。根の選択は劣化率に影響し、提示された結果ではMidpathを用いた平均劣化率はどのグラフでも1.4を超えなかった。BJSTSはJSTSの経路を上界として使い、JPS+型の探索で品質保証を導く。正確な保証を得るには、指定された重みwと探索条件が重要だが、抜粋は全ての実装上の詳細を示していない。
評価対象はMoving AIとIron Harvestのグリッドマップで、ゲーム、都市街路、迷路、部屋、ランダム、Iron Harvestのカテゴリが含まれる。JSTSについて、通常版、階段状迂回なし版、Tree Cache、最適経路を直接読み出す理想化オラクルを比較し、時間、セグメント数、幾何平均劣化率を測定した。BJSTSはJPS+、重み付きヒューリスティックを使うJPS+、JPS+BB+と比較された。抜粋には、全クエリ数、各地図の件数、使用したwの一覧は示されていない。
要約表では、A*の平均時間は89979マイクロ秒、JPSは536マイクロ秒、JPS+は349マイクロ秒、JPS+ with DHは85マイクロ秒、CH-JPDは54マイクロ秒、JPS+BB+は24マイクロ秒、Tree Cacheは4マイクロ秒、JSTSは0.3マイクロ秒とされる。JSTSは狭い通路のMazeを除く全地図で平均1マイクロ秒未満となり、Tree Cacheより大幅に高速で、平均経路コストの増加は最大5パーセントと報告される。Game、Street、Iron Harvestでは理想化オラクルより速く、Mazeではそれに競合する一方、Randomではジャンプの効果が小さい。結論では、JSTSは従来のグリッドA*に対して最大5桁、BJSTSは近最適な品質保証付きで最大4桁の性能向上と要約されるが、抜粋は全条件での再現を保証していない。
JSTSは、線形時間で通常数秒程度の前処理を行い、数百クロックサイクル規模で経路を返す方式である。品質を厳密に要求しない大量の経路問い合わせ、特に地図が頻繁には変わらないゲームの高レベル行動計画に適している可能性がある。品質保証が必要な場合はBJSTSが代替となり、指定した係数内の経路を単一桁マイクロ秒規模で平均的に求める。本研究の中心的な結論は、前処理と許容可能な最適性損失を交換することで、グリッド経路計画を理想化された経路出力の複雑性に近づけられるということである。
JSTSの経路品質には保証がなく、平均的に良好でも個別クエリや99パーセンタイルでは大きく劣化し得る。性能は地図構造、根の選択、ジャンプの有効性、メモリ配置に依存し、Randomや狭い通路では利点が弱い場合がある。BJSTSは保証を与えるが、最適性に近づけるほど探索の負担が増え、正確な改善はヒューリスティックの質に依存する。抜粋は、動的環境、メモリ使用量、前処理更新費用、全ての比較手法の実装公平性について十分な情報を確立していない。
本研究は、最適解を求めることだけでなく、経路出力そのものにかかる時間を基準にグリッド探索を捉えている点に意義がある。JSTSが理想化された最適経路オラクルに近づき、場合によっては上回るという報告は、前処理済み探索の実用的な限界を考える材料になる。ゲームの高レベル計画では、実際には経路を移動に使わず距離評価だけを行う問い合わせも多いという議論があり、そのような用途では速度と完全最適性の交換が有用になり得る。MAPF研究者にとっては、単一エージェントの高速な経路生成を低レベル部品として検討する際の参考となる。
グリッド上の単一エージェント経路計画、ゲームAI、頻繁な距離問い合わせ、地図が比較的静的な環境を研究する読者に適している。JPS、Tree Cache、前処理付き経路計画、速度と最適性のトレードオフに関心がある人にも有用である。MAPFやロボット計画への直接適用を考える場合は、衝突回避、動的障害物、複数エージェント間の相互作用が抜粋で評価されていない点を踏まえて読むべきである。