饒東寧，易善楨

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006）

概率規(guī)劃[1]是人工智能主要的研究方向之一。概率規(guī)劃問題的特點(diǎn)是并行性和概率性。并行性表示動(dòng)作可以并行執(zhí)行，概率性表示動(dòng)作的效果具有概率性[2]。并且概率規(guī)劃更加注重求解的過程，即最大累計(jì)獎(jiǎng)勵(lì)值，所以被廣泛用于現(xiàn)實(shí)問題的處理當(dāng)中。對于現(xiàn)實(shí)問題中動(dòng)作執(zhí)行需要一定時(shí)間的問題，使用考慮動(dòng)作執(zhí)行時(shí)間的時(shí)態(tài)規(guī)劃[3]對該類問題進(jìn)行求解。文獻(xiàn)[4]將概率規(guī)劃用于股票指數(shù)模擬與分析當(dāng)中，使用基于抽樣的方法進(jìn)行模擬，最終的模擬效果可以貼近真實(shí)的股票變化趨勢。

概率規(guī)劃描述的是一類具有大狀態(tài)空間的馬爾可夫決策問題,文獻(xiàn)[5]研究了概率規(guī)劃中計(jì)算的復(fù)雜性。而蒙特卡洛方法[6-7]是能夠接近最優(yōu)解的方法之一，文獻(xiàn)[8]使用了蒙特卡洛規(guī)劃處理大規(guī)模部分可觀察的馬爾科夫決策問題。目前主流的規(guī)劃器都是基于UCT[9](Upper Confidence Bounds on Trees)算法實(shí)現(xiàn)的。UCT將強(qiáng)盜算法的上置信區(qū)間應(yīng)用到基于蒙特卡洛樹搜索的規(guī)劃算法中。文獻(xiàn)[10]使用受UCT算法啟發(fā)的隨機(jī)搜索策略，在復(fù)雜空間中可以漸進(jìn)收斂。當(dāng)前表現(xiàn)最好的規(guī)劃器為SOGBOFA[11],其使用聚合模擬推導(dǎo)出計(jì)算圖，并通過基于梯度的搜索選擇最優(yōu)動(dòng)作，可以動(dòng)態(tài)平衡蒙特卡洛搜索和梯度搜索，加快收斂速度同時(shí)提高求解性能。文獻(xiàn)[12]提出了一種概率機(jī)器人規(guī)劃框架，使用一系列的生成程序構(gòu)建領(lǐng)域文件，并在框架中集成了最新的SOGBOFA規(guī)劃器，進(jìn)一步提高了概率規(guī)劃和機(jī)器人系統(tǒng)的集成度。

眾包技術(shù)[13]早已在商業(yè)上實(shí)現(xiàn)，主要的思想是將任務(wù)分派出去，利用不同的個(gè)體獨(dú)立處理任務(wù)。受此啟發(fā)將眾包概念和概率規(guī)劃結(jié)合，通過集成多個(gè)規(guī)劃器處理復(fù)雜的概率規(guī)劃問題。由于概率規(guī)劃中存在約束條件，拆分和合并規(guī)劃任務(wù)非常困難，所以對于每個(gè)規(guī)劃器來說，都需要獨(dú)立處理完整的規(guī)劃任務(wù)，即根據(jù)輸入狀態(tài)計(jì)算出可行動(dòng)作集。

目前概率規(guī)劃問題的求解存在很多的困難和挑戰(zhàn)。概率規(guī)劃問題具有并行和概率的特性，這導(dǎo)致其具有很大的狀態(tài)空間；隨著領(lǐng)域?qū)嵗?guī)模的增大，狀態(tài)空間也會(huì)呈指數(shù)的趨勢增大。同時(shí)越復(fù)雜領(lǐng)域，驗(yàn)證動(dòng)作的約束條件和狀態(tài)的演化過程也越慢，使得基于模擬的算法無法獲取最優(yōu)策略[14]。由于概率規(guī)劃的動(dòng)作是并行的，并且需要統(tǒng)一進(jìn)行動(dòng)作集的約束檢查，所以很難拆分概率規(guī)劃問題。同時(shí)，概率規(guī)劃領(lǐng)域現(xiàn)有的規(guī)劃器都是單線程求解，也缺乏眾包結(jié)合概率規(guī)劃問題的相關(guān)研究。針對以上問題本文提出了基于蒙特卡洛樹搜索的眾包概率規(guī)劃算法，主要的工作如下：

