2019, Vol. 40
2. 东北大学 机器人科学与工程学院, 辽宁 沈阳 110819
2. School of Robot Science & Engineering, Northeastern University, Shenyang 110819, China
阳光对人类日常生活的影响不可忽视.一方面, 阳光每年给地球带来了3850000EJ的能量[1], 其中部分能量被人们在日常生产生活中所利用；另一方面, 阳光也带来了很多的负面影响，阳光造成的光污染会增加驾驶员的事故率[2], 过多的紫外线照射将增加人们得皮肤癌的风险[3].
由于阳光对人们的日常生活影响巨大, 学者们开始了与之相关的广泛研究.本篇文章的思路基于这样一个事实——人类相关的运动轨迹非常容易受光照影响, 同时利用太阳能作为行驶能源或辅助能源的载具及机器人的数量与日俱增, 太阳光对太阳能电池板的照射时长将决定机器人和载具的工作时限, 并影响其运动轨迹规划.
在这些研究当中, 一些学者将重点放在静态环境中的能源收集和相关设施选址、建设等方面[4]；另外一些学者则将重点放在动态移动物体的阳光分析方面[5], 主要研究了阳光对单一移动物体运动轨迹的影响.而在实际使用中, 由于系统模型复杂、点集冗余等问题将降低系统的运行效率，因此如何提高轨迹分析系统的运行效率是本文重要的研究方向.
基于阳光信息的运动轨迹简化对于与阳光相关的轨迹分析系统来说是一个非常重要的环节.基于阳光的运动轨迹分析既可以帮助人们提高出行体验, 又可以提高太阳能电池板的能源收集效率.而在实际操作中, 人们往往会因为运动轨迹点冗余过多, 从而造成管理困难、计算量大等实际问题.基于阳光的运动轨迹简化, 可以减少系统的冗余点, 简化系统自身需要管理的点的数量, 从而提升运行效率.
本研究的挑战在于处理基于阳光分析的运动轨迹时, 如何建立一种模型, 既可以满足不同的应用, 又可以达到需要的精度；根据该模型, 可以有效地、可控地简化线段.为了攻克这一难关, 本文提出一种2D光照模型, 该模型可以有效描述阳光与运动轨迹的光照关系; 提出了基于该模型的运动轨迹简化方法, 可以有效、可控地简化运动轨迹.
1 研究动机 1.1 运动轨迹分析的挑战尽管基于阳光的运动轨迹分析有很多好处, 但是要实现这样的运动轨迹分析系统面临很多挑战.
模型复杂:不同需求的基于阳光的运动轨迹分析, 需要分析不同的阳光方向.例如, 舒适出行需要分析的是阳光来自左侧还是右侧; 能源收集需要分析的是阳光的特定角度; 安全驾驶需要分析的是阳光来自前方还是后方.需求不同, 则运动轨迹不同, 速度不同, 阳光相对运动物体的位置也不同, 阳光相对不同城市中心点的位置也不同；如果采用完全精确的基于阳光的运动轨迹计算方法对整条路径的光照情况做积分, 虽然计算精确, 但是计算量将十分巨大.
点集冗余:每一条运动轨迹都是由不同的点组成的, 以收集的美国公交车运动轨迹数据为例, 全美国共有由1360874个车站组成的66566条拥有不同形状的交通路线, 一共有31817504个转折点, 平均每条运动轨迹就有478个转折点.每有两个相邻的转折点, 就会有一个方向的路段, 分析如此多的转折点和路段在阳光下的变化情况, 是一个非常棘手的问题.
复杂的模型、大量的冗余点、海量的运动轨迹, 导致看似简单的基于阳光的运动轨迹分析, 实际上非常复杂.
1.2 市内运动轨迹的特点由于城市道路的建设特点, 在市区内产生的运动轨迹的行驶角度和每次转向的持续时间都有一定的特殊性——都是根据道路的结构, 聚集在某些区间内.市内运动轨迹的行驶角度和每次转向的持续时间的聚集性, 是本文设计得以成功的重要保证.以美国明尼阿波利斯的公共交通轨迹数据集为例, 本文首先分析了2017年7月的周末的418990条运动轨迹, 这些运动轨迹包含2581906个转折点, 从中发现市内运动轨迹有碎片化特性.
图 1是运动轨迹每次转向后的持续时间的累积分布函数(cumulative distribution function, CDF)图, 可以看到大部分运动轨迹每次转向后的持续时间都小于10s.这是因为数据信息对角度记录得非常详尽，很微小的角度变化就会产生大量新的数据; 大部分明尼阿波利斯的街道都非常短, 汽车行驶很短的时间就可以通过一条街道; 公交车站往往都设置在靠近路口的地方, 公交车刚离开车站遇到路口, 就会产生新的数据等.图 2是运动轨迹的角度分布图, 从图中可以看到轨迹的角度多集中在0°(360°), 90°, 180°, 270°, 这是由于城市的道路结构大多是由矩形组成的.
|
图 1 行驶时间的CDF图 Fig.1 CDF of driving time |
|
图 2 轨迹角度分布图 Fig.2 Distribution of directions of trajectories |
本文将利用市内运动轨迹的特性来依次解决1.1节提到的两个挑战.
首先讨论复杂模型问题.就运动轨迹而言, 运动轨迹内部的各个路段有不同的方向, 根据不同的需求, 需要采用不同的研究模型.本文建立了一个统一的二维光照运动轨迹模型, 在满足特定需求的同时, 既可以简化运动轨迹内路段, 又可以精确地统计出运动轨迹的光照时间.
其次解决点集冗余问题.通过上面的数据分析可以发现, 一个城市内运动轨迹的角度方向是呈碎片化分布的, 这种碎片化导致每一条运动轨迹都拥有很多点集.使用运动轨迹内点集数据, 结合相应的光照情况, 可以得到这些运动轨迹的光照信息.然而, 在这些点集数据中, 不是所有的点都包含了同等重要的光照信息.本文设计了一种简化法则, 过滤掉包含光照信息少的点, 在宏观逻辑上, 可以减少光照信息分析的计算量.
2 研究内容 2.1 光照模型在太阳能公交车行驶时, 为了更多地收集能量, 太阳能电池板需要尽量地对准太阳.但是由于能量所限, 加上汽车的方向不断变化, 实时自适应跟踪太阳的方向并不现实, 所以本文需要周期性地为太阳能电池板设定一个固定的角度, 以达到能源收集期望的最大化.如何大批量地处理这些运动轨迹, 成为本文的研究内容.为了更好地展现运动轨迹简化的内容, 本文在传统的光照模型中, 抽象出高效的移动物体的二维方向模型, 如图 3所示.假设太阳能电池板的朝向只有左和右, 并依照该假设, 给出如下设计.
|
图 3 二维方向模型 Fig.3 2D orientation model |
假设太阳每天围绕移动物体作顺时针的圆周运动, 如图 3中虚线圆所示.定义北为正方向, 同时定义太阳角度θs为正北到阳光方向的顺时针夹角; 相应地, 定义物体角度θm为正北到物体前进方向的夹角; θo为正北到运动轨迹反方向的顺时针夹角, θo=θm+180°.
对于任何物体, 用一个三维数据(i, θm(i), ti)和行驶速度vi记录其运动轨迹.其中i代表路段序号, θm(i)代表物体在路段i的前进方向, ti代表在路段i的行驶时间.在本文中, 假设运动轨迹匀速行驶, 运动轨迹的长度为∑vi·ti.所有角度都以正北方向为起点并顺时针旋转, 落入[0°, 360°)范围.以图 4为例, 该运动轨迹表示为(1, 90°, 7s), (2, 180°, 5s), (3, 90°, 6s).
|
图 4 基于阳光的运动轨迹分析实例 Fig.4 An example of the sunshine based trajectory |
当θs∈[θm, θo)时, 定义阳光在运动轨迹的右侧, 如图中阴影区域所示; 相反地, 如果阳光满足θs∈[θo, θm+360°), 定义阳光在运动轨迹的左侧.如图 3所示, 阴影部分代表阳光在运动轨迹右侧, 用ξ=－1表示; 白色部分代表阳光在运动轨迹左侧, 用ξ=1表示.对于任何物体的运动轨迹 
|
(1) |
以图 4运动轨迹为例, 当阳光方向为θs=315°时, 光照持续时间为(7s, -5s, 6s).
2.2 基于阳光的运动轨迹简化在阳光运动轨迹分析中, 不是所有的点都承载了相同的阳光信息, 因此通过建立模型, 过滤掉其中重要度低的点.
首先, 用γr, γs分别表示日出和日落的方向.见图 5a所示的路段
|
(2) |
|
图 5 基于阳光的运动轨迹简化 Fig.5 Simplification of sunshine-based trajectory |
相应地, 假设θm(i, j)和γs之间的角度为
|
(3) |
假设太阳每天都作角速度不变的圆周运动, 阳光每天在线段
|
(4) |
在线段
|
(5) |
结合线段的行驶时间ti, j, 定义该运动轨迹的阳光每日期望时间是
|
(6) |
如果一条运动轨迹
|
(7) |
为了删除运动轨迹中的冗余信息, 需要判别数据点的重要性.假设有一条运动轨迹
因为每条运动轨迹中除了起始点和终点都可以被删除, 所以每条拥有n个点的运动轨迹都有2n－2种重新组合的方式.用Tmax来约束简化运动轨迹的误差.本文需要选择一种保留点数最少并同时满足ΔEt≤Tmax的方案, 这个问题是一个NP难的问题, 所以利用遗传算法来求取其近似解[6-7].在遗传算法中, 用1和0的模式对运动轨迹点的保留与删除进行编码, 并用该方式对简化运动轨迹进行编码.用|n|表示保留点的个数, 种群的适应度函数如下:
|
(8) |
该算法利用了奥卡姆剃刀原理[5], 是一种准确度和连续性的折中方案[8-10].
对于任意未处理的有n个点的运动轨迹T(n>2), 先生成一个包含原始运动轨迹的随机种群, 种群的数量为4·(n-2).找到种群中适应度最小并同时满足ΔEt≤Tmax的序列, 并将其保存为最优序列Tbest.然后用遗传算法中标准的突变、交叉、选择, 生成新的种群.当进化代数达到40或者最优序列连续8代没有更新, 或者优化过的序列满足|n|=2时, 搜索停止, 此时最优序列Tbest中保存的, 即为运动轨迹T基于阳光的近似最优解.此最优解的约束为ΔEt≤Tmax.
3 结果与讨论 3.1 实验数据来源本文实验数据来自于真实世界中的General Transit Feed Specification(GTFS)数据.GTFS数据定义了一种公开的公共交通数据交换格式, 现在全球已经有1350个机构共享了他们的GTFS数据.图 6为美国明尼阿波利斯市区的GTFS数据示意图, 图中的点集为公交车站的位置信息.
|
图 6 明尼阿波利斯市的GTFS数据 Fig.6 The GTFS data of Minneapolis |
为了验证算法的可行性, 本文用明尼苏达2017年7月的GTFS数据进行实验.该数据共包括运动轨迹66438条, 共有497064个数据点, 平均每条运动轨迹包括7.5个点.图 7为数据的点集数量与参数Tmax的关系图.从图中可知, 随着Tmax的增长, 点集的数量不断减少, 当Tmax=10s/d时, 点集的数量可以减少1/2.由于起始点和终点不能被删除, 所以在Tmax=∞时, 每条运动轨迹都只保留起始点和终点, 即该数据最多可以简化73%的数据.
|
图 7 点集数量与Tmax的关系 Fig.7 Relationship of the number of points to Tmax |
图 8是Tmax=25s/d时, 明尼阿波利斯市的GTFS运动轨迹数据在相同尺度下简化前后的点密度热力图, 此时点集减少约66%;颜色越深, 代表单位区间内点的数量越多.从图中可以看出本文算法非常高效, 通过简化, 运动轨迹内点的数量大为减少.
|
图 8 简化前后点密度热力图对比 Fig.8 Comparison of heatmaps before and after simplifying points (a)—简化前热力图；(b)—简化后热力图. |
本文设计了一种基于阳光信息的运动轨迹简化方法.该方法针对运动轨迹碎片性的特点, 利用2D光照模型抽象阳光和运动轨迹的关系, 设计了一种基于阳光的线段简化方法, 解决了模型复杂和点集冗余的问题.真实数据仿真实验结果表明, 本文设计的方法可以在可控约束下, 以可控的代价有效地减少运动轨迹中点集的数量.基于阳光的运动轨迹分析有广泛的发展前景, 本文为其系统的高效运行提供了扎实的理论基础和算法铺垫.
| [1] |
Rhodes C J.
Solar energy:principles and possibilities[J]. Science Progress, 2010, 93(1): 37–112.
DOI:10.3184/003685010X12626410325807 |
| [2] |
Abdulaal A, Cintuglu M H, Asfour S, et al.
Solving the multivariant EV routing problem incorporating V2G and G2V options[J]. IEEE Transactions on Transportation Electrification, 2017, 3(1): 238–248.
DOI:10.1109/TTE.2016.2614385 |
| [3] |
Prochaska J O, Velicer W F, Redding C, et al.
Stage-based expert systems to guide a population of primary care patients to quit smoking, eat healthier, prevent skin cancer, and receive regular mammograms[J]. Preventive Medicine, 2005, 41(2): 406–416.
DOI:10.1016/j.ypmed.2004.09.050 |
| [4] |
Sengupta M, Habte A, Gueymard C, et al.Best practices handbook for the collection and use of solar resource data for solar energy applications[R]. Golden, CO: National Renewable Energy Lab(NREL), 2017.
|
| [5] |
Jiang L, Hua Y, Ma C, et al.SunChase: energy-efficient route planning for solar-powered EVs[C]// 2017 IEEE 37th International Conference on Distributed Computing Systems(ICDCS).New York: IEEE, 2017: 383-393.
|
| [6] |
Whitley D.
A genetic algorithm tutorial[J]. Statistics and Computing, 1994, 4(2): 65–85.
|
| [7] |
Falkenauer E.
Genetic algorithms and grouping problems[M]. New York: Wiley, 1998.
|
| [8] |
Grnwald P D, Myung I J, Pitt M A.
Advances in minimum description length:theory and applications(neural information processing)[M]. Cambridge: The MIT Press, 2005.
|
| [9] |
Lee J G, Han J, Li X.Trajectory outlier detection: a partition-and-detect framework[C]// 2008 IEEE 24th International Conference on Data Engineering(ICDE).New York: IEEE, 2008: 140-149.
|
| [10] |
Lee J G, Han J, Whang K Y.Trajectory clustering: a partition-and-group framework[C]//Proceedings of The 2007 ACM SIGMOD International Conference on Management of Data.Beijing: ACM, 2007: 593-604.
|