[發明專利]基于高程圖和蟻群尋食的三維路徑規劃方法

在審

• 申請號: 201310235123.9
• 申請日: 2013-06-14
• 公開（公告）號: CN103295080A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: 肖秦琨;王戈
• 申請（專利權）人: 西安工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06T17/00;G06T19/00
• 代理公司: 西安新思維專利商標事務所有限公司 61114
• 代理人: 黃秦芳

1.基于高程圖和蟻群尋食的三維路徑規劃方法，其特征在于：該方法包括以下步驟：

（1）利用抽象建模方法構造三維空間的仿真環境；

（2）將構造的三維空間進行表面的光滑處理；

（3）利用高程數學建模方法對已建立的三維地形進行數據采集，并形成高程圖的三維空間環境；

（4）將蟻群尋食方法分別運行在高程圖環境和抽象建模三維環境中，得到最優路徑。

2.根據權利要求1所述的一種基于高程圖和蟻群尋食的三維路徑規劃方法，其特征在于：所述的實現步驟（1）的具體步驟為：在matlab環境下進行三維環境建模，首先把三維地圖左下角的頂點作為三維空間的坐標原點O，在點O中建立三維坐標系，其中，x軸為沿經度增加的方向，y軸為沿緯度增加的方向，z軸為垂直于海平面方向；在該坐標系中以點O為頂點，沿x軸方向取三維地圖的最大長度ON，沿y軸方向取三維地圖的最大長度OO’，沿z軸方向取三維最大長度OP，構造了包含三維地圖的立方體區域OPMN-O’P’M’N’，該區域即為三維路徑的規劃空間。

3.根據權利要求1或2所述的一種基于高程圖和蟻群尋食方法的三維路徑規劃方法，其特征在于：所述的實現步驟（2）的具體步驟為：在matlab環境中輸入以下步驟：????

pause(3)

surfl(x1,y1,z)

shading?interp

colormap?pink

即可將構造的三維空間表面進行光滑處理。

4.根據權利要求3所述的一種基于高程圖和蟻群尋食的三維路徑規劃方法，其特征在于：所述的實現步驟（3）的具體步驟為：

假設三維激光測距系統采集的一組數據為w_i={w₁,w₂,…,w_n}，xy為任一激光點的三維直角坐標，數據對應方差為σ_i²={σ₁²,σ₂²,…,σ_n²}，σ_i²為相應激光點的方差，在構建高程圖環境之前，將xy平面平均劃分為多個柵格C_ij,?i和j表示柵格編號，并在柵格中存儲其周圍8個柵格的索引，考慮到存儲量、噪聲敏感度和后續的路徑規劃，將柵格尺寸設定為約等于機器人最長邊長；

把激光點對應到相應的柵格中,?在xy平面上激光點的分布函數近似為正態分布：

??????????????（1）

其中,w_i^xy為激光點x、y?坐標；σ_i^xy為x?和y的方差；

把激光點的有效區域定為x?和y?方向3?倍標準差范圍，激光點i對周圍8個柵格都有影響，即這8個柵格的參數都與激光點i有關，根據二維正態分布公式:

??????????（2）

計算激光對柵格的影響程度；

設激光點為柵格C_ij的第h?個點,?點w_i對柵格

C_ij的影響因子為

（3）

其中,x⁺、x^-、y⁺和y^-為柵格范圍,?是常量,?所以在計算中取μ∝N(p_i^xy，σ_i^xy),?對柵格C_ij中每個μ進行規一化處理,?柵格的高度值為柵格中所有激光點高度的加權平均,?即

???????????????????（4）

S_μ為柵格中激光點的影響因子之和。

5.根據權利要求4所述的一種基于高程圖和蟻群尋食的三維路徑規劃方法，其特征在于：所述的實現步驟（4）的具體步驟為：

步驟1：螞蟻開始搜索，根據蟻群搜索策略：螞蟻從當前點移動到下一個點時，根據啟發函數來計算可視區域內各點的選擇概率，啟發函數為

?（5）

螞蟻在平面∏_i上的當前點p_i選擇平面∏_i+1上下一個點p_i+1：

??（6）

其中，τ_a+1,u,v為平面∏_i+1上點p(i+1,u,v)的信息素值；

步驟2：信息素更新：在三維環境建模中已經把整個搜索空間離

散為一系列的三維離散點w_i={w₁,w₂,…,w_n}，所述離散點為蟻群尋食方法需要搜索的節點，把信息素儲存在模型的離散點中，每個散點都有一個信息素的值，該點信息素的大小代表對螞蟻的吸引程度，各點信息素在每只螞蟻經過后進行更新；

所述的的信息素的更新包括局部更新和全局更新兩部分，

所述的局部更新是增加螞蟻搜索未經過點的概率，達到全局搜索

的目的，局部信息素更新隨著螞蟻的搜索進行，信息素更新公式為

???????（7）

所述的全局更新是指當螞蟻完成一條路徑的搜索時，以該路徑的

長度作為評價值，從路徑集合中選擇出最短路徑，增加最短路徑各節點的信息素值，信息素更新公式如下：

?????????????（8）

當完成全局路徑規劃后，蟻群就會在路徑集合中選擇出的最優路徑。