(1) 提出了一個(gè)通用的眾包概率規(guī)劃框架，通過集成多個(gè)規(guī)劃器共同處理規(guī)劃問題。該框架可以整合多個(gè)規(guī)劃器的信息，并將最優(yōu)解信息共享給所有規(guī)劃器，提高求解效率。

(2) 提出了一種基于蒙特卡洛樹搜索的評價(jià)算法，使用改進(jìn)的蒙特卡洛采樣構(gòu)建前瞻樹，并計(jì)算狀態(tài)-動(dòng)作對的評價(jià)值，用于選擇最優(yōu)動(dòng)作。

(3) 對眾包框架和評價(jià)算法進(jìn)行優(yōu)化操作，提高框架的擴(kuò)展性和求解效率。

1 概率規(guī)劃

第四屆國際規(guī)劃比賽首次引入了概率規(guī)劃的比賽項(xiàng)目[15]，即國際概率規(guī)劃比賽(International Probabilistic Planning Competitions，IPPC)，在原有狀態(tài)轉(zhuǎn)移的過程中加入了隨機(jī)性。概率規(guī)劃描述的是抽象的馬爾科夫決策過程(Factored Markov Decision Process，F(xiàn)actored MDP)[16]。使用六元組T=＜V,A,P,R,h,S0＞[17]來表示Factored MDP問題，其中V為狀態(tài)集；S0為初始狀態(tài)；h為迭代步數(shù)，可為任意實(shí)數(shù)；P為轉(zhuǎn)移函數(shù)用于計(jì)算動(dòng)作A由狀態(tài)S轉(zhuǎn)移至S'的概率；R為獎(jiǎng)勵(lì)值計(jì)算函數(shù)[18]。概率規(guī)劃的目標(biāo)是在完成指定次數(shù)的迭代后最大化累計(jì)獎(jiǎng)勵(lì)值表示為

其中：rh為迭代步h的獎(jiǎng)勵(lì)值，horizon為總迭代次數(shù)。

為了更高效地表示概率規(guī)劃問題中動(dòng)作的并發(fā)和效果的概率性，在IPPC-2011開始，RDDL(Relational Dynamic Influence Diagram Language)[15]被用作概率規(guī)劃的描述語言。RDDL使用動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)(Dynamic Bayes Net，DBN)來表示Factored MDP問題中的動(dòng)作、狀態(tài)和概率轉(zhuǎn)換。RDDL可以支持多種變量類型和多層的動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)，更好地支持動(dòng)作的并發(fā)。IPPC官方提供了RDDL文件的解析和模擬工具rddlsim (RDDL Simulator)[19]進(jìn)行相關(guān)約束檢查和模擬狀態(tài)演化等操作。也有PlanVerb[20]這樣可以將RDDL文件和規(guī)劃器的輸出轉(zhuǎn)化為更容易理解的自然語言描述和因果解釋的方法。為保證公平性，IPPC中使用在線的方式評估參賽規(guī)劃器，其由調(diào)用rddlsim的服務(wù)端和調(diào)用規(guī)劃器客戶端組成[21]，在線評價(jià)方法如算法1所示。

算法1 IPPC在線評價(jià)算法

算法1中round為執(zhí)行輪次，服務(wù)端通過多輪執(zhí)行求得平均獎(jiǎng)勵(lì)值，避免小概率的極值影響整體評價(jià)的準(zhǔn)確性。客戶端的主要作用是初始化領(lǐng)域文件，同時(shí)將規(guī)劃器計(jì)算的結(jié)果發(fā)送給服務(wù)端，服務(wù)端和客戶端共同組成了在線評價(jià)算法。算法1輸入的客戶端負(fù)責(zé)調(diào)用規(guī)劃器，規(guī)劃器需要根據(jù)當(dāng)前狀態(tài)S找到可執(zhí)行動(dòng)作集。為了保證求得的動(dòng)作滿足約束條件，規(guī)劃器和客戶端都會(huì)進(jìn)行約束檢查，防止錯(cuò)誤的解影響后續(xù)的迭代過程。步驟4～9是一輪完整的概率規(guī)劃過程，horizon為規(guī)劃的步長，在領(lǐng)域的初始參數(shù)中給出。

2 算法設(shè)計(jì)

2.1 眾包概率規(guī)劃框架

