javascript - ワーカー タスクの割り当て

Question

シミュレーションでは、ワーカーはタスクを実行するためにマップ内を移動する必要があります。

各シミュレーション「ティック」で、1 マス移動できます。

隣接してタスクを実行するには、10 ティックかかります。

タスク スクエアは通過できません。ワーカーがいるマスは通過できません。複数のワーカーが正方形で作業できます。

労働者は互いに競合していません。目的は、すべてのタスクをできるだけ早く完了することです。

追加:理想的には、アルゴリズムは簡単に概念化でき、実装が簡単でなければなりません。それは誰もが望んでいることではありませんか？モデルを頻繁にゼロから再計算するのではなく、更新して再利用できるなど、効率的であれば大きなプラスです。理想的には、ローカルオプティマを使用できるため、NP 問題をブルートフォースしようとはしませんが、労働者が他人の計画にほとんど注意を払わない本質的にランダムな放浪ではなく、あからさまに貪欲になることを避け、少し先のことを考えます。

次に例を示します。

ワーカー 1 と 2 は、正方形 A、B、C、および D のタスクを完了する必要があります。

どのワーカーがどのタスクを実行するかをどのように決定しますか?

1 が A を実行し、2 が C を実行する必要があることは自明のようです。

1 は A から 4 マス離れているので、14 ティックで完了します。1 は次にどこに行くべきで、その理由は?

また、B のすぐ上に別のタスク (E) が配置されている場合はどうなるでしょうか。

次に進むべき場所を決定するためにワーカーが使用するロジックは何ですか?

私が試したこと：

趣味のRTSゲームなので、空いているワーカーが一番近いタスクに進むか、他のワーカーがやっていない一番近いタスクに進むようにしてみました。

この貪欲なアプローチは明らかに非効率的であることが証明されており、プレーヤーのテストにより、それが受け入れられないことが明らかになりました. 戦略的な採掘/構築/ファーミングがゲームの鍵であり、プレイヤーがすべての労働者を細かく管理してルーティングすることを望まないため、代わりに労働者が使用できるかなり公正で合理的に最適なアルゴリズムを探しています。

Answer 1

作業員が 1 人の場合でも、これは NP 完全な最適化問題です (巡回セールスマン問題になります) ので、「最適」については忘れましょう。

作業員 1 がタスク A1、A2、...、作業員 2 がタスク B1、B2、... を処理することがわかっている場合、その決定が下された後、独立した巡回セールスマンの解決を試みることができます。問題を 1 つずつ解決し、すべてのワーカーのスケジュールとパスを取得します。

ただし、問題は、移動セールスマンの問題を解決する前に、作業員の一連のタスク A1、A2、... を完了するのにかかる時間を知ることができないことです。タスクを実行します。

これは単なるゲームであり、労働者は最適な思想家ではないと想定できるため、確率過程を使用します。

1. すべてのタスクをすべてのワーカーにランダムに割り当てます
2. 貪欲なアルゴリズムを使用して、ワーカーのタスク グループ内のすべてのワーカーの歩行時間の上限を計算します
3. 1 つのタスクを 1 つのワーカーから別のワーカーに移動するか、2 つのワーカー間でタスクを交換します。
4. 移動が最大実行時間 (歩行時間 + タスク実行時間) の上限を減少させるかどうかに応じて、タブー検索またはシミュレーテッド アニーリングの原則に基づいてその移動を受け入れます。これにより、最後のタスクをできるだけ早く終了させることが目標になります。
5. N回の反復の後、停止し、巡回セールスマンのサブ問題に対するより良い解を計算します。たとえば、確率的探索を使用するか、問題が小さい場合は明示的に計算します(たとえば、従業員あたりのタスクが10未満の場合)。

Answer 2

最も近いタスクに貪欲にワーカーを割り当てるのではなく、最も遠いタスクをその「最も近い」ワーカー (つまり、パスが近くを通過し、それを処理するのに十分な余裕があるワーカー) に貪欲に割り当ててみてください。このようにして、すべてのタスクを完了するのにかかる最小時間の (貪欲な) 概念が得られます。

例えば：

D は「最も遠いタスク」であり、その用語をまだ定義していなくても、D を 1 に割り当てます。15 + 10 単位離れているので、t= 25 に設定し、2 から 25 のスラックを設定します。

