4

3 つの AI 初心者の質問:

  1. A* が最適なパスを見つけるためにヒューリスティックが許容されるのはなぜですか?
  2. 障害物が邪魔をしている場合、タイブレーキングテクニックは何の役に立つでしょうか?
  3. 障害物があるグリッド上のパスを見つけるのに適したアルゴリズムは? (パックマンみたいに)

最初の質問では、ヒューリスティックをベースとして、Manhattan distance呼び出しは h(x) です。では、なぜ A* は 8*h(x) + 5 という新しいヒューリスティックで最適でないパスを見つけなければならないのでしょうか? (乱数)。A* アルゴリズムで理解している限りでは、決定は関数に従って行われるf(x) = g(x) + h(x)ため、h をスケールアップすると、なぜ最大 \ 最小が変化するのでしょうか?

私はこの記事を読みました、そこで彼らはタイブレーキングのために小さな係数を掛けることについて話しました. だから、どう考えたらいいのかわからない。

2 番目の質問では、パックマン ゲームを解決するためのリンクのテクニックを試しました。マンハッタン距離ヒューリスティックを変更すると、より多くのノードが展開されました。私は、外殻のパスを優先する新しい重み付けスキームを「発明」しました-同じことです。後で、すべての関数の最大値を取得しようとしましたが (これも許容されるはずです)、それでもパフォーマンスが低下しました。私は何が欠けていますか？

3 番目の質問に追加するものはありません。前述のように、マンハッタンの距離よりも優れたものは見つかりません。

4

4 に答える 4

1

1）簡潔な答えは、ヒューリスティックが許容できない場合、（おそらく）最適ではない結果が得られるということです。あなたはこれを知っていたと思います。直観のために、許容できるヒューリスティックの定義を思い出してください。これは、決して現実よりも悲観的ではないヒューリスティックです。(楽観的でも悲観的でもないヒューリスティックがある場合、基本的にはすでに答えを持っているため、「常に楽観的である」と言います。) ヒューリスティックがいくつかの場所で悲観的である場合、最終的には最良の選択。

質問によるヒューリスティックのスケールアップとスケールダウンに関しては、数式の埋没コスト部分ではなく、数式のヒューリスティック部分のみをスケールアップしていることを覚えておいてください。それらをまったく同じように拡大できたとしても、違いはわかりませんが、常にそうできるとは限りません。あなたの例でさえ、あなたが追加した追加ビットはそれを台無しにします。

2-3) pacman を「解決する」というのが何を意味するのか、私にははっきりしません。空のグリッド内のすべてのドットを食べるための最短経路を見つけることよりも複雑な場合は、A* の範囲をはるかに超えていると思います。それでも、A* は私が選んだツールではありません。

于 2012-09-03T19:36:12.233 に答える
0
  1. ヒューリスティックが許容されない場合、ヒューリスティックは（場合によっては）目標に到達するためのコストを可能な限り低いコストよりも高く見積もるでしょう。したがって、最終的なパスは、「悪い」聴覚のためにコストがかかりすぎるように見えるパスを探索しなかった可能性があるため、最適ではない可能性があります。あなたの場合、8*h(x) + 5単調に使用するとすべての推定コストが増加するため、すべての推定パスのコストはすべて大きくなりますが、同じ方法で順序付けられます（たとえば、ヒューリスティックを使用して、パスの長さはA5、パスの長さは3でした。 BB（コスト29）は、A（コスト45）よりも短いと推定されます）。
  2. 記事に示されているように、マンハッタン距離+最初に述べたタイブレーカーは障害物に適しています。推定最大パス長を1000のままにしましたか、それともパックマンの実装ではこの値を高くする必要がありますか？
于 2012-09-03T10:27:56.897 に答える
0

質問 3:

実際にパックマン ゲームを作成している場合、それぞれの「ゴースト」のパスを見つける必要があります。また、ダイクストラのアルゴリズムを使用して、パック マンの位置を目標として使用し、各ゴーストの最適なパスを一度に計算することもできます。 . また、各「エッジ」(1 つのセルから次のセルに移動する) のコストは常に同じであるため、単純な幅優先探索を使用することもできます。最後に、各ゴーストを異なる方法で送信するためのCollaborative Diffusionもご覧ください。

于 2012-09-03T11:56:16.780 に答える
0

通常、ヒューリスティック関数が許容できない場合は、「最適ではない」ソリューションを短時間で見つけることができます (一種の「問題緩和」です)。ソリューションの「最適性」に厳密な制約がない場合は、許容できないヒューリスティック関数を使用できます。(たとえば、ゲーム AI では、最適なソリューションではなく、迅速なソリューションが必要です)。

今、パックマン AI の答えです。元の Pac-Man AI には、 A*、複雑な経路計画、グリッド スペース ナビゲーションはありません。Iann Millington 著『Artificial Intelligence for Games 』という本には、非常にシンプルですが非常に効果的な Pac-Man AI アルゴリズムがあります。

  1. ゴーストはジャンクションに到達するまで直線的に移動します。
  2. 分岐点で、彼らは次に進む方向を半ランダムに選択しました。

止まる。それで全部です。

半ランダムには、2 つのケースがあることを意味します。

  1. x/10回はランダムな方向を選択します。
  2. (10-x)/xプレーヤーの方向にルートを選択する回数 (プレーヤーとゴーストの位置の間の単純なオフセットによって計算されます)。

ゴーストごとに異なる x を選択して、それぞれに異なる「個性」を実現できます。

それでも A* を Pac-Man AI に使用したい場合、正方形グリッドの世界全体ではなく、ジャンクション (すべてのノードがジャンクションであるグラフ) のみを表すことをお勧めします。廊下の広場は本質的に役に立たない。;)

于 2012-09-03T15:48:00.717 に答える