[發明專利]一種任務時序邏輯約束的概率規劃識別方法

有效

• 申請號: 201811599707.3
• 申請日: 2018-12-26
• 公開（公告）號: CN109657868B
• 公開（公告）日: 2021-02-09
• 發明（設計）人: 方浩;宇文濤;陳杰;田戴熒;劉得明
• 申請（專利權）人: 北京理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 李微微;仇蕾安

1.一種任務時序邏輯約束的概率規劃識別方法，其特征在于，包括如下步驟：

步驟一，建立面向實際環境的時序邏輯任務模型：利用有限狀態轉移系統對實際環境建模，再利用線性時序邏輯語言對任務進行描述并轉換成對應Büchi自動機，將兩者相結合建立同時具有環境信息和任務信息的乘積式Büchi自動機；將任務集中的所有任務建立形成對應乘積式Büchi自動機，組成規劃庫；

步驟二，根據對目標智能體的觀測信息和規劃庫信息，綜合考慮智能體當前位置、姿態、歷史軌跡以及任務進程，基于Dijkstra算法設計規劃器，并得出規劃結果集和整體代價集，其中，智能體的姿態計算以智能體與目標點的朝向角為基準；

步驟三，將規劃和規劃識別相結合形成統一的整體，對于非合作智能體的未來目標和當前執行任務進行預測和辨識，提取規劃器的規劃結果集中反映的目標和任務，以規劃器的整體代價集為衡量標準，計算目標概率和任務概率；

其中，所述步驟三中，計算得到目標概率和任務概率后，得到預測目標準確率和辨識任務準確率，給出針對所設計概率規劃識別算法的評價標準；

所述步驟一中，具體包括如下步驟：

(1)帶權的有限狀態轉移系統：

針對智能體的實際環境建模問題，采用帶權的有限狀態轉移系統WFTS進行描述，定義如下：

定義1.帶權的有限狀態轉移系統(WFTS)由一個多元組組成：

T_c＝(Π,→_c,Π₀,AP,L_c,W_c)

其中：

Π＝{π₁,π₂,...,π_N}表示柵格化后實際環境的各個區域；

→_c：表示兩兩柵格區域之間的路徑連通關系；

Π₀：表示智能體在初始時刻的實際位置；

AP:表示描述不可再劃分任務的原子命題；

L_c:表示柵格區域對應的標簽函數，即柵格區域對應的任務原子命題的屬性；

W_c:表示權重，即智能體在柵格區域之間互相轉移所需的代價；

狀態π_i可到達的狀態表示為Post(π_i)＝{π_j∈Π|π_i→_cπ_j}；將待觀察目標智能體的移動軌跡用一個無窮狀態序列表示，τ＝π₁→π₂...，其中，π_i∈Post(π_i-1)；

(2)非確定性Büchi自動機：

利用線性時序邏輯LTL語言對原子命題AP進行描述，形成表達式相對于表達式存在一個與其對應的非確定性Büchi自動機NBA，記為

定義2.定義為五元組：

其中，Q表示由自動機中的各個狀態q₁,q₂,...,q_n組成的有限狀態集合；表示由自動機中的初始狀態組成的初始狀態集合；2^AP表示由任務原子命題組成的字母表；δ表示自動機中各狀態之間的轉移關系，表示由自動機中的可接受狀態組成的可接受集合；

(3)利用LTL語言對每個待辨識任務進行描述，并轉換成相應Büchi自動機；將WFTS和NBA相結合形成面向實際環境的時序邏輯任務模型：

定義3.帶權的乘積式Büchi自動機PBA表示為其中：

δ'＝Q'→2^Q'.π_j,q_n∈δ'(π_i,q_m)當且僅當(π_i,π_j)∈→_c并且q_n∈δ(q_m,L_c(π_i))；

Q₀'＝{π,q|π∈Π₀,q∈Q₀}，是初始狀態集；

F'＝{π,q|π∈Π₀,q∈F}，是可接受集；

W_p:是權重函數：

W_p(π_i,q_m,π_j,q_n)＝W_c(π_i,π_j)

其中π_j,q_n∈δ'(π_i,q_m)；

所述步驟二具體步驟包括：

定義4.針對時序邏輯任務的規劃問題定義為Pl＝{A_p,π_c,Q_c,Rs}，其中，A_p表示任務對應的乘積式自動機，π_c表示智能體的當前位置，Q_c表示當前時刻智能體可能對應的自動機中的狀態集，Rs表示以q′_c∈Q′_c為起始點的A_p的所有可接受序列組成的集合，

根據定義4，設定可接受序列的結構為:

R＝R_pre,R_suf＝q'_cq'_c+1…q'_f[q'_fq'_f+1…q'_n]

