李志帥，熊 剛，沈 震，董西松，劉希未，呂 鍵，劉 暢

?

教育用路徑可規(guī)劃智能車研發(fā)

李志帥1,2，熊 剛1,3，沈 震1,4，董西松1,4，劉希未3,4*，呂 鍵5，劉 暢6

（1. 中國科學(xué)院云計算中心，廣東 東莞 523808；2. 中國科學(xué)院大學(xué)，人工智能學(xué)院，北京 100049； 3. 中國科學(xué)院自動化研究所復(fù)雜系統(tǒng)管理與控制國家重點實驗室&北京市智能化技術(shù)與系統(tǒng)工程技術(shù)研究中心， 北京 100190；4. 青島智能產(chǎn)業(yè)技術(shù)研究院，智慧教育研究所，山東 青島 266109；5. 廣東朗呈醫(yī)療器械 科技有限公司，廣東 東莞 523808；6. 四川大學(xué)，計算機學(xué)院，四川 成都 610207）

針對高中科技社團和大學(xué)計算機相關(guān)專業(yè)科技創(chuàng)新教育需求，開發(fā)一種可以用于電子和計算機科技教學(xué)的智能小車。智能小車在完成路徑規(guī)劃后，可以按照規(guī)劃的路徑完成任務(wù)；還可以設(shè)定目標(biāo)點與障礙點，智能小車基于改進的Dijkstra算法自動搜索到達(dá)終點的最優(yōu)路徑。除了培養(yǎng)學(xué)生電子設(shè)計能力，通過智能小車編程實踐，也訓(xùn)練了學(xué)生對優(yōu)化算法的學(xué)習(xí)。首先，采用微軟基礎(chǔ)類MFC與Matlab混合編程編寫上位機界面，調(diào)用改進的Dijkstra算法進行路徑規(guī)劃。然后，將規(guī)劃好的路徑通過串口傳到下位機，由STM32控制執(zhí)行。最后，在柵格地圖中，通過仿真運行和實際應(yīng)用驗證了改進的Dijkstra算法的可行性，取得了較好的效果。

智能車路徑規(guī)劃；智慧教育；混合編程；Dijkstra算法；A*算法

0 引言

隨著人工智能技術(shù)的快速發(fā)展，人工智能與教育科學(xué)的深度融合以及人工智能技術(shù)的教育普及，都受到教育行業(yè)的高度重視并上升為國家戰(zhàn)略。圍繞這一戰(zhàn)略需求，首先需要研發(fā)相關(guān)教育裝備、設(shè)計多學(xué)科融合的課程體系，通過項目式課程訓(xùn)練學(xué)生實踐動手能力、培訓(xùn)創(chuàng)新精神[1]。

智能車，也稱為輪式機器人，是廣泛應(yīng)用于當(dāng)前的社會科學(xué)，包括科學(xué)技術(shù)教育，風(fēng)險檢測等領(lǐng)域。他們可以取代甚至超越人類來完成一些危險的環(huán)境任務(wù)。智能汽車在現(xiàn)實中發(fā)揮了重要作用，特別是在宇宙探測，海底和地震等災(zāi)難救援領(lǐng)域。作為集成了高科技的產(chǎn)品，智能小車可用于模擬和實驗，如路徑規(guī)劃，環(huán)境感知和自動駕駛等[2]。

路徑規(guī)劃用于解決機器人的最優(yōu)軌跡問題，即根據(jù)一些優(yōu)化標(biāo)準(zhǔn)（如最小工作成本，最短行駛路徑或最短行駛時間等）來找到工作空間的起點，目標(biāo)狀態(tài)可以獲得躲避障礙物的最佳路徑[3,4]。機器人的路徑規(guī)劃廣泛用于應(yīng)用場景，例如地圖導(dǎo)航、掃地機器人、無人駕駛車輛和倉庫分揀機器人等。

本文旨在開發(fā)一種智能小車，可用于高中科技學(xué)會的電子和計算機科學(xué)與技術(shù)教學(xué)或計算機科學(xué)或相關(guān)科目的科技創(chuàng)新教育需要。

