1、文章編號 2 2 2一種快速神經網絡路徑規劃算法 禹建麗 孫增圻 成久洋之洛陽工學院應用數學系 日本岡山理科大學工學部電子工學科 2清華大學計算機系國家智能技術與系統重點實驗室 日本岡山理科大學工學部信息工學科 2摘 要 本文研究已知障礙物形狀和位置環境下的全局路徑規劃問題 給出了一個路徑規劃算法 其能量函數利用神經網絡結構定義 根據路徑點位于障礙物內外的不同位置選取不同的動態運動方程 并針對障礙物的形狀設定各條邊的模擬退火初始溫度 仿真研究表明 本文提出的算法計算簡單 收斂速度快 能夠避免某些局部極值情況 規劃的無碰路徑達到了最短無碰路徑關鍵詞 全局路徑規劃 能量函數 神經網絡 模擬退火中圖

2、分類號 文獻標識碼 2 2 2 2 2 2 2 2 2 1引言 機器人路徑規劃問題可以分為兩種 一種是基 于環境先驗完全信息的全局路徑規劃 另一種是 基于傳感器信息的局部路徑規劃 后者環境是未 知或者部分未知的 全局路徑規劃已提出的典型方 法有可視圖法 ! 圖搜索法 ! 人工勢場法等 可視圖法 的優點是可以求得最短路徑 但缺乏靈活性 并且存 在組合爆炸問題 圖搜索法比較靈活 機器人的起始 點和目標點的改變不會造成連通圖的重新構造 但 不是任何時候都可以獲得最短路徑 可視圖法和圖 搜索法適用于多邊形障礙物的避障路徑規劃問題 但不適用解決圓形障礙物的避障路徑規劃問題 人 工勢場法的基本思想是通過尋

3、找路徑點的能量函數 的極小值點而使路徑避開障礙物 但存在局部極小 值問題且不適于尋求最短路徑 文獻 給出的 神經網絡路徑規劃算法 我們稱為原算法 引入網 絡結構和模擬退火等方法 計算簡單 能避免某些局 部極值情況 且具有并行性及易于從二維空間推廣 到三維空間等優點 對人工勢場法給予了較大的改 進 但在此算法中 由于路徑點的總能量函數是由碰 撞罰函數和距離函數兩部分的和構成的 而路徑點第 卷第 期 年 月 機器人 收稿日期一般由連接出發位置到目標位置的直線上均勻分布 的點序列開始 按使總能量函數減小的方向移動 所 以它得到的一般是無碰的且盡可能短的可行性路 徑 難以得到最短路徑 本文在該算法的基

4、礎上 提 出了一個改進算法 其主要特點是 改進算法 設有一個檢測器 它檢測并將每個路徑點的位置返 回給系統 系統對落在障礙物內部的點按使總能量 函數減小的方向移動 而障礙物外的點僅按距離減 小的方向移動 從而使規劃的無碰路徑達到了最短 無碰路徑 而且收斂速度明顯加快 改進算法除 了適用于障礙物是多邊形圍成的圖形外 還適用于 障礙物是圓形的情形 改進算法允許設定不同的 障礙物各條邊的模擬退火初始溫度 從而能夠簡單 地避免某些局部極小值的情況2 神經網絡路徑規劃 這一節敘述文獻 給出的神經網絡路徑規劃 算法2 1 碰撞罰函數一條路徑的碰撞罰函數定義為各路徑點的碰撞 罰函數之和 而一個點的碰撞罰函數

5、是通過它對各 個障礙物的神經網絡表示得到的 障礙物假設為多 邊形 圖 表示了一個點到一個障礙物的罰函數的 神經網絡 底層的兩個結點分別表示給定路徑點的 坐標 ! 中間層的每個結點相應于障礙物的一條邊 的不等式限制條件 底層和中間層的連接權系數就等于不等式中 ! 前面的系數 中間層每個結點的 閾值等于相應不等式中的常數項 中間層到頂層的 連接權為 頂層結點的閾值取為不等式的個數減去后的負數該連續網絡的運算關系為 其中各符號的含義為 頂層結點輸出 頂層結 點輸入 頂層結點閾值 中間層第 個結點 的輸出 中間層第 個結點的輸入 中間層第 個結點的閾值 第 個不等式限制條 件的系數 激發函數為常用的

6、形函數 即 其中 為模擬退火方法中的 /溫度 0 按以下規律變 化 整條路徑相應于碰撞函數部分的能量為 其中 是障礙物的個數 是路徑點的個數 表 示第 個路徑點 對第 個障礙物的碰撞函 數 圖 一個點到一個障礙物的罰函數的神經網絡 圖 神經網絡路徑規劃算法的計算實例 2 2 路徑規劃相應于路徑長度部分的能量定義為所有線段長度的平方和 即對所有路徑點 , 定義機 器 人 年 月 整條路徑的總能量函數定義為 其中 和 分別表示對每一部分的加權由于整個能量是各個路徑點函數 因此通過移 動每個路徑點 使其朝著能量減少的方向運動 最終 便能獲得總能量最小的路徑 關于點 的動 態運動方程為 其中 圖 是利