受眾包的啟發(fā)，在概率規(guī)劃中引入眾包的概念，利用不同形式計(jì)算資源處理規(guī)劃問題。該框架通過集成多個(gè)規(guī)劃器共同參與計(jì)算，并根據(jù)狀態(tài)-動(dòng)作評價(jià)算法選擇評價(jià)值最優(yōu)的動(dòng)作，以便獲得最優(yōu)解。同時(shí)該框架可以整合不同規(guī)劃器返回的結(jié)果，將當(dāng)前最優(yōu)解信息共享給其他的規(guī)劃器，在多個(gè)規(guī)劃器之間共享求解信息，從而增加跳出局部最優(yōu)解的能力，提高算法的求解性能。參考IPPC在線評價(jià)過程，眾包概率規(guī)劃框架由發(fā)布規(guī)劃任務(wù)的服務(wù)端和調(diào)用規(guī)劃器的客戶端兩部分組成。與算法1相比，眾包概率規(guī)劃框架中的服務(wù)端需要同時(shí)連接多個(gè)客戶端共同求解規(guī)劃問題。其中每個(gè)客戶端調(diào)用一個(gè)規(guī)劃器，規(guī)劃器的功能保持不變，依然是求解當(dāng)前狀態(tài)下的可行動(dòng)作集。眾包概率規(guī)劃框架如算法2所示。

算法2 眾包概率規(guī)劃框架

2.1.1 服務(wù)端流程

服務(wù)端主要負(fù)責(zé)與客戶端進(jìn)行交互，并存儲(chǔ)迭代過程中產(chǎn)生的信息。為了分擔(dān)服務(wù)端的計(jì)算壓力，將后繼狀態(tài)演化的過程放在客戶端。這樣的任務(wù)分配可以使服務(wù)端有更好的擴(kuò)展性，客戶端數(shù)量的增減不會(huì)影響服務(wù)端的效率。同時(shí)也可以保證每個(gè)客戶端擁有固定的計(jì)算任務(wù)，客戶端之間也互不影響。服務(wù)端的主要3個(gè)功能為對每個(gè)客戶端分派規(guī)劃任務(wù)，根據(jù)客戶端返回的信息和選擇最優(yōu)的動(dòng)作集并更新相應(yīng)的迭代信息。眾包概率規(guī)劃服務(wù)端的流程圖如圖1所示。

圖1 眾包概率規(guī)劃服務(wù)端流程圖Fig.1 Flow chart of crowdsourcing based probabilistic planning server

2.1.2 客戶端流程

客戶端主要負(fù)責(zé)調(diào)用規(guī)劃器求解規(guī)劃問題，進(jìn)行狀態(tài)演化和適應(yīng)度計(jì)算。每個(gè)客戶端都調(diào)用一個(gè)特定規(guī)劃器參與計(jì)算?？蛻舳耸紫韧ㄟ^規(guī)劃器，找到當(dāng)前狀態(tài)下的可執(zhí)行動(dòng)作集；然后使用rddlsim進(jìn)行約束檢查、獎(jiǎng)勵(lì)值計(jì)算，并根據(jù)領(lǐng)域描述隨機(jī)生成后繼狀態(tài)；計(jì)算對應(yīng)的狀態(tài)-動(dòng)作對的評價(jià)值；最后將可執(zhí)行動(dòng)作集、獎(jiǎng)勵(lì)值、后繼狀態(tài)、評價(jià)值等參數(shù)返回給服務(wù)端。眾包概率規(guī)劃客戶端的流程圖如圖2所示。

圖2 眾包概率規(guī)劃客戶端流程圖Fig.2 Flow chart of crowdsourcing based probabilistic planning client

2.1.3 通信協(xié)議

相比于IPPC中的消息傳輸，本框架中的交互次數(shù)和每次傳輸?shù)男畔⒘慷加兴黾?。為了統(tǒng)一格式，本文參考IPPC的通信協(xié)議[21]，并在此基礎(chǔ)上使用二進(jìn)制編碼方法，對狀態(tài)和動(dòng)作進(jìn)行編碼和解碼操作。通過傳輸編碼減少消息的大小，減少通信的時(shí)間消耗。眾包概率規(guī)劃中增加了客戶端的數(shù)量，所以服務(wù)端之間的通信次數(shù)也有所增加。但由于客戶端和服務(wù)端可以并行收發(fā)消息，和IPPC在線評價(jià)過程相比，通信的代價(jià)并沒有增加。

