A*ナビゲーション

概要と主要な概念

A*（「A Star」と発音する）は、ポイント間の最適なパスを見つけるためのよく知られた検索アルゴリズムです。このアルゴリズムは、タスク実行者オブジェクト（移動メンバー）が移動中に通過するノードのグリッドを使用します。各ノードは、移動メンバーが移動できる方向を指定します。このアルゴリズムは、ノード間を対角線方向に移動することを含め、移動方向のノードを検索して、どの方向が最も速いかを決定します。ノードのグリッドは、移動メンバーが移動できる場所を制限するか、特定のパスに沿って移動するように誘導するバリアを作成することで変更されます。

［設定］タブ

［設定］タブには、次のプロパティがあります。

延長深度

この数値は、ナビゲータの最も外側のバリアの外側に配置されるノードの数を指定します。この数は整数で、0より大きくなければなりません。

ｽﾑｰｽ回転

チェックボックスをオンにすると、移動者は曲がるとき滑らかに回転します。

ﾃﾞｨﾊﾞｲﾀﾞｰをｸﾞﾘｯﾄﾞにｽﾅｯﾌﾟ

チェックボックスをオンにすると、ディバイダーはA*グリッドのポイント間でスナップします。

ｷｬｯｼｭﾊﾟｽ

チェックボックスをオンにすると、処理時間を節約する目的で、A*ナビゲーターはパスをキャッシュして再利用します。なお、A*ナビゲーターは、ユーザーが動的バリアを使用していない場合にのみパスをキャッシュできます。パスのキャッシュが必要な場合は、できるだけ条件付きのﾙｰﾙを使用する必要があります。

ﾒﾝﾊﾞｰ

左側にあるボックスでは、表示するメンバーリストを選択します。［プロパティ］ボタンをクリックすると、選択したメンバーのプロパティウィンドウが開きます。右側にあるボックスには、現在選択されている状態ですべてのオブジェクトが表示されます。

アイコン	説明
	クリックするとモデル内の任意のオブジェクトがサンプリングされ、メンバーとして追加されます。
	クリックしてオブジェクト選択ウィンドウを開き、メンバーとして追加するオブジェクトを選択します。
	選択したメンバーを除外します。

［動作］タブ

ﾊﾟｽを検索

移動グリッド内のノードの検索方法を定義します。オプションは次のとおりです。

直角のみ - A*パス検索では、垂直または水平方向に移動するパスのみを見つけます。対角線方向の移動は使用されません。
対角 - A*パス検索では、対角線方向の移動が可能です。移動者は、1ユニットを垂直に、1ユニットを水平に同時に移動できます。
深い対角 - A*パス検索では、深い対角線方向の移動が可能になります。移動者は同時に2ユニットを縦に移動し、1ユニットを横に移動する、またはその逆に移動できます。

制限付き対角

オンにすると、移動者は、グリッド移動方向によって「xの次にy」と「yの次にx」の両方の方向順序付けを使用して対角線方向の目的地に移動できる場合は、対角線方向にだけ移動します。このボックスをオンにすると、移動者が角を曲がるときにパスを短くしすぎないことが保証されます。

衝突回避

チェックボックスをオンにすると、移動者がパスにノードを割り当て、通過後に割り当てを解除します。これにより、2人の移動者が同じノードを同時に通過することはありません。

非アクティブなメンバーを無視する

チェックボックスをオンにすると、衝突回避アルゴリズムにより、非アクティブ移動者が行った割り当てが無視されます。移動者が目的地に到着してアクティブな移動が終わると、移動者は衝突検出アルゴリズムで認識されなくなります。これでは、移動者がアクティブな移動をしていない他の移動者にぶつかることになります。

移動者が互いをひいてしまう軌道で走る状態は望ましくないものの、目的地が同じ他の移動者との衝突を避けるためにアイドル状態の移動者に必要な対応は、やや複雑で簡単にはわかりません。移動者が人間の場合は、互いにぶつからないよう道を譲り合い、遅延ペナルティもそれほど出ないのが一般的です。この遅延ペナルティの観点から、アイドル状態の移動者どうしが互いを無視できるようにすると、人間どうしが自然に道を譲り合う望ましい動作のシミュレーションとなります。

