機器人避障問題

沈璐璐

（陜西能源職業(yè)技術(shù)學(xué)院，西安，712000）

機器人避障問題

沈璐璐

（陜西能源職業(yè)技術(shù)學(xué)院，西安，712000）

本文主要研究了機器人在一個區(qū)域內(nèi)按照一定的行走規(guī)則避開該區(qū)域內(nèi)的十二個障礙物，由出發(fā)點到達目標(biāo)點的最短路徑和最短時間路徑的問題。首先分析得到行走路徑由圓弧和與那些圓弧相切的直線組成。然后將路徑中遇到的拐點分解為一個或者兩個的情況，并給出了各種情況下路徑距離以及切點坐標(biāo)的求法。最后針對不同的目標(biāo)點分別建立模型并計算出最短路徑距離以及途中直線和圓弧的起點、終點坐標(biāo)。在此基礎(chǔ)上，建立非線形規(guī)劃模型，利用LINGO求出的最短時間路徑。

最短路徑;最短時間路徑;非線形規(guī)劃模型;LINGO

0 引言

圖1是一個800×800的平面區(qū)域，內(nèi)部有12個不同形狀的障礙物。在處有一個機器人，它只能在區(qū)域內(nèi)活動且不能與障礙物碰撞。機器人的行走路徑由直線和圓弧組成，其中圓弧是轉(zhuǎn)彎路徑，該路徑由與直線相切的圓弧組成，也可以由兩個或多個相切的圓弧組成，但每個圓弧的半徑最小為10個單位。同時機器人行走線路與障礙物間的最近距離為10個單位。機器人直線行走的最大速度為個單位/秒，最大轉(zhuǎn)彎速度為是轉(zhuǎn)彎半徑。障礙物的數(shù)學(xué)描述如下表：

圖1

1 模型分析與求解

1.1 問題一

根據(jù)行走規(guī)則，畫出行走過程中的危險隔離線，每到拐點處，隔離線都為半徑為10的圓弧。不難發(fā)現(xiàn)，起點到目標(biāo)點的路徑中不管障礙物有多少，最短的路徑都應(yīng)該是若干半徑為10的圓弧和與那些圓弧相切的直線組成。此問題中求的最短路徑中遇到的拐點要么為1個，要么為多個，對于不同個數(shù)的拐點分情況討論如下。

（1） 一個拐點：

圖2

（2） 多個拐點：多個拐點可每次只考慮兩個拐點，最后再相加。兩個拐點的情況可分為圖3和圖4兩種。

圖3

圖4

從O到A有兩條路徑，如圖5。

圖5

圖6

1.2 問題二

2 模型的評價

本模型全面考慮了出發(fā)點到目標(biāo)點的可行路徑，并選擇出幾條可能的最短路徑，分情況討論并計算出各條路徑的距離，最終比較得出最短路徑，結(jié)果精確度較高。并建立非線形規(guī)劃模型求解出從出發(fā)點到目標(biāo)點的最短時間，簡單易懂，利用軟件求解，精確度高且費時少。但是當(dāng)障礙物較多或者障礙物形狀，本模型還需進一步改進，尋找更高效的方法。

[1] 機器人行走問題, http://wenku.baidu.com/ view/606c2a094a7302768e99399a.html.

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

[3] 韓中庚，數(shù)學(xué)建模方法及其應(yīng)用[M]，北京：高等教育出版社，2005.

公式1：

The robot obstacle avoidance

Shen Lulu
(Shaanxi Energy Vocational and Technical College,Xi’an,712000,China)

This paper studies the shortest path and the shortest time path problem from the starting point to the target point in a region with twelve obstacles,the robot walks in that area according to certain rules to avoid those obstacles.Firstly,the walking path constituted by some arcs and straigt lines tangent to those arcs.The path can be decomposed into one or two inflection points,then gives solving methods of the path distance and tangent point coordinate in various situations.Finally,for different target points,models are established and calculates the shortest path distance and the starting and ending points coordinates of the straight lines and arcs.On this basis,a non-linear programming model is established, and the shortest time path form O to A is solved by LINGO.

The shortest path;The shortest time path;non-linear programming model;LINGO