基于笛卡兒坐標系的迷宮路徑規(guī)劃算法

1、文章編號：（）軟件時空基于笛卡兒坐標系的迷宮路徑規(guī)劃算法（四川大學(xué)）袁潔龔曉峰摘要：針對迷宮這類特殊的環(huán)境模型，提出了基于笛卡兒坐標系的新的路徑規(guī)劃算法。該算法通過找出機器人行駛方向和位置變化的關(guān)系，方便快捷地實現(xiàn)了對路徑的記憶，并且在到達終點后能夠通過一種簡單的路徑優(yōu)化算法算出最短路徑，最終實現(xiàn)以最短路徑返回。此算法的可行性已通過輪式機器人實例得到證實。關(guān)鍵字：路徑搜索；路徑規(guī)劃；笛卡兒坐標；機器人；迷宮中圖分類號：文獻標識碼：，：，引言自從特別是嵌入式系統(tǒng)出現(xiàn)以來，輪式迷宮機器人和路徑規(guī)劃算法一直是許多先進國家作為培養(yǎng)訓(xùn)練計算機和控制類學(xué)生的兩大重要課題。對迷宮機器人技術(shù)而言，路徑規(guī)劃的關(guān)

2、鍵就在于建立適當?shù)沫h(huán)境模型。本文提出了一種將迷宮環(huán)境模型建立在笛卡兒坐標系上的路徑規(guī)劃算法。該算法的核心思想是：通過事先確定坐標系的原點和正方向，將迷宮環(huán)境中的點與笛卡兒坐標一一對應(yīng)起來，以便于機器人進行各種環(huán)境信息的記憶和處理。本文首先從一個簡單的迷宮模型著手，詳細介紹了從環(huán)境建模，到路徑記憶，再到路徑優(yōu)化完整實現(xiàn)過程。針對這種迷宮模型，我們已經(jīng)研制出了相應(yīng)的輪式機器人實例，實現(xiàn)了完整的路徑規(guī)劃。與傳統(tǒng)迷宮機器人不同的是，在將迷宮環(huán)境映射到笛卡兒坐標的前提下，機器人可以更為簡單靈活的對走過的路徑進行規(guī)劃和記憶。到達終點后，能夠計算出從起點到終點的最短路徑并按此路徑返回，從而真正實現(xiàn)了機器人從

3、學(xué)習到記憶，從分析再到實踐的一個完整的擬人化過程。最后本文還對更為復(fù)雜的迷宮環(huán)境進行深入的分析研究，從而將這種迷宮規(guī)劃算法推向更寬的應(yīng)用領(lǐng)域。感器獲取。本設(shè)計屬于后者，通過機器人不斷的前行搜索，得到一個環(huán)境模型，再找出從起點到目標點的符合一定性能的可行或最優(yōu)路徑，它涉及的基本問題是環(huán)境模型的表達和搜索策略和優(yōu)化方法。常用的基于傳感器的路徑規(guī)劃方法主要有柵格法、人工勢場法、遺傳算法及模糊控制算法等。刪格法主要思想是將機器人工作空間分為具有二值信息的網(wǎng)格單元，分別表示自由空間和障礙物，由此引導(dǎo)機器人找到可行路徑。人工勢場法是由提出的一種基于勢場的方法。在機器人工作空間建立虛擬人工勢場，目標點對機器

4、人產(chǎn)生引力，障礙物產(chǎn)生斥力，機器人在合力作用下找出可行路徑。遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化的搜索算法。模糊控制算法則是把傳感信息和目標模糊化，利用隸屬度函數(shù)控制機器人運動。對于迷宮這類特殊的環(huán)境模型，這些方法都顯得過于復(fù)雜而不適用。于是，我們試圖尋找一種更為簡單方便的環(huán)境建模方法來處理迷宮環(huán)境這類問題。技術(shù)創(chuàng)新路徑規(guī)劃技術(shù)概述路徑規(guī)劃技術(shù)是機器人研究領(lǐng)域中的一個重要分支。所謂機器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某個或某些優(yōu)化準則（如工作代價最小、行走路線最短、行走時間最短等），在其工作空間中找到一條從起始狀態(tài)到目標狀態(tài)的能避開障礙物的最優(yōu)路徑。路徑規(guī)劃大體分為兩種：一種是

5、基于模型的路徑規(guī)劃，作業(yè)環(huán)境的都是預(yù)知的；另一種是基于傳感器信息的路徑規(guī)劃，作業(yè)環(huán)境全部未知，障礙物的尺寸、形狀和位置信息必須通過傳袁潔：碩士圖設(shè)計中的環(huán)境模型郵局訂閱號：元年技術(shù)應(yīng)用例軟件時空中文核心期刊微計算機信息（管控一體化）年第卷第期機器人行駛時，每遇到一個路口，就將當前坐標記下（，前面我們已經(jīng)假設(shè)在設(shè)計中，路口間的距離都是一個刪格）。的邊長即單位長度，所以機器人經(jīng)過的長度也都是單位，其變，只和當前行駛方向和上一個路口坐標（，）有關(guān)。化規(guī)律如下：表坐標變化與行駛方向的關(guān)系迷宮環(huán)境模型的建立迷宮環(huán)境主要有兩個特點：一是路徑主要是直線，二是路徑大部分是垂直相交。針對這兩個特點，我們用白紙和