割り当て解除時間のオフセット

追加の待機時間を定義します。この時間が過ぎたら、移動者が離れるグリッドノードの割り当てを解除します。デフォルト（0.00）では、移動者は次のノードへの移動を開始するのと同時にそのノードをリリースします。この値がゼロより大きい場合、移動者はこの追加時間だけ待機してからノードを解放します。

ﾀｰﾝ時に停止

チェックボックスをオンにすると、新しい方向に曲がる必要がある移動者は停止し、新しい方向に回転します。

ﾀｰﾝｽﾋﾟｰﾄﾞ

移動者がターンで停止し、回転するときに使用するターン速度を定義します。

ﾀｰﾝの遅延

ターン時の停止に関連付ける追加の遅延時間を定義します。移動者が停止し、回転しなければならないとき、新しい方向へのターンにかかる時間にこの遅延時間が追加されます。

ﾄﾗﾍﾞﾙ時間別ﾙｰﾄ検索

チェックボックスをオンにすると、A*検索アルゴリズムは、パスの望ましさを評価するコスト関数として移動距離の代わりに移動時間を使用します。これを使用する際の主な違いは、移動者が曲がるために止まると、曲がるのにかかる時間を計算し、それをコスト関数に適用することです。

ﾃﾞﾌｫﾙﾄ優先ﾊﾟｽの重み

優先パスにカスタムの重みを加えない場合に使用されるデフォルトの重みです。有効な値は0から1までの数値です。パスの重みを0に設定すると、そのパスがこのデフォルトを使用するようにします。

［ビジュアル］タブ

これらのプロパティを使用して、A*機能の表示をオンまたはオフにします。

バリア

チェックボックスをオンにすると、バリアが表示されます。

ｸﾞﾘｯﾄﾞの境界

チェックボックスをオンにすると、グリッドの境界を示す青色のボックスが描画されます。

ｸﾞﾘｯﾄﾞのﾉｰﾄﾞ

チェックボックスをオンにすると、グリッドの個々のノードが表示されます。これらは、移動者がそのノードから移動できる方向を示す黄色の直線です。

ﾒﾝﾊﾞｰ

チェックボックスをオンにすると、移動者の下に青色の円が表示され、A*ナビゲーターに接続された固定リソースの下に青色の長方形が表示されます。

占有

チェックボックスをオンにすると、移動者から（その移動者に）割り当てられたノードまで線が引かれます。

ヒートマップ

チェックボックスをオンにすると、ドロップダウンで選択したオプションに基づいてヒートマップが生成されます。［最大ヒート値］は選択されたドロップダウンオプションに対応し、ヒートマップを着色するためのしきい値を定義します。

ﾄﾗﾍﾞﾙの範囲

チェックボックスをオンにすると、3Dビューで強調表示されたオブジェクトの周りに赤と青のひし形が表示されます。移動者にこのオブジェクトに移動する移動タスクが与えられると、A*ナビゲーターは、赤いひし形でマークされた任意のノードと移動者との間の最短経路を計算します。移動者はこの最短経路に沿って移動を開始します。移動者が青いひし形でマークされたノードのいずれかに到達すると、オブジェクトに到着となり、移動タスクは完了します。

ﾙｰﾄ検索ｱﾙｺﾞﾘｽﾞﾑのﾃﾞﾊﾞｯｸﾞまたは表示

このチェックボックスは主にデバッグ目的で使用します。チェックボックスをオンにすると、A*検索アルゴリズムは、各移動者の最終パス検索オペレーションを追跡する追加データを保存します。この情報を参照するには：