我們項目開發(fā)用于教育的智能小車采用路徑優(yōu)化算法，可以獨立找到最優(yōu)路徑，為用戶學(xué)習(xí)智能汽車及相關(guān)算法提供應(yīng)用案例和優(yōu)化算法開發(fā)平臺。在路徑規(guī)劃完成后，可以控制小車根據(jù)自己的計劃路徑完成任務(wù)，同時也可以人為地設(shè)定目標(biāo)點和障礙點。優(yōu)化算法（遺傳算法，A*算法等）可以在現(xiàn)實中應(yīng)用以找到最優(yōu)路徑。路徑優(yōu)化算法在教育教學(xué)應(yīng)用和智能交通路徑選擇與規(guī)劃中非常重要。

本文安排如下，在第一部分介紹了智能車系統(tǒng)的整體設(shè)計；在第二部分介紹描述了路徑規(guī)劃算法以及本系統(tǒng)所使用的遺傳算法（GA）和A*算法兩種優(yōu)化方法；第三部分詳述了兩種優(yōu)化算法在尋找通過目標(biāo)點最優(yōu)路徑和柵格避障地圖的具體應(yīng)用和改進；第四部分介紹了結(jié)合智能車硬件得出在交互平臺應(yīng)用結(jié)果；最后，在第五部分對實驗結(jié)果做出了分析與改進方向。

1 教育用智能車系統(tǒng)的整體設(shè)計

本文將優(yōu)化算法與智能車相結(jié)合，研究的重點在于設(shè)計交互界面和智能車硬件系統(tǒng)并根據(jù)不同任務(wù)在實現(xiàn)路徑自主尋優(yōu)。系統(tǒng)包含智能車硬件以及單片機控制系統(tǒng)以及電腦可操控交互界面：生成二維現(xiàn)場地圖，在地圖中可以人為規(guī)劃智能車的運動軌跡并使智能車按照指定軌跡運動，在此基礎(chǔ)上使用Matlab編寫最優(yōu)化算法實現(xiàn)最優(yōu)化路徑，找到通過選定點的最短路徑，并將路徑發(fā)送給智能車，用單片機控制使之按照優(yōu)化后路徑走完地圖，在完成最優(yōu)化算法的同時，實現(xiàn)面向教育、教學(xué)使用的智能車開發(fā)。

本文采用微軟基礎(chǔ)類MFC編寫上位機交互界面，通過調(diào)用Matlab引擎的方式運行Matlab編寫好的遺傳算法和A*算法等優(yōu)化算法，分別針對不同優(yōu)化任務(wù)進行路徑規(guī)劃；然后將規(guī)劃好的路徑通過串口控制智能車行進；最后通過仿真運行和實際應(yīng)用驗證了混合編程來進行路徑規(guī)劃算法的可行性，學(xué)習(xí)者只需在Matlab端將優(yōu)化算法實現(xiàn)，在本文設(shè)計的交互平臺上通過調(diào)用Matlab引擎的方式加載優(yōu)化算法進而控制智能車，而無需自行設(shè)計交互界面以及編寫智能車程序和硬件設(shè)置，以便將更多的精力放在優(yōu)化算法學(xué)習(xí)實踐上。

由需要設(shè)計系統(tǒng)結(jié)構(gòu)我們可以得到智能車控制的過程如圖1所示。

圖1 總體方案設(shè)計流程圖

一個完整智能車控制系統(tǒng)的實現(xiàn)需要各個模塊相互結(jié)合共同作用，由上述流程和它們之間的關(guān)系，我們可得系統(tǒng)的總體設(shè)計方案，總體方案（圖1）分成上位機設(shè)計，通信模塊，智能車系統(tǒng)控制三部分。

上位機的交互界面實現(xiàn)了三個功能案例，可以按照不同的需求進行路徑規(guī)劃：