6、黑線組成一個簡單的機器人迷宮（圖）。黑線有一定的寬度，并且相互垂直，作為機器人的導(dǎo)航線，代表機器人可以自由通過的安全路徑。白紙代表環(huán)境中有障礙物的區(qū)域。首先將地圖分解成相互連接的矩形柵格（如圖虛線所示）。柵格不一定一樣大，但要保證每一條安全路徑都要在柵格邊線上。我們始終假設(shè)起點是原點，起始方向為正方向，我們就可以把迷宮地圖完全映射到一個笛卡兒直角坐標系上。我們把每個柵格邊長定義為單位長度，把每個路徑相交處和死胡同盡頭定義為路口，這樣，每個路口都對應(yīng)一個整數(shù)坐標。如在上面的迷宮圖中，起點坐標為（，），終點坐標為（，）。為了研究方便，我們還對迷宮進行了限制，要求我們的迷宮是樹型迷宮。即迷宮中任意兩

7、點只有唯一一條路徑可以連通，即不存在回路。通過上表對機器人經(jīng)過的路口坐標依次進行記錄，就可以實現(xiàn)迷宮地圖在內(nèi)存上的映射。前面已經(jīng)提到，迷宮搜索策略我們用的時左轉(zhuǎn)優(yōu)先法?，F(xiàn)在就以圖的迷宮模型為例，列出機器人前行時依次經(jīng)過的坐標點。，當路徑信息在內(nèi)存中得到完整映射后，就需要一種算法讓機器人知道回去的最短路徑。我們是這樣實現(xiàn)的：將機器人經(jīng)過的坐標逐一進行比較，找出其中相同坐標，刪去兩相等坐標點中間的其他點，就得到的機器人返回時必須需經(jīng)過的坐標點。該算法的物理意義就是屏蔽掉所走過的盲道，得到主干道。繼續(xù)以上面迷宮模型為例，通過計算，得到主干道坐標點信息：迷宮搜索和路徑規(guī)劃技術(shù)創(chuàng)新迷宮的路徑搜索迷宮的搜

8、索策略可以簡單描述為：進入一路口，搜索并選擇一路徑往前走，若此路不通則返回選擇另一未走過路徑往前走，如此反復(fù)直至找到迷宮出口標志。實施這種搜索策略可以采路徑編碼法和固定的左轉(zhuǎn)或固用三種方法：即直接地圖映射法、定的右轉(zhuǎn)法。對于這個樹型迷宮，最常見的搜索法是固定左轉(zhuǎn)法。即機器人遇到路口，始終向左轉(zhuǎn)，如無左分支，則直走，如遇到的是死胡同，則原路返回直到遇到有左分支的路口?？梢宰C明，這樣最終可以走出迷宮或?qū)崿F(xiàn)迷宮遍歷。，按照前進時的逆運算，就可以通過坐標點求出每個路口的轉(zhuǎn)彎情況。功能擴展前面介紹的設(shè)計實例，是笛卡兒坐標下的路徑規(guī)劃算法的一種簡單的實現(xiàn)。但在現(xiàn)實生活中，我們遇到的迷宮模型要復(fù)雜的多（如圖

9、）。路徑的記憶和優(yōu)化由于迷宮模型的路徑都是直線，機器人當前位置只和它的上一個位置，當前行使方向以及行駛的單位長度有關(guān)。只需要記憶機器人當前行使的方向和經(jīng)過的單位長度，就可以根據(jù)上一次的坐標計算出當前坐標。還是以我們的設(shè)計實例為例。為了表述簡單，我們將軸正向稱為東，再按上北下南左西右東的習慣，將東南西北四個方向分別與坐標軸方向?qū)?yīng)。四個方向用兩個位標志表示，定義如下：東：，南：，西：，北：每轉(zhuǎn)一次彎，方機器人初始方向是東，即方向標志位為。向標志位發(fā)生相應(yīng)的變化。其變化規(guī)律如圖。當機器人左轉(zhuǎn)時，其方向變化如外圈實線箭頭所示；右轉(zhuǎn)時，其方向變化如外圈虛線箭頭所示；原地掉頭時，方向變化如內(nèi)圈箭頭所示。

10、圖復(fù)雜的迷宮地圖這種迷宮的路徑規(guī)劃，難點之一在于路口坐標的確定。由于路徑不是在規(guī)則的柵格的邊上，路口間的距離不再只是單位長度，要對每個路口準確的定位，必須用更精確的表示方法。為了得到更為精確的坐標值，機器人必須具有測距功能。我們采取的方法是在車輪上均勻裝上幾個霍爾傳感器，記錄下車輪轉(zhuǎn)動數(shù)和角度，測量機器人的行程，從而得到兩路口間的距離，用表二來代替前面介紹的實例中的表，就可以按照圖方向標志與小加轉(zhuǎn)彎運動關(guān)系前面介紹的方法對這種較為復(fù)雜的迷宮環(huán)境進行路徑規(guī)劃。元年郵局訂閱號：例表坐標變化與行駛方向的關(guān)系軟件時空楊傳華，楊萍，周美艷，劉金利自學(xué)習移動機器人在未知環(huán)境中的路徑規(guī)劃，（）：于紅斌，李孝

