Stochastic Model Predictive Control for Autonomous Mobility on Demand
Stochastic Model Predictive Control for Autonomous Mobility on Demand
复制标题
DOI：
10.1109/itsc.2018.8569459
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Matthew W. Tsao;Ramón Iglesias;M. Pavone
中科院分区：
文献类型：
--
作者：
Matthew W. Tsao;Ramón Iglesias;M. Pavone
本文提出了一种随机模型预测控制 (MPC) 算法，该算法利用短期概率预测来调度和重新平衡自主按需移动系统 (AMoD)，即自动驾驶车队。我们首先根据时间扩展的网络流模型提出核心随机优化问题。然后，为了改善其易处理性，我们提出了两个关键的放宽措施。首先，我们用样本平均逼近代替原来的随机问题，并提供其性能保证。其次，我们将控制器分为两个子模块。第一个子模块将车辆分配给现有客户，第二个子模块在整个城市重新分配空置车辆。这使得问题能够作为两个完全单模线性程序来解决，从而允许控制器扩展到较大的问题规模。最后，我们基于真实数据在两个场景中测试了所提出的算法，并表明它优于现有的最先进算法。特别是，在使用共享出行公司滴滴出行的客户数据进行的模拟中，与最先进的非随机算法相比，此处介绍的算法显示客户等待时间减少了 62.3%。
This paper presents a stochastic, model predictive control (MPC) algorithm that leverages short-term probabilistic forecasts for dispatching and rebalancing Autonomous Mobility-on-Demand systems (AMoD), i.e. fleets of self-driving vehicles. We first present the core stochastic optimization problem in terms of a time-expanded network flow model. Then, to ameliorate its tractability, we present two key relaxations. First, we replace the original stochastic problem with a Sample Average Approximation, and provide its performance guarantees. Second, we divide the controller into two submodules. The first submodule assigns vehicles to existing customers and the second redistributes vacant vehicles throughout the city. This enables the problem to be solved as two totally unimodular linear programs, allowing the controller to scale to large problem sizes. Finally, we test the proposed algorithm in two scenarios based on real data and show that it outperforms prior state-of-the-art algorithms. In particular, in a simulation using customer data from the ridesharing company DiDi Chuxing, the algorithm presented here exhibits a 62.3 percent reduction in customer waiting time compared to state of the art non-stochastic algorithms.