4連結グリッドマップにおいて、出現や消失を繰り返す動的な障害物を回避しながら、始点から終点までの総コスト（到着時刻）を最小化する最適経路を求める問題。時間軸の導入により探索空間が膨大になるだけでなく、移動順序が異なるだけでコストが同一となる「空間的対称性」や、待機アクションのタイミングが異なるだけの「時間的対称性」が多数存在するため、従来の探索手法では効率的な探索が困難である。
既存の標準的な手法であるSIPPが時間的な対称性の打破に留まっていたのに対し、JPSTは空間的・時間的な両方の対称性を同時に特定して排除する点に新規性がある。垂直・水平移動を優先し待機を遅らせる新しい正規順序を導入することで、同じコストを持つ重複した経路の展開を抑制し、中間ノードをスキップして時間的ジャンプポイントを直接特定することを可能にした。
Vertical-then-Horizontal-then-Wait (VHW) と呼ばれる、垂直移動、水平移動、待機の順に優先して実行する正規順序を導入する。ノード展開時には、この順序を維持できない隣接セルを枝刈りし、現在の移動方向とは異なる移動が強制される地点を時間的ジャンプポイントとして特定する。再帰的な探索プロセスにおいて、待機、水平、垂直の順で経路の連続性を確認し、中間ノードをOPENリストに追加することなくジャンプポイントのみを後続ノードとして生成する。また、ビットフィールドを用いた高速スキャンや、待機アクションを即座に展開してデッドエンドを判定する投機的待機などの最適化技術を用いる。
ゲームのマップを用いた移動障害物シナリオおよび制約条件下での経路探索実験において、SIPPや時間拡張A*と比較評価を行った。評価指標として実行時間を用い、マンハッタン距離やPerfect 2Dヒューリスティックを用いた結果、JPSTは多くのケースでSIPPに対し数倍から1桁以上の高速化を達成した。特に空間的な対称性が高い広大なマップにおいて顕著な性能向上を示した。
廊下のような空間的対称性が少ないマップでは、JPSTの優位性が減少する。また、エージェント間の衝突回避において、頂点だけでなくエッジ（移動経路）を中心とした制約管理を行うことで、エッジ衝突にも対応可能な枠組みへの拡張が挙げられる。
4接続のグリッドベースの経路計画において、出現や消失を繰り返す時間的・移動的な障害物を考慮する問題は、ゲームやロボティクスなどの様々な場面で一般的ですが、解決が困難な場合があります。この困難さは、時間軸の導入によって探索空間が膨大になること、およびグリッド上の移動順序が異なるだけで経路として区別できない対称的な経路が多数存在することに起因します。本論文では、Jump Point Searchの形式を用いた新しい最適アルゴリズムを提案し、これらの対称性を特定して打破することで探索効率を向上させています。提案手法は、この分野の標準的な手法であるSIPPと比較して、複数の要因において1桁以上の性能向上を実現しています。
本研究では、時間経過とともに移動する障害物が存在する4連結グリッドマップにおいて、時間最適経路を探索する問題を扱う。時間軸を導入した探索では、待機アクションの追加による分岐数の増加や、各セルに時間インデックスを付与することによる状態数の増大に加え、経路の順序のみが異なる空間的対称性および時間的対称性が課題となる。これに対し、提案手法であるTemporal Jump Point Search (JPS-T) は、垂直移動、水平移動、待機の順に優先して実行するVHWという新しい正規順序を導入することで、これらの対称性を打破する。この順序は、垂直・水平移動を可能な限り早期に行い、待機を可能な限り遅らせる経路を生成するものであり、展開されたノードごとに重複する対称的な経路を枝刈りすることで探索性能を向上させる。実験の結果、JPS-TはSIPPと比較して、ロボティクスやゲームのような幅広い設定において、数倍から10倍以上の高速化を実現している。
本研究では、2次元のグリッドマップを時間軸で拡張したタイムエクスパンデッド・グリッドを扱う。グリッドマップは、通行可能または通行不能な正方形のセルで構成され、上下左右の4方向への移動が可能で、各移動のコストは1である。タイムエクスパンデッド・グリッドでは、各移動が1タイムステップ分時間を進め、セルは座標と時間の組み合わせで表される。移動アクションには、4方向の移動に加えて、その場に留まり時間を1進める待機（WAIT）が含まれ、待機もコスト1である。経路とは、初期位置から目標位置まで、すべてのセルが通行可能であり、かつ各ステップが有効な移動によって接続されたセルの時系列列である。本研究の目的は、始点から終点までの経路において、恒久的な障害物および時間とともに変化する動的な障害物をすべて回避しつつ、総コスト、すなわち到着時刻 k を最小化する最適経路を見つけることである。
本研究では、時間的に変化する障害物が存在する時間拡張グリッドマップに対応するため、Jump Point Searchを拡張したTemporal JPS（JPST）を提案している。この手法の核心は、Vertical-then-Horizontal-then-Wait（VHW）と呼ばれる新しい標準的な経路順序の導入にある。VHW順序では、垂直および水平方向の移動を可能な限り前倒しで行い、待機動作を可能な限り遅らせることで、探索における対称性を排除する。具体的には、垂直移動と水平移動の順序入れ替え、待機動作と移動動作の順序入れ替え、および移動動作を待機動作に置き換える操作によって、同じコストと到着時間を持つ別の有効な経路が生成されない状態を標準的であると定義する。ノード展開時には、現在の経路をこの標準的な順序に従って継続できる隣接位置のみを後続ノードとして考慮する。この性質により、時間拡張グリッドにおける任意の最適経路に対して、コストと到着時間が等しく、かつVHW順序に従う等価な経路が必ず存在することが保証されている。
JPSTは、ノードを拡張する際に隣接セルの集合を削減するための枝刈り規則を適用します。空間的な枝刈りでは、垂直・水平・待機（VHW）の正規順序を維持できない隣接セルを除去することで、バックトラックを回避します。例えば、ある方向へ移動した際、垂直方向の移動をより早い段階で行うことで同等のコストで到達できる経路が存在する場合、それ以外の順序の経路は枝刈りの対象となりますが、障害物によって垂直移動が制限されている場合は、そのセルを生成することが強制されます。時間的な枝刈りでは、一時的な障害物が存在する状況において、障害物が消失するまで待機する動作や、障害物が消えるタイミングに合わせて特定のセルへ到達する動作を考慮します。待機動作の後は、通常、正規順序に基づき一つの隣接セルを除いて他のセルを枝刈りできます。定理によれば、任意の最適経路は、垂直方向の動作を優先し待機動作を後にするVHW正規順序へと組み替えることが可能であり、組み替えた後も経路の有効性とコストは維持されます。
本手法は、A*探索の効率化のために、特定の優先順位（VHW順序）に基づく経路の連続性を再帰的に探索し、中間ノードをOPENリストに追加することなく「時間的ジャンプポイント」を直接特定する手法を提案している。時間的ジャンプポイントとは、目的地であるか、あるいは現在の移動方向とは異なる別の移動が強制される地点を指す。この強制される状態とは、優先順位の高い移動を試みた場合に経路が成立しない状況を意味する。再帰的な探索では、待機、水平移動、垂直移動の順に探索を行うことで、常にVHW順序に従った正規の経路のみを辿ることを保証している。また、障害物が消失した後の時刻において、待機行動が目的地への到達に寄与しない場合は、その枝をデッドエンドとして即座に切り捨てる。この再帰的な枝刈りにより、探索は中間ノードをスキップしてジャンプポイントのみを後続ノードとして生成でき、最適性を維持したまま探索を進めることが可能である。
JPSTを用いた探索の具体例として、時間拡張されたグリッドにおける最適経路探索の複雑さが示されている。開始地点と目標地点が隣接していても、時間経過とともに直接的な経路が遮断される状況において、JPSTは待機や移動といった標準的な動作を選択しながら探索を行う。この過程では、障害物が消失した直後に強制的な移動が必要となる時間的ジャンプポイントを特定することで、探索空間を体系的に探索する。最適経路が空間的なサイクル、すなわち同じ場所を時間差で経由することを含むケースや、3次元空間での探索も示されており、特定の時間ステップで障害物が消失した際にのみ有効なジャンプポイントが生成される様子が記述されている。多くの探索枝は、強制的な移動が発生した後の行き止まり判定によって枝刈りされる。
JPSTの実用的な運用に関する検討事項として、まず経路の具体化が挙げられる。隣接する時間ジャンプポイント間のx、y、t各次元の差分に基づき、垂直移動、水平移動、待機移動の順序で構成される標準的なサブパスを生成することで、最適かつ有効な経路を導出できる。探索効率向上のため、スキャン範囲を一定のステップ数に制限するジャンプ制限を導入しており、これにより不要な領域のスキャンを抑制する。また、ビットフィールド表現を用いて障害物の位置を管理することで、32ステップ単位の高速なスキャンを実現している。待機動作の最適化については、投機的待機という手法を提案しており、到達可能な待機後継者を即座に展開して強制隣接ノードを生成することで、探索リストへの不要なノード追加を防ぎ、探索を加速させる。さらに、時間軸の膨張によるメモリ消費を抑えるため、各座標における通行可能な時間区間を管理するセーフインターバルを利用し、時間的対称性を打破しつつ探索を高速化している。最後に、エージェント間の衝突回避への拡張として、頂点衝突だけでなく、エッジを中心とした制約管理を行うことで、エッジ衝突にも対応可能な枠組みが示されている。
本研究では、提案手法であるJPSTと既存手法であるSIPPの性能を、移動障害物が存在する環境と制約条件下での経路探索の2つの設定で評価しています。移動障害物の実験では、ゲームのマップを用いた複数のシナリオにおいて、過去の最適解を障害物の軌跡として利用し、マンハッタン距離または事前計算されたPerfect 2Dヒューリスティックを用いて比較を行いました。その結果、JPSTは多くのケースでSIPPを上回り、特に空間的な対称性が高い広大なマップやマンハッタン距離を用いた場合に、数倍から1桁以上の高速化を実現しました。一方で、障害物の数が増えて時間的な制約が強まると、ジャンプ距離が短くなりノード展開が増えるため、JPSTの優位性は低下し、障害物が極端に多い場合は両手法とも時間拡張A*と同等の性能に収束します。制約条件下での実験においても、JPSTはSIPPや時間拡張A*に対して、数倍から数桁の実行時間の短縮を示しました。特に、高速スキャン（fast scanning）の最適化が性能向上に大きく寄与することが確認されています。また、Perfect 2Dヒューリスティックを用いた場合、JPSTの利点は強力な推定値によるものよりも、空間的な対称性を打破する能力に起因していることが示されました。
本研究では、時間的に変化する障害物が存在する4連結グリッドマップにおける経路探索のための新しいアルゴリズムであるTemporal Jump Point Search (JPST) を提案している。JPSTは、垂直、水平、待機の順で探索を行うVHWと呼ばれる新しい標準的な順序付けスキームを採用することで、空間的および時間的な対称性を打破しており、高速かつ最適で、完全にオンラインでの動作が可能である。既存の主要なプランナーであるSIPPと比較した実験では、時間的な制約が少ない場合から数万個に及ぶ場合まで幅広く検証が行われ、JPSTは数倍から1桁以上の高速化を実現することが示された。