服務(wù)端需要接收所有客戶端返回的計(jì)算結(jié)果，用于下一次的迭代操作。其中就包含狀態(tài)的演化結(jié)果、所執(zhí)行的動(dòng)作集、狀態(tài)-動(dòng)作對的評價(jià)值以及動(dòng)作的獎(jiǎng)勵(lì)值等信息。服務(wù)端接收消息后更新迭代信息，并進(jìn)入到下一次迭代。在下一次迭代開始時(shí)，服務(wù)端會(huì)選擇上一次迭代的最優(yōu)動(dòng)作對應(yīng)的后繼狀態(tài)，并發(fā)送給所有的客戶端，共享全局的求解信息?？蛻舳诵枰?dú)立完成一步的規(guī)劃過程，需要從服務(wù)端接收上一步的最優(yōu)解和迭代步數(shù)等信息。圖3使用順序圖表示眾包概率規(guī)劃框架中服務(wù)端與每個(gè)客戶端的交互過程，不同客戶端之間是獨(dú)立且并行的。

圖3 眾包概率規(guī)劃框架順序圖Fig.3 Sequence diagram of crowdsourcing based probabilistic planning framework

在消息傳輸過程中，不可避免地會(huì)出現(xiàn)消息傳輸異常的情況。如在運(yùn)行過程中服務(wù)端接收客戶端異常消息，會(huì)直接忽略對應(yīng)客戶端的消息，使用剩下客戶端返回的信息進(jìn)行計(jì)算。如遇到以下異常情況會(huì)重啟客戶端和服務(wù)端：在會(huì)話開始的階段發(fā)生消息傳輸異常、客戶端和服務(wù)端連接異常以及會(huì)影響到求解過程的異常情況。

2.2 狀態(tài)-動(dòng)作評價(jià)算法

對于多個(gè)客戶端返回的迭代信息，本文使用統(tǒng)一的評價(jià)算法，用于評價(jià)并選擇最優(yōu)的迭代信息。概率規(guī)劃中即時(shí)獎(jiǎng)勵(lì)值只能體現(xiàn)當(dāng)前狀態(tài)和動(dòng)作的即時(shí)效果，并不能反映當(dāng)前動(dòng)作對后續(xù)結(jié)果的影響[22]和后繼狀態(tài)概率分布的期望。所以不能使用即時(shí)獎(jiǎng)勵(lì)值作為評價(jià)的唯一標(biāo)準(zhǔn)。由于概率規(guī)劃的目標(biāo)為最大化累計(jì)獎(jiǎng)勵(lì)，估計(jì)當(dāng)前動(dòng)作對后續(xù)產(chǎn)生的影響，將是評價(jià)算法重要的部分。動(dòng)作對后續(xù)的影響主要表現(xiàn)為后續(xù)幾步迭代中狀態(tài)概率分布的期望。所以本文提出了統(tǒng)一的狀態(tài)-動(dòng)作對評價(jià)算法，使用當(dāng)前動(dòng)作的即時(shí)獎(jiǎng)勵(lì)值和狀態(tài)期望的估計(jì)值共同作為狀態(tài)-動(dòng)作對的評價(jià)值，用于對客戶端返回信息進(jìn)行評估。

狀態(tài)-動(dòng)作的評價(jià)值為基于蒙特卡洛樹搜索算法計(jì)算出的狀態(tài)估計(jì)值和執(zhí)行當(dāng)前動(dòng)作的即時(shí)獎(jiǎng)勵(lì)值的加權(quán)和。其中的權(quán)值為一個(gè)自適應(yīng)參數(shù)，在迭代初期估計(jì)值所占權(quán)重更大，有利于全局搜索；而在迭代后期即時(shí)獎(jiǎng)勵(lì)所占比重更大，有利于局部搜索；動(dòng)態(tài)地平衡全局和局部搜索，可以增加找到最優(yōu)解的概率。評價(jià)值計(jì)算公式為

式中：ri為動(dòng)作i的即時(shí)獎(jiǎng)勵(lì)值，avg_ej為狀態(tài)j基于蒙特卡洛樹搜索的平均估計(jì)值，h為當(dāng)前的迭代步數(shù)，horizon為總的迭代次數(shù)。估計(jì)值的計(jì)算主要分為構(gòu)建前瞻樹和回溯更新估計(jì)值兩部分。

2.2.1 構(gòu)建前瞻樹

