用Q-Learning算法实现无人车智能代理程序

优达学城的第四个项目,通过Q-Learning算法来实现一个简单的无人车代驾程序。

先来一张训练过程的动图。

训练过程

01 需求分析

一个无人车需要满足的最基本需求就是安全性和可靠性。安全性用来保证用户安全,可靠性用来保证在限定时间内将用户送达目的地。安全性和可靠性划分为A+、A、B、C、D、F六个等级。

安全性

安全性具体表现为遵守交通规则,避免交通事故。

假设有一个简化的世界,路口的交通灯是老式交通灯,不带左右转向指示灯。

简易世界

红线代表红灯的路段。

仅考虑红绿灯就够了吗???NO!!!

根据一般的交通规则我们可以知道,红灯时停止直行和左转,但是可以右转;绿灯时可以任意方向行驶。

在该规则下,最可能引发安全隐患的情况有以下三种:

因此确保安全性需要同时考虑红绿灯、交叉方向车辆、左侧车辆、右侧车辆的意图方向。

  • 绿灯时,想左转,但是交叉方向有直行的车。(见图1)
  • 红灯时,想右转,但是左侧有直行车辆。(见图2)
  • 绿灯时,想直行,但是右侧有右转车辆。(见图3)

引发安全隐患的情况

可靠性

可靠性指按时到达目的地。由于路况的不确定,我们不能确定哪条路那种方式是最短时间消耗,比如遇到堵车,即使目的地就在前方,可能绕个道也比等待耗时短,所以这种情况下,我们只要时刻知道目的地的方位就行。

02

Q-Learning算法

我是通过查阅一个简明的Q-learning教程和知乎上Flappy Bird学习Q-Learning理解的Q-Learning算法。

下图是我画的一个漫画。

分数部分(奖励)

用通俗易懂的语言来讲(可能表述不严谨)Q-Learning算法,比如无人驾驶车,初始阶段,小车不知道自己会遇到什么样的状态(路况),也不知道该采取什么样的策略(前行?左转?右转?什么也不做?),每训练一次可能遇到一种状态,就把它记录下来,比如这一次采取了前行的办法,则世界根据这个动作给它一个打分,下一次又遇到了相同状态,采取了左转策略,则世界根据这个动作再给它一个打分……经过数次训练,小车可能知道了这种状态下自己的所有行动对应的分数,在下一次遇到该状态的时候,则采取分数最高的行动作为本次策略,结束了吗?

没有,采取了分数最高行动之后,世界根据这个动作又要给小车一个打分,就意味着要刷新这一次分数,如何刷新呢?放弃原来的分数重新打分吗?不,我们希望综合原来的分数和本次的分数来打分,也就是Q-Learning公式中的学习率alpha

Q-Learning公式

公式中,t代表训练轮次,s代表状态,a代表动作,r(a)代表所采取的动作a的奖励(分数),alpha代表学习率,gamma代表折扣因子,gamma后面的max代表下一个状态中分数最高的动作的分数,不难发现,与简明教程中房间不同,在无人车中,并不知道下一个状态最高的动作是什么,因为路况是不确定的,所以令gamma=0,则公式便成了

简化后的公式

从公式可以看出,学习率alpha越大,Q值更新依据过去经验越少,alpha越小,Q值更新依据过去经验越大。

至此,分数部分完毕。

动作选择部分

除了分数部分,还有一个重要部分,动作选择。每次该如何确定策略?引入一个探索因子epsilon。

小车的动作选择来源于以往经验和一丢丢“冒险”,就像我们学习新东西需要尝试一样,探索因子越大,小车越爱冒险,依据以往经验越少,探索因子越小,小车越拘束 ,依据以往经验越多。

不难想到,合适的探索因子是需要变化,比如一开始,小车什么都不知道,没有经验可循,因此探索因子应该大一些,越往后,探索因子可适当减小,偶尔根据以往经验决定动作,偶尔冒险决定动作。

具体在程序中的使用就是:探索因子为0-1,产生一个0-1的随机数,如果随机数小于等于探索因子,则冒险,大于,则根据以往经验,这样小车的每个动作就有一定概率是冒险,一定概率是以往经验。

至此,动作选择部分完毕。

具体实现

代码太多且涉及优达学城的版权,因此不贴了,核心逻辑根据上下文的探讨完全可以自己编码实现,重要的是原理的理解。

状态空间

根据需求分析,需要考虑的状态有目的地方向、红绿灯、交叉方向车辆、左侧车辆、右侧车辆,分别用waypoint、light、oncoming、left、right表示,waypoint有4种可能:forward、left、right、None,None代表到达目的地,算一种状态,但不占状态空间,因为到了目的地就不用判断light之类了,所以waypoint有3种状态,light有红和绿两种状态,oncoming、left、right有forward、left、right、None四种状态,则共有3x2x4x4x4=384种状态,所以状态空间的大小是384。