7、用此算法的計算實例 因為總能量函數 是有碰撞罰函數和距離函數兩部分組 成的 路徑點是向著盡量遠離障礙物且使路徑較短 的位置移動 因此 一般情況下 開始由于溫度較高 路徑點移動到遠離障礙物的位置 隨著溫度值的減 小 路徑的長度逐漸得到改善 最后收斂到無碰的可 行性路徑3快速神經網絡最短路徑規劃算法 在快速神經網絡路徑規劃算法中 設計了一個 檢測器 它實際上是一個神經網絡分類器 利用檢測 器 在路徑規劃的過程中始終檢測著路徑點的位置 由神經網絡分類器判斷該點是否在障礙物 內 即是否與障礙物相碰 并將檢測結果返回系統 神經網絡分類器就是在路徑點到一個障礙物的罰函 數的神經網絡中 中間層和頂層結點的激

8、發函數取 為階躍函數 則中間層的每個結點是決定該結點是 否滿足它的限定條件 若滿足 輸出為 否則輸出為 若所有中間點均滿足 則頂層輸出為 它表示該 點在障礙物內 若中間點檢測出其中至少有一個不 滿足限制條件 頂層輸出便為 它表示該點在障礙 物外系統根據檢測器返回的信息 選擇路徑點的動 態運動方程 若路徑點在障礙物內則按動態運動方 程 移動 若路徑點在障礙物之外 則按動態 運動方程 移動 即若路徑點在障礙物外或障礙 物內的路徑點一旦移出了障礙物就僅按減少路徑長 度的方向移動 不再向遠離障礙物的方向移動 從而 使路徑能快速收斂到無碰的最短路徑下面給出改進的快速神經網絡最短路徑規劃算 法 在此作了

9、點假設 障礙物是多邊形圍成的 平面圖形或者是圓形的平面圖形 機器人為圓形 點機器人 計算時障礙物的尺寸按機器人的半徑作 了適當拓展 障礙物為靜止的步驟 輸入出發點 及目標點 的坐標 對于 初始路徑一般取為出發點到目標點的直線上均勻分布的點列 當 時 , 步驟 2 對于路徑點 用檢測器檢測是否在障礙物內步驟 3 若 在障礙物內 則按下列運 動方程移動 其中 用于 位于多邊形的障礙物內的情況 用于 位于圓心在 的圓形障 礙物內的情況 若在障礙物之外 則按下列運動方 程移動 步驟 4 重復執行步驟 步驟 直到路徑收斂 這里 整條路徑總能量函數的定義與原算法相 同 一個點到一個障礙物的罰函數的神經網絡

10、結構 如圖 但是中間層第 個結點的輸出改為了 中間層第 個結點的激發函數改為 第 卷第 期 禹建麗等 一種快速神經網絡路徑規劃算法 其中 是相應于障礙物每一條邊的初始溫度 即可 以根據障礙物的形狀 設定各邊的不同的初始溫度 這樣對于一些不對稱圖形可避免其罰函數曲面形成 一邊倒的情況 從而避免路徑規劃收斂到局部極小 值 最后 中間層第 個結點的輸入 當障礙物是 多邊形圍成的平面圖形時同原算法的 式 當障礙 物是圓形的平面圖形時不等式的個數取為一 即中 間層只有一個結點 且輸入為 其中 為圓形障礙物的半徑 為圓形障礙物 的圓心4 仿真實驗 圖 是在參數 和圖 的完全一樣的情況下用改進算法進行 的仿

11、真實驗結果 它是一條折線形的最短無碰路徑 圖 是圖 和圖 中兩種算法下仿真實 驗收斂速度的比較 其中橫軸是計算次數 次 縱軸是路徑長度 點線是實際無碰最短路徑長 度 實線是圖 的仿真實驗的收斂速度曲線 虛 線是圖 的仿真實驗的收斂速度曲線 它表明改進 算法的收斂速度快于原算法的收斂速度圖 的仿真實驗表明 改進算法不僅適用于障 礙物是多邊形圍成的圖形 而且適用于障礙物是圓 形的情形 在多個障礙物的環境中改進算法也能得 到最短的無碰路徑 其中初始溫度均為 圖 仿真實驗 1 圖 仿真實驗 1 機 器 人 年 月5結論 本文給出了一個快速神經網絡最短路徑規劃算 法 成功地得到了最短的無碰路徑 而且計算

12、簡單 收斂速度快 它除了適用于障礙物是多邊形圍成的 圖形外 還適用于障礙物是圓形的情形 而且能夠簡 單地避免某些局部極小值的情況 為移動機器人的 最優路徑規劃提供了一個簡捷有效的算法參考文獻 孫增圻 智能控制理論與技術 清華大學出版社 2 2 9 2 16 13 15孟慶浩 彭商賢 劉大偉 基于 2 圖啟發式搜索的移動機器人 全局路徑規劃 機器人 20 2 2 2 2 8 2 2 2 22作者簡介禹建麗 2 女 碩士 副教授 研究領域 模糊控制 遺 傳算法 神經網絡 機器人智能控制 2 男 博士 副教授 研究領域 自適應控制 機器人智能控制等上接第 頁參考文獻 2 2 20楊雨東 徐光佑 朱志剛 維幀間運動估計方法 清華大學學 報 自然科學版 37艾海舟 張朋飛 何克忠 江濰 張軍宇 室外移動機器人的視覺臨 場感系統 機器人