估計(jì)值是對動(dòng)作產(chǎn)生的影響進(jìn)行估計(jì)，也是對狀態(tài)的期望進(jìn)行估計(jì)。使用基于蒙特卡洛樹搜索算法的超前搜索建立前瞻樹，然后從前瞻樹葉子結(jié)點(diǎn)回溯，逐步計(jì)算狀態(tài)的估計(jì)值。本文將模擬規(guī)劃執(zhí)行的步數(shù)定義為搜索深度，將每個(gè)狀態(tài)的后繼狀態(tài)個(gè)數(shù)稱為分支因子數(shù)。前瞻樹中的節(jié)點(diǎn)表示狀態(tài)，邊表示執(zhí)行的動(dòng)作，產(chǎn)生的獎(jiǎng)勵(lì)值為邊的權(quán)值。

本文采用了改進(jìn)的蒙特卡洛樹搜索方法，蒙特卡洛樹搜索是基于抽樣的搜索算法，有很強(qiáng)的通用性，可以應(yīng)用到有不同的領(lǐng)域需求和變量類型的領(lǐng)域中。為了更好地對當(dāng)前狀態(tài)的概率分布進(jìn)行估計(jì)，需要有足夠多的后繼狀態(tài)，這就需要多次對當(dāng)前狀態(tài)進(jìn)行采樣，模擬出盡可能多的后繼狀態(tài)。

蒙特卡洛樹搜索算法是通過多次模擬，構(gòu)建搜索樹。但這種方式得到的分支因子較小，不能準(zhǔn)確評價(jià)狀態(tài)的期望。同時(shí)這種模擬優(yōu)先進(jìn)行深度探索，但概率規(guī)劃中深度越大估計(jì)值的隨機(jī)性就越強(qiáng)，進(jìn)而導(dǎo)致估值不準(zhǔn)。本文使用改進(jìn)的蒙特卡洛樹搜索構(gòu)建前瞻樹，優(yōu)先對分支因子進(jìn)行擴(kuò)展而不是深度搜索。足夠大的分支因子可以降低后繼狀態(tài)概率分布期望的估值誤差[23]，在保證當(dāng)前估值準(zhǔn)確的前提下進(jìn)行深度搜索。構(gòu)建前瞻樹步驟如算法3所示。

算法3 構(gòu)建前瞻樹

算法3的輸入為狀態(tài)搜索列表List，每次會(huì)擴(kuò)展?fàn)顟B(tài)搜索列表List中第一個(gè)節(jié)點(diǎn)，直到時(shí)間結(jié)束。輸出的前瞻樹只在第一次迭代的時(shí)候才會(huì)初始化，在后續(xù)的迭代過程中不斷地更新前瞻樹。

圖4表示的是前瞻樹構(gòu)建過程中的一步，當(dāng)前狀態(tài)為S1，對應(yīng)算法3中步驟4、5。步驟4通過使用增強(qiáng)的隨機(jī)搜索策略和自適應(yīng)的時(shí)間限制，找到一個(gè)動(dòng)作a1。步驟5為調(diào)用rddlsim執(zhí)行動(dòng)作a1生成后繼狀態(tài)S'2，并計(jì)算獎(jiǎng)勵(lì)值r12。步驟5允許執(zhí)行重復(fù)的動(dòng)作，這時(shí)如果得到的后繼狀態(tài)不同就會(huì)出現(xiàn)圖4的S'3和S'4這種情況，而獎(jiǎng)勵(lì)值只受動(dòng)作和當(dāng)前狀態(tài)影響，所以r13和r14是相同的。重復(fù)執(zhí)行步驟4～6就會(huì)得到圖4中的狀態(tài){S'2,S'3,S'4,S'5}及對應(yīng)的節(jié)點(diǎn)。

圖4 構(gòu)建前瞻樹Fig.4 Building the lookahead tree

算法3的步驟2和步驟8中都可能會(huì)出現(xiàn)狀態(tài)重復(fù)的情況，這時(shí)就需要消除重復(fù)狀態(tài)。為了減小存儲(chǔ)前瞻樹所消耗的空間，使用2.1.3節(jié)中的二進(jìn)制編碼方式，在節(jié)點(diǎn)和邊中存儲(chǔ)動(dòng)作和狀態(tài)的編碼。為了防止前瞻樹無限增長，對其最大節(jié)點(diǎn)數(shù)也做了限制。當(dāng)超過最大節(jié)點(diǎn)數(shù)時(shí)，會(huì)刪除那些長時(shí)間未訪問的節(jié)點(diǎn)。在步驟2中遇到重復(fù)狀態(tài)時(shí)，就可以直接使用之前計(jì)算的結(jié)果，減少計(jì)算次數(shù)，加快收斂速度。步驟8使用實(shí)際采樣的結(jié)果計(jì)算概率分布。

