园区内资源的智能化部署有助于降低部署成本，提高资源使用率。如何部署有限的资源更好地服务人群，是普适计算领域研究的问题之一。普适计算领域会议UbiComp2020（2020年9月12日至17日）近日在线上召开。在刚结束的Location and Human Mobility分会场上，京东城市分享了被会议收录的论文《Dynamic Public Resource Allocation based on Human Mobility Prediction》。本期技术前沿，我们将介绍如何基于人流量的变化动态部署公共资源。
在一些POI（兴趣点）比较密集的园区里，如游乐园、公园等地，游客们一天内通常会在不同地点停留观赏游玩。如果停留的地方没有设置垃圾桶，游客们就很有可能会把产生的垃圾随意丢弃，严重影响了环境的整洁和增加了环卫工人工作量。无奈之下，管理人员不得不在所有人可能去的地方都放置垃圾桶，避免行人乱扔垃圾的情况出现。而这种大量垃圾桶的部署，一方面成本较高，另一方面增加了清理维护的难度。然而，由于人群的移动特性，人群在时域和空域上的分布是高度不均匀的，这就导致这些大量部署的垃圾桶有较低的使用率。图1展示了北京欢乐谷垃圾桶的空间分布和人群在一天中不同时段的空间分布。我们可以很明显的看到，用红色虚线框标识的垃圾桶并非每时每刻都在使用中。
图2展示了95个垃圾桶全天的平均使用率，其中70%-80%的垃圾桶没有被充分利用起来。除了由于非数据驱动的静态选址导致的低使用率问题，人群的动态特性是另一个导致该问题的重要因素。
基于这些观察，一个很自然的问题是：如果这些垃圾桶可以移动，我们有没有可能用更少的垃圾桶服务相同数量的人群？值得一提的是，除垃圾桶之外，具有类似目标的资源还包括广告牌以及监控摄像头等等。幸运的是，由于机器人系统的高速发展，多种多样的无人车为了物流及运输目的出现了(图3)。除此之外，有些公司，如京东等开发了能够运输任意负载的通用移动底座，如图4所示，能够让任意资源移动起来。
图3. 无人车. 图4. 通用移动底座.
于是，京东城市联合西安电子科技大学等机构，提出了一种基于预测人口流动的动态公共资源部署方法。基于这种方法，我们能够用更少的资源达到原先静态部署方式相同的全天人群覆盖率。然而，要为这些动态公共资源（或称为智能体）设计一种有效的调度策略并不容易，有以下三方面难点，如图5所示：首先，由于预算的原因，资源的个数是非常有限的，所以我们不能在每一个时间片都覆盖所有区域；其次，智能体有能量的限制，如果我们每一个时间片都将智能体派到大化人群覆盖的地方去，能量会很容易消耗完毕；后，智能体的动作空间非常大，一个智能体可以移动到服务区域内的任意位置，同时一个地点可以被任意智能体服务，计算一种优的策略非常的耗时。
为了克服前两个挑战，我们首先执行多时间步的人流量预测，让我们对未来人流量的动态变化有一个更好的理解，然后我们提出了一个多智能体长期大覆盖调度MALMCS（Multi-Agent Long-term Maximal Coverage Scheduling）问题，该问题基于多步人流量预测结果，在考虑每个智能体能量约束的情况下，调度多个智能体来大化全天的人流量覆盖。为了进一步克服第三个挑战，我们提出了一种启发式算法——能量自适应调度EADS（Energy Adaptive Scheduling）来高效和有效地调度智能体。
我们的问题设置如图6所示。我们将服务区域离散化成均匀大小的栅格，每一个栅格有一个随时间片变化的人流量读数。我们有k个同质的智能体，每个都有相同的能量约束。每个智能体都有一个服务半径，代表了它能服务其周边的区域的大小。同时，该问题中我们认为如果至少有一个智能体能服务栅格，那个栅格中的人流量就被覆盖了。在运营区域中，有一个静态的充电站，所有的智能体必须在充电站开始和结束一天的动态部署。其中栅格化的人流量读数可以来自移动应用程序的时空报点数据或者GPS轨迹数据，通过JUST的时空特征提取模块，我们可以很容易转换成区域栅格数据。
基于以上设定，MALMCS问题定义如下：基于预测得到的直至当天服务时间结束人流量多步预测结果，计算每个智能体后续时间片的位置方位序列，使得在不耗尽每个智能体能量的情况下，让全天服务时间内人流量覆盖实现大化。与大多数规划问题相同，我们在论文中证明了该问题是一个NP难问题。其中，得到多步人流量预测结果的方法现在已经有较多的研究，我们这里采用了当前较为先进的一种基于矩阵分解和深度神经网络的算法[1]，该算法同样来源于京东城市的一个研究工作。
- 模型预测控制MPC（Model Predictive Control）策略
由于长期的预测很难做到非常准确，我们采用了模型预测控制MPC策略。在一天的服务时间段内，每两个连续时间片中间有一个决策时间。当一个决策时间到来后，基于实时观测到的人流量，我们会预测下一时间片直至当天服务时间结束每一时间片的人流量。然后我们会基于新的未来人流量预测结果以及智能体当前的位置和剩余能量，解MALMCS问题，但我们只执行智能体个位置移动决策。当下一决策时间到来后，我们执行相同的操作。我们通过这种策略，克服长期预测误差过大，导致调度结果严重偏离优策略的问题。由于MALMCS是一个NP难问题，计算优解非常耗时。因此，我们提出了一个两步的启发式算法——能量自适应调度EADS来高效地解决这个问题。步是多层级大覆盖调度，在这一步中，我们试图找到一种调度策略使得智能体在未来每一时间片都移动到该时间片预测的大覆盖的位置上去，同时保证每个智能体的能量不会耗尽。如果我们无法找到这种调度策略，我们执行第二步能量感知调度，在这一步中我们寻找一种调度策略能够在能量约束下大化未来人流量覆盖。
这一步的主要思想是，如果对于未来每一个时间片，我们都能派智能体去大化覆盖预测的该时间片的人流量的位置上去，如果预测较为准确，我们就能够获得大的全天人流量覆盖。所以，我们只需要检查是否存在一个多层级的位置序列分配，让所有智能体都不耗尽能量。如果存在，该调度策略就是满足我们优化目标的优策略。要实现该目的，分为两步：步，在未来每一个时间片中选择出实现大覆盖的k个地点。给定一个时间片的人流量空间分布，选择k个地点让整体服务的人流量大化本质是经典的带权重的大k覆盖问题，已被证明是NP难问题 [2]。一种较为直接的贪心算法是：每一步在当前未覆盖地点中选择一个能覆盖多人群的地点，如图7所示，直到选出k个地点。通过这种算法，我们未来每一个时间片都能得到k个选择出的地点。
第二步，将智能体在不同时间片分配到上一步中选择得到的地点，使得能量剩余少的智能体的剩余能量大化，并检查这种分配方式是否可行。使能量剩余少的智能体的剩余能量大化等价于让消耗能量多的智能体能量消耗小化，其本质是一个经典的多层级瓶颈分配问题（multi-level bottleneck assignment problem，MBAP） [3]。可以通过迭代式的解单层瓶颈分配问题（linear bottleneck assignment problem, LBAP）来解决。如图8所示，我们先通过每一层单独解LBAP，我们得到初始分配方案，然后通过调整每一层的分配，尝试是否存在更优方案。算法停止后，如果该分配方案消耗的能量满足能量约束，我们就返回该结果作为我们的调度策略。
如果让消耗能量多的智能体能量消耗小化的策略能不能满足能量约束，意味着智能体一定无法保证每时每刻都移动到大覆盖的地点去，因此我们执行第二步能量感知调度。该方法基于爬山算法，核心思想是我们首先初始化一个策略把智能体派去能让未来预测的平均人流量大化的k个地点，然后让智能体未来一直停在那些地点，如图9所示。从而保证智能体即使未来不移动，我们仍然能够得到一个相对不错的全天人流量覆盖结果。
图9. 策略初始化.
然后我们迭代式地对未来一个时间片，一个智能体，选择一个地点调整能使得人群覆盖增益大化，直到不存在一种调整能够使全天人流量覆盖能够进一步提高，我们的策略改进就停止，并返回每个智能体后续的位置访问序列。
我们从腾讯位置大数据[4]获取了北京欢乐谷从2018年1月1日至2018年10月31日（10个月）的人流量热力图数据，每个时间片为1小时，包含51x108=5,508个栅格，每个栅格大小为10mx10m。我们同时通过实地勘察，收集了园区内95个垃圾桶的位置，其空间分布如图1所示。人流量在一周内的分布如图10所示，由于欢乐谷是一个娱乐场所，我们可以发现周末的人流量是周内人流量的2-3倍。人流量的空间分布如图11所示，我们发现80%的人流其实分布在人流量排名前12.6%的栅格中，这揭示了人流量在空间上的分布高度倾斜。我们同样在图11上画出了垃圾桶的空间分布，80%的垃圾桶分布在人流量排名前18%的栅格中，说明了现有的垃圾桶分布和人群的空间分布具有一定的相关性。但是也有16%的垃圾桶分布在几乎不太有人的栅格，我们猜测原因可能是由于园区的高速发展和娱乐设备的迁移，之前部署的垃圾桶无法服务现在的人群。
图10. 时间分布. 图11. 空间分布.
我们使用欢乐谷过去9个月的人流量数据做训练，得到我们的多时间步人流量预测模型。基于该模型和后一个月真实的人流量数据，我们验证了我们调度算法的有效性。我们以后一个月平均每天能覆盖的人群指数（ADCC）作为评价指标，其中每天能覆盖的人群指数是每个时间片能够覆盖用户指数的总和。
我们比较了不同部署策略下ADCC的差异，对于EADS，我们默认设置智能体的服务面积是10mx10m，每个智能体的能量约束等价于能够移动500m。随着资源个数的增加，不同部署策略下ADCC的变化结果如图12所示。Current是现有的95个垃圾桶的部署策略，灰线代表了其现在的人群覆盖水平。Static是进行静态的大k覆盖选址策略，在该策略下，为了达到相同的人群覆盖率，大约需要44个资源。相对应的，我们提出的EADS方法，只需要19个资源。同时，如果只进行一次规划而不使用MPC策略（EADS-nMPC），我们发现效果有显著的下降，这也印证了我们前面说的，长期预测的结果并不可靠，通过MPC策略，可以减轻预测偏差带来的调度结果不合理。当我们不进行能量约束（EADS-Inf）时，资源使用有略微减少，但是要求智能体有更大的能量上限（实验中等价移动距离约要增大1倍）。EADS-Inf (Theo.)是我们基于未来真实的人流量变化（现实中不可能做到）同时不限制能量约束得到的规划结果，它与EADS-Inf效果上的差距主要是由于模型预测误差造成的。在未来，通过积累历史上更长时间的数据，获得一个更准确的模型，我们有机会实现资源的进一步减少。总体而言，EADS与Current与Static相比，大约实现了80%和56.8%的资源节约，具有较为显著的优势。
[1] Pan Z., et al. Matrix Factorization for Spatio-Temporal Neural Networks with Applications to Urban Flow Prediction. CIKM 2019.[2] Khuller S., et al. The Budgeted Maximum Coverage Problem. Information Processing Letters 70, 1(1999), 39–45, 1999.[3] Dokka T. et al. Approximating the Multi-level Bottleneck Assignment Problem. In International Workshop on Algorithms and Computation. Springer, 64–75, 2012.
