基于神经网络的AI赛车游戏算法

余婷，刘循

（四川大学计算机学院学院，成都　610065）

YU Ting，LIU Xun

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

基于神经网络的AI赛车游戏算法

余婷，刘循

（四川大学计算机学院学院，成都610065）

0　引言

长久以来赛车游戏就是深受全世界玩家喜爱的游戏类型之一，爱好赛车游戏的玩家们在竞速比赛中主要以速度最快、路线最短为目标，从而使得赛车跑完赛程所花时间最短。非玩家选手也是如此，在给定比赛轨道和赛车的情况下，非玩家选手需要预判一个合理的目标轨迹，然后按照这个轨迹行驶从而达到优异的成绩。而合理的轨迹受轨道形状、汽车气动性能、咬地过弯等因素的影响［3］。

在商业游戏中，通常是领域专家给出赛车的目标轨迹［5］，由游戏开发者通过实际的游戏进行调试。这种手动调试的过程对于游戏开发来说是非常耗费时间的。而文献［1］中的自动轨迹生成的研究又将最短路径和取得最大速度（最小曲率）的轨迹两者分开计算，再将两者折中，从而确定赛车的目标轨迹，这是一种全局最优的方法。但是在实际应用中，由于各种因素的影响赛车无法按照全局最优得到的轨迹行驶，例如障碍物或者其他赛车的撞击。如果实时计算目标轨迹，通常计算量很大，因此本文提出一个基于神经网络的赛车算法。具体实现为：①利用轨迹规划在原始路径上产生目标点，同时优化目标点降低路径曲率；②根据目标点利用遍历算法产生赛车的正向和侧向加速度数据集，然后训练神经网络；③利用局部优化检查加速度的值，确保生成的加速度不会使赛车冲出轨道。

1　算法描述

我们用三个子算法构成模拟玩家行为的智能算法：轨迹规划、神经网络、局部优化。

轨迹规划在赛道上产生目标点，神经网络根据目标点产生运动物体的正向和侧向加速度，最后局部优化检查生成的加速度有没有使物体冲出轨道的可能，它限制加速度在安全的范围内。

1.1轨迹规划

我们设定赛车的可视范围为S，把从赛车位置开始的S段长度的赛道坐标记录下来。算法首先将赛车当前坐标点和最末的轨迹坐标点连成线段L，然后，求轨线上各个坐标点到线段L的垂直距离。如果没有一个点的垂直距离大于预先设定的限制dl，则算法结束，产生的目标点只有一个，即最末的轨线坐标点。如果轨线上存在点的垂直距离大于dl，则将距离最大的点变为新目标点，将原来的线段分为两段。如此递归地进行下去，最后停止。

对距离当前坐标点最近的目标点作“切角”和“延角”的操作。参数手动调整，使路径曲率减小。

图1　在赛车的可视范围内，利用轨迹规划算法计算出物体运动的最优轨迹

1.2神经网络

图2　神经网络的5维输入，右边图出现的概率小于1%

神经网络的输入层、隐藏层存储了权值，权值的修改使用梯度。梯度的计算采用Backpropagation［9］。

我们使用的神经网络有两层，接受5维输入，1维输出，隐藏层为10维。激活函数为tanh-linear。5维的输入参数分别是：赛车的当前速度（v），当前速度于第一个目标点的角度（θ1），当前位置到第一个目标点的距离（L1），当前位置、第一个目标点、第二个目标点形成的夹角 （θ2），第一个目标点到第二个目标点的距离（L2）。如图2，图2中与左边图相对应的另一种情况是右边图。但实验表明，右边图出现的概率小于1%，所以，神经网络忽略此情况。输出的值是一个介于0和1之间的比值，其表示如下：

F表示赛车产生的向正前方的加速度，UpLimit表示赛车的最大加速度，为正值。DownLimit表示赛车的最大减速度，为负值。当神经网络产生target比值后，就可以通过逆变换得到正向加速度，正向加速度确定后，侧向加速度也就确定了。

我们利用遍历算法产生一个训练集。遍历算法根据目标点产生赛车的正向和侧向加速度。算法先尝试

用最大的加速度到达下一个目标点。当赛车到达第一个目标点时，判断赛车是否可以到达下一个目标点，如果出现超速而无法到达的情况，则回溯，将赛车运动的加速度减小一个定值。如此重复，直到找到最终的解。将遍历算法的输入和输出经过处理后记录下来，就可以输入到神经网络进行学习。选择隐藏层不同维数的神经网络进行测试，选取最优的。训练的方法为Levenberg-Marquardt［7］。选取的性能函数为均方误差。训练集被随机的分成了三个集合：训练、验证、测试。

1.3局部优化

由于遍历算法和神经网络产生的加速度，都无法保证赛车不会冲出轨道。因此，我们利用局部优化接收产生的加速度。假设赛车在一定时间内按照给定的加速度运动，判断赛车在这段时间内是否有可能冲出轨道。如果有可能的话，则产生一个局部安全的加速度。

2　实验结果

我们使用的训练示例有11544个，训练神经网络的结构为：两层，tanh-linear型，输入5维，输出1维。隐藏层维数不同的各个神经网络比较如图3。

综合计算效果、计算时间以及防止过拟合的考虑，最后选择隐藏层为10个节点。

2.1神经网络与遍历算法结果比较比较在相同的输入下，两种算法计算出的正向加速度和侧向加速度，共比较2031组。后者减去前者差值分布如图4（a）。（赛车最大向前加速度为3，最大减速度为-10，侧向加速度为1，侧向减速度为-1）

2.2算法效果对比

如图4（b），选择100个轨道，每个3圈，比较两种算法控制赛车的运行时间。大多数情况下，遍历算法优于神经网络。

2.3算法消耗时间分析比较

遍历算法运行时间波动较大。受外部输入和内部参数的共同影响。当超速较多时，回溯次数增多，运行时间变大。同时，增大赛车最大加速度值，减小步长step，回溯也会增多。相反，神经网络的计算时间固定，仅受自身机构影响。

图3　隐藏层维数不同的各个神经网络比较

图4　神经网络与遍历算法结果比较

3　结语

本文利用神经网络模仿玩家行为，在给定赛车和赛道的情况下，算法首先根据赛车和赛道的情况计算出最短路径，并对最短路径做切角、延角操作，确保了路径在实际场景中的可行性。接着找出合适的加速度减少了赛车的运动时间。从实验结果可以看出，神经网络的模仿效果很理想。算法体现出优点：（1）计算用时稳定且较快；（2）插值效果好。未来的研究重点是使算法适用于赛道中存在障碍物以及其他玩家的情景，同时降低神经网络控制赛车的运动时间。

［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，Fyfe 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-），女，重庆丰都人，硕士，研究方向为人工智能、计算机智能

2016-06-03

2016-08-20

赛车游戏中控制非玩家选手的智能算法在比赛场景中存在其他车辆或者障碍物时，不能仅靠整个赛场确定赛车的运动轨迹，需要根据当前状态调整非玩家选手的运动轨迹。从而实现非玩家赛车跑完赛程所花时间最短。基于赛车固有加速度以及赛车安全性的考虑提出基于神经网络AI赛车游戏算法，算法从三个方面模仿玩家行为从而实现赛车竞速时间的减少，实验证明算法的可行性和有效性。

赛车游戏；神经网络；轨迹规划；遍历算法；局部优化

刘循（1963-），女，四川人，博士，副教授，研究方向为计算机应用

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.