受時(shí)間的限制，需要在有限時(shí)間內(nèi)優(yōu)先擴(kuò)展分支因子，所以擴(kuò)展的深度是動(dòng)態(tài)變化的。步驟9中的最大深度限制僅用于迭代后期，目的是防止采樣深度超過剩余迭代次數(shù)，而浪費(fèi)計(jì)算資源。

2.2.2 回溯計(jì)算估計(jì)值

采用對前瞻樹回溯的方式，從葉子結(jié)點(diǎn)開始計(jì)算節(jié)點(diǎn)的估計(jì)值。節(jié)點(diǎn)i的估計(jì)值為邊的權(quán)值和對應(yīng)后繼狀態(tài)估計(jì)值的加權(quán)平均，計(jì)算公式為

式中：NS為節(jié)點(diǎn)i的子節(jié)點(diǎn)的集合；rij為節(jié)點(diǎn)i和j之間的邊的權(quán)值，為執(zhí)行動(dòng)作的即時(shí)獎(jiǎng)勵(lì)值；pj為節(jié)點(diǎn)j對應(yīng)狀態(tài)出現(xiàn)的概率；葉子結(jié)點(diǎn)初始適應(yīng)度為0。

節(jié)點(diǎn)的概率為其中的狀態(tài)出現(xiàn)的次數(shù)/總采樣次數(shù)。如圖4所示，其中沒有出現(xiàn)重復(fù)狀態(tài)的情況，那么每個(gè)狀態(tài)的概率為0.25。所以狀態(tài)S1的估計(jì)值計(jì)算公式為e1=0.25 (r12+e2) + 0.25 (r13+e3) + 0.25 (r14+e4) + 0.25 (r15+e5)。

受時(shí)間的影響，不同的客戶端計(jì)算的搜索的深度不確定，所以使用平均估值作最終的狀態(tài)估值，即

式中：deep為節(jié)點(diǎn)j的深度，ej為節(jié)點(diǎn)j的估計(jì)值。

使用隨機(jī)抽樣的方式進(jìn)行模擬，將模擬過程的獎(jiǎng)勵(lì)值作為狀態(tài)的估計(jì)值，用于評價(jià)動(dòng)作對后續(xù)規(guī)劃的“影響”。當(dāng)模擬的分支因子足夠大就可以近似估計(jì)后繼狀態(tài)的概率分布；模擬搜索深度越大時(shí)，估計(jì)值就越接近于動(dòng)作的真實(shí)獎(jiǎng)勵(lì)值。在時(shí)間充裕的極限情況下，本算法可以遍歷所有的情況，得到的估計(jì)值就是實(shí)際概率分布的期望值。

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用IPPC中的基準(zhǔn)領(lǐng)域作為測試，包括IPPC-2014[24]的4個(gè)領(lǐng)域(Elevators、Skill teaching、Tamarisk、Traffic)和IPPC-2018[25]的4個(gè)領(lǐng)域(Academic Advising、Cooperative Recon、Manufacturer、Red-finned Blue-eye)作為實(shí)驗(yàn)的測試集。每個(gè)領(lǐng)域有10個(gè)實(shí)例，每個(gè)實(shí)例運(yùn)行75輪，記錄平均的獎(jiǎng)勵(lì)值和每輪獎(jiǎng)勵(lì)值的標(biāo)準(zhǔn)差，用于結(jié)果分析。實(shí)驗(yàn)環(huán)境為Ubuntu 20.04.3， Intel Core(TM) i7-11 700 @2.5GHz，31.2 GB RAM，使用java1.8實(shí)現(xiàn)算法。實(shí)驗(yàn)分為不同策略之間的性能對比和本算法的擴(kuò)展性對比兩部分。

3.2 策略對比實(shí)驗(yàn)

