余婷，劉循

（四川大學(xué)計(jì)算機(jī)學(xué)院學(xué)院，成都　610065）

YU Ting，LIU Xun

（College of Computer Science，Sichuan University，Chengdu 610065）

基于神經(jīng)網(wǎng)絡(luò)的AI賽車游戲算法

余婷，劉循

（四川大學(xué)計(jì)算機(jī)學(xué)院學(xué)院，成都610065）

0　引言

長(zhǎng)久以來賽車游戲就是深受全世界玩家喜愛的游戲類型之一，愛好賽車游戲的玩家們?cè)诟?jìng)速比賽中主要以速度最快、路線最短為目標(biāo)，從而使得賽車跑完賽程所花時(shí)間最短。非玩家選手也是如此，在給定比賽軌道和賽車的情況下，非玩家選手需要預(yù)判一個(gè)合理的目標(biāo)軌跡，然后按照這個(gè)軌跡行駛從而達(dá)到優(yōu)異的成績(jī)。而合理的軌跡受軌道形狀、汽車氣動(dòng)性能、咬地過彎等因素的影響［3］。

在商業(yè)游戲中，通常是領(lǐng)域?qū)＜医o出賽車的目標(biāo)軌跡［5］，由游戲開發(fā)者通過實(shí)際的游戲進(jìn)行調(diào)試。這種手動(dòng)調(diào)試的過程對(duì)于游戲開發(fā)來說是非常耗費(fèi)時(shí)間的。而文獻(xiàn)［1］中的自動(dòng)軌跡生成的研究又將最短路徑和取得最大速度（最小曲率）的軌跡兩者分開計(jì)算，再將兩者折中，從而確定賽車的目標(biāo)軌跡，這是一種全局最優(yōu)的方法。但是在實(shí)際應(yīng)用中，由于各種因素的影響賽車無法按照全局最優(yōu)得到的軌跡行駛，例如障礙物或者其他賽車的撞擊。如果實(shí)時(shí)計(jì)算目標(biāo)軌跡，通常計(jì)算量很大，因此本文提出一個(gè)基于神經(jīng)網(wǎng)絡(luò)的賽車算法。具體實(shí)現(xiàn)為：①利用軌跡規(guī)劃在原始路徑上產(chǎn)生目標(biāo)點(diǎn)，同時(shí)優(yōu)化目標(biāo)點(diǎn)降低路徑曲率；②根據(jù)目標(biāo)點(diǎn)利用遍歷算法產(chǎn)生賽車的正向和側(cè)向加速度數(shù)據(jù)集，然后訓(xùn)練神經(jīng)網(wǎng)絡(luò)；③利用局部?jī)?yōu)化檢查加速度的值，確保生成的加速度不會(huì)使賽車沖出軌道。

1　算法描述

我們用三個(gè)子算法構(gòu)成模擬玩家行為的智能算法：軌跡規(guī)劃、神經(jīng)網(wǎng)絡(luò)、局部?jī)?yōu)化。

軌跡規(guī)劃在賽道上產(chǎn)生目標(biāo)點(diǎn)，神經(jīng)網(wǎng)絡(luò)根據(jù)目標(biāo)點(diǎn)產(chǎn)生運(yùn)動(dòng)物體的正向和側(cè)向加速度，最后局部?jī)?yōu)化檢查生成的加速度有沒有使物體沖出軌道的可能，它限制加速度在安全的范圍內(nèi)。

1.1軌跡規(guī)劃

我們?cè)O(shè)定賽車的可視范圍為S，把從賽車位置開始的S段長(zhǎng)度的賽道坐標(biāo)記錄下來。算法首先將賽車當(dāng)前坐標(biāo)點(diǎn)和最末的軌跡坐標(biāo)點(diǎn)連成線段L，然后，求軌線上各個(gè)坐標(biāo)點(diǎn)到線段L的垂直距離。如果沒有一個(gè)點(diǎn)的垂直距離大于預(yù)先設(shè)定的限制dl，則算法結(jié)束，產(chǎn)生的目標(biāo)點(diǎn)只有一個(gè)，即最末的軌線坐標(biāo)點(diǎn)。如果軌線上存在點(diǎn)的垂直距離大于dl，則將距離最大的點(diǎn)變?yōu)樾履繕?biāo)點(diǎn)，將原來的線段分為兩段。如此遞歸地進(jìn)行下去，最后停止。