［ﾙｰﾄ検索ｱﾙｺﾞﾘｽﾞﾑのﾃﾞﾊﾞｯｸﾞまたは表示］チェックボックスをオンにします。
［適用］ボタンを押します。
モデルを実行します。
移動者をクリックするかShiftキーを押して選択します。移動者を選択すると、その移動者の前回のパス検索オペレーションに関連付けられた一連の点がA*グリッド上に表示されます。
- 緑色の点は、A*「開いたセット」内にあるノードを表します。
- 赤い点は、「閉じたセット」内にあるノードを表します。
- 青い点は、「開いたセット」から「閉じたセット」に解決されているノードを示します。
- また、各ノードの横にテキストが表示され、「g + h = f」の式が表示されます。ここで、gはノードに到達するためのコスト、hはノードから目的地までのヒューリスティック計算、fは2つの合計です。
［完了率］トラッカーを調整し、進行中のルーティングアルゴリズムを参照してください。

［条件付きのﾙｰﾙ］タブ

このタブは、ルーティングアルゴリズムでバリア、ディバイダー、優先パス、またはブリッジを適用する条件付きルールを定義するために使用します。

A*グリッド

A*のパス検索では、移動パスを解決するためにグリッドが使用されます。グリッドとは、移動エリアを囲む2次元の平面です。モデル内にバリア、ディバイダーなどをドラッグした後でモデルをリセットすると、それらのオブジェクトを囲む青い長方形の境界で表されたグリッドが表示されます。グリッドはノードの2次元配列であり、ノード間の距離はユーザーが定義します。A*移動者は、グリッド内のあるノードから別のノードに移動します。隣接ノード間で移動ができるかどうかは、バリアとディバイダーによって決まります。

どのA*モデルにも、少なくとも1つのグリッドがあります。A*モデルに含まれるバリア、ディバイダー、優先パスなどすべてを囲むために、グリッドは自動的に大きくなります。さらに、左側のライブラリからグリッドをドラッグすることで、グリッドを追加することもできます。グリッドは、他のオブジェクトと同様に、3Dビューで移動やサイズ変更ができます。また、その［ﾌﾟﾛﾊﾟﾃｨ］ペインを通して、グリッドのノード間隔やz位置を定義することもできます。

グリッドオブジェクトは、次のプロパティパネルを使用します。

ｸﾞﾘｯﾄﾞ

［ﾃﾞｨﾊﾞｲﾀﾞｰ / ﾊﾟｽ］プロパティパネル

ディバイダーオブジェクトとパスオブジェクトは、次のプロパティパネルを使用します。

ﾃﾞｨﾊﾞｲﾀﾞｰ/ﾊﾟｽ

［ﾊﾞﾘｱ］プロパティパネル

バリアオブジェクトは、次のプロパティパネルを使用します。

ﾊﾞﾘｱ

ノード割り当て/衝突回避

［衝突回避］チェックボックスをオンにした場合、A*モジュールはノード割り当てメカニズムを使用してオブジェクトどうしが衝突しないようにします。新しい目的地への移動タスクを開始した移動者は、次のハイレベルロジックを実行します。

パスを計算する - ロジックはまず、標準的なA*検索アルゴリズムを使用して、移動者の現在地から目的地までのパスのうち、A*グリッド内の隣接ノードを経由するパスを求めます。
キネマティクスを構築する/ノード割り当てをスケジューリングする - 次に、アルゴリズムは、そのパスを移動するためのキネマティクスを構築します。キネマティクスを構築したアルゴリズムは、パスに沿ってノード割り当てを「スケジューリング」します。基本的には、「タスク実行者Yは時間Aから時間BまでノードXを割り当てる必要がある」というデータを格納します。そのため、各ノードは、「私は、時間Aから時間BまでTE Yによって割り当てられ、時間Cから時間DまでTE Zによって割り当てられる」といったデータを持つことになります。
次のイベントを作成する - こうしたキネマティクスを構築するときに割り当て時間の「衝突」が見つからない（さらに、パス上にブリッジがない）場合、アルゴリズムは、パス全体のキネマティクスを構築し、割り当てのタイミングをスケジューリングし、目的地に到着したときの最終イベントを作成します。しかし、割り当てのスケジューリングの際に時間の衝突が見つかった場合、後でノードを割り当てるTEは、ノードの割り当てが必要になる時間のためにonBlockイベントを作成します。このブロックが発生すると、オブジェクトはブロック状態に移行し、ノードが解放されるまで待った後、現地点からすべてのプロセスをやり直します。