本節(jié)主要對比本文方法在最優(yōu)參數(shù)設(shè)定下和其他策略之間的性能差異。由于目前沒有眾包結(jié)合概率規(guī)劃的相關(guān)工作，本文使用最優(yōu)的SOGBOFA規(guī)劃器和使用最廣泛的Random規(guī)劃器作為客戶端的規(guī)劃器，同時(shí)使用單一客戶端的SOBBOFA和Random共同作為基準(zhǔn)策略。采用IPC得分[11]作為評價(jià)指標(biāo)，將每個(gè)策略的平均累計(jì)獎(jiǎng)勵(lì)進(jìn)行歸一化處理。使用同一實(shí)例中表現(xiàn)最優(yōu)和最差的策略返回的解計(jì)算得分，獎(jiǎng)勵(lì)值最高的策略對應(yīng)的得分為1，最低的得分為0。IPC得分提供了一個(gè)標(biāo)準(zhǔn)化分?jǐn)?shù)，已經(jīng)成為對比不同策略的標(biāo)準(zhǔn)方法。獎(jiǎng)勵(lì)值得分sri計(jì)算公式為

式中：ri為當(dāng)前策略的獎(jiǎng)勵(lì)值，rmax為最優(yōu)策略對應(yīng)的獎(jiǎng)勵(lì)值，rmin為最差策略對應(yīng)的獎(jiǎng)勵(lì)值。

為了比較不同策略的求解穩(wěn)定性，同時(shí)計(jì)算每個(gè)策略75輪的標(biāo)準(zhǔn)差，并計(jì)算標(biāo)準(zhǔn)差得分，計(jì)算公式為

式中：di為當(dāng)前策略的獎(jiǎng)勵(lì)值標(biāo)準(zhǔn)差，dmax為所有策略中最大的標(biāo)準(zhǔn)差，dmin為所有策略中最小的標(biāo)準(zhǔn)差。

表1為對比的策略名以及對應(yīng)的參數(shù)設(shè)置。 其中的Rand和SOG使用單一客戶端的策略，測試隨機(jī)(Random)規(guī)劃器和SOGBOFA規(guī)劃器的性能；GCR(Greedy Crowdsourcing Based Probabilistic Planning with Random)和GCS(Greedy Crowdsourcing Based Probabilistic Planning with SOGBOFA)使用即時(shí)獎(jiǎng)勵(lì)作為評價(jià)值的貪心眾包概率規(guī)劃框架策略；ECR(Evaluation Based Crowdsourcing Based Probabilistic Planning with Random)和ECS(Evaluation Based Crowdsourcing Based Probabilistic Planning with SOGBOFA)使用狀態(tài)-動(dòng)作評價(jià)算法的眾包概率規(guī)劃框架策略，后面的數(shù)字為客戶端的個(gè)數(shù)；ECRS是ECR和ECS兩個(gè)策略的融合，使用混合客戶端的策略。實(shí)驗(yàn)結(jié)果如表2所示，為不同策略的平均獎(jiǎng)勵(lì)值得分和標(biāo)準(zhǔn)差得分情況。

表1 不同策略的參數(shù)設(shè)置Table 1 Parameter settings of different policies

表2 不同策略的平均獎(jiǎng)勵(lì)值得分和標(biāo)準(zhǔn)差得分Table 2 The reward scores and deviation scores of different policies

首先對比Rand、GCR、ECR-5三個(gè)策略，從得分來看，使用了眾包框架的GCR和ECR兩個(gè)策略相較于Rand都有一定的提升，分別獲得了4.35和32.64的得分。而對比GCR和ECR發(fā)現(xiàn)，由于ECR使用了評價(jià)算法，結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于使用即時(shí)獎(jiǎng)勵(lì)為評價(jià)值的GCR的策略。

為了保證對比的公平性，對于SOG策略設(shè)定單步的時(shí)間限制為2.5 s；使用5個(gè)客戶端的GCS和ECS-5，單步時(shí)間總限制為0.5 s。假設(shè)在相同的硬件條件下，1個(gè)策略運(yùn)行2.5 s和5個(gè)相同策略運(yùn)行0.5 s消耗了同樣的計(jì)算資源。由表2可知，在相同資源限制下，使用了貪心眾包規(guī)劃框架的GCS取得了和SOG相近的分?jǐn)?shù)。雖然ECS-5加入了評價(jià)算法，進(jìn)一步壓縮了每個(gè)客戶端中SOGBOFA的單步時(shí)間，但求解效果遠(yuǎn)遠(yuǎn)領(lǐng)先同樣條件下的SOG和GCS策略。表明本眾包概率規(guī)劃框架有著很小的性能損失，同時(shí)基于蒙特卡洛樹搜索的狀態(tài)-動(dòng)作評價(jià)算法具有很小評價(jià)誤差，對算法性能的提升有正向的作用。

