最適動作を探索する

[miyashita64]

完了条件

• 最小と思われる動作コスト(動作時間の期待値)で、開始時の仮想走行体を目標とするノード(座標)にするためのゲーム動作群を出力できる

実現方法

• A*アルゴリズムで探索する

入力

• 開始状態:探索開始時の仮想走行体(座標, 方位)
• 終了位置:目標とするノード( or 座標？)

仮想走行体 ≒ (走行体の)状態

出力

• 最適動作:CompositGameMotion

暫定手順

0. 開始状態から1つのゲーム動作で遷移できる状態を遷移可能状態とする
1. 遷移可能状態の中から予測コストが最も小さい状態を状態を選択する
2. 選した状態から1つのゲーム動作で遷移できる仮想走行体を遷移可能状態に追加する
3. 終了位置に該当する状態を選択するまで、1と2を繰り返す

予測コスト=開始状態からその状態への実動作コスト+その状態から終了状態までのマンハッタン距離

本来、実動作コストは動作変換から取得するが、未実装であるため、調整動作や回頭角度を無視したような暫定的なコストを用いる。動作前後のノードの種類によって対応するゲーム動作のコストを参照する？

関連資料（省略可）

[mutotaka0426]

指摘も何もできないから，何を渡して何を返すかくらいは書いてほしい． モデル的には渡すのは走行体とノードだけど，ゲームエリア情報との兼ね合いを考えてどうする想定なのかとかね 結果の返し方は，CompositeGameMotionで返した方が色々楽かもしれないけど，そこは任せる

運搬経路を探索するって書いてあるけど，運搬動作の探索ではなくて？ 実際にはゲーム動作のリストを返すようにしてほしいけど，動作を求めるところまでは今回はしない？ うまいこと分けれそうならそれでもいいとは思うけど

[mutotaka0426]

予測コスト=開始状態からその状態への実動作コスト+その状態から終了状態までのマンハッタン距離

動作コストの単位は時間だから，マンハッタン距離と同列に計算したらおかしくなると思う というかこの場合Aアルゴリズムになる？ ※Aアルゴリズムだと最適解を求められることが保証されない

A*アルゴリズムは，予測コストは実際にかかるコスト以下でなければならないっていう制約条件があるんだけど，時間と距離だとそもそも比較できないから，「その状態から終了状態までのマンハッタン距離」じゃなくて「その状態から終了状態になるまでに少なくともかかるコスト」であるべきだと思う

「その状態から終了状態になるまでに少なくともかかるコスト」は，A*アルゴリズムで言う所のヒューリスティック関数に当たるんだけど，これをいかに実際のコストに近づけるかが肝だね 俺がパッと思いついたので言うと，ノード間移動のゲーム動作のうち最小のコストを引っ張ってきて，それで予測コストを求めるとか（実際にそんな動作ができるかは別として）？

ヒューリスティック関数については，実装する中で試行錯誤すると思うから任せるけど，色々とわかんなくなったら，俺や菅とかなら経験してるから相談乗れると思う（宮下君がいるから心配いらないと思うけど！） 一応参考文献載せときます

参考資料

実際に武藤が参考にした記事

• よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき)
• A* - Wikipedia

  AアルゴリズムとA*アルゴリズムの違いについて

• 【探索】ダイクストラ法・最良優先探索・Aアルゴリズムの比較。

[mutotaka0426]

動作コストの単位は時間だから，マンハッタン距離と同列に計算したらおかしくなると思う というかこの場合Aアルゴリズムになる？ ※Aアルゴリズムだと最適解を求められることが保証されない

最短のゲーム動作の時間よりも必ず小さくなるように距離を補正できればA*にはなるかも？ ヒューリスティック関数で出すコストが，実際のコストに近ければ近いほど探索は最適化されるから，ヒューリスティック関数はちゃんと考えた方がいいけどね

ヒューリスティック関数の一つの案だけど，ゴールまでのユークリッド距離を求めて，その距離を直進したときの動作時間とかどうかな？ 直進の動作時間は，距離別でいくつかデータ取って回帰分析しておけば出せるだろうし，これなら実際の動作時間よりも必ず小さくなるよね？ 参考程度にお納めください