[發(fā)明專利]適用于動態(tài)環(huán)境的LTL-A*-A*最優(yōu)路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201610893302.5
• 申請日: 2016-10-13
• 公開（公告）號: CN106500697B
• 公開（公告）日: 2019-05-28
• 發(fā)明（設(shè)計）人: 禹鑫燚;郭永奎;汪濤;盧靚;歐林林
• 申請（專利權(quán)）人: 浙江工業(yè)大學
• 主分類號: G01C21/20
• 分類號: G01C21/20;G05B13/04
• 代理公司: 杭州天正專利事務(wù)所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種適用于動態(tài)環(huán)境的LTL-A*-A*最優(yōu)路徑規(guī)劃方法，具體步驟如下：

步驟1：將機器人所在的環(huán)境建模為一個加權(quán)切換系統(tǒng)模型，加權(quán)切換系統(tǒng)是一個元組T:＝(Q,q₀,δ_T,∏,ζ,ω_T)，其中Q為一個有限狀態(tài)集，即環(huán)境中選取的路徑節(jié)點集；q₀∈Q代表初始狀態(tài)，即機器人運行的起點；δ_T→2^Q代表切換關(guān)系，即環(huán)境中各個路徑節(jié)點之間的連通狀況；∏代表原子命題集；ζ:Q→2^∏代表標識函數(shù)集；ω_T代表切換權(quán)重且ω_T>0，即機器人在環(huán)境中任意兩路徑節(jié)點之間運行的成本；在加權(quán)切換系統(tǒng)中原子命題代表加權(quán)切換系統(tǒng)中各個狀態(tài)的屬性，當且僅當狀態(tài)q處原子命題π為真時，π∈ζ(q)才成立，若q₂∈δ_T(q₁)，則q₂為q₁的后續(xù)狀態(tài)；加權(quán)切換系統(tǒng)中的一條軌跡r_T是由T中的有限個狀態(tài)組成，即r_T＝q₀q₁q₂...，其中對于任意的i≥0都有q_i+1∈δ_T(q_i)成立，軌跡r_T包含了有限個標識函數(shù)o＝o₀o₁o₂...，其中o_i∈ζ(q_i)；

步驟2：根據(jù)線性時序邏輯理論，利用線性時序任務(wù)公式φ描述移動機器人的復(fù)雜任務(wù)；遍歷任務(wù)公式Fp₁∧Fp₂∧Fp₃，其中，p₁、p₂和p₃代表環(huán)境中的節(jié)點，∧為布爾算子與操作，遍歷任務(wù)公式Fp₁∧Fp₂∧Fp₃則表示機器人最終到達p₁、最終到達p₂和最終到達p₃，也就是機器人必須遍歷所有我們感興趣的任務(wù)節(jié)點；避障任務(wù)公式其中o₁、o₂和o₃表示環(huán)境中的障礙物，為布爾算子非操作，避障任務(wù)公式則表示機器人到達p₁節(jié)點之前要避開o₁、o₂和o₃三個障礙物；

步驟3：為了將環(huán)境信息與任務(wù)信息相融合，通過LTL2BA工具包將線性時序任務(wù)公式φ轉(zhuǎn)換為任務(wù)可行性圖表的形式，即Büchi自動機，Büchi自動機是一個元組B:＝(S_B,S_B0,∑_B,δ_B,F_B)；其中，S_B代表一個有限的狀態(tài)集；S_B0∈S_B代表初始狀態(tài)；∑_B代表輸入的字符表；代表切換函數(shù)；代表最終狀態(tài)集；

步驟4：將機器人運行環(huán)境對應(yīng)的加權(quán)切換系統(tǒng)T:＝(Q,q₀,δ_T,∏,ζ,ω_T)和任務(wù)公式對應(yīng)的Büchi自動機B:＝(S_B,S_B0,∑_B,δ_B,F_B)做笛卡爾乘積，構(gòu)建即任務(wù)可行網(wǎng)絡(luò)拓撲P，即P為一個元組(S_P,S_P0,δ_P,w_P,F_P)，其中S_P＝Q×S_B代表狀態(tài)集；S_P0＝{q₀}×S_B0代表初始狀態(tài)集；代表切換函數(shù)，其定義為當且僅當q_j∈δ_T(q_i)并且s_l∈δ_B(s_k,ζ(q_i))時，(q_j,s_l)∈δ_P((q_i,s_k))成立；w_P為繼承自T的權(quán)重，即當(q_j,s_l)∈δ_P((q_j,s_l))時，則ω_P((q_i,s_k),(q_j,s_l))＝ω_T(q_i,q_j)；F_P＝Q×F_B代表一個最終的接收狀態(tài)集；任務(wù)可行網(wǎng)絡(luò)拓撲通過笛卡爾乘積將環(huán)境信息與任務(wù)需求相融合，確保了最終尋優(yōu)所得路徑既能夠符合環(huán)境信息，又能夠滿足任務(wù)需求；

步驟5：在步驟4得到的任務(wù)可行性網(wǎng)絡(luò)拓撲上，第一次利用A*算法搜索出全局最優(yōu)路徑，由于任務(wù)可行性網(wǎng)絡(luò)拓撲包含了環(huán)境信息和任務(wù)信息，所以搜索出來的路徑可以保證為全局最優(yōu)路徑，A*算法是一種啟發(fā)式搜索算法，在搜索過程中通過建立估價函數(shù)來判斷優(yōu)先搜索方向，可以很大提高搜索效率；然后把在P圖上搜索出來的路徑映射回實際環(huán)境中得到移動機器人實際的運動路徑，即r_P為P圖中對應(yīng)路徑，r_T為時間環(huán)境T圖對應(yīng)路徑，機器人按照r_T進行執(zhí)行任務(wù)；

步驟6：根據(jù)機器人執(zhí)行任務(wù)過程中的環(huán)境變化信息，更新加權(quán)切換系統(tǒng)模型，并產(chǎn)生局部任務(wù)公式，再次利用A*算法進行局部搜索，獲得局部最優(yōu)路徑；規(guī)劃所得路徑為：r_T＝p₁→p₈→p₁₅→p₁₆→p₁₇時，p₁,p₈,p₁₅,p₁₆,p₁₇為環(huán)境中的節(jié)點，當機器人運行達到節(jié)點p₁₅時發(fā)現(xiàn)節(jié)點p₁₆遇堵，無法通過節(jié)點p₁₆到達節(jié)點p₁₇，此時，將環(huán)境所對應(yīng)的加權(quán)切換系統(tǒng)中節(jié)點p₁₆標識為障礙物，得到局部起點為p₁₅到達局部終點p₁₇，途中避開p₁₆的局部任務(wù)，然后采用A*算法進行局部搜索，機器人按照所的路徑到達p₁₇后，繼續(xù)按照全局路徑執(zhí)行任務(wù)，以此類推，當機器人在運行過程中環(huán)境路況發(fā)生變化時，則重復(fù)采用A*算法進行局部搜索最優(yōu)路徑，直至移動機器人完成指定任務(wù)。

2.根據(jù)權(quán)利要求1所描述的適用于動態(tài)環(huán)境的LTL-A*-A*最優(yōu)路徑規(guī)劃方法，其特征在于該方法基于LTL理論根據(jù)機器人工作環(huán)境進行多次最優(yōu)路徑搜索，使該方法適用于動態(tài)環(huán)境，并在任務(wù)可行性網(wǎng)絡(luò)拓撲上采用A*算法高效地搜索出既滿足環(huán)境信息又符合任務(wù)要求的最優(yōu)路徑。