ノード割り当てメカニズムは、移動者のパス上にあるノードを割り当てるだけではありません。移動者の対角移動が設定されている場合は、対角線上に隣接するノードの間にあるノードも割り当てます。つまり、この割り当てアルゴリズムで移動者どうしの衝突を適切に回避したい場合、ノードを移動者全体が収まる十分なサイズにする必要があります。グリッドのノードサイズが小さすぎる場合、移動者どうしが重なってしまいます。あるいは、A*ノード割り当てメカニズムを無効化し、A*ネットワークとエージェントモジュールを併用して独自の衝突回避スキームを実装することもできます。

加速度/減速度

A*ネットワークは、ネットワーク上を移動するオブジェクトの加速と減速もサポートしています。一般に、これは自由に動く自律移動ロボットのシミュレーションを想定しており、必ずしも人を想定したものではありません。人モジュールのように人のシミュレーションを行う場合、このシナリオでは加速度/減速度の使用が不利に働くことがあるため（後述）、加速度と減速度のプロパティを0に設定した方がよい場合もあります。［人を作成］アクティビティは、作成された人をA*ネットワークにアタッチするとき、この処理を自動的に行います。

加速度/減速度を使用するときに考慮すべき事項は次のとおりです。

ノード割り当てのタイミング - 移動者の減速度が0でない場合、ノード割り当てのタイミングが変わります。移動者は、ある時点でノードの割り当てを行います。その時点で割り当てに失敗した場合、割り当てに失敗したノードの手前にあるグリッドノードで停止するために、減速するスペースがまだ残った状態となります。その結果、減速度が0以外の小さな値の場合、移動者はかなり手前で割り当てを行うことになり、他の移動者のパスをブロックすることになります。
終了速度が0以外 - 移動/オフセット/ロード/アンロードタスクの終了速度が0以外の場合、移動者は目的地に完全に到着する前に、タスクを実際に早めに終了します。これにより、後続のタスクがすぐに割り当てられない場合や前進をブロックされたときに、オブジェクトがやむを得ず急停止するのを防ぐことができます。代わりに、オブジェクトはかなり手前で割り当てを行ってから、目的地に向けて減速できるようにタスクを早めに終了します。すぐに新しいタスクが割り当てられた場合、オブジェクトは前のタスクを終了した、目的地より手前の地点から新しいタスクを開始します。

TASKTYPE_TRAVELタスクのデフォルトの終了速度は、移動者の最高速度です。これは、移動タスクの直後には一般にオフセット/ロード/アンロードタスクが続くためです。そのため、減速せずに次のタスクにすぐに移ることができるように、ユーザーは通常このタスクを最高速度で終えたいと考えます。A*の使用目的は、タスクを早く終わらせることです。移動者が目的地に向かって常に移動し続けるようにしたい場合は、減速度を0に設定するか、タスクの終了速度を0にしてください。

A*歩行者のイベント

タスク実行者をA*ネットワークにアタッチするとき、このオブジェクトは追加イベントをいくつか取得します。

On AStar Block

移動者が割り当て時間の衝突が発生したグリッドノードの後の割り当て者であり、本来であればその時点でノードを割り当てる必要がある場合に、このイベントが起動します。

On AStar Reroute

移動者がブロックされ、そのブロックによって割り当てリクエストのデッドロックサイクルが発生した場合、このイベントが起動します。このとき、A*モジュールは、デッドロックサイクルのメンバーの1つを迂回するロジックを実行して、デッドロックを回避します。

On AStar Continue

移動者がブロック状態から続行状態に移行したとき、つまり、割り当てを試みたノードが解放されたとき、このイベントが起動します。

On AStar Bridge Arrival

移動者がA*ブリッジに到着したときに起動します。

On AStar Bridge Continue

移動者がA*ブリッジから続行したときに起動します。

On AStar Calculate Path

目的地への新しいパスが計算されたときに起動します。

On AStar Navigate Path

移動者が最終目的地または次の「イベント」地点（例：ブロックポイントまたはブリッジ到着ポイント）に向けてキネマティクスを構築し、ノード割り当てをスケジューリングしたときに起動します。