日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

効率的なタスク割り当てのための希望順位戦略の自律的学習法の提案
飯嶋 直輝

杉山 歩未

早野 真史

菅原 俊治

近年の情報技術の発達によって多くの情報が利用可能となり，それによって複数の機能と多様な情報を組み合わせたサービスの提供が可能となっている．これらのサービスは様々な分散環境やその連携で実現できると考えられ，各計
算機 (エージェント) にどのタスクを割り当てるかを適切に決定する必要があるが，これにはサービスの要求条件やエージェントの特性を考慮する必要があり，適切かつ効率的なタスク割り当ては困難な課題となる．そこで，本研究では継続的に様々なタスクが発生する環境を想定し，全体の社会的効用に加え，これとは必ずしも整合しないかもしれない選好を個別に考慮できるタスク割り当て問題に対し，各エージェントがシステム全体として求める効用を追求するとともに，それぞれの観点から個々の特徴や実績に基づき，全体に最大限貢献できるタスクの順位づけ戦略を学習する手法を提案し，システム全体として高い効率を実現できることを実験的に示す

1 はじめに近年の情報技術の発達により，多くの情報が利用可能となり，それによって複数の機能と多様な情報を組

ソース Ri = {r1i , . . . , rhi } を持つ．ここで h はリソー
スの種類を表し，rki はリソースの量を表す．この値が大きいほどタスクの処理能力が高いことを表す．また，離散時間の単位として tick を導入する．

み合わせたサービスの提供が可能となっている．これ

タスク t は三つ組 (S t , wt , dt ) で表される．S t =らサービスの実現には様々な分散環境やその連携で実{si1 , . . . , sih } は t を処理するのに必要なリソース量現できると考えられ，各計算機にどのタスクを割り当を表す．エージェントはタスク t を処理すると報酬てるかを適切に決定する必要がある．しかし，これにwt を得る．本論文では wt を t の必要リソースの和はサービスの要求条件やエージェントの特性を考慮す||S t || =る必要があり，適切かつ効率的な割り当ては困難な課などの違う値も考えられる．また本研究では，時間経題であり，多くの研究が行われている [1] [2] [3]．

過で報酬が変化するタスクも考える．i が t を割り当∑hk=1stk とするが，もちろん社会的な価値

そこで，本研究ではシステム全体の効用を追求するてられたとき，i はタスク処理を開始する．処理にかとともに，計算機（エージェント）それぞれの観点か

かる時間は t のリソースと i のリソースの比とし，以ら全体（社会的）に最大限貢献できるタスク選択やタ下の式で求める．

スクの順位づけ戦略を学習する方法を提案する．

P T i (t) = max {⌈stk /rki ⌉}

(1)

1≤k≤h

dt は t のデッドラインを表し，その時刻までに処理

2 タスク割当問題を終えなければ t は廃棄される．

エージェントの集合を A = {1, . . . , n} とする．エー

l tick においてタスク集合 Tl = {t1 , . . . , tm } が与ジェント i ∈ A は，タスクを処理する能力を表すリ

えられたとき，エージェント i はデッドラインまでに処理できるタスクに対して，タスクとそのタスク

Naoki Iijima, Ayumi Sugiyama, Masashi Hayano,Toshiharu Sugawara, 早稲田大学理工学研究科情報理工・情報通信専攻, Dept. of Information and Computer Science, Waseda University.

iの価値の組の順序集合 B i = ⟨(ti1 , v1i ), . . . (tiNi , vN)⟩i(m ≥ Ni ) を決定し，マネージャーへ送信する．Tl は
l tick におけるシステムのタスクプールと呼ぶ．効用価値 vki はタスクの報酬や処理時間など，共通的で割り当ても可能となる．) タスクの処理後，i は報酬比較可能な値である．tik の希望順位は i の選好戦略

