張 蓉

(天津工程職業(yè)技術(shù)學(xué)院，天津 300280)

非線性規(guī)劃在機(jī)器人避障問題中的應(yīng)用研究

張 蓉

(天津工程職業(yè)技術(shù)學(xué)院，天津 300280)

本文針對機(jī)器人避障的最短路徑和最短時間路徑問題建立優(yōu)化模型，主要研究機(jī)器人行走過程中如何避開障礙物到達(dá)目標(biāo)點(diǎn)的最短路徑及最短時間路徑。經(jīng)分析可得，最短路徑一定是由線和圓弧組成的。為方便計(jì)算，把較長的路徑拆分為較簡單的線圓結(jié)構(gòu)圖。依據(jù)這種方法，無論多復(fù)雜的路徑圖都可以拆分為這種相對簡單的線圓結(jié)構(gòu)來求解。對于最短路徑問題，可通過窮舉法找出可行路徑，再用AutoCAD作出精確的路徑圖選出相對較短的路徑，并利用Mathematic計(jì)算出路徑長度，經(jīng)計(jì)算可得機(jī)器人路障的最短路程。對于最短時間問題，由于轉(zhuǎn)彎的半徑和弧的圓心是未知的，路徑是無法確定的，所以建立了非線性規(guī)劃的優(yōu)化模型，用LINGO軟件求解得到。

最短路徑；最短時間路徑；避障問題；非線性規(guī)劃；LINGO軟件；Mathematic軟件；AutoCAD制圖；優(yōu)化模型

1 引言

非線性規(guī)劃是具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃，是運(yùn)籌學(xué)的一個重要分支。非線性規(guī)劃是20世紀(jì)50年代才開始形成的一門新興學(xué)科。70年代又得到進(jìn)一步的發(fā)展。非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)設(shè)計(jì)提供了有力的工具。

2 機(jī)器人避障問題

一個800×800的平面場景圖如圖1所示，在原點(diǎn)O(0, 0)點(diǎn)處有一個機(jī)器人，它只能在該平面場景范圍內(nèi)活動。圖1中有12個不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：

編號障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形(300，400)邊長2002圓形圓心坐標(biāo)(550，450)，半徑703平行四邊形(360，240)底邊長140，左上頂點(diǎn)坐標(biāo)(400，330)4三角形(280，100)上頂點(diǎn)坐標(biāo)(345，210)，右下頂點(diǎn)坐標(biāo)(410，100)5正方形(80，60)邊長1506三角形(60，300)上頂點(diǎn)坐標(biāo)(150，435)，右下頂點(diǎn)坐標(biāo)(235，300)7長方形(0，470)長220，寬608平行四邊形(150，600)底邊長90，左上頂點(diǎn)坐標(biāo)(180，680)9長方形(370，680)長60，寬12010正方形(540，600)邊長13011正方形(640，520)邊長8012長方形(500，140)長300，寬60

在圖1的平面場景中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)(要求目標(biāo)點(diǎn)與障礙物的距離至少超過10個單位)。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機(jī)器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無法完成行走。

圖1 800×800平面場景圖

建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景圖中4個點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計(jì)算：

(1) 機(jī)器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。

(2) 機(jī)器人從O(0, 0)出發(fā)，到達(dá)A的最短時間路徑。

注：要給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時間。

3 模型的建立

3.1 符號假設(shè)

在建立模型之前，先將模型建立在一下客觀條件下：1.機(jī)器人在直線和圓弧中都能以各自的速度勻速行走，2.機(jī)器人在直線和圓弧之間連接時不停，3.除了指定障礙物外，機(jī)器人不受其他一切阻礙，4.機(jī)器人可以不停的走指定路程，5.障礙物是如題所說的完全的規(guī)則圖形，6.人在行走過程中可以將它看為質(zhì)點(diǎn)

文中涉及到的符號：(1)v：機(jī)器人直線行走的最大速度 (2)li：總路徑的總長度 (3)v(ρ)：機(jī)器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度 (4)(xi,yi)、(mi,ni)：表示圖中點(diǎn)的坐標(biāo) (5)r：轉(zhuǎn)彎半徑

3.2 問題分析

(1)問題一中要求機(jī)器人從O點(diǎn)出發(fā)到達(dá)A、B、C及經(jīng)過A、B、C回到O的最短路程。由于問題中障礙物太多，我們?yōu)榱撕喕瘑栴}AutoCAD做出精確的機(jī)器人行走路線圖，其中我們用直線及倒圓角把機(jī)器人不可去的地方用線畫出來，從而直觀的表示出機(jī)器人可以去的地方，然后我們便可以用切線把起點(diǎn)倒終點(diǎn)之間的無窮路線找出來，由于圖中只提絕對精確的，所以通過比較可去掉明顯路程較大的路程，然后在通過數(shù)值計(jì)算找出剩下路程中的最短路程。

