[發明專利]基于高效搜索策略在不確定性環境下的在線規劃方法

在審

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

1.一種基于高效搜索策略在不確定性環境下的在線規劃方法，其特征在于：將機器人的狀態視為一個信念，以POMDP算法初始化當前信念的上、下邊界后，通過折扣化上下限表示當前信念的全部信息進而執行前向搜索構建信念樹，以此獲得當前信念下的最優策略；所述信念樹的每一個節點代表一個信念，父節點與子節點通過行為-觀測分支連接。

2.根據權利要求1所述的基于高效搜索策略在不確定性環境下的在線規劃方法，其特征在于，所述POMDP算法采用在線POMDP規劃算法DESPOT-DULB，包括以下步驟：

步驟S1：智能體在當前信念空間中隨機采樣K個狀態以構建狀態集合Φ_b；

步驟S2：以信念b作為根節點b₀構建信念樹D，初始化當前信念b經驗價值的上界U(b)、下界L(b)和RWDU最優值V^*(b)的上界μ(b)、下界l(b)；

步驟S3：定義智能體的當前信念b的不確定性為∈(b)＝μ(b)-l(b)，并進一步判斷當前不確定性是否滿足∈(b)＜∈₀或運行時間是否大于T_max，如果條件滿足，執行步驟S5，否則，執行步驟S4；

步驟S4：對作為根節點b₀的信念b進行前向搜索以擴展信念樹；

步驟S5：當擴展的作為子節點的信念b滿足要求，信念樹停止擴展并自下而上對節點執行備份BACKUP(D，b)，若遇到受阻節點，則執行剪切操作PRUNE(D，b)；

步驟S6：對于作為根節點b₀的信念b，選擇信念樹返回的最大的l(b)對應的最優行為a^*，即并與默認策略π₀的值L(b)比較，以選擇最優行為；

步驟S7：智能體重復以上的過程，直到到達目標點。

3.根據權利要求2所述的基于高效搜索策略在不確定性環境下的在線規劃方法，其特征在于：步驟S2具體包括以下過程：

利用經驗值的計算形式其中V_π，φ表示模擬策略π，計算每一個采樣序列φ∈Φ_b的折扣獎勵；其中對于U(b)的計算通過假設狀態是完全可觀測的，將在線POMDP問題轉換成在線MDP問題，然后計算MDP環境下的最優價值V_MDP：

經驗值下界的計算利用一個默認策略π₀來獲取，默認策略為固定行為或隨機行為，對于每一個節點b的每一個序列Φ_b模擬默認策略進行有限次數的探索，計算每一個序列的折扣獎勵再求平均值獲得；

對應的RWDU的上限μ(b)和下限l(b)通過U(b)和L(b)依據正規化加權折扣效用函數RWDU：

求得：

其中，γ是一個折扣因子，|Φ_b|是通過節點b的場景數量，Δ(b)表示節點b在策略π中的深度，π_b是節點b處的子樹，|π_b|表示π_b的大小，|π_b|＝0，λ是正規化因子；指的是在b處執行默認策略π₀的正規化加權折扣效用值。