表2中GCR、ECS-5的標(biāo)準(zhǔn)差相對Rand和SOG有一定的提升。而帶有評價(jià)算法的眾包概率規(guī)劃策略ECR和ECS-5在標(biāo)準(zhǔn)差方面又有進(jìn)一步的提升。說明眾包概率規(guī)劃框架和狀態(tài)-動(dòng)作評價(jià)算法在求解穩(wěn)定性上也有一定提升。

為了測試眾包概率規(guī)劃對不同規(guī)劃器的兼容性和求解能力，利用有限的資源，進(jìn)行了ECS-10和ECRS兩組額外的實(shí)驗(yàn)。在ECS-10中，放寬了資源的限制，使用10個(gè)客戶端從而得到了當(dāng)前策略中的最高分，并在7個(gè)領(lǐng)域中都取得了最高分。在ECRS的客戶端使用了Random和SOGBOFA兩種不同的規(guī)劃器，雖然最終的效果不如ECS-5，但也說明了使用不同種類規(guī)劃器混合處理規(guī)劃問題的可行性。

3.3 擴(kuò)展性實(shí)驗(yàn)

本節(jié)對眾包概率規(guī)劃框架的擴(kuò)展性進(jìn)行檢測，測試隨著客戶端數(shù)量的增加，算法的整體求解效果以及運(yùn)行時(shí)間的差異。使用性能最低的策略作為本實(shí)驗(yàn)的基準(zhǔn)策略，計(jì)算其他策略的性能提升比例。提升比例可以清晰展現(xiàn)求解性能相對于基準(zhǔn)策略的好壞。使用式(8)計(jì)算不同策略的提升比例。

式中：ri表示當(dāng)前策略的獎(jiǎng)勵(lì)值，rbase為基準(zhǔn)策略的獎(jiǎng)勵(lì)值。

提升比例可以直觀地表示不同參數(shù)設(shè)置對于求解效果的影響，采用效果最差的Random規(guī)劃器，即客戶端數(shù)量為1的策略作為計(jì)算比例的基準(zhǔn)。實(shí)驗(yàn)結(jié)果如表3所示。

表3 對比不同客戶端個(gè)數(shù)的提升比例Table 3 Comparison the increase ratio of different client numbers

表3的cooperative-recon領(lǐng)域中，Random規(guī)劃器求解到的累計(jì)獎(jiǎng)勵(lì)值為零，出現(xiàn)無法計(jì)算提升比例的情況；對于剩下的策略來說，隨著客戶端數(shù)量的增加，有一定概率找到可執(zhí)行動(dòng)作并取得正的獎(jiǎng)勵(lì)值，所以在cooperative-recon領(lǐng)域中剩下的策略不會(huì)差于Random規(guī)劃器。在academic-advising中隨著客戶端數(shù)量增加，性能提升并不明顯，甚至在manufacturer領(lǐng)域中還有降低，說明在這兩個(gè)領(lǐng)域中目前的評價(jià)算法還存在很大的改進(jìn)空間。但綜合來看隨著客戶端數(shù)量的上升，求解性能也不斷增加；客戶端個(gè)數(shù)為10相比于Random規(guī)劃器有著平均68%的提升。隨著客戶端數(shù)量的增加，服務(wù)端的計(jì)算壓力并沒有明顯增加，說明調(diào)用不同規(guī)劃器的客戶端之間可以保持并行，擴(kuò)展性不受影響。

4 結(jié)語

本文針對概率規(guī)劃的求解困難，提出了基于蒙特卡洛樹搜索的眾包概率規(guī)劃算法，成功將眾包和概率規(guī)劃結(jié)合。根據(jù)眾包的思想，使用多個(gè)規(guī)劃器共同處理概率規(guī)劃問題，同時(shí)充分利用有限的計(jì)算資源。實(shí)驗(yàn)結(jié)果表明本算法有著很小的性能損失，在相同資源限制下，求解效果和穩(wěn)定性方面都有優(yōu)勢。在計(jì)算資源充足的情況下可以加快問題的求解，同時(shí)提升求解質(zhì)量。在今后的工作中可以繼續(xù)對評價(jià)算法進(jìn)行改進(jìn)，改進(jìn)實(shí)驗(yàn)中表現(xiàn)較差的manufacturer領(lǐng)域，提高評價(jià)算法的效率，盡可能降低評價(jià)誤差。