功能一在交互界面通過使用鼠標(biāo)鍵點擊來設(shè)置路徑，通過串行通信模塊控制智能車按照自己設(shè)定的路徑進行行駛；

功能二使用鼠標(biāo)來設(shè)定多個目標(biāo)點，每個點只經(jīng)過一次，找到智能小車通過每個點的最短路徑，類似于TSP（旅行商）問題，然后控制小車按照該最短路徑行進；

功能三通過按鍵響應(yīng)來生成的柵格地圖并在其中隨意設(shè)置障礙點和目標(biāo)終點，相當(dāng)于制作了一個迷宮，起點設(shè)在左上角的坐標(biāo)原點，使用優(yōu)化算法規(guī)劃出通過該迷宮的最短路徑并通過串口發(fā)送給智能車控制其按該最短路徑行駛，增加趣味性同時也鼓勵學(xué)生深入探究優(yōu)化算法，以體現(xiàn)其教育應(yīng)用價值。

本文設(shè)計的系統(tǒng)同時也在下位機進行了智能車硬件搭建以及單片機控制程序設(shè)計，以上三個功能各自在實現(xiàn)后，將規(guī)劃好的路徑通過串口發(fā)送給智能小車，接收串口數(shù)據(jù)并將得到的數(shù)據(jù)進行處理，然后控制智能車按照該數(shù)據(jù)前進。

由于本系統(tǒng)設(shè)計應(yīng)用在教育場景，考慮到易于中學(xué)生學(xué)習(xí)優(yōu)化準(zhǔn)則以及加快算法運行速度，在功能二設(shè)置目標(biāo)點尋找經(jīng)過所有點最的短路徑過程采用了遺傳算法(GA)，功能三在柵格圖上模擬真實場景采用A*(A-Star)算法進行智能車的路徑規(guī)劃，并針對柵格迷宮地圖設(shè)計了對應(yīng)的啟發(fā)函數(shù)h(x)。而功能一是用來給學(xué)生等用戶自主設(shè)置路徑，因此無需優(yōu)化。

2 路徑規(guī)劃算法描述

常見路徑規(guī)劃算法可大致分為：基于采樣的方法，如維諾圖，概率圖法PRM和快速拓展隨機樹法RRT等；基于節(jié)點的方法，如A*、D*算法等；基于數(shù)學(xué)模型方法，如混合整數(shù)非線性規(guī)劃MILP等；基于生物啟發(fā)式算法，如遺傳算法、粒子群算法等[5]。近幾年隨著機器學(xué)習(xí)的快速發(fā)展，基于神經(jīng)網(wǎng)絡(luò)和強化學(xué)習(xí)的路徑規(guī)劃也逐漸開始占據(jù)重要地位。

2.1 遺傳算法GA描述

遺傳算法（GeneticAlgorithm，GA）是通過模擬生物進化過程來完成優(yōu)化搜索，其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不以梯度信息為基礎(chǔ)。適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計和人工生命等領(lǐng)域[6]。作為一種全局優(yōu)化搜索算法，遺傳算法以簡單通用、魯棒性強、適于并行處理的優(yōu)點取得了廣泛的應(yīng)用。

遺傳算法的基本操作有選擇、交叉和變異。

選擇是從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)的個體的操作。選擇算子，有時又稱為再生算子（Rep-roduction operator）選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子有以下集中：適應(yīng)度比例方法、隨機遍歷抽樣法、局部選擇法[7]。

2.2 A*(A-Star)算法描述

A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法[9]。算法中的設(shè)計的啟發(fā)函數(shù)()距離估算值與實際值()越接近，最終搜索速度越快。公式表示為：

其中，()是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價估計，()是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價，()是從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的估計代價。