對(duì)距離當(dāng)前坐標(biāo)點(diǎn)最近的目標(biāo)點(diǎn)作“切角”和“延角”的操作。參數(shù)手動(dòng)調(diào)整，使路徑曲率減小。

圖1　在賽車的可視范圍內(nèi)，利用軌跡規(guī)劃算法計(jì)算出物體運(yùn)動(dòng)的最優(yōu)軌跡

1.2神經(jīng)網(wǎng)絡(luò)

圖2　神經(jīng)網(wǎng)絡(luò)的5維輸入，右邊圖出現(xiàn)的概率小于1%

神經(jīng)網(wǎng)絡(luò)的輸入層、隱藏層存儲(chǔ)了權(quán)值，權(quán)值的修改使用梯度。梯度的計(jì)算采用Backpropagation［9］。

我們使用的神經(jīng)網(wǎng)絡(luò)有兩層，接受5維輸入，1維輸出，隱藏層為10維。激活函數(shù)為tanh-linear。5維的輸入?yún)?shù)分別是：賽車的當(dāng)前速度（v），當(dāng)前速度于第一個(gè)目標(biāo)點(diǎn)的角度（θ1），當(dāng)前位置到第一個(gè)目標(biāo)點(diǎn)的距離（L1），當(dāng)前位置、第一個(gè)目標(biāo)點(diǎn)、第二個(gè)目標(biāo)點(diǎn)形成的夾角 （θ2），第一個(gè)目標(biāo)點(diǎn)到第二個(gè)目標(biāo)點(diǎn)的距離（L2）。如圖2，圖2中與左邊圖相對(duì)應(yīng)的另一種情況是右邊圖。但實(shí)驗(yàn)表明，右邊圖出現(xiàn)的概率小于1%，所以，神經(jīng)網(wǎng)絡(luò)忽略此情況。輸出的值是一個(gè)介于0和1之間的比值，其表示如下：

F表示賽車產(chǎn)生的向正前方的加速度，UpLimit表示賽車的最大加速度，為正值。DownLimit表示賽車的最大減速度，為負(fù)值。當(dāng)神經(jīng)網(wǎng)絡(luò)產(chǎn)生target比值后，就可以通過逆變換得到正向加速度，正向加速度確定后，側(cè)向加速度也就確定了。

我們利用遍歷算法產(chǎn)生一個(gè)訓(xùn)練集。遍歷算法根據(jù)目標(biāo)點(diǎn)產(chǎn)生賽車的正向和側(cè)向加速度。算法先嘗試

用最大的加速度到達(dá)下一個(gè)目標(biāo)點(diǎn)。當(dāng)賽車到達(dá)第一個(gè)目標(biāo)點(diǎn)時(shí)，判斷賽車是否可以到達(dá)下一個(gè)目標(biāo)點(diǎn)，如果出現(xiàn)超速而無法到達(dá)的情況，則回溯，將賽車運(yùn)動(dòng)的加速度減小一個(gè)定值。如此重復(fù)，直到找到最終的解。將遍歷算法的輸入和輸出經(jīng)過處理后記錄下來，就可以輸入到神經(jīng)網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)。選擇隱藏層不同維數(shù)的神經(jīng)網(wǎng)絡(luò)進(jìn)行測(cè)試，選取最優(yōu)的。訓(xùn)練的方法為L(zhǎng)evenberg-Marquardt［7］。選取的性能函數(shù)為均方誤差。訓(xùn)練集被隨機(jī)的分成了三個(gè)集合：訓(xùn)練、驗(yàn)證、測(cè)試。

1.3局部?jī)?yōu)化

由于遍歷算法和神經(jīng)網(wǎng)絡(luò)產(chǎn)生的加速度，都無法保證賽車不會(huì)沖出軌道。因此，我們利用局部?jī)?yōu)化接收產(chǎn)生的加速度。假設(shè)賽車在一定時(shí)間內(nèi)按照給定的加速度運(yùn)動(dòng)，判斷賽車在這段時(shí)間內(nèi)是否有可能沖出軌道。如果有可能的話，則產(chǎn)生一個(gè)局部安全的加速度。

