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

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

?

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

圖1 總體方案設計流程圖

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

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

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

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

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

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

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

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

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

2.1 遺傳算法GA描述

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

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

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

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

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

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

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

3 遺傳算法和A*算法的應用

3.1 遺傳算法的應用

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

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

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

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

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

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

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

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

表1 遺傳算法設計步驟

Tab.1 The steps of designing Genetic algorithm

3.2 A*算法的應用

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

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

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

=+ 10′（4）

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

本文采用的是序號法，應用過程如下：

以10*10的柵格圖為例，假設為有向有權圖，每一個點為一個狀態(tài)，且該狀態(tài)只可以到達與之相鄰八個狀態(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ù)()已經(jīng)得到，接下來進行啟發(fā)函數(shù)()的設置，()一般選擇Manhattan距離，也可以將h(n)設置成0，此時A*算法將退化成Dijkstra算法。由于柵格地圖的特點，狀態(tài)點到其他狀態(tài)點距離d≥1總是成立，結合啟發(fā)函數(shù)0≤()≤()的特點，將啟發(fā)函數(shù)設置為() = 1，通過對比采用不同啟發(fā)函數(shù)算法所消耗的總時間，可以發(fā)現(xiàn)，雖然最終規(guī)劃好的路徑一致，但() = 1時的算法運行時間遠小于() = 0的運行時間，也即啟發(fā)函數(shù)越接近目標真實距離算法運行總時間越短。

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

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

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

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

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

A*算法設計步驟如表2所示。

表2 A*算法設計過程

Tab.2 A* algorithm design process

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

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

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

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

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

3.5 結合交互界面的算法設計效果

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

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

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

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

4.1 智能車硬件結構的設計

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

4.2 下位機智能車控制程序設計

4.2.1 控制智能車的設計

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

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

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

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

4.3 智能車設計結果

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

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

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

5 結果分析與討論

5.1 應用驗證

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

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

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

可能的來源如下：

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

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

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

5.2 結語

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

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

圖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] 陳平. 輔助駕駛中控制與決策關鍵技術研究[D]. 上海交通大學, 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]. 中國科學技術大學, 2010.

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

[7] 金希東. 遺傳算法及其應用[D]. 西南交通大學, 1996.

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

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

[10] 尹芳. 一次路由計算實現(xiàn)層次路由的拓撲方法: CN, CN 1816000 A[P]. 2006.

[11] 任世軍, 洪炳镕, 黃德海. 一種基于柵格擴展的機器人路徑規(guī)劃方法[J]. 哈爾濱工業(yè)大學學報, 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)，國家自然科學基金項目(61773381, 61773382, 61533019)；廣東省科技廳項目(2016B090910001, 2017B090912001)；青島市科技惠民專項項目(16-6-2-62-nsh)；2017湖北省中科院省院合作專項項目；廣東省引進領軍人才計劃(00201511)；東莞創(chuàng)新領軍人才項目(熊剛，呂鍵)等

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

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

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