保證找到最短路徑條件，關(guān)鍵在于估價函數(shù)()和啟發(fā)函數(shù)()的選取。我們以()表達(dá)狀態(tài)n到目標(biāo)狀態(tài)的真實距離耗散，那么()的選取大致有如下三種情況：在()<()這種情況下，搜索的點數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解。當(dāng)()=()，即距離估計()等于最短距離時，路徑搜索過程將嚴(yán)格沿著最短路徑進行，此時的搜索效率是最高的。如果()>()，搜索的點數(shù)少，搜索范圍小，效率高，但卻不能保證得到最優(yōu)解[10]。本文在A*算法應(yīng)用時結(jié)合柵格地圖的特點設(shè)計了不同的啟發(fā)函數(shù)，并對比了不同啟發(fā)函數(shù)之間的性能差異。

3 遺傳算法和A*算法的應(yīng)用

3.1 遺傳算法的應(yīng)用

本文遺傳算法求解過程參數(shù)設(shè)置如下：

（1）種群初始化。將每一個人為設(shè)定的目標(biāo)點進行個體編碼，采用1-n的實數(shù)隨機排列的實數(shù)編碼方式，初始化的參數(shù)有種群個數(shù)M、染色體基因個數(shù)（即目標(biāo)點的個數(shù)）、迭代次數(shù)C、交叉概率P、變異概率P。

（2）適應(yīng)度函數(shù)。對于任意兩個目標(biāo)點之間的距離(,)已知，每個染色體（即n個目標(biāo)點的隨機排列）可計算出總距離，因此可將一個隨機全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)()：

即距離越短，適應(yīng)度函數(shù)越好。

（3）選擇操作。本文采用輪盤賭法，產(chǎn)生初始群體后，根據(jù)計算的個體適應(yīng)度，對整個群體進行適應(yīng)度從小到大排序，設(shè)定選擇百分比p，為保持群體的多樣性在進行選擇時，規(guī)定選擇p/2的好個體，再選擇p/2的個體放入到交配池中進行交叉、變異等遺傳操作。

（4）交叉操作。對于個體，隨機的選擇兩個個體，在對應(yīng)位置交換若干個基因片段，同時保證每個個體依然是1-n的隨機排列，防止進入局部收斂。

（5）變異操作。對于變異操作，隨機選取個體，同時隨機選取個體的兩個基因進行交換以實現(xiàn)變異操作。

在染色體編解碼和交叉變異算子等參數(shù)設(shè)計完成后，接下來考慮遺傳算法的具體實現(xiàn)步驟，本文所使用的遺傳算法具體步驟如表1所示。

表1 遺傳算法設(shè)計步驟

Tab.1 The steps of designing Genetic algorithm

3.2 A*算法的應(yīng)用

本文使用A*算法使之應(yīng)用于功能三的柵格地圖迷宮中，在應(yīng)用之前首先我們需要確定柵格的位置，進行柵格的標(biāo)識，一般用以下方法[11]：

（1）直角坐標(biāo)法。使用直角坐標(biāo)系的方法，按照左上為坐標(biāo)原點，水平向右設(shè)置為X軸，豎直向下設(shè)置為Y軸，計數(shù)x，y軸柵格的個數(shù)使用()坐標(biāo)將柵格的位置進行標(biāo)記,如式（4）所示。

（2）序號法。不使用直角方法，直接對柵格進行計數(shù)標(biāo)記序號，從左上角為1，按照從上到下，從左到右的順序依次標(biāo)號，上述兩種柵格標(biāo)識方法分別為公式（4）和（5），都是表示的同一個位置：

=+ 10′（4）

式（5）中，mod表示取p/10之余數(shù)，int表示取p/10之整數(shù)[12]。

本文采用的是序號法，應(yīng)用過程如下：

以10*10的柵格圖為例，假設(shè)為有向有權(quán)圖，每一個點為一個狀態(tài)，且該狀態(tài)只可以到達(dá)與之相鄰八個狀態(tài)，其位置用序號法表示的差值為[-11,-10,-9,-1, 0, 1, 9, 10, 11]，且真實距離()為[1.4, 1, 1.4, 1, 0, 1, 1.4, 1, 1.4]，在定義的地圖上設(shè)置障礙點和終點。

