Multi-Objective Task Assignment and Multiagent Planning with Hybrid GPU-CPU Acceleration ?

[yukarinoki]

https://arxiv.org/abs/2305.04397

要約：タスクの集合とエージェントのグループを用いた割り当てと計画は、マルチエージェントシステムにおける重要な問題です。一般的にエージェントの数が増えるとマルチエージェントモデルのサイズも指数関数的に増加するため、スケーラビリティが課題となります。我々はランダムなタスク割り当てと複数の目標制約を考慮し、この問題を個々のエージェント-タスクモデルに分散させることができることを示しています。我々は、与えられたコストと確率の閾値に対応する点が、形式的な問題において実行可能かどうかをチェックする「点指向のパレート計算」アルゴリズムを提案しています。与えられた点が実行不可能な場合、我々のアルゴリズムは与えられた点に最も近いパレート最適な点を見つけます。我々は、GPUとマルチコアの両方を同時に活用する初のマルチオブジェクティブモデルチェックフレームワークを提供しています。我々のフレームワークは、並列計算のための負荷分散問題としてCPUとGPUデバイスを管理します。実験により、並列化によって逐次計算よりも大幅な実行時間の高速化が達成されることが示されています。

[yukarinoki]

MDP = Markov Decision Proscesses PMC = Probabilistic model checking LTL = Linear Temporal Logic

[yukarinoki]

数学的、マルコフ決定問題のGPU込みのフォーミュレーションを考えて、うまいやり方も考えた。実験というのも、data warehouse rayoutのsimulationであって、あるプログラムが速く動くとかではない