失踪目标时空搜索策略
背景简介
查找跟踪可疑车辆或人员在城市安全管理中至关重要。比如，有人14:00目击了可疑车辆，但很快就失去了该车的线索，现在是15:00，警察想知道现在这辆车在哪。于是去调监控，城市中有成千上万的摄像头，记录了从目击到当前时刻各个地段的情况，定义一次时空搜索为“检查可疑车辆是否出现在某个时刻某个地段的记录中”，问题出现了：如何才能用最少次数的时空搜索找到这辆车当前在哪？
传统搜索策略是在当前时刻遍历所有地点的记录（ALT）。一个值得探究的想法是，能否把一部分搜索用于中间时刻，从而大幅减少总的搜索次数。
图1 研究的背景和动机
理论和技术简介
我们首次定义了这一时空搜索问题，具体设计了若干时空搜索策略。其中一种启发式中间时刻搜索策略（IHMs）的基本思想是：在每一步中，根据一个启发式指标来确定哪个时刻是搜索的最佳时刻，该指标是“估计的单位时间跨度下所需增加的搜索次数”；在该时刻，按预测的目标出现概率的降序逐个搜索地段，直到找到目标；迭代此步骤，直到在当前时刻找到目标。我们还进一步提出了基于强化学习的时空搜索策略。
图2 几种时空搜索策略的比较
演示简介
假设某车辆在过去某时刻被目击后失踪，现打算利用城市中布下的监控摄像头进行搜索，目标是用最少次数的时空搜索找到这辆车当前在哪。
演示界面分为左上、左下、右上、右下四个部分。左上可以切换显示哪种时空搜索策略，目前演示了IHMs（启发式中间时刻搜索）策略和ALT策略（当前时刻遍历所有地点的记录）。左下显示当前车辆的起始位置，历史轨迹等信息。右上显示车辆进行搜索的当前时刻与目标搜索时刻。右下对比了在两种策略下所需的搜索次数。在进入演示界面后，首先应当选择时空搜索策略（默认IHMs策略），再点击“点击开始搜索”按钮，即可开始时空搜索，此时会展示该车经过该点的多条历史轨迹。点击继续搜索，展示该策略下获得的推测点。若推测成功，车辆移动到推测点，提示搜索成功，并推测下一个点的位置。若推测失败，车辆不移动，重新推测下一个点的位置，直至找到目标。
图3 几种策略下的失踪车辆搜索演示界面
成果列表
- 【论文】Z Yu, L Han, C Chen, W Guo, Z Yu. “Object tracking by the least spatiotemporal searches”, IEEE Internet of Things Journal , 2021, 8 (16), 12934-12946.
- 【论文】L Han, C Tu, Z Yu, F Huang, W Guo, C Chen, Z Yu. “Minimizing the Cost of Spatiotemporal Searches Based on Reinforcement Learning with Probabilistic States”, Wireless Communications and Mobile Computing, 2022, 2022(3): 1-14.
- 【论文】韩磊, 於志勇, 朱伟平, 於志文. “面向车辆目的地推测的时空搜索优化”, 计算机工程, 2020, 46(2): 28-34.
- 【专利】於志勇,韩磊,黄昉菀,郭文忠.“基于强化学习算法的失踪目标搜索方法”,中国专利，2019年申请，ZL20191117 9955.7.
- 【专利】於志勇,韩磊,陈星,郭龙坤,郑相涵. “一种基于贪心策略的失踪目标搜索方法”，中国专利，2018年申请，ZL20181136 3492.5.