《虚拟行人仿真最低能耗动态避障》由会员分享，可在线阅读，更多相关《虚拟行人仿真最低能耗动态避障（9页珍藏版）》请在金锄头文库上搜索。
1、虚拟行人仿真最低能耗动态避障刘景昊; 李远志; 王雷期刊名称】计算机系统应用年(卷),期】2019(028)010【总页数】6页(P233-238) 【关键词】 碰撞避免;虚拟行人; 速度障碍;最低能耗;线性规划【作者】 刘景昊; 李远志;王雷【作者单位】 中国科学技术大学信息科学技术学院 自动化系 合肥 230027【正文语种】 中 文 碰撞避免是计算机虚拟行人仿真的一个基本问题,通常我们可以将其定义为:仿真行 人在虚拟环境中朝目标点的运动过程中,需在每个仿真周期内感知其他静态及动态 实体的存在,若有碰撞可能则采取一定的措施(如调整速度等)避免碰撞1.碰撞避免问题在机器人,虚拟智能体仿真,实
2、时交通模拟等领域均有广泛的研究.现有 的方法一般分成集中式与分布式两种.前者将环境中所有运动实体当成一个完整的 系统,通过理论分析的方法计算所有的碰撞可能,并协调统一地完成避碰操作,但是由 于原理的限制,这种方法仅限应用于单智能体或者少量行人仿真中2.分布式的方法 则将每一个运动实体建模为独立感知周围环境以此指导决策,最终采取相应动作的 智能体.很显然,分布式的方法可以方便且直观地模拟虚拟人群的运动过程.许多碰撞 避免算法都是基于速度障碍模型(velocity obstacles),通过计算相对速度的闽科夫 斯基矢量和,确定行人的可行速度域,从而选择合适新速度避免碰撞.这一类的方法在各领域的研
3、究均有广泛的应用3-5.Berg等人提出的优化相互速度障碍模型 (ORCA)算法6即为经典的基于速度障碍模型的n-body碰撞避免算法，该算法将行 人动态避碰问题转化为线性规划进行求解.因其高效的性能和逼真的仿真结果而被 广泛地应用于动态避碰中7,8.然而现实中行人的运动往往存在着天然的差异性,不同行人因年龄,性格,速度等特性 差异,导致实际的避碰策略存在着个性化特征.为获得更为逼真的仿真效果,提升人群 仿真的真实性和科学性,本文在ORCA算法的基础上加以拓展,并引入行人最低能耗 的概念,设计并实现了行人最低能耗的动态避障算法.1 速度障碍模型概述1.1 速度障碍定义本文所讨论的行人动态避障问
4、题定义如下:仿真平面存在n个仿真行人，每一个行人 均从自身的出发点按照一定的物理限制(最大速度,最大加速度,不能碰撞等)在一个 平面内朝目标点移动.为简化分析起见,我们将行人简化为具有一定半径的圆模型.我 们使用D (p,r)表示圆心为p半径为r的圆模型.对于位置分别在pA和pB处的两个行人速度分别为vA和vB，为衡量在未来两行 人是否有可能发生碰撞，对于行人A,我们可以在速度平面将其考虑成质点，图1中的 阴影扇形区域即表示行人B以速度vB对于行人A的相对速度障碍V OAB(vB),而 只要两行人的相对速度落在这一扇形区域内,则未来一定会发生碰撞.公式定义如下:式中,为行人B速度为vB对行人A
5、的速度障碍，其中入(pA,vA-vB)为从出发沿 vA-vB方向出发的射线,B-A为集合B与集合-A的闵可夫斯基矢量和，数学定义 如下:图1 速度障碍模型简单地，我们可以对上述情况进行拓展，即考虑行人A周围若干个行人分别求出对应的速度障碍,此时只需调整速度使其新的相对速度落于所有其他行人相对速度障碍 区域外即可.1.2改进ORCA算法原始的速度障碍法在计算自身的速度障碍时均假定其他智能体按照之前的速度前进, 彼此之间并无合作策略;且不考虑时间窗口,只要有碰撞可能均需调整速度方向,因此 会出现轨迹振荡、抖动等不真实现象9.为解决这一问题,RVO及ORCA等算法相 继被提出,作为行人仿真的底层避障
6、算法被广泛使用.首先智能体在计算速度障碍时应当考虑未来最近一段时间窗口 t内，类似地如图2(b )所示的阴影区域的类扇形即为考虑时间窗口后的速度障碍区域,数学表示为：ORCA算法假设所有的虚拟行人按照相同的避障策略调整速度进行避障，其核心在 于将速度障碍约束调整为线性直线约束对照图2(c),具体步骤可以描述为：(1) 求解相对速度为优化速度,一般初始值选取为虚拟行人的当前速度;(2) 求解边界上离相对速度最近的一点x,获得从指向x的矢量u.(3) 假设智能体都按照相同策略避障,求解与相垂直的直线分成两个半平面,与第(2)步 中经过点x的边界法向量n同向的半平面作为优化相互半平面约束速度集合，数
7、学 定义见式(5),同理求解.4)与其他周围所有智能体求得由直线约束所包围的可行速度域,从中求解与优化目 标最接近的最优速度.图2 ORCA示意图 在每一步仿真迭代中,智能体获取自身及其视野范围内其他智能体的位置和速度,基 于这些信息可以计算出该智能体A与其他所有智能体的优化相互半平面约束速度 集合;此外,行人还受到自身最大速度的限制因此在ORCA模型下受到的速度选择 约束可以表示为:为了体现行人避障策略采取中存在的差异性,我们将式(5)改写成:其中, 为调节系数,我们将其定义为:式中如果虚拟行人在进入局部避障时速度相同，=1/2,则退化成普通的ORCA模型; 而当虚拟行人的速度存在差异时,不
8、失一般性,我们令，则有且也即速度较小的行 人因为速度低，可以更为方便地调整速度方向，因此承担更多的“主动避障”的责任. 通过调节系数引入,我们可以得到差异化的仿真结果.类似地,静态障碍物可以视为速度为0的障碍物,因此同样的约束构造方法也适用于 静态障碍物.2 虚拟行人动态避障算法我们将仿真行人建模为在一个仿真周期t内不停感知周围环境并采取相应动作的 自治智能体基于改进ORCA算法,结合行人运动最低能耗函数，为仿真行人设计了 动态避障算法.2.1基于最低能耗的行人运动模型最小能耗这一概念最早由Zipf1O提出用于描述生物的运动，可简单概括为：“自然 环境中的生物体在达到自己目标的运动中倾向于采用
9、估计能量消耗最低的方 式”.Guy11 等人将这一原则引入仿真行人的建模提出了经典的Pledestrian模型. 在他的研究中指出,在没有外部因素干扰的条件下,行人的运动按照能耗最低方式进行考虑这一点Fledestrian所采用的行人能耗方程如下:式中,P为单位质量的瞬时能耗,m为行人的质量,t为时间窗口,Eqd为行人按照当前 速度运动一段时间t后到达到位置q,从q再运动到目标d所耗费的能量对于运动 中的仿真行人而言,P的计算方式表示如下：式中N为行人瞬时速度,es表示行人静止能耗参数,ed为运动能耗参数，对于具体的 行人是一个常数.Whittle等人12通过对行人在不同运动速度下的单位时间耗
10、氧量 研究测算出普通行人的es和ed的平均值分别为2.23 J(kgs)-1和1.26 Js(kg-1m-2).在对行人的观察研究中,人们发现行人还有保持自身运动方向的“惯性趋势”13, 因此在变换运动方向时理论上行人应消耗额外的能量,而这在原始的最小能耗方程 中并无考虑.且行人在进行动态避障时,主要应考虑的为对速度方向的改变量;因此我 们可以将行人的瞬时能耗方程修改为:式中,3为行人在变换速度方向时的瞬时角速度大小，同理er为转动能耗参数，前人 研究表明13这一参数的取值约为0.5 2.0 Jskg-1rad-2.式(11)使得我们可以对虚拟行人变换方向的转动能量加以量化.er的数值越大，表
11、示 行人在角速度较大时所消耗的能量也越多.本文的瞬时能耗方程修改可以对虚拟行 人动态避障时在速度方向的变化量上给出理论依据,因此更适用于大规模人群仿真 行人速度方向变更比较频繁时的场景.行人的动态避障是一个局部动态过程,往往并没有一个确切的目标点,因此不能直接 采用式(9)来计算行人的局部避障过程中最低能量消耗.另外,我们注意到行人在完成 动态避障后会回归顶层寻路模块得到的期望速度,一般为指向最终目标点的方向.因 此我们可以参照文献13的处理方法,考虑如图3所示情况,即行人在时间 t0 时刻位 于pA从速度vt-1二vpref转为vt，并经过一段时间t后到达qA撚后行人经过一 段以o为圆心，转
12、弯半径为p二vmax/wmin的匀速圆周运动尽快将速度转换为期 望速度v pref，最终到达q 4完成整个局部避障过程.图3 行人避障速度调整代入式(7)和式(9),并考虑到图3所示的几何关系可得:因此行人动态避障选择新速度时,可以将可行的速度域代入式(13)中得到当前条件 下的最优避障速度,并据此更新位置.2.2 最低能耗局部动态避障算法 如前文所述,我们需要选择在可选速度范围内使得完成局部避障最低能耗的速度,即目标行人的ORCA半平面交集组成了速度可行域，从中选取最优的点问题是计算几 何中典型的二维线性规划问题，使用文献14 中的随机算法已被证明可以在O(n)的 期望时间内对这一问题高效求
13、解,n为约束个数因此我们对每一段线性约束以随机 的顺序逐个求解，在每一段可行线性约束边界进行m次采样分别计算额外的能耗值 E,最终选择能耗最优的新速度，仿真行人并依此到达新位置，即：综上,我们可以将我们的仿真行人动态避障算法总结如下:算法1最低能耗局部动态避障算法输入:虚拟行人位置pi,速度vi,采样数量m输出: 更新速度vinew.(1)获取邻近障碍物线性约束:通过kd-tree等数据结构获取虚拟行 人周围的虚拟行人状态信息，按照式(6)和式(7)计算障碍物约束集L.(2)依次对L中 每一条直线进行线性分析得到的可选速度上下限，并在所选区域进行m次采样，分别 计算式(13)得到最优避碰速度.
14、(3)将上一步得到的最优避碰速度作为虚拟行人的新 速度,并更新位置(4)重复(1)-(3)步,直到虚拟行人到达其目的地.通过对上述算法的分析可知，我们的算法时间复杂度为O (nm),其中n为智能体周 围障碍物的个数,m为计算能耗最优的离散采样点数量在算法1第(1)步获取动态 障碍物时,我们可以只考虑最近N个障碍物的影响现实世界中超高密度人群大约为 5 7人/m215,因此我们将N设定为10,m设定为100,计算量对于当前计算机硬 件计算能力而言足以接受,第3节中通过实验分析表明本文提出的避障算法可以满 足虚拟大规模人群仿真的实时性要求( 30 fps).3 实验分析 实验首先验证虚拟行人的动态
15、避障过程,然后衡量了我们方法在性能上的表现,最后 验证本文方法可以通过简单的参数设置得到差异化的行人的避障效果.3.1虚拟行人动态避障实验我们在小规模的场景下验证了行人动态避障的效果场景一如图4(a)所示的，为行人 分别从左右迎面前进;场景二如图4(b)所示，两列行人分别朝斜对角的目标点前进;可 以看出我们的算法可以让行人正确完成避障并到达目的地.图4 行人动态避障过程3.2 性能实验 在大规模的行人仿真中,在比较拥挤的情况下依然需要确保行人之间不存在碰撞.为 了衡量我们的方法在大规模人群下的表现，我们设计了 Circle场景，即行人建模为半 径0.5 m的圆，行人均匀分布在半径为500 m的
16、大圆上，每个行人目标点设置为经 过圆心的圆对面一点.仿真行人开始会往圆心汇聚,在圆心附近达到避碰高峰,行人调 整自身速度避免碰撞,之后平滑地往目标点前进.图5比较了我们的方法与原始 ORCA算法在相同场景,不同智能体的数目下人群仿真时间可以看出由于我们采用 最低能耗的方式可以显著降低总仿真时间,也即可以获得更为流畅的仿真结果,提升 仿真效率我们的方法使用C#编写，运行在普通PC (CPU Intel i7-7700HQ 2.8 GHz双核,RAM 8 GB)上，图6给出了我们的方法和原始的ORCA算法在不同智能 体个数时每帧计算时间.可以看出我们的方法因为计算量的增加,每帧运算时间大概 是原始ORCA算法的两倍左右.图5 Circle场景不同智