训练轮次

根据我的代码,每一轮有20次选择,最极端的情况是20这20次学的同一种状态的同一个动作,因此384种状态,每种4个动作,想学完所有状态,则需要384x4=1536轮训练。

探索因子的衰减函数

探索因子的可选衰减函数有:

衰减函数

a代表任意一个常数,t代表训练轮次。

参数可以随意选择,但是原则是需要让探索因子在一定轮次内合理衰减到某个设定值(即epsilon的tolerance),假设使用第一个衰减函数公式,a=0.999,经过1536轮训练后,epsilon=0.215074991847,所以tolerance设置为0.21,这样无人车就可以在合理训练轮次内合理地衰减到tolerance。

alpha的选择

alpha参数需要自己调参,一般取0.5左右的值。

实现效果

随机动作选择:

随机动作选择

可以看出,安全性和可靠性不管趋势还是结果都完全随机,很差。

用Q-Learning进行1500+轮训练

1500+轮训练

可以看出,事故越来越少,每个动作的评分也越来越高,可靠性也逐渐提高,且逐渐收敛。最终安全性和可靠性都较高。

用Q-Learning进行1500+轮训练后的状态文件截图

1536轮训练后的状态文件截图

经过1500+次训练后,学习到了382种状态,还有2种没学到,可能需要更多轮训练,也可能不需要,人工智能算法都达不到绝对稳定。

折扣因子gamma去哪了

智能车在行驶过程中只知道目的地的大方向,不知道距离目的地的距离,因此下一个状态是不知道的,且起点和终点也不固定,因此用gamma是没有意义的。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员宝库

AI 玩微信小游戏跳一跳的正确姿势,Auto-Jump 算法详解

来源:肖泰洪 + 安捷 链接:zhuanlan.zhihu.com/p/32636329 ? 最近,微信小游戏跳一跳可以说是火遍了全国,从小孩子到大孩子仿佛每...

3275
来自专栏开心的学习之路

用Q-Learning算法实现无人车智能代理程序

优达学城的第四个项目,通过Q-Learning算法来实现一个简单的无人车代驾程序。 先来一张训练过程的动图。 ? 需求分析 一个无人车需要满足的最基本...

3525
来自专栏量子位

AI玩微信跳一跳的正确姿势:跳一跳Auto-Jump算法详解

作者:肖泰洪 安捷 北京大学 | 数学科学学院研究生 量子位 已获授权编辑发布 转载请联系原作者 ? 最近,微信小游戏跳一跳可以说是火遍了全国,从小孩子到大孩子...

3335
来自专栏AI科技大本营的专栏

玩音乐,敲架子鼓,一个被“耽误了”的机器学习高手

多数伏在案前敲击键盘的程序员或许都曾憧憬:黑框眼镜、格子衬衫、脚踩凉拖背后的另一番模样的自己。

663
来自专栏大数据文摘

李飞飞CS231n项目:这两位工程师想用神经网络帮你还原买家秀

每当某个明星或者时尚博主在微博或者朋友圈po出一张图,这就是一次低成本的营销机会。随着网购与照片分享变得越来越流行,利用用户原创内容(UGC, User Gen...

560
来自专栏AI科技评论

学界丨MIT 开了一门只有九小时的课,教你用深度学习构建自动驾驶

MIT 紧跟时代步伐,开设的 6.S094 课程名为《为自动驾驶构建深度学习》的课程,旨在教学生们为自动驾驶搭建一个深度学习系统,授课者为 Lex Fridma...

3485
来自专栏机器之心

教程 | AI玩微信跳一跳的正确姿势:跳一跳Auto-Jump算法详解

36911
来自专栏量子位

深度神经网络(DNN)是否模拟了人类大脑皮层结构?

作者:Harold Yue 中国科学院大学 | 认知神经科学 量子位 已获授权编辑发布 我自己是生物本科,认知神经科学研究生在读,课余时间比较喜欢编程和机器学习...

34510
来自专栏携程技术中心

深度学习系列 | 深度学习在搜狗无线搜索广告中的应用

编者:本文来自搜狗资深研究员舒鹏在携程技术中心主办的深度学习Meetup中的主题演讲,介绍了深度学习在搜狗无线搜索广告中的应用及成果。戳上面的“携程技术中心”(...

34411
来自专栏AI研习社

AI 玩微信跳一跳的正确姿势——跳一跳 Auto-Jump 算法详解

最近,微信小游戏跳一跳可以说是火遍了全国,从小孩子到大孩子仿佛每一个人都在刷跳一跳,作为无(zhi)所(hui)不(ban)能(zhuan)的 AI 程序员,我...

3538

扫描关注云+社区