真實距離函數(shù)()已經(jīng)得到，接下來進行啟發(fā)函數(shù)()的設(shè)置，()一般選擇Manhattan距離，也可以將h(n)設(shè)置成0，此時A*算法將退化成Dijkstra算法。由于柵格地圖的特點，狀態(tài)點到其他狀態(tài)點距離d≥1總是成立，結(jié)合啟發(fā)函數(shù)0≤()≤()的特點，將啟發(fā)函數(shù)設(shè)置為() = 1，通過對比采用不同啟發(fā)函數(shù)算法所消耗的總時間，可以發(fā)現(xiàn)，雖然最終規(guī)劃好的路徑一致，但() = 1時的算法運行時間遠(yuǎn)小于() = 0的運行時間，也即啟發(fā)函數(shù)越接近目標(biāo)真實距離算法運行總時間越短。

圖2 搜索環(huán)境簡圖

在設(shè)定障礙點后需要把所有點到此障礙點的距離函數(shù)()設(shè)置為無窮大(inf)，構(gòu)造相應(yīng)的權(quán)值矩陣，初始化并進行規(guī)劃過程：

（1）初始化權(quán)值矩陣，由于是10*10柵格有100個位置，所以權(quán)值矩陣大小為100*100，其對角陣為0，只有附近的點才能到達(dá)，因此除了附近的點其余點距離都是無窮大，位于邊界的點有部分也是不可達(dá)的也要將相鄰位置設(shè)為無窮遠(yuǎn)。注意的是，在四條邊界上，即使在數(shù)字上相鄰也不可以認(rèn)為能到達(dá)，比如，10在第一行的最后一列，11在第二行的第一列，二者在柵格中不相鄰，它們之間的距離設(shè)置為無窮大。

（2）設(shè)置障礙點和終點，將所有點的狀態(tài)到障礙點距離設(shè)置為無窮大（inf），這樣即使點的位置在柵格中相鄰，也變成了不可達(dá)，終點作為算法的一個輸入變量，可以任意設(shè)置。

（3）將權(quán)值矩陣和終點輸入A*算法函數(shù)中進行計算得到實現(xiàn)路徑。

A*算法設(shè)計步驟如表2所示。

表2 A*算法設(shè)計過程

Tab.2 A* algorithm design process

3.3 遺傳算法的實現(xiàn)效果

在Matlab程序中設(shè)定：群體規(guī)模為10，最大演化代數(shù)為1000，交叉概率為0.4，變異概率為0.2。得到最優(yōu)路徑結(jié)果如圖3所示，其中左上目標(biāo)點為起點。

3.4 A*算法的實現(xiàn)效果

圖3 由遺傳算法得到的最優(yōu)路徑結(jié)果

圖4 用A*算法對不同障礙物位置進行網(wǎng)格地圖規(guī)劃結(jié)果

3.5 結(jié)合交互界面的算法設(shè)計效果

在運行內(nèi)存4GB，Intel core i3 CPU，Windows 10 系統(tǒng)的PC機上進行算法實現(xiàn)，開發(fā)環(huán)境為Visual Stdio 2013和Matlab，使用MFC編寫交互界面，鼠標(biāo)點擊目標(biāo)點后，調(diào)用Matlab引擎進行路徑規(guī)劃，上位機交互界面MFC編寫，實現(xiàn)了在交互界面的編輯路徑后，調(diào)用Matlab進行路徑規(guī)劃，然后將規(guī)劃結(jié)果信息通過串口發(fā)送智能車。

