[發(fā)明專利]基于高效搜索策略在不確定性環(huán)境下的在線規(guī)劃方法

在審

• 申請?zhí)枺?/td>: 202111401793.4
• 申請日: 2021-11-24
• 公開（公告）號: CN114118441A
• 公開（公告）日: 2022-03-01
• 發(fā)明（設(shè)計）人: 陳彥杰;劉江蔣;張智星;蘭立民;陳敏俊
• 申請（專利權(quán)）人: 福州大學
• 主分類號: G06N20/00
• 分類號: G06N20/00;G06F16/903;G06F16/901;B25J9/16
• 代理公司: 福州元創(chuàng)專利商標代理有限公司 35100
• 代理人: 丘鴻超;蔡學俊

本發(fā)明提出一種基于高效搜索策略在不確定性環(huán)境下的在線規(guī)劃方法，將機器人的狀態(tài)視為一個信念，以POMDP算法初始化當前信念的上、下邊界后，通過折扣化上下限表示當前信念的全部信息進而執(zhí)行前向搜索構(gòu)建信念樹，以此獲得當前信念下的最優(yōu)策略；所述信念樹的每一個節(jié)點代表一個信念，父節(jié)點與子節(jié)點通過行為?觀測分支連接。本發(fā)明提供的DESPOT?DULB算法性能優(yōu)于DESPOT和POMCP，在收斂速度以及策略質(zhì)量上具有優(yōu)勢。

技術(shù)領(lǐng)域

本發(fā)明屬于機器人技術(shù)領(lǐng)域，涉及一種基于高效搜索策略在不確定性環(huán)境下的在線規(guī)劃方法。

背景技術(shù)

隨著科學與信息技術(shù)的快速發(fā)展，機器人已經(jīng)逐步的融入了人類日常生活。運動規(guī)劃作為機器人研究的重要研究領(lǐng)域，也得到了廣泛的關(guān)注。

基于啟發(fā)式搜索的運動規(guī)劃方法能在有限的時間和空間內(nèi)計算出接近最優(yōu)的可行解，傳統(tǒng)的基于啟發(fā)式搜索的規(guī)劃算法有模擬退火算法(SA)、遺傳算法(GA)、以及蟻群算法(ACO)等。SA算法的特點可以高效地求解NP完全問題，如貨郎擔問題(TravellingSalesman Problem)、最大截問題(Max Cut Problem)、 0-1背包問題(Zero One KnapsackProblem)、圖著色問題(Graph Colouring Problem)等，但其參數(shù)難以控制，不能保證一次就收斂到最優(yōu)值，一般需要多次嘗試才能獲得且大部分情況下還是會陷入局部最優(yōu)值。GA算法基于生物進化和遺傳進行全局最優(yōu)化，具有良好的全局搜索能力，但存在早熟收斂等問題。ANN 算法人工神經(jīng)網(wǎng)絡是受生物神經(jīng)網(wǎng)絡啟發(fā)而構(gòu)建的算法模型，算法那可以快速調(diào)整并有效適應新環(huán)境，但對硬件的要求高、計算和訓練時間長等問題。ACO算法是一種用來尋找優(yōu)化路徑的概率型算法，該算法是受到螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為所啟發(fā)，是一種全局優(yōu)化算法，但其收斂的速度較慢等問題。上述啟發(fā)式算法在特定的問題上都能有效的規(guī)劃接近最優(yōu)的路徑，但都未考慮環(huán)境、傳感器等帶來的模型的不確定性問題，在現(xiàn)實環(huán)境下模型通常是不確定的。決策論規(guī)劃對于解決存在不確定性下的規(guī)劃具有重要意義，因此基于強化學習的運動規(guī)劃研究是很好的研究課題。

強化學習是一個多領(lǐng)域的交叉學科，比如：機器學習、決策與運籌學、深度學習以及控制工程等。在一個強化學習系統(tǒng)中，智能體(Agent)以“試錯”的方式進行學習，通過與環(huán)境進行交互獲得的獎勵指導行為使智能體獲得長期最大的獎勵。因此，強化學習是解決最優(yōu)序列決策問題的重要方法。在強化學習中，智能體在確定性環(huán)境和不確定性環(huán)境一般可以表示為馬爾可夫決策過程(MDP) 和部分可觀測馬爾可夫決策過程(POMDP)模型。區(qū)別在于智能體在MDP模型中，對于自身的狀態(tài)是完全可觀測的，但在POMDP模型中，自身的狀態(tài)是部分可觀測的。

在早期研究MDP問題主要關(guān)注于離散的狀態(tài)和動作空間。但是在現(xiàn)實任務中，需要處理連續(xù)的狀態(tài)和動作空間，算法的學習效率和適用性無法滿足最新要求。近年來，強化學習方法的近似求解器能夠有效的改善上述問題，比如近似價值函數(shù)迭代、近似策略迭代以及演員-評價算法等。強化學習算法不僅關(guān)注于單一的長期獎勵目標，而且在多目標規(guī)劃的強化學習問題上也有很大的發(fā)展，如以多目標學習改善自主陸地車輛縱向控制的柔性、多機多任務規(guī)劃等。但MDP模型未考慮環(huán)境、傳感器等方面帶來的不確定性，會造成計算的策略質(zhì)量較差。

對于不確定性環(huán)境下的規(guī)劃，POMDP提供了一個的基本框架。POMDP框架已經(jīng)能夠較好的解決現(xiàn)實世界的序列決策問題?？紤]到機器人在執(zhí)行任務時，制約機器人可靠運行的重要因素是環(huán)境、傳感器等不確定性。因此，機器人在具有較大狀態(tài)和觀測空間的不確定性環(huán)境下實現(xiàn)在線有效的規(guī)劃是機器人領(lǐng)域重要的課題。POMDP通過將當前的可能狀態(tài)表示為一個信念(Belief)，規(guī)劃算法不斷執(zhí)行前向搜索來構(gòu)建信念樹，信念樹的每一個節(jié)點代表一個信念，父節(jié)點與子節(jié)點通過行為-觀測分支連接起來。然而POMDP在一些最壞情況下是無法計算的，由于“維度災難”和“歷史信息災難”。盡管如此，一些近似的POMDP求解器：DESPOT、POMCP和POMCPOW等已經(jīng)被廣泛應用于許多任務中，如資源管理、無人駕駛、導航以及機械臂等。