(2)問題二中要求解從O到A的最短時間路徑，轉(zhuǎn)彎時圓弧的半徑和圓心無法確定，切點(diǎn)的坐標(biāo)無法確定。所以不能用第一問的窮舉法，優(yōu)化建模時只能用非線性規(guī)劃。最后再用LINGO求解最優(yōu)解。

3.3 模型分析

模型準(zhǔn)備一：

模型準(zhǔn)備二：

模型準(zhǔn)備三：

3.4 模型求解

3.4.1 問題一

(1)O到A的最短路程圖(如圖四)

由圖我們可以知道，從O到A的無數(shù)條路徑中只有圖中兩條相對較短，其他路徑的長度均大于圖中兩條。為了確定最短路線，我們對路線進(jìn)行數(shù)值計(jì)算，由三個準(zhǔn)備及mathematica計(jì)算，圖中兩條路線的總長度(l1表示障礙物5上邊綠色線路圖，l2表示障礙物下邊綠色線路圖)。

圖一

圖二

圖三

計(jì)算可得：l1=471.073 ，l2=498.426

由于l1

(2)O到B的最短路程圖(如圖五)

由圖我們可以知道，從O到B的無數(shù)條路程中只有圖中兩條相對較短，其他路程的長度大于圖中兩條路程的長。為了確定最短路線，我們對路線進(jìn)行數(shù)值計(jì)算，由三個準(zhǔn)備及mathematica計(jì)算圖中兩條路線的總長度(l3表示障礙物6左邊綠色線路圖，l4表示障礙物6右邊綠色線路圖)。

圖四

圖五

計(jì)算可得：l3=891.113，l4=913.563

由于l3

(3)O到C的最短路程圖(如圖六)

由圖我們可以知道，從O到C的無數(shù)條路程中只有圖中四條相對較短，其他路程的長度均大于圖中四條路程的長。在l5和l6之間的兩條路徑由于轉(zhuǎn)彎太多長度明顯大于l5和l6兩條路徑的長，所以只計(jì)算l5和l6兩條路徑的長。為了確定l5和l6兩條路徑的最短路線，利用LINGO軟件進(jìn)行數(shù)值計(jì)算、三個準(zhǔn)備及mathematic軟件計(jì)算圖中兩條路線的總長度(l5表示障礙物5上邊綠色線路圖，l6表示障礙物5下邊綠色線路圖)。

計(jì)算可得：l5=1947.378，l6=1091.537

由于l5>l6，所以l6即下邊綠色線路圖最短，它的切點(diǎn)坐標(biāo)從左到右依次為：(232.115,50.2262)、(232.169,50.2381)、(403.644,107.72)、(407.831,109.762)、(491.655,205.51)、(492.062,206.082)(727.938,513.918)、(730,520)、(730,600)、(727.718,606.359)圓心坐標(biāo)(230，60)、(410，100)、(500,200)、(720，520)、(720,600)

(4)A到B的最短路程圖(如圖七)

由圖我們可以知道，從O到B的無數(shù)條路程中只有圖中兩條相對較短，其他路程的長度大于圖中兩條路程的長，于是求解圖中兩條路徑的長。

圖六

圖七

為了確定最短路線，我們對路線進(jìn)行數(shù)值計(jì)算，由三個準(zhǔn)備及mathematic計(jì)算圖中兩條路線的總長度(l7表示障礙物8左邊綠色線路圖，l8表示障礙物8右邊綠色線路圖)l7=562.635，l8=568.815

由于l7

(5)B到C的最短路程圖(如圖八)

由圖我們可以知道，從B到C的無數(shù)條路徑中只有圖中兩條相對較短，其他路徑的長度大于圖中兩條路徑的長，于是求解圖中兩條路徑的長。經(jīng)分析可得，障礙物10下的路徑由于轉(zhuǎn)彎太多所以舍去。則確定l9為最短路線，我們對路線進(jìn)行數(shù)值計(jì)算，由三個準(zhǔn)備及mathematic計(jì)算圖中l(wèi)1路徑的總長度(l9為障礙物10上邊的路徑)。

計(jì)算可得：l9=839.735

它的切點(diǎn)坐標(biāo)從左到右依次為:(270.586,689.983)、(272,689.798)、(272,670.202)、(370,670)、(430,670)、(435.588,671.707)、(534.412,738.293)、(540,740)、(670,740)、(679.767,732.145)圓心坐標(biāo)為(720,680)、(370,680)、(430,680)、(540,730)、(670,730)