2　實(shí)驗(yàn)結(jié)果

我們使用的訓(xùn)練示例有11544個(gè)，訓(xùn)練神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)為：兩層，tanh-linear型，輸入5維，輸出1維。隱藏層維數(shù)不同的各個(gè)神經(jīng)網(wǎng)絡(luò)比較如圖3。

綜合計(jì)算效果、計(jì)算時(shí)間以及防止過擬合的考慮，最后選擇隱藏層為10個(gè)節(jié)點(diǎn)。

2.1神經(jīng)網(wǎng)絡(luò)與遍歷算法結(jié)果比較比較在相同的輸入下，兩種算法計(jì)算出的正向加速度和側(cè)向加速度，共比較2031組。后者減去前者差值分布如圖4（a）。（賽車最大向前加速度為3，最大減速度為-10，側(cè)向加速度為1，側(cè)向減速度為-1）

2.2算法效果對(duì)比

如圖4（b），選擇100個(gè)軌道，每個(gè)3圈，比較兩種算法控制賽車的運(yùn)行時(shí)間。大多數(shù)情況下，遍歷算法優(yōu)于神經(jīng)網(wǎng)絡(luò)。

2.3算法消耗時(shí)間分析比較

遍歷算法運(yùn)行時(shí)間波動(dòng)較大。受外部輸入和內(nèi)部參數(shù)的共同影響。當(dāng)超速較多時(shí)，回溯次數(shù)增多，運(yùn)行時(shí)間變大。同時(shí)，增大賽車最大加速度值，減小步長(zhǎng)step，回溯也會(huì)增多。相反，神經(jīng)網(wǎng)絡(luò)的計(jì)算時(shí)間固定，僅受自身機(jī)構(gòu)影響。

圖3　隱藏層維數(shù)不同的各個(gè)神經(jīng)網(wǎng)絡(luò)比較

圖4　神經(jīng)網(wǎng)絡(luò)與遍歷算法結(jié)果比較

3　結(jié)語

本文利用神經(jīng)網(wǎng)絡(luò)模仿玩家行為，在給定賽車和賽道的情況下，算法首先根據(jù)賽車和賽道的情況計(jì)算出最短路徑，并對(duì)最短路徑做切角、延角操作，確保了路徑在實(shí)際場(chǎng)景中的可行性。接著找出合適的加速度減少了賽車的運(yùn)動(dòng)時(shí)間。從實(shí)驗(yàn)結(jié)果可以看出，神經(jīng)網(wǎng)絡(luò)的模仿效果很理想。算法體現(xiàn)出優(yōu)點(diǎn)：（1）計(jì)算用時(shí)穩(wěn)定且較快；（2）插值效果好。未來的研究重點(diǎn)是使算法適用于賽道中存在障礙物以及其他玩家的情景，同時(shí)降低神經(jīng)網(wǎng)絡(luò)控制賽車的運(yùn)動(dòng)時(shí)間。

［1］Cardamone L，Loiacono D，Lanzi P L，et al.Searching for the Optimal Racing Line Using Genetic Algorithms［C］.Computational Intelligence and Games（CIG），2010 IEEE Symposium on.IEEE，2010：388-394.

［2］Botta M，Gautieri V，Loiacono D，et al.Evolving the Optimal Racing Line in a High-End Racing Game［C］.Computational Intelligence and Games（CIG），2012 IEEE Conference on.IEEE，2012：108-115.

［3］Braghin F，Cheli F，Melzi S，et al.Race Driver Model［J］.Computers&Structures，2008，86（13）：503-1516.

［4］Tang H，Tan C H，Tan K C，et al.Neural Network Versus Behavior Based Approach in Simulated Car Racing Game［C］.Evolving and Self-Developing Intelligent Systems，2009.ESDIS'09.IEEE Workshop on.IEEE，2009：58-65.

［5］Lecchi S.Artificial Intelligence in Racing Games［C］.Computational Intelligence and Games，2009.CIG 2009.IEEE Symposium on. IEEE，2009：1-1.

