《半Markov決策過程基於靈敏度最佳化及其套用》是依託哈爾濱工業大學，由李衍傑擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：半Markov決策過程基於靈敏度最佳化及其套用
- 依託單位：哈爾濱工業大學
- 項目類別：青年科學基金項目
- 項目負責人：李衍傑
項目摘要,結題摘要,
項目摘要
半Markov決策過程(SMDP)最佳化算法在隨機動態系統的性能最佳化方面起到重要的作用。目前SMDP最佳化算法多受到維數災、模型災、收斂速度慢和存儲量大等問題的限制。本項目擬從SMDP性能靈敏度（包括性能差和性能導數）的角度，重點研究平均報酬準則下的SMDP的最佳化算法及其在多機器人協調控制問題中的套用，主要包括：（1）利用SMDP樣本軌道的攝動分析，研究SMDP性能靈敏度的勢結構特性；（2）基於SMDP性能差公式，研究SMDP基於值函式的強化學習算法；基於SMDP性能導數公式，研究SMDP策略梯度學習算法；（3）融合時間集中的思想，研究時間集中的基於值函式的強化學習算法和策略梯度學習算法；同時利用SMDP模型及其性能靈敏度闡明時間集中方法的機理，探索時間集中方法在MDP最佳化算法中的套用；（4）以多機器人協調控制問題為套用實例，驗證學習算法的有效性和實用性。
結題摘要
半Markov決策過程(Semi-MDP, SMDP)是一類比Markov決策過程(MDP)更具一般性的隨機過程，其最佳化算法在隨機動態系統的性能最佳化方面起到重要的作用。目前SMDP 最佳化算法多受到維數災、模型災、收斂速度慢和存儲量大等問題的限制。本項目從SMDP 性能靈敏度（包括性能差和性能導數）的角度，研究了平均報酬準則下的SMDP 的最佳化理論算法及其在相關實際問題中的套用，從多方面實現了對上述局限的解決，實現了項目申請既定的研究計畫和目標，共發表論文10篇，其中在《歐洲運籌學》(JCR一區)發表長文2篇，EI檢索7篇，申請1項專利。主要取得的成果包括：(1)在連續時間型性能靈敏度公式基礎上，首次提出了離散時間型性能靈敏度公式，通過研究發現SMDP具有連續時間和離散時間兩方面特徵，即它可以從連續時間和離散時間兩種角度進行理論分析和算法設計。這種兩面性一方面從性能靈敏度角度為現有的最佳化算法提供了統一的研究思路，另一方面又發展了多種新的最佳化算法。從兩種不同的角度，我們得到了不同的策略疊代算法和值疊代算法，雖然部分算法在以往的研究中曾經獨立提出過，本項目將它們從性能靈敏度角度給出了系統的統一化；提出了新的SMDP最佳化算法，如新的值疊代算法，新的策略梯度最佳化算法和新的策略梯度算法。這些算法在存儲量和運算量等方面得到了較大的改進，如：提出的策略梯度算法僅需要現有方法一半的存儲空間和運算量。(2)基於攝動分析方法，通過引入廣義攝動實現因子，利用樣本軌道攝動直觀構造出了SMDP的性能靈敏度公式，為SMDP性能靈敏度公式提供了直觀解釋，簡化了SMDP的相關最佳化理論。(3)從SMDP角度研究了時間集中思想，為時間集中的MDP提出了統一的研究方法，不僅從性能靈敏度角度分析了已有的算法，而且給出了新的基於時間集中的最佳化算法，如基於最短路徑的值疊代算法和線上的策略梯度算法等。(4)在值函式的估計方面，提出了一種基於耦合（Coupling）的具有幾何方差減少的估計方法，避免了現有算法因需要計算穩態分布和數值截斷所帶了的收斂速度慢和截斷誤差大等問題。(5)將研究結果套用於動態電源管理問題，實現了一種線上式的動態電源管理方法，該方法已申請國家專利。 (6)在多機器人任務分配方面，利用性能靈敏度分析方法提出了一種基於拍賣的實時任務分配方法，實現了智慧型倉庫系統中多機器人靜態和動態任務分配。
