一種面向自動駕駛推理任務的工作流調度策略
2021-03-21 05:11:58林凱，盧宇，陳星，林兵
小型微型計算機系統 2021年3期
林 凱，盧 宇，陳 星，林 兵
1(福建師范大學 物理與能源學院，福州 350117) 2(福州大學 數學與計算機科學學院，福州 350116)
1 引 言
隨著機動車保有量的增加，道路擁堵、交通安全、環境污染等問題日益突出.自動駕駛車輛的發展為這些問題提供了新的解決方案.高度自動化的車輛駕駛可以提高駕駛的便利性和舒適性，提高道路系統的整體交通效率和安全性，緩解交通擁堵，大大減少人為失誤造成的事故.此外，它還可以減少汽車尾氣排放對環境的污染，顯著提高燃油效率.
當自動駕駛車輛行駛在道路上，傳感系統會檢測當前的交通狀況，將路況信息傳遞到車輛的推理系統中，推理系統需要在短時間內處理這些信息.隨后，車輛的傳動系統就能做出諸如加速、轉向等一系列響應動作[1].由于OBU的計算能力不足，在容錯時間約束下，選擇合理的調度平臺，優化自動推理任務的完成時間是自動駕駛技術中重點關注的問題.
邊緣計算為了將計算任務卸載到終端用戶附近的邊緣服務器，利用計算和存儲資源位于終端設備和云數據中心之間的邊緣設備.其目的是將計算任務卸載到終端用戶附近的邊緣服務器，并在數據源附近處理計算任務，從而縮短響應時間.邊緣環境下推理任務的分解與調度能夠很好地滿足推理任務的低延遲處理要求，并產生良好的實時處理效果[2].
在自動駕駛推理任務的研究中，很少關注推理任務的調度問題，大部分研究集中自動駕駛過程中的交通狀況識別和推理分析[3-5].自動駕駛的推理任務調度問題類似于協同設計的任務調度和工作流調度.因此，協同設計任務和工作流調度的研究方案可以應用于自動駕駛推理任務工作流調度中.由于推理任務通常調度在OBU上[6]，這將導致推理任務調度的高延遲，無法滿足推理任務的安全性和實時性要求.目前，啟發式算法被廣泛應用于解決協同設計任務和工作流調度問題，如蟻群算法、粒子群算法、遺傳算法等[7-9]，這些算法雖然能較好地解決工作流調度問題和協同設計任務，但收斂速度慢，容易陷入局部最優解，不能很好地滿足推理任務的低延遲要求.近年來，強化學習被應用于解決協同設計任務和工作流的調度問題.該算法通過與不確定環境的交互作用來修正實際值與預測值之間的偏差，收斂速度較快.這些研究為自動駕駛推理任務工作流調度提供了一種新的解決方案[10-12].雖然推理任務的結構類似于協同設計任務和工作流，但是自動駕駛車輛生成的推理任務需要滿足實時系統的低延遲要求.因此，有必要設計合適的調度策略和算法，以滿足自主駕駛推理任務的要求.
基于以上研究現狀，針對自動駕駛推理任務實時系統，根據車輛駕駛過程中推理任務和邊緣環境的變化，本文首先設計出一種在邊緣環境下的自動駕駛推理任務工作流調度策略，并充分利用邊緣計算平臺的計算能力對推理任務進行調度.其次，利用SA-QL算法來尋找自動駕駛推理任務工作流的低延時調度方案.最后，本文對SA-RL算法和PSO算法進行了性能比較.
本文的主要貢獻如下：
1)設計了一種推理任務工作流調度策略，考慮在不同時間窗內邊緣環境和實時推理任務的變化情況，在滿足任務約束的條件下計算任務完成時間；
2)在邊緣環境下進行自動駕駛推理任務工作流調度處理，在滿足推理任務約束條件下，減少任務完成時間；
3)引入SA-QL，結合本文提出的推理任務工作流調度策略，優化自動駕駛實時推理任務工作流執行時間.
本文余下部分組織布局如下.第2部介紹目前相關研究工作；第3部分對自動駕駛推理任務工作流調度問題進行描述與分析，確定問題模型以及要求解的目標，并用實例分析推理任務調度過程；第4部分提出了基于強化學習算法的推理任務工作流調度策略，設計了推理任務工作流調度算法來計算推理任務完成時間，提出了適用于本文研究問題的SA-QL算法；第5部分進行實驗結果的討論與分析，對SA-RL算法及PSO算法進行性能差異的分析；最后一部分總結全文，并討論本文未來的改進與展望.
2 研究現狀
針對自動駕駛，當前的研究工作主要集中于自動駕駛推理任務路況信息的推理決策和識別.例如Teichmann等人[3]提出了一種聯合分類、檢測和語義分割的語義推理方法，雖然加快了推理速度，在數據集中表現非常出色，但是仍存在著計算瓶頸和能耗大的問題，這些研究中，對推理決策過程進行建模優化，在自動駕駛推理決策問題中取得了不錯的效果，但未涉及推理任務調度問題的研究工作；Vacek等人[4]提出了一種基于案例推理的認知汽車情景解釋方法，該方法依靠基于案例的推理來預測當前場景的演變并選擇合適的行為，但是沒有使用實際場景進行測試來顯示這種方法的潛力，而且沒有提出如何評估無案例知識下行為后果的方法；高振海等人[5]，針對決策過程的因果關聯問題,建立了車輛跟馳行為的馬爾可夫決策過程模型，基于增強Q學習算法對該模型進行求解，驗證了方法的可行性與有效性，提升了決策過程的因果關聯性，改善了傳統決策方法中既定的邏輯切換策略并規避了固有設計理念中多參數調校的難題，使自動駕駛過程中車輛動作的選擇更貼合實際，但是回報函數的設計缺少舒適性等其他指標的考慮，沒有驗證算法的穩定性；王娟娟等人[6]基于可并行的有向無環圖提出了一種自動駕駛硬實時推理任務調度機制，保證所有進入車載計算系統的推理任務都能在其截止期之前完成，有效提升自動駕駛時應急避險的安全性，但是研究中將推理任務調度至車載處理器進行處理，存在著處理設備計算能力不足，處理時延高的問題，不能很好的滿足自動駕駛推理任務的實時性要求.
由于自動駕駛推理任務與協同設計任務及工作流結構相似，因此將協同設計任務與工作流調度問題的研究方法應用于自動駕駛推理任務的調度上具有可行性.在工作流調度問題的研究中，研究者主要采用仿生算法進行問題求解，例如Meena等人[7]提出了一種元啟發式成本效用遺傳算法，考慮了云的異構性、按需付費價格模型，以及虛擬機性能變化和啟動時間等因素，在云環境中，滿足最后期限的同時，最大限度地降低工作流的執行成本，雖然在執行時間與執行成本上取得了不錯的效果，但是未考慮到虛擬機的關閉時間，以及虛擬機部署在不同數據中心之間的數據傳輸成本，這些因素將影響工作流的總體執行成本.Zhu等人[8]基于進化多目標優化算法來解決基礎設施即服務平臺上的工作流調度問題，提出了一種針對特定問題的編碼和種群初始化、適應度評價和遺傳算子的新方案，結果表明，算法具有較高的穩定性，可以獲得更好的解決方案，但未考慮多個定價方案、實例類型、云的情況以及通信和存儲的成本；Xie等人[9]提出了一種全新的非局部收斂粒子群優化算法，應用非線性慣性權重來平衡和調整粒子的全局和局部搜索能力，通過加速粒子群加快近最優解的搜索速度，通過選擇和變異操作，使粒子群以一定的概率逃離局部極值，保持粒子群的多樣性，減少極大地降低了云邊緣環境下工作流調度的時間和經濟成本.
隨著強化學習算法的發展，一些研究者將其運用至協同設計任務及工作流調度問題中，并取得了不錯的效果.例如，Wang 等人[10]將深度Q網絡模型應用于多代理增強學習環境中，以指導云上多工作流的調度，構建了一個馬爾可夫博弈模型，該模型以工作流應用程序和異構虛擬機的數量作為狀態輸入，以最大完成時間和成本作為回報，優化了多工作流的完成時間和用戶成本，雖然生成調度策略優于傳統算法，但是提出的方法未考慮更多的QoS指標，如可靠性、安全性、負載平衡等，并且依賴于任務和候選云服務器的QoS數據信息，在實際應用中，如果歷史QoS數據不足，收集數據的工作十分昂貴和耗時；Orhean等人[11]針對分布式系統中的調度問題，考慮了節點的異質性及其在網格中的配置，提出了一種強化學習算法，從而確定一個更低執行時間的調度策略，但是由于分布式系統的復雜性，學習模型存在局限性，當系統添加的節點過多，強化學習代理將無法正確學習最佳策略.陳圣磊等人[12]建立了任務調度問題的目標模型，給出調度問題的馬爾可夫決策過程描述，提出一種基于多步信息更新值函數的多步Q學習調度算法(Multi-step Q Learning Algorithm,MQ)，該算法收斂速度較快，能有效地解決任務調度問題，雖然采用多步Q學習算法能有效平衡協同設計任務調度的計算量和預見能力，但是由于算法步數的變化對算法性能有較大影響，而在自動駕駛推理任務工作流調度問題中，路況復雜性大，實時推理任務各同，數量大，不可能對所有實時推理任務進行參數優化，所以MQ算法并不適用于本文所論述的問題.
目前對自動駕駛推理任務調度的研究相對不足，因此本文從協同設計任務與工作流調度研究方法出發，對邊緣環境下的自動駕駛產生的實時推理任務調度問題進行研究討論.一方面，本文設計了一種推理任務工作流調度策略，通過SA-QL優化推理任務工作流完成時間，在嚴格容忍時間限制滿足推理任務實時系統低時延的約束條件，提高自動駕駛過程中推理任務調度的成功率；另一方面，本文證明了SA-RL算法和PSO算法在自動駕駛推理任務工作流調度問題上的可行性，并進一步分析了SA-RL算法和PSO算法在自動駕駛推理任務工作流調度問題求解中的性能差異.
3 問題描述
3.1 問題定義
對于自動駕駛推理任務而言，任務具有實時性的特點，在不同時間窗內會產生不同實時推理任務，并且邊緣環境中邊緣節點數量也在不斷發生變化.圖1描述了邊緣環境下自動駕駛車輛產生的推理任務的不同以及邊緣節點在不同時間窗中的變化情況.
圖1 不同時間窗上邊緣環境及推理任務變化情況Fig.1 Change of edge environment and reasoning task in different time windows
(1)
(2)
(3)
(4)
為了在邊緣環境中更好地利用邊緣節點的計算資源，規定邊緣節點調度處理子任務要滿足特定的處理原則：
1)在相同邊緣節點上的子任務要按深度串行執行，若深度相等，則按子任務序號升序執行，子任務深度由公式(5)表示；
2)在不同邊緣節點上的子任務可并行執行；
3)每個子任務只能被一個邊緣節點所調度，由公式(6)表示；
4)當邊緣節點上分配的所有子任務傳輸完成時開始處理子任務.
(5)
(6)
(7)
(8)
根據以上定義，自動駕駛推理任務工作流調度問題可以形式化地描述為：合理指派子任務到各個邊緣節點上處理，結合推理任務工作流調度策略，在滿足實時推理任務可容忍時間、子任務間偏序約束以及邊緣節點處理原則下，優化實時推理任務完成時間，如公式(9)所示:
(9)
formula(6)
3.2 問題分析
圖2為某個時間窗下邊緣環境及自動駕駛車輛推理任務情況，此時邊緣環境中有2個邊緣節點{f1,f2}，自動駕駛汽車產生的實時推理任務可劃分為4個子任務{n1,n2,n3,n4}，子任務間有著4條時序約束有向邊{e1,2,e1,3,e2,4,e3,4}，可容忍時間為30毫秒.
圖2 邊緣環境及自動駕駛車輛推理任務情況Fig.2 Edge environment and reasoning task of autonomous vehicle
該實時推理任務存在可行調度方案，其邊緣節點-子任務匹配矩陣如表1所示，表2為邊緣節點-子任務平均傳輸時間矩陣，表3為邊緣節點-子任務平均完成時間矩陣，表4為子任務-子任務平均傳輸時間矩陣，實時推理任務調度過程如3所示，總完成時間為17毫秒，其中所有子任務傳輸至邊緣節點的傳輸時間為3毫秒，調度時間為14毫秒，最差調度下調度總時間為24毫秒，小于實時推理任務可容忍時間.
表1 邊緣節點-子任務匹配矩陣Table 1 Matching matrix between edge-node and sub-task
表2 邊緣節點-子任務平均傳輸時間矩陣Table 2 Average transmission time matrix between edge-node and sub-task
表3 邊緣節點-子任務平均完成時間矩陣Table 3 Average completion time matrix between edge-node and sub-task
圖
表4 子任務-子任務平均傳輸時間矩陣Table 4 Average transmission time matrix among sub-tasks
圖3 實時推理任務調度過程Fig.3 Scheduling process of real time reasoning task
4 基于強化學習算法的推理任務工作流調度策略
在自動駕駛汽車運行過程中，路況不斷發生變化，感知系統不斷將路況信息傳遞給推理系統，推理系統處理的實時推理任務在不斷變化，而這些實時推理任務往往有著不同的約束條件，為了在滿足約束條件的前提下，降低調度處理時延，提出一種推理任務工作流調度策略，在該策略下，假設自動駕駛車輛所處的邊緣環境為理想狀態，即在當前時間窗內邊緣環境中所有邊緣節點都沒有宕機的情況，其中推理任務工作流調度算法根據當前時間窗的邊緣環境及實時推理任務來計算完成時間.
4.1 推理任務工作流調度策略
在不同時間窗內，自動駕駛車輛產生的實時推理任務與邊緣環境將動態發生變化，有以下變化情況：
1)實時推理任務分解后的子任務數量；
2)實時推理任務分解后的子任務間偏序關系；
3)實時推理任務的可容忍時間；
4)當前時間窗可用邊緣節點數.
實時推理任務完成時間與自動駕駛車輛產生的實時推理任務與邊緣環境的變化有關，因此推理任務的完成時間就要在動態變化的邊緣環境中進行計算.
推理任務工作流調度算法如算法1所示.
算法1.推理任務工作流調度算法
輸入：si,mi,Gi,Ami×si,Cmi×si
1.初始化：入度數組I→?及節點隊列Q→?，直接前驅節點集合R→?，前驅任務數據最長傳輸時間T(i)→0
2.由Gi計算I(i)
3.將I(i)=0的節點入隊，設置當前深度p→1，已遍歷的節點數u→0，當前層的節點數k為當前隊列大小
4.whileQ≠?
5.ifu=kthen
6.p→p+1，u→0，k為當前隊列大小
7.end if
8. 隊首出隊，出隊節點為v，設置D(v)→p
9.u→u+1
10.fori←0tosi
11.if存在v至i的有向邊then
12. 將v加入R(i)
13.I(i)→I(i)-1
14.T(i)→MAX(T(i),V(v,i))
15.ifI(i)=0then
16. 將任務i加入Q
17.end if
18.end if
19.end for
20.end while
21.由Ami×si為邊緣節點分配子任務
22.同一邊緣節點中子任務按任務深度值升序排序
23.初始化：完成列表O→?,子任務剩余執行時間Y(i)=C(*,i)+T(i)，當前時間h→0
24.whileO中元素個數小于si
25. 為每個邊緣節點確定要執行的子任務,該子任務要滿足其直接前驅集合為O子集
26. 在當前執行的子任務中找出最少執行時間w
27.Y(i)→Y(i)-w，如果Y(i)=0，則加入O
28.h→h+w
29.end while
30.returnh
4.2 強化學習算法
4.2.1 馬爾可夫決策過程模型
馬爾可夫決策過程(Markov Decision Process,MDP)模型是強化學習算法的基本模型，由于現實環境中狀態轉移的概率往往和歷史狀態有關，這樣很難建立模型，因此可以根據馬爾科夫性(即無后效性，也就是指環境中的下個狀態只與當前狀態信息有關，而與歷史的狀態無關)來簡化模型，使得下個狀態只與當前狀態和所采取的動作有關[13].
本文所研究的任務調度問題有以下特點：
1)沒有任何的先驗模型；
2)狀態空間中可解狀態數隨子任務數以及可行解約束條件動態變化；
3)動作空間中的動作數與子任務數相等.
既要滿足子任務時序約束，又要滿足嚴格容忍時間約束
基于以上特點，本文的MDP模型如下：
·智能體：子任務
·狀態：邊緣節點-子任務分配矩陣
·動作：動作空間內動作數等于子任務數si，如果當前狀態au,k=1表示第k個子任務當前部署在第u個邊緣節點中，那么執行動作k后，au,k=0，ax,k=1，其中x=(u+1)%mi表示將第k個子任務部署到下一個邊緣節點
4.2.2 基于推理任務工作流調度策略的Q-learning算法
Q-learning是一種時序差分(Temporal-Difference,TD)算法，它基于隨機過程且不依賴模型(Model-Free)，無狀態轉化概率矩陣.由于算法更新價值函數時會選擇最大價值進行更新，而動作選擇不一定按最大價值所對應動作，因此會導致價值函數的樂觀估計，由于這一特性，Q-learning屬于離線策略(off-policy)學習方法[14].
Q-learning價值函數根據
Q-learning價值函數更新方式如下：
Q(s,a)=Q(s,a)+α[r+γmaxa′Q(s′,a′)-Q(s,a)]
(10)
其中α為學習效率，表示價值函數更新的程度，r為即時獎勵，表示轉移至下一個狀態所得到的獎勵，γ為折扣因子，表示后續狀態的價值對當前狀態的影響程度，maxa′Q(s′,a′)為選取的價值最大的狀態-動作對的值.
由于：
Qreal=r+γmaxa′Q(s′,a′)
(11)
Qeval=Q(s,a)
(12)
因此，價值函數更新公式可進一步表示為：
Q(s,a)=Q(s,a)+α(Qreal-Qeval)
(13)
即Q-learning價值函數的更新可表示為價值函數值加上現實值與估計值的差值與學習效率的乘積.
為了平衡算法的探索與開發，本文采用Metropolis準則[15]進行動作的選擇，其中退火策略采用等比降溫策略：
Tk=θkT0
(14)
其中T0為初始溫度，k為當前回合次數，θ為降溫系數.
為減小狀態-動作值表大小，減少狀態搜索耗時，本文選擇在可解狀態空間中進行探索，即算法中探索的所有狀態均滿足公式(9)中的約束條件.基于推理任務工作流調度策略的Q-learning算法如算法2所示.
算法2.基于推理任務工作流調度策略的Q-learning算法
輸入：回合數，回合迭代數，初始狀態，初始溫度
輸出：Q(s,a)
1.fori←0to回合數
2. 隨機選取動作，使初始狀態變為可行解
3.forj←0to回合迭代數
4. 根據Metropolis準則選擇動作，該動作轉移的狀態必須為可行解狀態
5. 執行動作，轉移狀態
7. 根據<當前狀態,選擇動作,即時獎勵,轉移后狀態>四元組信息由公式(10)進行價值函數的更新
8. 根據公式(14)進行對當前溫度進行降溫處理
9.end for
10.end for
5 算法實驗與分析
5.1 實驗參數設置
通過多次實驗調參結果，本文設置強化學習算法參數：α=0.01，γ=0.9，λ=0.5，λ為Sarsa(λ)[16]、Q(λ)[16]算法中效用跡矩陣衰減率，回合數為100，回合迭代數為1000；設置PSO算法參數：ω=0.9，c1=2，c2=2；設置模擬退火參數：T0=150，θ=0.9.
本文采用文獻[12]的調度實例，假設該實時推理任務可容忍時間為 60毫秒，任務分解后有7個子任務，子任務間時序約束的DAG如圖4所示.
圖4 子任務間時序約束的DAGFig.4 DAG with temporal constraints among sub-tasks
設當前邊緣環境中有3個可用邊緣節點，子任務在各邊緣節點上平均完成時間、平均傳輸時間、子任務間平均傳輸時間如表5、表6、表7所示.
表5 邊緣節點-子任務平均傳輸時間矩陣Table 5 Average transmission time matrix between edge-node and sub-task
表6 邊緣節點-子任務平均完成時間矩陣Table 6 Average completion time matrix between edge-node and sub-task
表7 子任務-子任務平均傳輸時間矩陣Table 7 Average transmission time matrix among sub-tasks
5.2 對比算法
為了驗證SA-RL算法在自動駕駛推理任務調度上的有效性，本文選擇TD(0)算法：Sarsa[17]，TD(λ)算法：Sarsa(λ)、Q(λ)作為對比算法.為了比較SA-RL與傳統啟發式算法的性能區別，本文選擇PSO[18]作為比較算法，其中PSO算法中粒子比較方式[19]如下：
1)兩個粒子都滿足可行解條件：選擇完成時間較小的粒子;
2)兩個粒子都不滿足可行解條件：選擇完成時間較小的粒子;
3)一個粒子滿足可行解條件，一個粒子不滿足可行解條件：選擇滿足可行解條件的粒子.
5.3 實驗結果與分析
本實驗的實驗環境為，CPU：Intel(R)Core(TM)i7-4720HQ CPU 2.60GHz，內存：8GB，操作系統：Windows 10，編程語言：Python.
由搜索算法可得狀態空間可解狀態數為2042個.
在該實例中，SA-RL算法和PSO算法均能找到2個最優邊緣節點-子任務匹配矩陣：
傳輸時間為3毫秒，實時推理任務最短的最佳運行時間均為32毫秒，匹配矩陣1對應分配策略的調度處理過程如圖5所示.
圖5 最優分配策略1調度處理過程Fig.5 Scheduling process of optimal allocation strategy 1
以圖5為例分析對應邊緣節點-子任務分配方案調度過程：
1)根據子任務深度與子任務序號為邊緣節點分配子任務：f1:{n1,n4,n5},f2:{n2,n7},f3:{n3,n6}；
2)經過3毫秒，所有子任務卸載到對應的邊緣節點上，子任務1卸載至邊緣節點1上執行，到6毫秒時子任務1完成；
3)子任務2經過卸載至邊緣節點2上，經過2毫秒任務間的數據傳輸時間，子任務開始執行，到10毫秒時，子任務2完成；
4)子任務3、4分別卸載至邊緣節點3、1上，經過1毫秒任務間的數據傳輸時間以及4毫秒的任務處理時間，到15毫秒時子任務4完成，此時子任務3還剩2毫秒的數據傳輸時間以及2毫秒的任務處理時間；
5)子任務5卸載至邊緣節點1進行任務調度，到19毫秒時，子任務3完成，此時子任務5還剩2毫秒的數據傳輸時間以及2毫秒的任務處理時間；
6)子任務6卸載至邊緣節點3進行任務調度，到23毫秒時，子任務5完成，此時子任務6還剩1毫秒的任務處理時間；
7)經過1毫秒，到24毫秒時，子任務6完成；
8)子任務7卸載至邊緣節點2進行任務調度，經過5毫秒任務間的數據傳輸時間以及3毫秒的任務處理時間，到32毫秒時完成調度.
SA-RL算法與PSO算法每10回合平均完成時間如圖6所示.隨著回合數不斷增加，各算法平均完成時間不斷降低，平均完成時間均低于可容忍時間.從圖中可以看出，回合剛開始，強化學習算法平均完成時間波動較小且維持在較高水平，這是因為初始溫度較高，因此選擇隨機動作的概率較大；但是隨著Metropolis準則的降溫處理，回合即將達到設定的回合數時，強化學習算法以接近于1的概率選擇最佳動作，因此算法平均完成時間不斷下降，其中Sarsa(λ)、Q(λ)算法收斂較早，這是因為算法中引入了效用跡矩陣，采用多步更新策略，因此能加快收斂速度.
圖6 每10回合平均完成時間Fig.6 Average completion time of every 10 rounds
除此之外，PSO算法的平均完成時間雖然一直在下降但是波動較大，平均完成時間會維持在較高水平，這是由于啟發式算法收斂速度慢、易陷入局部最優解的特點導致的.
SA-RL算法每10回合平均獎勵如圖7所示.隨著回合數不斷增加，各強化學習算法平均獎勵不斷提高，在后期收斂過程中Sarsa(λ)、Q(λ)的平均獎勵值維持在較高水平，這是由于算法收斂速度快，因此會更快得到更優的價值函數.
圖7 每10回合平均獎勵Fig.7 Average reward of every 10 rounds
SA-RL算法與PSO算法每10回合完成時間平均方差如圖8所示.從圖中可以看出PSO算法與SA-RL算法相比，平均方差維持在較高水平，平均完成時間波動較大.Sarsa(λ)、Q(λ)較其他強化學習算法而言，收斂較快，平均方差能維持在較低水平，平均完成時間波動較小.
圖8 每10回合完成時間平均方差Fig.8 Average variance of completion time
SA-RL算法運行5次探索到所有可解狀態數時的回合次數如表8所示.從表中可以看出SA-RL算法探索到所有可解狀態數的回合數相差不大，其中TD(λ)算法探索到所有可解狀態所需的回合次數少于TD(0).
表8 探索到所有可解狀態時的回合次數Table 8 Amount of rounds when SA-RL found all feasible states
SA-RL算法運行5次探索到所有可解狀態數時的耗時如表9所示.從表中可以看出當探索到所有可解狀態時，Q-learning、Sarsa較Sarsa(λ)、Q(λ)而言耗時較短，原因是Sarsa(λ)、Q(λ)算法進行學習時不僅要對遍歷過狀態的狀態-動作表進行更新，還要對效用跡矩陣進行更新，隨著狀態空間的增大，算法所要更新的表空間不斷增加，因此耗時較長.
表9 探索到所有可解狀態時的耗時Table 9 Time when SA-RL found all feasible states
綜上所述，對于自動駕駛實時推理任務工作流調度問題，SA-RL算法與PSO算法在實驗中均能找到符合約束條件的優解，均具備可行性的特點；強化學習算法與PSO算法每回合平均完成時間均隨著回合數增加不斷降低，不斷趨于收斂狀態，證明了強化學習算法與PSO算法的有效性；在探索可行解狀態過程中，Q-learning、Sarsa耗時較短，表明TD(0)算法探索性較強；由每回合平均完成時間與完成時間平均方差的變化，可以看出Sarsa(λ)、Q(λ)收斂較快，平均方差最終維持在較低水平，波動較小，表明TD(λ)算法的收斂性更強.
6 結 論
針對自動駕駛推理任務工作流調度問題，提出了一種基于強化學習算法的推理任務工作流調度策略.實驗結果表明，該策略能快速有效地找到滿足容錯時間的調度方案.SA-QL和Sarsa在探索可行狀態上所耗費的時間更少.這說明TD(0)算法更具探索性.從平均完成時間的變化以及平均方差可以看出，Sarsa(λ)和Q(λ)收斂更快.此外，Sarsa(λ)和Q(λ)的平均方差保持在較低水平，波動較小.實驗表明，TD(λ)算法具有良好的收斂性.
在未來的工作中，我們將考慮云計算和車聯網混合環境下的調度問題，以促進卸載設備的多樣性和任務調度的靈活性.此外，我們還將考慮使用RL算法結合深度學習技術來優化推理任務的完成時間.