整體設(shè)計界面如圖5(a)所示。用戶使用功能一在圖5(b)中隨意設(shè)置交互界面中的路徑后，單擊“發(fā)送”按鈕，從com發(fā)送出規(guī)劃好的路徑信息。智能車串行模塊接收該數(shù)據(jù)，然后SCM控制電機按照信息運行。圖5(c)顯示功能二的實現(xiàn)：在空白地圖中，隨機設(shè)置10個人工點。在Matlab中實現(xiàn)遺傳算法后，在交互界面上調(diào)用Matlab引擎，找到通過10個點的最短路徑，然后將規(guī)劃好的最優(yōu)路徑信息返回給上位機。當(dāng)點擊“發(fā)送”按鈕時，路徑信息將被發(fā)送到智能車的串行數(shù)據(jù)接收模塊。圖5(d)顯示了功能三的實現(xiàn)過程：在網(wǎng)格圖中，我們可以隨意設(shè)置障礙點和目標(biāo)節(jié)點來模擬迷宮然后我們設(shè)置路徑的這些信息被發(fā)送到Matlab引擎并寫入m文件在Matlab中開始執(zhí)行使用有關(guān)障礙物和目的地的路徑信息并實現(xiàn)A*算法，我們可以找到通過迷宮的最佳路徑并將路徑信息返回到交互式界面。從結(jié)果中可以看出，獲得的路徑是最優(yōu)的。

圖5 （a）通過Visual C ++實現(xiàn)交互界面的整體設(shè)計；（b）功能一的工作圖：學(xué)習(xí)者使用Matlab引擎實現(xiàn)遺傳算法，然后將計劃優(yōu)化從Matlab傳輸?shù)絍C接口，和其他用戶可以隨意設(shè)置路徑；（c）功能二的實現(xiàn)：隨機人工設(shè)置10個目標(biāo)點；（d）功能三的實現(xiàn)過程：可以在網(wǎng)格圖中隨意設(shè)置障礙點和最終節(jié)點。然后將最終結(jié)點和障礙物數(shù)據(jù)信息傳遞給Matlab引擎。

4 智能車的系統(tǒng)實現(xiàn)

4.1 智能車硬件結(jié)構(gòu)的設(shè)計

智能車硬件采用RP5履帶車、L298n驅(qū)動電機，控制核心板為STM32f103c8t6，用藍(lán)牙串口與上位機通信，使用光電編碼器作為轉(zhuǎn)角與前進距離的反饋，采用J-LINK仿真器JTAG接口模式進行程序下載調(diào)試。

4.2 下位機智能車控制程序設(shè)計

4.2.1 控制智能車的設(shè)計

在運行內(nèi)存4 GB，Intel core i3 CPU，Windows 10系統(tǒng)的PC機上使用Keil uversion 5進行單片機程序的編譯和下載調(diào)試。

使用Timer2的4個通道產(chǎn)生4路PWM波，分別控制兩個輪子的正反轉(zhuǎn)，使用Timer3和Timer4定時器正交編碼模式，分別測量兩輪編碼器的轉(zhuǎn)的圈數(shù)進行角度和距離的反饋，及時控制校正小車的運動軌跡，在直行時讀取兩個編碼器的偏差，將偏差通過PID控制器改變PWM波的占空比來進行校正；在轉(zhuǎn)彎時，將兩輪的編碼器圈數(shù)相加，通過公式（6）來計算：

4.2.2 引入PID控制器來消除誤差

在直線前進過程中會產(chǎn)生誤差累積，導(dǎo)致偏離直線軌跡，產(chǎn)生較大誤差，因此引入PID控制器，兩輪的編碼器差值輸入到控制器中，通過PID運算修正輸出的PWM波，將誤差消除[13]。

4.3 智能車設(shè)計結(jié)果

圖6(a)是小車的實物圖，硬件組成已在圖中標(biāo)明。收到串口數(shù)據(jù)后，STM32核心板開始控制智能車按照規(guī)劃好的軌跡行進。直行給前進的電機PWM波，轉(zhuǎn)彎時采用原地轉(zhuǎn)彎的方式，一個電機正向轉(zhuǎn)，另一個電機反向轉(zhuǎn)來實現(xiàn)。

圖6(b)是上位機的USB轉(zhuǎn)串口模塊以及藍(lán)牙發(fā)送模塊，負(fù)責(zé)將路徑信息發(fā)送至下位機。

圖6 智能車系統(tǒng)所需硬件設(shè)計

5 結(jié)果分析與討論

