【正文】 以應(yīng)用在機(jī)器人實(shí)踐中。 A星算法簡介：首先將地圖分為不同的節(jié)點(diǎn)，儲存節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的關(guān)系，將地圖中不可達(dá)的地方設(shè)置為死節(jié)點(diǎn)。如上圖所示，G值可以看做從綠色節(jié)點(diǎn)到周圍節(jié)點(diǎn)的距離，H值是可以看做相鄰節(jié)點(diǎn)到目的地紅色節(jié)點(diǎn)的距離。而計(jì)算H值時(shí)采用簡單的曼哈頓算法（移動像過街道一樣只有橫向與縱向位移），每經(jīng)過一個(gè)格子加十，死節(jié)點(diǎn)也需計(jì)算進(jìn)入。這樣重復(fù)下去就可以生成一條相對較短的路徑 如上圖所示就是A星算法生成最短路徑的過程。 下面給出A星算法的偽代碼實(shí)現(xiàn)：(firstnode) //將開始節(jié)點(diǎn)加入堆,同時(shí)也是加入openlistdo{ fleast=()。 //取出的元素作為當(dāng)前節(jié)點(diǎn) =1 //1:on close 0:not on open nor on close for(int i=。i++) //考察當(dāng)前節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn) for(int j=。j++) { if(map[i][j]!=unwalkable||!onclose(node(i,j))) //相鄰節(jié)點(diǎn)可通并且沒有考察過 { if(!onopen(node(i,j))) //相鄰節(jié)點(diǎn)不在openlist中 { (node(i,j))。 //設(shè)置相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn) node(i,j).calculate(f,g,h)。 } else { =+addcost。 node(i,j).fcost=node(i,j).gcost+node(i,j).hcost。 node(i,j).recaculate(f,g,h)。 //輸出路徑elsecoutpath not find。 A星算法應(yīng)用在本次機(jī)器人制作需要以下幾個(gè)工作： 、地圖的劃分 A星算法需要知道地圖的分布，因此合理將場地劃分是執(zhí)行程序的第一步。 之后在這個(gè)區(qū)域上劃分小塊，考慮到機(jī)器人繞障礙的精度要求，我們將可行區(qū)域劃分為200X200MM的小區(qū)域，以區(qū)域中心作為節(jié)點(diǎn)所在位置，如下圖所示，所畫區(qū)域恰好分成諸多小塊、節(jié)點(diǎn)的儲存為了避免不穩(wěn)定性，我們設(shè)定機(jī)器人只能沿節(jié)點(diǎn)橫向或縱向移動（G值不能為14），將每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)用結(jié)構(gòu)體儲存，結(jié)構(gòu)體應(yīng)該包括節(jié)點(diǎn)編號，節(jié)點(diǎn)死活，節(jié)點(diǎn)鄰居指針，節(jié)點(diǎn)中心坐標(biāo)等元素。這對于繞障礙以及出現(xiàn)故障重新開始時(shí)重新定標(biāo)起到幫助作用。 //該方塊的x坐標(biāo) float y。 //該方塊的G值 float H。 //該方塊的右鄰方塊（right） rect L。 //該方塊的上鄰方塊（top） rect D。 //該方塊的死活狀態(tài)Int N //該方塊的編號}*rect。同理可以得到要走到L方塊需要順時(shí)針旋轉(zhuǎn)的角度：angle= （(direct%41)*(90) 180)%360。當(dāng)角度轉(zhuǎn)完后，再前行200mm即可到達(dá)下一節(jié)點(diǎn)這樣就可以從一個(gè)節(jié)點(diǎn)移動到它任意鄰居節(jié)點(diǎn)。首先發(fā)現(xiàn)障礙并且確定障礙位置和障礙所在節(jié)點(diǎn)（發(fā)現(xiàn)障礙的算法見程序部分的識別板塊），之后并不能簡單刪除該節(jié)點(diǎn)，如果只刪除單一節(jié)點(diǎn)有時(shí)并不能生成符合實(shí)際的最優(yōu)路徑。改進(jìn)以后的刪除方式見下圖 這樣機(jī)器人若想到對面去只有一條路可以選擇就是繞道（我們設(shè)定機(jī)器人轉(zhuǎn)向只能原地旋轉(zhuǎn)再前行）。如果路被堵死的情況：機(jī)器人前行檢測到障礙并刪除節(jié)點(diǎn)機(jī)器人重新生成最優(yōu)路徑并轉(zhuǎn)向。 綜上，我們可以對基于A星算法的導(dǎo)購過程進(jìn)行一個(gè)概述：開始時(shí)機(jī)器人受到指令，了解商品節(jié)點(diǎn)位置機(jī)器人生成最優(yōu)路徑并按照路徑行走機(jī)器人發(fā)現(xiàn)障礙，將障礙位置節(jié)點(diǎn)刪除，重新生成最優(yōu)路徑，再次遇到障礙之后重復(fù)刪除步驟和最優(yōu)路徑生成步驟報(bào)價(jià)，導(dǎo)購階段結(jié)束機(jī)器人到達(dá)商品位置，移動到與商品間距不超過200mm處，重復(fù)2過程尋找下一物品跟隨部分：跟隨部分不再需要機(jī)器人自己尋找最優(yōu)路徑，而是只要跟著人走就可以了，因此也就不再需要使用劃分的方塊，考慮到前后的一致性，機(jī)器人按照如下圖的路徑行走比較合適（與導(dǎo)購階段的路徑相比只是將方塊去掉了）：跟隨階段有幾個(gè)主要的問題需要解決：。但由于導(dǎo)購階段人跟隨在機(jī)器人后方，因此機(jī)器人只需要通過超聲波傳感器測出與人之間的距離，就可以通過調(diào)整自己的速度來達(dá)到距離上的要求，這樣來看機(jī)器人后方并沒有安裝攝像頭的必要。但是由于超聲波傳感器基本上只能測量與它正對的物體的距離，而機(jī)器人需要測量的人的位置不是固定的，因此在機(jī)器人上安裝多個(gè)超聲波傳感器是必要的；由于測量與障礙之間的距離是非常重要的（這涉及到導(dǎo)購階段的挖掉死方塊），為了保證盡可能準(zhǔn)確地測出機(jī)器人與障礙之間的距離，我們通過雙目識別來測量，這需要機(jī)器人前方有兩個(gè)攝像頭。其中前方的兩個(gè)攝像頭的高度在500mm(障礙的高度)以下，通過雙目識別技術(shù)，這兩個(gè)攝像頭可以比較有效精準(zhǔn)地識別圓柱體障礙物到機(jī)器人的距離。由于測量人的上半身的距離比較容易，因此前后的超聲波傳感器都放置在機(jī)器人的頂部，這樣可以達(dá)到人的腰部的高度；由于安裝在機(jī)器人前面（后面）的超聲波傳感器之間的距離為200mm，超聲波傳感器與機(jī)器人邊緣的距離為150mm，而人的腰部寬度一般大于200mm，因此可以保證在跟隨過程中只要人大致在機(jī)器人前方時(shí)，就能保證至少有一個(gè)超聲波傳感器是正對著前方的人的，如下圖所示：在導(dǎo)購和跟隨過程中，只要人的中心位置在上圖所示兩條綠色虛線范圍之內(nèi)，機(jī)器人就能比較準(zhǔn)確地測定與人之間的距離。），因此圖中所示范圍與實(shí)際相比還要略小一些。我們的機(jī)械結(jié)構(gòu)設(shè)計(jì)留出了這種裝置。 導(dǎo)購階段商品的位置是提前輸入給電腦，而跟隨階段的商品由攝像機(jī)識別條形碼，由電腦將條形碼信息與商品信息對應(yīng)并順利完成計(jì)算與報(bào)價(jià)、分類等過程。 在跟隨過程中，商品的識別我們決定采用條形碼識別的方案，現(xiàn)今的商品上都貼有條形碼標(biāo)識，很容易通過商品上的條形碼來判別商品的各項(xiàng)信息（類別，價(jià)格等）。常見的條