基于深度强化学习的智联网汽车感知任务分配

Near-Optimal Vehicular Crowdsensing Task Allocation Empowered by Deep Reinforcement Learning

随着智能/辅助/自动驾驶以及电动汽车技术的飞速发展,当前智联网汽车配备越来越多的传感器,拥有越来越强大的计算、存储和通信能力.作为智联网汽车中重要一类,出租车、滴滴等网约车(Mobility-on-demand vehicles)具有城市覆盖规模大和粒度细,以及空闲时间充足的优点.因此,利用这些智联网汽车现有的移动感知设备能够为城市大规模、细粒度、低成本的感知提供很好的机会.本文以出租车、滴滴等这一类重要的智联网汽车为研究对象,重点研究它们的感知任务分配问题,主要面临两方面挑战:一是智联网汽车载客收益(如出租车载客收入)以及汽车/感知任务分布具有时空动态性,导致智联网汽车的感知成本具有高时空动态性且很难建模和学习.二是感知任务的最优分配问题是NP-hard问题,具有指数级时间复杂度.同时,高移动性的智联网汽车对任务的实时分配要求很高.因此,如何对大规模的智联网汽车实现任务的最优实时分配具有挑战性.为了解决这两个挑战,本文提出基于深度强化学习的智联网汽车感知任务分配方法.通过深度强化学习模型对高时空动态性的汽车感知成本进行精确学习,然后基于学习结果进行感知任务的实时最优分配.具体地,针对挑战一,利用基于双注意力机制的循环神经网络挖掘汽车载客收益的时空相关性,并结合驾驶耗费模型,学习智联网汽车的感知成本.针对挑战二,首先通过问题等价转换和理论分析,证明该任务的最优分配问题具有单调子模目标函数和q-独立系统约束条件.然后,基于子模优化理论,联合考虑整体收益和边际效益,提出多项式时间复杂度的近似最优分配算法(近似率为1/2+c_(max)/c_(min)),其中c_(max)和c_(min)分别表示所有感知成本的最大和最小值.最后,基于两个大规模的智联网汽车数据集(重庆市,约12493辆车;纽约市,约超过1.13亿个行程),对所提方法进行深入全面的评估.实验结果表明,所提方法比7种对比方法平均提高载客收益的预测精度25.1%,提高任务分配的总感知效益37.7%.同时,面向城市道路违规停车监测应用,构建智联网汽车感知原型系统.基于该系统验证了所提方法的可行性和实际应用价值.

With the rapid development of intelligent vehicular technologies,such as Self-driving systems and Advanced Driver Assistance systems,off-the-shelf intelligent vehicles are equipped with more and more sensors,including GPS,camera,Lidar,etc.,thus possessing powerful capabilities of computation and communication along with large-scale storage capacity.As an important kind of the intelligent vehicle,the Mobility-On-Demand(MOD)vehicles(such as Uber,DiDi,and connected taxis)have large-scale,fine-grained coverage in cities along with non-negligible amounts of spare time.Hence,utilizing their available sensors provides promising opportunities in achieving large-scale,fine-grained,and low-cost vehicular crowdsensing for smart cities.As a result,this paper focuses on these MOD vehicles and studies how to optimally allocate the vehicular crowdsensing tasks for the MOD vehicles.It chiefly involves two main challenges:(1)Both the distributions of the MOD vehicles and the sensing tasks have spatial-temporal differences.Also,the pick-up earnings of MOD vehicles vary with the location and time.Hence,it renders the sensing cost highly dynamic in both temporal and spatial dimensions.Even worse,such sensing cost is hard to model because of its highly dynamic nature.(2)The optimal sensing task allocation is a NP-hard problem,which has exponential time complexity.Furthermore,owing to the high mobility of the vehicles,it requires real-time task allocation in vehicular crowdsensing.To address these challenges,we propose a deep reinforcement learning-empowered near-optimal task allocation method for vehicular crowdsensing.We utilize deep reinforcement learning to extract the highly dynamic sensing cost of vehicles,which is fed back to optimally allocate the sensing tasks for each MOD vehicle.Specifically,targeting the first challenge,we deploy the Encoder-Decoder Recurrent Neural Network based on dual attentions(including the spatial attention and the temporal attention)to extract the spatial-temporal correlations of pick-up earnings,which are then used to learn the sensing cost according to the driving cost model.Furthermore,through the equivalent problem transformation,we prove that the task allocation problem has a submodular objective function and a q-dependent constraint.Hence,based on the sub-modularity theory,we propose a near-optimal task allocation algorithm,jointly considering the total utility and marginal utility.It is proved to achieve a 1/2+c_(max)/c_(min)-approximation ratio in polynomial time,where c_(max) and c_(min) represent the maximal and minimal values of the sensing costs for all the vehicles,respectively.Finally,we exploit two large-scale datasets to evaluate the performance of the proposed method.One dataset is about 12493 MOD vehicles in Chongqing City,China,while the other is about 113 million vehicle trips in New York City,America.The results demonstrate that our method averagely improves the prediction accuracy of pick-up earnings and the allocation utility of sensing tasks by 25.1%and 37.7%,respectively,compared with seven baselines.Moreover,we implement a prototype system for on-road illegal parking detection,i.e.,leveraging the smartphone sensor(such as camera and GPS)of massive MOD vehicles to detect the on-road illegal parking events when driving on roads.Based on this system,we validate the proposed method is feasible and significant in practical applications.