(6)由以上問題可以得出從O→A→B→C→O的最短路徑為L=l1+l6+l7+l9=2964.944

3.4.2 問題二

從O到A的最短時間路徑圖(如圖九)

圖八

圖九

機(jī)器人從O經(jīng)過弧KF到A的示意圖，設(shè)O、A、F、G、I、J、K、L、E、H的坐標(biāo)為(x1，y1)，(x2，y2)(x3，y3)(x4，y4)(x5，y5)(x6，y6)(x7，y7)(x8，y8)(x9，y9)(x10，y10)直線AG、AJ、DI、DK、AH，斜率K1、K2、K3、K4、K5圓心角θ，半徑為R0，弧長為l.

模型的建立

(x6-x8)2+(y6-y8)2+(x2-x6)2+(y2-y6)2=(x2-x8)2+(y2-y8)2

(x1-x8)2+(y1-y8)2=(x1-x7)2+(y1-y7)2+(x7-x8)2+(y7-y8)2

(x2-x3)2+(y2-y3)2=(x2-x10)2+(y2-y10)2+102,102=(x3-x10)2+(y3-y10)2

102+(x4-x2)2+(y4-y2)2=(x2-x9)2+(y2-y9)2,102=(x4-x9)2+(y4-y9)2

y8-y7>0.1，x7-x8>0.1，300-x8>1，x8-x6>0.01，x1=0、y1=0、x2=300、y2=300、x3=80、y3=210、x9=235、y9=300

(x6-x8)2+(y6-y8)2+(x2-x6)2+(y2-y6)2=(x2-x8)2+(y2-y8)2

(x1-x8)2+(y1-y8)2=(x1-x7)2+(y1-y7)2+(x7-x8)2+(y7-y8)2

(x2-x3)2+(y2-y3)2=(x2-x10)2+(y2-y10)2+102,102=(x3-x10)2+(y3-y10)2

102+(x4-x2)2+(y4-y2)2=(x2-x9)2+(y2-y9)2,102=(x4-x9)2+(y4-y9)2

x8-x7>0.1，x8-x6>0.1，y8-y6<0.1，y6-220>1，y8-y7>0.1，x7-x8>0.1，300-x8>1

x8-x6>0.01，x1=0、y1=0、x2=300、y2=300、x3=230、y3=60、x9=280、y9=100

通過LINGO計(jì)算可得出最少時間為t=109.714s

4 模型的評價改進(jìn)及推廣

本文建立模型時采用LINGO軟件編程、mathematic軟件和CAD制圖，可信度較高，實(shí)用性較強(qiáng)，路線圖精確清晰，給建模求解帶來了方便，其中效率有待進(jìn)一步改進(jìn)，以適用障礙物多模型的建立。

該模型簡單明了，思路清晰，容易理解，可以靈活應(yīng)用，具有很強(qiáng)的使用價值，因此該模型推廣到運(yùn)輸網(wǎng)絡(luò)中、避障救援項(xiàng)目、艦船通道路線設(shè)計(jì)中、城市道路建設(shè)、物資供應(yīng)站選址等也有很重要的作用，分析和研究最短路問題趨于熱門化。

[1]胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社，2007.

[2]謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件[M].北京：清華大學(xué)出版社，2005.

The Research of the Application of Nonlinear Programming in the Obstacle Avoidance of Robots

ZHANG Rong

(TianjinEngineeringVocationalandTechnicalCollege,Tianjin, 300280)

This paper mainly aimed to find the shortest path and the shortest time path when robots tried to avoid the obstacles to get to the target point and to establish an optimization model for these two paths. The analysis showed that the shortest path must always be composed with lines and arcs. For convenience, we split the longer path into relatively simple line round structures and no matter how complex the path graphs are, all of them can be solved by this method. For the shortest path, we can find the viable path by the method of exhaustion and then use AutoCAD software to make a precise path graph in order to select a relatively shorter one, the length of it can be calculated by use of Mathematic software and that is the shortest path of obstacle avoidance of robots. For the shortest time path, due to the unknown radius of the turning and center of the arc, it can not be determined, so we can establish an optimization model for the nonlinear programming to get it by use of LINGO software.

shortest path;the shortest time path; obstacle avoidance; nonlinear programming; LINGO software; Mathematic software; AutoCAD drawing; optimization model

2014-07-07

張蓉(1980-)，女，漢族，天津工程職業(yè)技術(shù)學(xué)院講師，從事數(shù)學(xué)及計(jì)算機(jī)教學(xué)與研究工作。

TP242

A

1673-582X(2015)02-0047-06