5.1 應(yīng)用驗證

設(shè)置上位機路徑規(guī)劃的距離與現(xiàn)實的比例尺為1 : 45，即在上位機設(shè)計的1厘米就是實際的0.45米，驗證過程如下：

在實際中設(shè)置障礙物，在上位機上錄入障礙點，設(shè)定目標(biāo)點之后進行路徑規(guī)劃，不僅在上位機中出現(xiàn)了路徑，同時調(diào)用Matlab畫出了行動軌跡，智能車按照上位機規(guī)劃的路（圖7）前進即為最優(yōu)路徑。

結(jié)果分析：在上位機進行路徑規(guī)劃之后，傳到下位機執(zhí)行時會產(chǎn)生一定的誤差，經(jīng)過分析與查找，

可能的來源如下：

（1）編碼器不夠精確，導(dǎo)致直行以及轉(zhuǎn)角計數(shù)不夠，角度產(chǎn)生偏差；

（2）在轉(zhuǎn)角時可能并不是理性情況下原地轉(zhuǎn)，重心會有一定的偏離；

（3）兩個輪子的電機對稱性不夠理想，雖然控制輸出的PWM波相同，但電機轉(zhuǎn)速不同，產(chǎn)生偏差，引入PID控制消除兩輪轉(zhuǎn)速偏差時，會引起小車位置的偏離。

5.2 結(jié)語

本文利用MFC和Matlab等實現(xiàn)了對智能車的實際路徑規(guī)劃，加入遺傳算法和A*路徑規(guī)劃優(yōu)化算法使之分別應(yīng)用于目標(biāo)點尋找最優(yōu)路徑和柵格地圖迷宮避障中，驗證了其可行性，不僅在仿真中可以實現(xiàn)，將這種算法理論應(yīng)用于實際控制智能車方面也取得了比較好的效果。針對控制智能車產(chǎn)生的偏差，可以通過引入更多反饋措施例如定位裝置等進行修正；同時，交互界面的設(shè)計還需要繼續(xù)完善，以滿足教育研究者的不同需求。

本文使用VC設(shè)計的交互平臺進行方便中學(xué)生的教育、教學(xué)過程，通過在交互界面調(diào)用Matlab引擎的方式運行Matlab文件中的遺傳算法和A*等優(yōu)化算法，分別針對不同優(yōu)化任務(wù)進行路徑規(guī)劃，將規(guī)劃好的路徑通過串口控制智能車行進。通過仿真運行和實際應(yīng)用驗證了利用VC和Matlab混合編程方法，使用不同的路徑優(yōu)化算法控制智能車的可行性，學(xué)習(xí)者在學(xué)習(xí)實踐智能車路徑規(guī)劃時，只需編寫不同的路徑規(guī)劃算法再通過VC調(diào)用即可，無需再另行設(shè)計交互界面和編寫智能車程序，大大減少中學(xué)生和大學(xué)生的編程難度，從而可以進行更多的探索與嘗試。

圖7 錄入障礙點并規(guī)劃路徑

總體來說，控制效果比較理想，完成了按照規(guī)劃之后的路徑行駛，能夠成功加載優(yōu)化后的路徑信息并實現(xiàn)現(xiàn)實中避障。

[1] LIU, X W, Gong X Y, Wang F Y, Sun R, Gao Y, Zhang Y, Zhou J, and Deng X. A new framework of science and technology innovation education for k-12 in Qingdao, China. [C]// 2017 ASEE International Forum, June 28, 2017. Columbus, OH, USA.

[2] 陳平. 輔助駕駛中控制與決策關(guān)鍵技術(shù)研究[D]. 上海交通大學(xué), 2011.

[3] DAI B, XIAO X M, CAI Z X. Current Status and Future Development of Mobile Robot Path Planning Technology [J]. Control Engineering of China, 2005, 12(3): 198-202.

[4] 沈小偉. 移動機器人路徑規(guī)劃研究[J]. Engineering of China, 2005, 12(3): 198-202.

