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

張 蓉

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

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

張 蓉

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

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

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

1 引言

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

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

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

編號(hào)障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形(300，400)邊長(zhǎng)2002圓形圓心坐標(biāo)(550，450)，半徑703平行四邊形(360，240)底邊長(zhǎng)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)邊長(zhǎng)1506三角形(60，300)上頂點(diǎn)坐標(biāo)(150，435)，右下頂點(diǎn)坐標(biāo)(235，300)7長(zhǎng)方形(0，470)長(zhǎng)220，寬608平行四邊形(150，600)底邊長(zhǎng)90，左上頂點(diǎn)坐標(biāo)(180，680)9長(zhǎng)方形(370，680)長(zhǎng)60，寬12010正方形(540，600)邊長(zhǎng)13011正方形(640，520)邊長(zhǎng)8012長(zhǎng)方形(500，140)長(zhǎng)300，寬60

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

圖1 800×800平面場(chǎng)景圖

建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型。對(duì)場(chǎng)景圖中4個(gè)點(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的最短時(shí)間路徑。

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

3 模型的建立

3.1 符號(hào)假設(shè)

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

文中涉及到的符號(hào)：(1)v：機(jī)器人直線行走的最大速度 (2)li：總路徑的總長(zhǎng)度 (3)v(ρ)：機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(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)榱撕?jiǎn)化問題AutoCAD做出精確的機(jī)器人行走路線圖，其中我們用直線及倒圓角把機(jī)器人不可去的地方用線畫出來，從而直觀的表示出機(jī)器人可以去的地方，然后我們便可以用切線把起點(diǎn)倒終點(diǎn)之間的無(wú)窮路線找出來，由于圖中只提絕對(duì)精確的，所以通過比較可去掉明顯路程較大的路程，然后在通過數(shù)值計(jì)算找出剩下路程中的最短路程。

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

3.3 模型分析

模型準(zhǔn)備一：

模型準(zhǔn)備二：

模型準(zhǔn)備三：

3.4 模型求解

3.4.1 問題一

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

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

圖一

圖二

圖三

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

由于l1

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

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

圖四

圖五

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

由于l3

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

由圖我們可以知道，從O到C的無(wú)數(shù)條路程中只有圖中四條相對(duì)較短，其他路程的長(zhǎng)度均大于圖中四條路程的長(zhǎng)。在l5和l6之間的兩條路徑由于轉(zhuǎn)彎太多長(zhǎng)度明顯大于l5和l6兩條路徑的長(zhǎng)，所以只計(jì)算l5和l6兩條路徑的長(zhǎng)。為了確定l5和l6兩條路徑的最短路線，利用LINGO軟件進(jìn)行數(shù)值計(jì)算、三個(gè)準(zhǔn)備及mathematic軟件計(jì)算圖中兩條路線的總長(zhǎng)度(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的無(wú)數(shù)條路程中只有圖中兩條相對(duì)較短，其他路程的長(zhǎng)度大于圖中兩條路程的長(zhǎng)，于是求解圖中兩條路徑的長(zhǎng)。

圖六

圖七

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

由于l7

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

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

3.4.2 問題二

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

圖八

圖九

機(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，弧長(zhǎng)為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ì)算可得出最少時(shí)間為t=109.714s

4 模型的評(píng)價(jià)改進(jìn)及推廣

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

該模型簡(jiǎn)單明了，思路清晰，容易理解，可以靈活應(yīng)用，具有很強(qiáng)的使用價(jià)值，因此該模型推廣到運(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