[發明專利]適用于動態環境的LTL-A*-A*最優路徑規劃方法

有效

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

本發明公開了一種可應用于動態環境的LTL?A*?A*最優路徑規劃方法，該發明將線性時序邏輯(LTL)能夠滿足實際應用中復雜的任務需求的優點和A*算法搜索效率高的優點相結合，其主要包括LTL?A*全局路徑尋優和基于A*算法的局部路徑尋優兩部分。首先，通過LTL?A*全局路徑尋優部分搜索出環境中滿足任務需求的最優路徑；然后，機器人對搜索得到的全局最優路徑進行跟蹤，并檢測環境信息；最后，當局部環境發生變化，使得全局最優路徑中部分路段無法繼續通行時，則采用A*算法搜索局部最優路徑，繞過無法通行路段后繼續沿著全局最優路徑運行，完成指定任務。

技術領域

本發明涉及動態環境中最優路徑規劃領域，針對移動機器人的工作環境會出現動態變化特點，本發明提出了基于線性時序邏輯(linear temporal logic,LTL)的LTL-A*-A*最優路徑規劃方法，能夠根據環境變化進行二次路徑尋優，保證移動機器人高效地完成目標任務。

背景技術

近年來，隨著科技的發展，人們生產、生活中對于智能化機器人的需求越來越大，對機器人智能化水平的要求也越來越高。目前智能化機器人主要有4大應用范圍：工業機器人、探索機器人、服務機器人、軍事機器人。根據應用范圍，各種智能移動機器人的能力略有差異，但都應具備基本的感知工作環境、任務規劃和決策控制能力。智能移動機器人的體系結構包括感知、規劃和執行三種基本要素。其中，路徑規劃是智能移動機器人能夠高效完成任務的基礎。

現有的移動機器人路徑規劃方法可以分為兩類：靜態的路徑規劃方法和動態的路徑規劃方法。全局的路徑規劃方法，諸如基于時序邏輯的路徑規劃算法、遺傳算法、粒子群優化算法、蟻群優化算法、模擬退火法等，都能夠根據給定的機器人運行環境規劃出靜態環境中的最優路徑。然而，現有的靜態的路徑規劃方法都是離線的路徑規劃方法，無法適用于動態變化的環境，而且計算量都較大，尋優路徑時間較長；此外，大部分現有的全局的路徑規劃方法僅針對“從點A到點B，途中避開障礙物”這類簡單的任務，仍無法滿足實際應用中復雜的任務需求。動態的路徑規劃方法，諸如人工神經網絡算法、啟發式搜索算法、基于采樣的路徑規劃算法等，都是在線的路徑規劃算法，能夠適用于動態變化的環境的。但是，現有的動態的路徑規劃方法同樣存在著無法滿足實際應用中復雜任務需求的不足。

基于線性時序邏輯(linear temporal logic,LTL)理論的移動機器人路徑規劃方法采用線性時序任務公式描述實際應用中復雜的任務需求，并將環境信息與任務信息相融合以確保能夠搜索出既符合環境信息，又滿足任務需求的最優路徑。但是，一方面傳統的基于LTL理論的路徑規劃算法采用Dijkstra算法搜索路徑，計算量較大，路徑尋優效率與環境復雜度以及任務節點數成正比；另一方面，傳統的基于LTL理論的路徑規劃算法只針對靜態環境，當機器人運行過程中局部環境發生變化時若采用基于LTL理論的路徑規劃算法重新規劃，則過于復雜。

A*算法是一種啟發式路徑規劃算法，在Dijkstra算法上引入了啟發式代價函數來篩選路徑節點，從而降低了計算量，提高了搜索效率。但是單純的A*算法其只針對“從點A到點B，中間避開障礙物”這類簡單的任務，無法滿足實際應用中諸如始終保持一定的范圍之內(安全性)，按序訪問某幾個點(保證性)后，巡回訪問某幾個點(循環性)，圖中避開某些點(避障)，到達某些點后必須到達另外一些點才能繼續任務(反應性)等復雜的任務。

發明內容

本發明要克服現有技術的上述缺點，提供一種使機器人能夠適應動態環境，更能高效的執行任務的機器人動態路徑最優規劃方法。