11、安基于刪格法的機器人快速路徑規(guī)劃微電子學(xué)與計算機，（）：莊慧忠，杜樹新，吳鐵軍機器人路徑規(guī)劃及相關(guān)算法研究科技通報（）李強，林良明，顏國正基于進化的移動機器人路徑規(guī)劃方法式（）這種迷宮路徑規(guī)劃，還有個難點是在進行路徑優(yōu)化時，如何識別相同的路口。因為受測距誤差和轉(zhuǎn)彎時位移等因素的影響，同一坐標在多次經(jīng)過時不可能得到完全相同的坐標。在坐標比較時，我們引入一個誤差系數(shù)，當時，就認為這兩個坐標是同一坐標。的大小關(guān)系著路徑優(yōu)化的正確與否。的值和迷宮的復(fù)雜程度和誤差大小有關(guān)，可以在程序中實現(xiàn)設(shè)置好，也可以路徑探索時通過模糊算法計算得出。這種方法，已經(jīng)通過仿真和試驗得以證實。另外，可以證明，只要迷宮起點沒有

12、設(shè)置在回路內(nèi)，機器人用固定左轉(zhuǎn)法是不會在回路中循環(huán)的。但若機器人的起點設(shè)在回路以內(nèi)，就極有可能陷入死循環(huán)。針對這種問題，我們用一個轉(zhuǎn)彎計數(shù)器記錄轉(zhuǎn)彎情況。該計數(shù)器初值是，每左轉(zhuǎn)一次計數(shù)器加，右轉(zhuǎn)一次減，當計數(shù)器絕對值大于時，說明進入循環(huán)，機器人改變路徑搜索方式，改用固定右轉(zhuǎn)法搜索。通過仿真，已經(jīng)證明這種方法的可行性。：，：作者簡介：袁潔，女（），漢，四川樂山人，碩士，研究方向：檢測技術(shù)與自動化裝置；龔曉峰：男（），漢，浙江金華人，副教授，博士，研究方向：計算機控制與管理：（），（），；（）（），（四川成都四川大學(xué)電氣信息學(xué)院）袁潔龔曉峰（，）小結(jié)本文以一個簡單的迷宮模型為例，提出了一種將迷宮環(huán)

13、境模型建立在笛卡兒坐標系上的方法?；诘芽▋鹤鴺私⒌沫h(huán)境模型，只需要確定原點和軸正方向，就可以唯一確定迷宮中每個點的坐標。這種方法描述簡單，理解容易，而且大大簡化了路徑的記憶過程和優(yōu)化過程。由于我們研究的對象是迷宮，此算法適用的環(huán)境模型必須滿足兩個前提：路徑都是直線，相交都成直角。這兩個前提在一定程度上限制了算法的運用范圍，在更復(fù)雜的機器人工作環(huán)境下，需要對此算法作更多的改進。但是，在現(xiàn)實生活中，大多數(shù)建筑、公路以及人造軌道基本都是直線型且垂直相交的。因此，這種基于笛卡兒坐標系的路徑規(guī)劃算法，無論在教學(xué)還是在實際生活中都有很高的研究價值。本文作者創(chuàng)新點：迷宮具有以下兩個突出特征：安全路徑都是

14、直線，路徑相交成直角。針對類似這樣的環(huán)境模型，提出了一種新路徑規(guī)劃方法，即把環(huán)境映射到一個笛卡兒坐標上，用坐標值表示環(huán)境中的節(jié)點。這樣大大簡化了機器人路徑記憶的難度，同時又為路徑優(yōu)化提供了很大的方便。只需要比較走過的路徑，找出其中重復(fù)的節(jié)點，屏蔽掉相同節(jié)點間的路徑，即可得到從起點到終點的最短路徑。這種路徑規(guī)劃算法思想簡單，易于實現(xiàn)，且擴展性強，可廣泛應(yīng)用于現(xiàn)代建筑、公路及軌道的機器人路徑規(guī)劃中，有很大的實用價值。通訊地址：（四川四川省成都市四川大學(xué)電氣信息學(xué)院研）袁潔（收稿日期：）（修稿日期：）技術(shù)創(chuàng)新（上接第頁）董輝，信號處理濾波器設(shè)計基于和朱義勝，北京，電子工業(yè)出版社，作者簡介：湯寧生（），男（漢族），安徽滁州人，電子科技大學(xué)自動化工程學(xué)院，檢測與自動化裝置（專業(yè)），碩士研究生，主要從事數(shù)據(jù)采集和混合濾波器組研究；黃建國，男，電子科技大學(xué)教授，從事電子測量、系統(tǒng)集成等方面的科研工作；王志剛，男，電子科技大學(xué)高級工程師，主