［6］Bishop C M.Pattern Recognition and Machine Learning［M］.Singapore：Springer，2006：241-249.

［7］Reynaldi A，Lukas S，Margaretha H.Backpropagation and Levenberg-Marquardt Algorithm for Training Finite Element Neural Network ［C］.Computer Modeling and Simulation（EMS），2012 Sixth UKSim/AMSS European Symposium on.IEEE，2012：89-94.

［8］Bourg D M，Seemann G.AI for Game Developers［M］."O'Reilly Media，Inc."，2004：Section 14.3.

［9］Coulom R.Reinforcement Learning Using Neural Networks，with Applications to Motor Control［D］.Institute National Polytechnique de Grenoble-INPG，2002.

［10］Tan C I，Tai W K.Path Stitching：Controllable Racing Path Generation［C］.International Conference on Machine Learning and Cybernetics.2009，5：2939-2944.

［11］Haykin S，Network N.A Comprehensive Foundation［J］.Neural Networks，2004，2（2004）.

［12］Chaperot B，F(xiàn)yfe C.Advanced Artificial Intelligence Techniques Applied to a Motocross Game［J］.Computing and Information Systems，2006，10（2）：27.

［13］Togelius J，Lucas S M.Arms Races and Car Races［M］.Parallel Problem Solving from Nature-PPSN IX.Springer Berlin Heidelberg，2006：613-622.

［14］Togelius J，Lucas S M.Evolving Robust and Specialized Car Racing Skills［C］.Evolutionary Computation，2006.CEC 2006.IEEE Congress on.IEEE，2006：1187-1194.

［15］Togelius J，Lucas S M，De Nardi R.Computational Intelligence in Racing Games［M］.Advanced Intelligent Paradigms in Computer Games.Springer Berlin Heidelberg，2007：39-69.

［16］Cardamone L，Loiacono D，Lanzi P L.On-Line Neuroevolution Applied to the Open Racing Car Simulator［C］.Evolutionary Computation，2009.CEC'09.IEEE Congress on.IEEE，2009：2622-2629.

YU Ting，LIU Xun

（College of Computer Science，Sichuan University，Chengdu 610065）

Racing Car Games；Neural Networks；Path-Planning；Force-Gen；Local-Optimization

AI Racing Game Algorithm Based on Neural Networks

1007-1423（2016）24-0003-04DOI：10.3969/j.issn.1007-1423.2016.24.001

余婷（1991-），女，重慶豐都人，碩士，研究方向?yàn)槿斯ぶ悄?、?jì)算機(jī)智能

2016-06-03

2016-08-20

賽車游戲中控制非玩家選手的智能算法在比賽場(chǎng)景中存在其他車輛或者障礙物時(shí)，不能僅靠整個(gè)賽場(chǎng)確定賽車的運(yùn)動(dòng)軌跡，需要根據(jù)當(dāng)前狀態(tài)調(diào)整非玩家選手的運(yùn)動(dòng)軌跡。從而實(shí)現(xiàn)非玩家賽車跑完賽程所花時(shí)間最短?；谫愜嚬逃屑铀俣纫约百愜嚢踩缘目紤]提出基于神經(jīng)網(wǎng)絡(luò)AI賽車游戲算法，算法從三個(gè)方面模仿玩家行為從而實(shí)現(xiàn)賽車競(jìng)速時(shí)間的減少，實(shí)驗(yàn)證明算法的可行性和有效性。

賽車游戲；神經(jīng)網(wǎng)絡(luò)；軌跡規(guī)劃；遍歷算法；局部?jī)?yōu)化

劉循（1963-），女，四川人，博士，副教授，研究方向?yàn)橛?jì)算機(jī)應(yīng)用

Racing game is mainly under the competition scene，and there are other cars or obstacle.In order to achieve the best lap-time on a given track with a given car，need to adjust the trajectory of the non-player based on the current status of the game rather than determine that by the entire stadium.Following this sentiment，trains neural networks to play racing games by simulating the behavior of the players.The algorithm is based on the acceleration and car safety，and imitate from three steps.It proves that the algorithm is feasible and effective.