ここで、最短ルートを考慮して、次のタスクを割り当てる距離コストを示します。

    A   B   C   D  
1  10  22  24   -
2  29  19  18   -

しかし、貪欲な考えによる真のコストは次のとおりです。最大時間の増加t。

    A   B   C   D  
1  10  22  24   -
2   4  0    0   -

C のコストが最も高いため (貪欲な観点からは最も危険なタスクです)、C を 2 に割り当てます。

次回の費用は以下の通りです

    A   B   slack    A  B
1  10  22     0     10 22
2  21  11  (-)7     14  4

22 が最大時間の最大の増加であるため、B を割り当てtます。ワーカー 2 に割り当てます。

...

ナップザックの問題には多くのアプローチがありますが、シンプルさが必要な場合は、おそらく次に試すことになります。たぶん、タスク間の最短経路を保存します。少し先のことを考えるのは、明らかに貪欲な方法です。

Answer 3

これは確かに、複数のエージェントの巡回セールスマン問題 (TSP、http://en.wikipedia.org/wiki/Travelling_salesman_problem ) によく似ています。実際には、複数のナップザック (MKP、http://en.wikipedia.org/wiki/Knapsack_problem#Multiple_knapsack_problem ) やビン パッキング ( http://en.wikipedia.org/wiki/Bin_packing_problem ) に似た問題です。

この状況に適したアルゴリズムのグループがあり、それは「Ant コロニー最適化」(ACO、http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms ) と呼ばれます。

この 2 つを組み合わせるために、ACO を使用して MKP 問題を解決する実装があります。この場合、これは良い方法のようです。たとえば、次のようになります。

http://www.researchgate.net/publication/221246039_Probabilistic_Model_of_Ant_Colony_Optimization_for_Multiple_Knapsack_Problem

Answer 4

TobiMcNamobiのアプローチに似たものを提案しますが、より洗練されています。

• 各ワーカーの空のワークキューを初期化し、zこのキューを終了するのにかかる時間を設定します。
• 各タスクに 0 に設定されたプロパティを与えますd。これは、現在の計画に従って、このタスクが「既に処理されている」ことを示します。
• すべてのワーカーが少なくとも 1 つのジョブを持ち、 ( z> 一定の値または一定の時間が経過するまで) 繰り返す:
  • w最小限のワーカーの 1 つを取りzます。
    • pのキューの最新エントリの位置、wまたはwキューが空の場合は の位置に設定します。
    • このワーカー キューにないタスクを距離の順にループします。p
      • 計算するdistance/d
      • この値の最小値が見つかった場合は、このタスクをワーカーのキューに追加し、タスクまでの距離 + 7 を加算しz、 を加算1/zしdます。ループを壊します。

これを実行する前に、最も近いタスクまでの距離に従ってワーカーを並べ替える必要があります。それ以外の場合、最初のタスクはかなりランダムに与えられ、最初のタスクが最も重要なタスクになります。

これは、ジョブまたはワーカーが追加されるたびに更新できます。以前の値の一部を再利用する (ワーカーのキュー内のタスクに一致zを追加するなど、中間結果を保存するなど) と、この更新はかなり高速になるはずです。

いずれにせよ、これもおそらく時々更新する必要があります。なぜなら、このアルゴリズムは、十分に未来に進むとかなり不正確になるからです。

distance/d式にも微調整が必​​要かもしれませんが、ここではテストが大いに役立つと思います。

「最小」の定義はあなた次第です。最大でさらに 5 つのタスクをチェックすることをお勧めします。グローバルな最小値を見つけることは、不必要にコストがかかるようです。

Answer 5

「リアルタイム」の貪欲さは悪いものであることが判明したと思います。なぜなら、労働者は、到着するまでに完了するか、ほぼ完了しているタスクに向かって暴走することになるからです。そこで、計画アルゴリズムを提案します。それは、各ワーカーを一連のタスクにインテリジェントに割り当てる方法であり、シーケンスの結合がカバーされます。

他の人が言うように、TSP はこの計画要件に組み込まれているため、これは NP ハードの問題です。

しかし、最適な長さの 2 倍以下のパスを生成する TSP 用の簡単な多項式時間近似アルゴリズムがあります。すべての作業現場と 1 つの作業員を含む最小スパニング ツリーを計算するだけです。次に、各エッジを各方向に 1 回横断する明らかなパスは、すべてのノードに接触します。

もちろん、バックトラックするときは、すでに訪問したノードを「ビーライン」で通過できます。これは、MST を先行順にトラバースすることで、タスク シーケンスを発行するだけであることを意味します。三角形の不等式のため、このパスは多くの場合、最適な 2 倍よりもかなり優れています。(ここでは斜めのステップが許可されていると仮定しています。そうでない場合、これは正しくありませんが、アルゴリズムは引き続き正常に動作します。)

したがって、計画へのアプローチは次のとおりです。

1. 各ワーカーとすべての作業サイトの MST を計算します。
2. 各ワーカー W に関連付けられた MST を使用して、事前注文パスを計算します。それらを訪問します。
3. 次に、簡単なイベント ドリブン シミュレーションを実行して、以下のように計画を立てます。(これは、計画を立てるためだけの、ゲーム シミュレーション内の「内部」シミュレーションです。)

以下のアルゴリズムでは、イベントには予想される発生クロック時刻が含まれており、この時刻をキーとしてイベント キューに配置されます。

Let Arrive(W, T, L) be an arrival event of worker W 
  at task T starting from previous location L, traveling the shortest path
Let Complete(W, T) be a completion event for worker W of task T

For each worker W, place Arrive(W, T_W1, S_W) on the queue
While events are left on the queue
  Remove an event E
  If E is an arrival Arrive(W, TW_i, L) 
    If TW_i has no worker yet, 
      Assign TW_i to W
      Schedule a future event Complete(W, TW_i) 10 time units in the future.
    Else // T has a worker
      Schedule Arrive(W, TW_{i+1}, L), if TW_{i+1} exists
  Else E is a completion Complete(W, TW_i)
    Schedule Arrive(W, TW_{i+1}, TW_i), if TW_{i+1} exists

次に、この (内部) シミュレーションで発見された順序で、各ワーカーの割り当てを実行します。

到着時刻は、最も直接的なルートを取得するために、以前の場所と目的地を使用して計算されます。

このアルゴリズムはかなり貪欲ですが、「事前に」貪欲です。事前にタスクを割り当てるようにシミュレートしているため、到着前に別のワーカーによって完了または十分に開始されるタスクに、ワイルド グース チェイスでワーカーを送信することは決してありません。

さらに、最適な TSP ルートの 2 倍を超える距離をカバーするワーカーは存在しません。

Answer 6

これは RTS ゲームなので、シンプルで高速でわかりやすいアプローチを選択しようと思います。

1. パフォーマンスが重要なため、高速である必要があります
2. ゲームでは、ミニオンが期待どおりに動作する必要があるため、ワーカーがあちこちに移動する理由を簡単に理解できるはずです。プレイヤーのために考えようとしないでください。

もちろん、最初は貪欲なアプローチを試みます。しかし、あなたはそれがうまくいかないことをすでに述べました。

次に、2 次貪欲アルゴリズムのようなものを試してみます。各ワーカーは、最も近いタスク A を選択し、次に A の次に最も近いタスク B を選択します。これまでに誰も選択していないタスクを (!) 選択しようとします。そんな感じ。

小さくシンプルにしてください。心に留めておいてください。どのアルゴリズムを選択しても、惨めに失敗する場合があります。やっぱりフリーランチはありません。

Answer 7

ワーカーの外観は、人間が行うものに似ている必要があると思います (アルゴリズムは、人間が行うように各作業を割り当てる必要があります)。アルゴリズムがそうでない場合、プレーヤーは AI が何をしているのか疑問に思い、おそらく手動でルーティングしようとします (最適ではない場合でも)。「グローバルに最適な」ソリューションは、おそらく人間が行うこととは似ていないと思います...

したがって、あなたの (Will) 初期アルゴリズムは、機能するためにわずかな改善が必要なだけかもしれないと主張します。各ワーカーが最も近い空いているジョブに向かいますが、そこに行くことをシミュレートし、ワーカーがジョブに到達するか、近くにある別のワーカーが空いているときにシミュレーションを停止します (その後、そのワーカーはそのジョブを取得します)。空いている仕事に到達できない場合は、最も近い占有されている仕事を選択し、そこで助けてください。