其中q_f'＝π_f,q_f∈F'；

定義整體代價：

式中，第一個累加部分表示沿前綴部分的累積，第一個累加部分表示沿后綴部分的累積；γ≥0是一個常數，表示前綴代價與后綴代價的相對權重系數；

定義5.針對時序邏輯任務的概率規劃識別問題定義為Pr＝{A_p,π_c,Q_c,Rs,Os,Gs,Ps}，其中：

Os表示智能體的歷史移動軌跡；

表示目標概率集，表示智能體下一步目標是π_i的概率，Π_g表示待預測目標集；

表示任務概率集，表示當前執行任務是的概率，表示所有任務的集合；

當構建完成A_p之后，以A_p作為輸入參數，計算可接受序列集Rs，獲取多種規劃路徑；使用Dijkstra算法，計算帶權圖中從單點出發到一組目標點的路徑，具體步驟如下:

①對于用線性時序邏輯語言描述的任務集將其中每個任務轉換成對應Büchi自動機利用FTS對目標智能體工作環境建模形成T_c，并確定待預測目標集Π_g；利用PBA對和T_c進行乘積操作構成并建立規劃庫

②通過觀測獲取目標智能體歷史移動軌跡Os＝π₀,...,π_c，對于π_i，0≤i＜c，有；

當i＝c時，π_c表示目標智能體當前位置信息，有:

③考慮歷史移動軌跡Os的影響：

1)、令i＝1

2)、對于q′_i∈Q′_i，如果則保留q′_i；否則，將q′_i從集合Q′_i中刪除；

3)、i＝i+1

4)、判斷i＞c是否成立：如果成立，結束步驟3)，得到經過處理后Q′_c；否則返回2)；

④使用Dijkstra算法計算從當前狀態q′_c∈Q′_c到一個可接受狀態的最短路徑，是的可接受狀態集，記為

⑤使用Dijkstra算法計算中每一個可接受狀態回到自身的最短循環路徑，記為

⑥對于定義：

定義規劃結果序列中第一個屬于待識別目標集Π_g的π_i為下的智能體下一步目標，記為

規劃器根據觀測所得目標智能體的信息，計算出符合實際環境和任務集的規劃結果集R_sum為：

根據所得規劃結果集R_sum，得出智能體下一步目標集Π_gsum為：

根據整體代價R計算公式得到的整體代價整體代價集Cost_sum為：

其中，在設計規劃器過程中，考慮智能體朝向與目標之間夾角的影響，則令X_i表示第i時刻智能體X的位置，朝向由表示，則在第i時刻，智能體X朝向與目標A之間的夾角為：

所述步驟四具體包括如下步驟：

①對作處理，定義：

其中，exp{x}表示e^x，是正則化懲罰系數，由智能體姿態決定，λ是常數，

②在規劃結果集R_sum中，將所有規劃目標為π_k且任務為的規劃結果對應的整體代價相加，得到：

將所有規劃目標任務為的規劃結果對應的整體代價相加，得到：

將規劃結果集所有規劃對應的整體代價相加，有：

③針對目標智能體當前執行任務的辨識，根據觀測軌跡Os計算任務集Φ中的任務概率規劃結果集中符合的整體代價所占比重，即為后驗概率

首先，假設任務集Φ中的任務相互獨立，計算在任務的情況下，目標為π_k的后驗概率

之后，根據觀測軌跡Os計算待預測目標集Π_g中的目標概率即后驗概率P(π_k|Os)：

2.如權利要求1所述的一種任務時序邏輯約束的概率規劃識別方法，其特征在于，還包括對預測目標準確率和辨識任務準確率的計算，具體為：

智能體的實際目標集為G_true(i)＝{g_t(0),...,～g_t(i)}，預測目標集為G_pred(i)＝{max(Gs(0)),...,max(Gs(i))}，其中，g_t(i)，max(Gs(i))分別表示第i時刻智能體的實際目標和預測目標概率最大的目標，g_t(i),max(Gs(i))∈Π_g；智能體的實際執行任務集為預測執行任務集為Φ_pred(i)＝{max(Ps(0)),...,max(Ps(i))}，其中，max(Ps(i))表示第i時刻智能體的實際執行任務和預測任務概率最大的任務，max(Ps(i))∈Φ；

第i時刻，目標預測準確率GA(i)為：

GA(i)＝plen(G_true(i)∩G_pred(i))/len(G_true(i))

其中，len(G)表示集合G的長度；

第i時刻，任務辨識準確率TA(i)為

TA(i)＝len(Φ_true(i)∩Φ_pred(i))/len(Φ_true(i))。