wt を得る．l tick で割り当てられなかったタスクは，ic (tik ) によって決定するものとする．i の希望順位はデッドラインによって廃棄されない場合，Tl+1 に持他のエージェントと必ずしも整合しない．l tick にち越される．そして新しいタスクが Tl+1 に追加され，おいて Abusy
をタスク処理中のエージェントの集合，
lf reeをタスクを割り当てられていないエージェントAl

上記の処理を繰り返す．の集合とする．
毎 時 間 ，発 生 し た タ ス ク は Tl に 追 加 さ れ る ．

∀i ∈3 提案手法 : 選好戦略の決定学習
エージェントの選好戦略の集合を C とする．これ

Afl ree は c に従って B i を決定する．そしてらの選好戦略は，順序集合 B の決定に利用される．

タスクを B に基づいて割り当てを行う．本提案手法

C={HRF,EDF,SPTF,CEF} とし，左から順に報酬

では，このタスク割り当て問題を SORA/PO [4] とみの大きい（HRF），デッドラインが近い（EDF），自なす．これはエージェントの集合 A = {1, · · · , n} と身にとって処理時間の短い（SPTF），1 tick あたりタスクの集合 T = {t1 , · · · , tm }，そしてエージェントに得られる報酬 (報酬/処理時間) が大きいタスクをi ∈ A のタスクと，それに対応した価値の順序集合優先する戦略（CEF）を表す．本論文では，環境やi)⟩ を与えられたとき，以下= ⟨(ti1 , v1i ), . . . (tiN , vN

負荷，自分の能力に応じてエージェントが C から自Bi分に適切な戦略 c を学習する．はじめにエージェンのように定義される．

ト i は戦略それぞれについてその有用度を示す E 値

定義
タスクの集合を T とし，B = {B |i ∈ A} (ただし．
iE i (c) を持つ．なお，E i (c) の初期値は 0 とする毎時i)⟩) を希望の集合とすると
B i = ⟨(ti1 , v1i ), . . . (tiN , vN間，i は E i (c) が最大となる選好戦略 c を ε-greedy 法き，SORA/PO は以下の条件 (3) を満たし，価値のによって戦略を選択し，それに従って B i を決定する．

総和を最大にする割り当て L∗ (⊂ T × A) を求めるこ

まず E i (c) の学習のために，マネージャーは最近とと定義する．

Jall =∑の K 回の (K 個のタスク) 割り当てに関する統計情

VoiL∗ (i) ,(2)(t,i)∈L∗

subject toFor ∀(t, i) ∈ L∗ and 0 < ∀k < oL∗ (i),if ∃tik s.t. aL∗ (t′ ) = j, then voj L∗ (j) ≥ vki . (3)
これはエージェント i が割り当てられたタスクよりも希望順位の高いタスク t′ が他のエージェント j に割り当てられるとき，i の t′ に対する価値 vki よりも jの t′ に対する価値 voj L∗ (j) が低くはないことを示している．
この問題は組み合わせ問題であり，最適解を求めるのは困難である．そこで，準最適解を求める

SRNF/RD アルゴリズム [4] を使って解を導出する．
これは希望順位を考慮し，不満を発生させずに準最適解を求めるアルゴリズムである．本研究では，エージェントは一度に１つのタスクしか処理できないとする． (しかし．Abusy のエージェントにも負荷に応じて B を宣言できるようにすれば．複数のタスクの報として，報酬 wt ，処理開始からデッドラインまでの時間 dt − ls (t)，処理時間 lc (t) − ls (t)，を S に保存する，ただし t は処理したタスクを，ls (t) はタス
クの処理開始時間，lc (t) はタスクの処理終了時間を表す．なお，K を超える場合は古い情報を削除する．
この値は後に述べる統計量の計算に利用する．
エージェント i ∈ A がタスク t を割り当てられたとき，次の式で E 値を更新する．

E i (c) ← (1 − α)E i (c) + αR(t)(4)

ここで α ∈ [0, 1] は学習率であり，R は E 値の報酬(これを E 報酬と呼ぶ) である．そして，E 報酬を以下のように定義する．
t
 ± θc − µ̂ccŝc
R =gL (i) ̸= null

(5)
−1gL (i) = null
± は条件により選択する．ここで θct とはタスク t に

関する希望順位を決定するための指標の推定値で，EDF であれば処理開始からデッドラインまでの時間
dt − ls (t)，HRF ならばタスクの報酬の値 wt ，SPTF

は処理時間 lc (t) − ls (t)，CEF は wt /(lc − ls ) の推定値となる．µ̂c ，ŝc はそれぞれ指標を標準化するための標本平均と不偏標本標準偏差であり，これらはマネージャーが S から以下の式で計算し，タスク t の割り当ての際に t とともにエージェントに送る．
1 ∑ sµ̂c =θ̂cKs∈Sŝc=1
K −1(∑)(θ̂cs − µ̂c )2s∈S

従って Rc はそれぞれの指標を表す標準化された統計量となる．このように E 報酬を与えることで，エー

図11 tick あたりの平均効用値の推移

ジェントは自分にとって得意な戦略を学習することができる．たとえば EDF 戦略の場合，他のエージェン
トよりもより dt − ls (t) が小さいタスクを処理するほど E 報酬が大きくなる (この場合は式 (5) で − をと値が減少するタスクであり，以下のように定義する．
()h∑lc (t) − lg (t)wt =stk × 1 −(8)2(dt − lg (t))
k=1

ここで lg (t) はタスクが発生した時間を表す．これは，る)．また，エージェントはそれぞれ異なる戦略を持

効用値は時間とともに線形に減少し，デッドラインのつことになる．E 値は Q 値の概念に近いが，報酬は直前では半分になる．

共通ではなく，各戦略ごとに表した統計量を標準化し

タスクは時間経過とともにポアソン分布 p0 (λ) にたもので，その戦略による全体の位置付けを表す．

従って発生し，タスクプールに追加される．1 tick に平均で発生するタスク数 λ は，どの戦略でも廃棄タス

4 評価実験

クが現れ始める値の 26 と設定した．タスクのデッドラ

4. 1 実験環境

イン dt は 15 から 25 の間でランダムな値とする．タ

本実験の目的は，時間経過に伴いタスクの性質が変スクを処理していないエージェント i ∈ Afl ree は選好化する環境において，選好戦略の学習が柔軟にこれi)⟩
戦略に基づき希望リスト B i = ⟨(ti1 , v1i ), . . . (tiN , vNに対応でき，高い効率を実現することを示すことでを宣言する．Ni を大きくすると割り当て対象も増加ある．

するが，計算コストも増える．ここでは Ni = 5 とし

本実験ではエージェント数 |A| を 300 とし，エージェントとタスクのリソースの種類数は３とする．
エージェントは所持する全てのリソースが多いものと少ないものの２種類存在し，1 ≤ k ≤ 3 について

5 ≤ rki ≤ 7 or 2 ≤ rki ≤ 4(6)た．また，K = 50 とし，学習率 α = 0.1，ε = 0.1 とする．
本実験では，全体のシミュレーション時間を 310000

tick とし，初めの 10000 tick を初期学習の時間とする．初めは全てのタスクがタイプ１のタスクであるの範囲でランダムで設定する．また，タスクは以下のが，10000 tick 後は 3000 tick 毎にタイプ 2 の発生す範囲で要求リソースをランダムに設定する．

る割合を 1%ずつ増加させる．以下に示す実験結果は

30 ≤ sik ≤ 60 (1 ≤ k ≤ 3)

(7)

50 回の試行の平均値をとったものである．

本実験では，SORA/PO における価値はタスクの効用値とし，システムとしてこれを最大化することを4. 2 効用値とエージェントの戦略の推移目的とする．タスクの報酬値については２種類仮定

図 1 に 1 tick あたりに獲得したタスクの効用値のし，第一をデッドラインまでに処理できれば一定の効総和の推移を，図 2 に提案手法を実装したエージェ用値が得られるタスクとし，これをタイプ１と呼ぶ．

ントが選択した選好戦略の割合の推移を示す．図中

タイプ２のタスクはデッドラインに近くに従って報酬で学習する提案手法に関してはラベルを LEARN とが割り当てられずに負の報酬を得るのを回避するためである．そして，タイプ２のタスクが増えるにつれて CEF を選択するエージェントが減少する．これはCEF のエージェントがタイプ１のタスクに集中して競合が発生することが原因である．このとき，他の戦略に比べて SPTF のエージェントがより増加している．これは能力の低いエージェントと比べて処理時間が短いため，比較的大きな報酬を得やすいからである．最後にタイプ２のタスクのみになると，CEF を
図2

エージェントの戦略推移選択しても競合が減るため CEF を選択するエージェントの割合が増加する．

し，以後提案手法を LEARN と呼ぶ．また，ラベル

EDF，HRF，SPTF，CRF はそれぞれの選好戦略に5 まとめと今後の課題統一したときの結果を示す．

本研究ではエージェントがタスクに対して，自身のまず単一戦略に着目すると，図 1 から環境の変化能力や周囲の環境を考慮して自分のタスクへの希望につれて効用値の総和を最大化する戦略も変化するを宣言できるタスク割り当て問題を提案した．その問ことがわかる．例えば CEF は，初めは一番良く，環題に対し，エージェントが周囲の状況とシステムへの境の変化に従って順位が下がるが，最終的には再び貢献度を考慮して自分の戦略を自律的に選択する手一番目に戻る．これは，CEF は効用値を処理時間で法を提案した．実験によって，戦略を学習することに割った値を報酬とするので，タイプ 2 のタスク処理

よってエージェントが変化する環境に柔軟に戦略を変で得られる報酬は少なく，タイプ２のタスクの増加に更し，全体の効率を上げることを示した．

伴い，エージェントはタイプ１のタスクに集中し，か今後の課題としては環境を変えて実験を行うこと，つタイプ２のタスクは廃棄されやすくなり，効用値がまたエージェントの希望の宣言の際に通信時間を考慮低くなる．しかし，タイプ２のタスクのみに近づくとすることなどである．

希望の偏りがなくなり，再び効用値が上がる．
他方，提案手法に着目すると，図 1 で LEARN はタスクのタイプに関わらず常に単一戦略よりも効用値の総和が高くなった．これは，単一の戦略でなく各エージェントが個々の戦略を貢献度に応じて自律的に選択したためと言える．
図 2 を見ると，戦略を学習するエージェントは環境によって選択する選好戦略の割合が異なることがわかる．例えば，HRF は時間経過に伴い選択される割合が徐々に減少するが，EDF は時間経過に伴い徐々に選ばれる割合が増加し，200000 tick あたりから停滞している．SPTF は初めは選択される割合が上昇するが，250000 tick あたりから減少する．逆に SSTF
は初めは選択される割合が減少するが，250000 tickあたりから上昇する．全てのエージェントが同じ戦略にならないのは，同じタスクに希望が集中し，タスク参 考 文 献[ 1 ] Y. Jiang, “A survey of task allocation and loadbalancing in distributed systems,” IEEE Transactions on Parallel and Distributed Systems, vol.27,no.2, pp.585–599, 2016.
[ 2 ] H. Izakian, A. Abraham, and B.T. Ladani, “Anauction method for resource allocation in computational grids,” Future Generation Computer Systems, vol.26, no.2, pp.228–235, 2010.
[ 3 ] H. Aziz, P. Biró, J. Lang, J. Lesca, and J. Monnot, “Optimal reallocation under additive and ordinal preferences,” Proc. of the 2016 International
Conference on Autonomous Agents & Multiagent
Systems, pp.402–410, International Foundation forAutonomous Agents and Multiagent Systems, 2016.
[ 4 ] K. Saito and T. Sugawara, “Single-object resource allocation in multiple bid declaration withpreferential order,” Computer and Information Science (ICIS), 2015 IEEE/ACIS 14th International
Conference on, pp.341–347, June 2015.