2次元グリッドワールド上のA-starでの時間ベース制約の扱い

Question

ノードとエッジを指定する2次元グリッドワールドのグラフから始めました。スタートとゴールを与えられました。私はA *を使って最短経路を見つけることができました。

時間の概念が導入され、現在のノードで待機することが許可されているという点で、問題は少し修正されました。与えられた問題は次のような例で考えることができます。

線形世界の中に配列a（1：6）の形でノードがあるとします。 エージェントは2から開始して6に進む必要があります。前述のように、私はA *を使用してこれを計画することができました。最適なパスは、2-> 3-> 4-> 5-> 6です。

今、時間が画像に入るとします。 3-> 4のような各遷移は、1時間単位が経過したことを意味する。エージェントは時刻t = 0で移動を開始し、時刻t = 3でノード5に行くことができないことを伝える。したがって、最適なパスは次のとおりです。2-> 3-> 4-> 4-> 5-> 6

しかし、私はA *を使ってこの計画を作成する方法を考えることができません。私の考えはこれでした：私は3次元=（x、y、t）ではなく、（x、y）で計画します。グラフ構造が保持されている限り、A *はどんな次元でも処理できます。

しかし、私は（2,0）どこで私は（ノード、時間）を使用するように開始を知っているので、私は混乱していた。しかし、目標は何ですか？私はそれが（6、t）のようなものであることを知っています。しかし、私は何を知りませんか？だから、現在のノードから目標までヒューリスティックを計算したいときはいつでも、目標が何であるかわからないので、私は困惑しています。 A *を使用してこの問題を処理する方法。この例は代表的なものであり、非常に単純化されています。私は2D世界で作業していますが、問題は例で説明したものと同じです。

このような問題が対処されている研究論文を引用すると非常に役に立ちますが、明らかにこの問題の過剰な研究であることを避けてください。誰かが最良の擬似コードを与えることができれば。

Answer 1

モデルは完全に動的ではなく、変更を事前に知っているので、A *アルゴリズムの簡単な変更によってパスを見つけることができます。
まず、状態を拡張すると、 。
第二に、あなたのフリンジリストに状態のネイバーを追加するときに、時間の制約をチェックし、あなたがあなたの質問に言及配置する必要があります：

state: position, time, h 

current_state = priority_queue.top 
priority_queue.add(state(current_state.position, current_state.time+1, new_h)) 
for each neighbor of current state: 
    if possible to be at neighbor.position at current_state.time+1 
     priority_queue.add(state(neighbor.position, current_state.time+1, h)) 

しかしあなたの世界は、動的Aを実装する必要があり、完全に動的である場合* D *のようなアルゴリズム。または、初期モデルでA *を実行することができます。そして、途中で障害物に遭遇したときは、A *を使って障害物に関する地図を変更しながら新しい経路を見つけようとします。