首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >滴滴如何使用人工智能来欺骗司机和乘客的?

滴滴如何使用人工智能来欺骗司机和乘客的?

作者头像
用户1594945
发布2019-07-31 14:06:54
1.4K0
发布2019-07-31 14:06:54
举报
文章被收录于专栏:AI启蒙研究院AI启蒙研究院

近期北京打车异常困难,政府严格要求京牌京户,导致合格的网约车数量锐减。我们该如何打车呢?先说结论:从五环外远距离打车去三里屯,是最容易打到车。而晚高峰从金融街往天安门,最难打车。

最近,滴滴AI实验室在KDD2018上发表论文《Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach》,KDD是大数据挖掘方向的顶级会议,滴滴详细介绍了如何利用人工智能方法,优化匹配乘客与司机的订单,达到提高每日订单金额总数的。这篇文章算法极其简单,整篇文章基本没有超出四级英语的词汇,这么简单的一篇论文,能够发表在顶级会议上,完全得益于滴滴掌握了海量的订单大数据。而且近期国内大的互联网公司在人工智能领域的顶级会议上,发表了大量的学术论文,不得不感慨,搞AI研究,有数据是王道啊!

好了,废话不多说,我将从以下几个小问题,分析滴滴是怎么做的。尤其是第6个问题,教大家如何聪明的打车。不想看公式的,直接跳到第6问。

1、滴滴打车的如何匹配乘客和司机?

如这个图所示,某一时刻,有n个乘客,m个司机。由于一个司机只能接一个乘客的订单,在计算机图论里,这是一个二分图的带权匹配问题,用Kuhn-Munkres算法就能得到最优解。这里的权重看滴滴的目的是什么?如果以最短距离为目标,那么连接乘客与司机之间的线的权重就是二者之间的距离。

2、以距离最近的方式匹配乘客与司机是最好的吗?

不是,滴滴最终的目标是一天里所有的订单价格总和最大为目标。这就涉及到一天内将司机乘客匹配后的订单之和加起来。由于一天内需要做很多次匹配,那么在每一个时刻,如何确定司机与乘客之间的连线的权重的问题,是一个典型的马尔可夫决策过程(Markov Decision Process, MDP)。

3、马尔可夫决策过程如果计算得到决策函数:π(s)?

这是一个强化学习过程,其中s是指司机所处的时间与空间,而每一次决策(接某个乘客单或者不接单)的回报G(s)就是打车费用,强化学习中的价值函数Vπ(S)和状态-行为函数Qπ(S)。由于强化学习的模型未知(也就是状态转移函数未知),无法用常规的策略迭代方法,本文用的一步时间差分方法TD(1)计算状态-行为函数V(S)。算法如下图所示,T表示时间,网格表示空间。

4、在未来的订单收入如何贴现到当前的价值函数V(S)中?

文中给出的一个做法是:每隔十分钟衰减为90%,也就是强化学习中的折扣因子γ=0.9,例如30分钟以后的一笔100元的订单收入,贴现到当前为100*0.9*0.9*0.9=72.9元。

司机在某个时间和空间的价值函数V(S),等于未来所有订单收入贴现到现在价值。

5、强化学习方法是如何迭代优化价值函数V(S)的?

第一步:基于滴滴的历史订单,用线性规划方法先离线计算出一个初始的V0(S);

第二步:收集待分配的司机和订单列表; 计算每个司乘匹配对应的动和状态-行为函数Q(S,a)=V(s’)+R,并以此为权重建立二分图,再基于Kuhn-Munkres算法匹配乘客和司机;

第三步:循环第一步和第二步,在第二步得到的匹配策略,用一步时间差分方法TD(1)更新v(s)。

用可视化的方式显示V(S),红色代表V(S)值越大,蓝色表示V(S)值越小。以下是某市晚高峰时候的V(S),越靠近市中心,价值函数V(S)越大。表示司机在市中心接单的汇报优于在郊区,用大白话说,也就是司机尽量开到市中心去,那儿好接单。

下图是早高峰的价值函数V(S)图,与晚高峰不同,二环内的V(S)较小。也即是早高峰的时候,司机尽量不要去市中心,那儿接单收益不高。这点也很容易理解,早高峰时候市中心的车多,供大于求。

6、作为乘客,同等条件下,如何才能比别人更快的叫到车呢?

有四个因素:一是订单的价格。其他条件相同情况下,订单的价格越大。越容易叫到车。体现在公式里,就是强化学习中的一步状态奖励R越大,价值函数V(S)越大。

二是乘客的位置。其他条件相同情况下,位置在热门区域,越难叫到车。因为在一步时间差分方法TD(1)中,v(s)更新为v(s)+a(R+γv(s)-v(s)),因此当前的v(s)越大,更新后的v(s)越小,与司机匹配的权重越小,越不容易接叫到车。这个大家都有同感,下班时的金融街叫车多难啊!

三是目的地的位置。其他条件相同情况下,目的地在热门区域,越容易叫到车。因为在一步时间差分方法TD(1)中,v(s)更新为v(s)+a(R+γv(s’)-v(s)),若v(s’)越大,也就是目的地是热门区域,那么更新后的v(s)越大,越容易叫到车。比如两个乘客在三环同时下单,一个叫车去五环,一个叫车去市天安门,那么去天安门的乘客优先叫到车。

四是与司机的距离。其他条件相同情况下,与司机的距离越近,越容易叫到车。因为距离越近,接客的时间越短,那么订单完成后经过折扣γ,贴现回报R越大。

7、下一步还能如何优化?

当前,以每十分钟,每一定的区域,将时空进行划分为很多“小区”,这种方式还是比较粗,其根本原因是计算简单,用一个不算大的矩阵就能存下价值函数。能不能划分得更细?比如输入将GPS位置和精确到秒的时间一起,作为估算价值函数的输入。那么这个矩阵异常的大,必须要用深度学习方法对价值函数进行建模,其中深度学习方法相比矩阵方法,模型参数大大减小。再利用强化学习方法优化价值函数。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-12-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 AI启蒙研究院 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档