[5] 賈亞軍. 生物啟發(fā)式算法及其改進研究[D]. 中國科學(xué)技術(shù)大學(xué), 2010.

[6] 孫健, 鐘義信, 王偉. 利用遺傳算法求解TSP(Travelling Salesman Problem)問題的探討[C]// 全國信息論與通信理論學(xué)術(shù)會議. 2000.

[7] 金希東. 遺傳算法及其應(yīng)用[D]. 西南交通大學(xué), 1996.

[8] 梁宇宏, 張欣. 對遺傳算法的輪盤賭選擇方式的改進[J]. 信息技術(shù), 2009, 33(12): 127-129.

[9] 黃蓉, 劉敏. 基于A*算法求解最短路徑的實現(xiàn)原理[J]. 企業(yè)家天地(下半月刊), 2009(7): 124-125.

[10] 尹芳. 一次路由計算實現(xiàn)層次路由的拓?fù)浞椒? CN, CN 1816000 A[P]. 2006.

[11] 任世軍, 洪炳镕, 黃德海. 一種基于柵格擴展的機器人路徑規(guī)劃方法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2001, 33(1): 68-72.

[12] ZHAO Y L. Data structures and algorithms [M]. Tsinghua University press, 2008.

[13] 劉金琨. 先進PID控制MATLAB仿真[電子資源][M]. 電子工業(yè)出版社, 2004

Development of Educational Smart Car with Path Planning Algorithm

LI Zhi-shuai1,2, XIONG Gang1,3, SHEN Zhen1,4, DONG Xi-song1,4, LIU Xi-wei3,4*, LU Jian5, LIU Chang6

(1. Cloud Computing Center, Chinese Academy of Sciences, Dongguan 523808, China; 2. School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing 100049, China; 3. The State Key Laboratory of Management and Control for Complex Systems & The Beijing Engineering Research Center of Intelligent Systems and Technology, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China;4. Institute of Smart Education Systems, Qingdao Academy of Intelligent Industries, Qingdao 266109, China; 5. Guangdong Launca Medical Device Technology Co., Ltd. Dongguan 523808, China; 6. College of Software Engineering, Sichuan University, Chengdu 610207, China)

Aiming at the demand of science & technology club in high schools and college computer science innovation education in colleges, we developed a smart car which can be used in electronic and computer science and technology teaching to provide students with a platform to study smart cars and path optimization algorithms. The host computer system is developed by Visual C++ and calls the Matlab engine to run the genetic algorithm and A* or other optimization algorithms, carrying out path planning for different tasks and controlling the smart car through the serial port. Through simulation and practical application, it is verified that in our interactive platform, different path planning algorithms designed by Matlab can be implemented to control the smart cars. When students want to study the path planning and then control the smart car, they only need to use Matlab to implement the path planning algorithm of the smart car, without designing a platform of interactive interface and a program of smart car controlling in addition.

Smart car path planning; Smart education; hybrid programming; Genetic algorithm; A-star algorithm

TP3

A

10.3969/j.issn.1003-6970.2018.09.001

國家重點研發(fā)計劃項目(No.2018YFB1004800)，國家自然科學(xué)基金項目(61773381, 61773382, 61533019)；廣東省科技廳項目(2016B090910001, 2017B090912001)；青島市科技惠民專項項目(16-6-2-62-nsh)；2017湖北省中科院省院合作專項項目；廣東省引進領(lǐng)軍人才計劃(00201511)；東莞創(chuàng)新領(lǐng)軍人才項目(熊剛，呂鍵)等

李志帥（1995-），男，碩士研究生在讀，主要從事智能系統(tǒng)、復(fù)雜系統(tǒng)管理與控制等方面的科研工作。

劉希未，副研究員，主要研究方向：智慧教育，復(fù)雜系統(tǒng)管理與控制等。

本文著錄格式：李志帥，熊剛，沈震，等. 教育用路徑可規(guī)劃智能車研發(fā)[J]. 軟件，2018，39（9）：01-08