摘 要：为满足自主导航轨迹定性和定量评测要求，提出一种基于不确定性云模型的轨迹分析计算方法．该方法通过提取机器人自主行驶和避障行为中的运动轨迹特征，建立对应的方位偏离、方向偏差和避障安全距离轨迹特征云模型，以云模型的期望作为轨迹特征基本度量，以熵和超熵表达特征所具有的模糊性和随机性．利用云模型所具有的不确定性度量优势，反映系统自主导航过程中的瞬时状态和系统稳定性．实验结果表明，该方法能够有效评估自主导航系统轨迹数据，并能够弥补基于增强学习的方法无法直观反映系统评价稳定性的不足．
关键词：轨迹评测；自主导航；不确定性分析；云模型
Autonomous Navigation Trajectory Evaluation Method Based on Uncertainty Analysis
Abstract:In order to achieve qualitative and quantitative evaluation of autonomous navigation trajectory, a trajectoryanalysis method based on uncertainty cloud model is proposed. In this method, robot’s trajectory features are extractedfrom autonomous driving and avoiding actions, and corresponding feature cloud models for position warp, direction warpand obstacle-avoidance safety distance trajectories are generated. In cloud model, expectation is the basic metric of trajec-tories, and the fuzziness and randomness of features are expressed by entropy and hyper-entropy. By taking advantages ofuncertainty metric of cloud models, the transient state and stability in autonomous navigation can be calculated. Experimentresults show that this method can effectively be used in trajectory evaluation of autonomous navigation, and it can compensateshortcomings of reinforcement learning methods in stability evaluation.
Keywords:trajectory evaluation; autonomous navigation; uncertainty analysis; cloud model
　　1 引言（Introduction）
　　自主导航能力是地面智能机器人智能水平的核心体现之一，也是系统自主规划、决策、控制以及完成多机器人协同工作的前提和保证．对地面智能机器人自主导航能力的测试评估，一方面可以得到系统性能指标，另一方面也可以度量被测系统与基准系统的差异程度，为地面智能机器人的设计和性能改善提供科学依据和指导[1]．
　　目前，对地面智能机器人导航轨迹的评测仍是一个较困难的问题．一方面，评测对象不同于简单的物理量，不具有公度性；另一方面，从测试轨迹数据到评估目标之间缺少科学的映射关系．随着智能科学和认知科学的发展，智能系统测试评估得到了越来越多的重视．美国国家标准研究院（NIST）建立了无人系统自主级别ALFUS框架[2]．框架将自主性定义为系统自我管理水平和质量的总体量度，通过整合多种类别的无人系统，建立了以“自主性”为核心，涵盖环境复杂度（EC）、任务复杂度（MC）和人机交互程度（HI）三因素的评价体系[3]．各因素的分解、权重设置和评测方法等仍在进一步研究中．针对自主机器人在非结构化自然地形条件下的环境感知能力，DARPA实施了地面智能机器人学习计划（LAGR）项目．Hadsell等根据地面水平匹配和立体视觉数据变化度量将地形分为较近范围地形、高可信度区域、低可信度区域、高可信度障碍和低可信度障碍5类，通过训练分类器实现地形分类，并将分类结果准确率作为视觉感知能力的度量依据[4]．Procopio等则通过对目标点先存储后引用， 建立地形模型库，采用人工标记与多次通过某地形后检查地形识别误差的方法，对学习能力进行评估[5]．Evans通过对XUV无人车和DeepBlue博弈系统的研究，提出了一种基于代价分析的评测方法[6]．
　　国内的相关研究中，文[7]引入了模糊概念，建立了简单模糊综合评价模型，根据最大隶属原则得到了整体性能等级划分结果．仿真实验中将各属性划分为4个等级，能够实现粗略判定但评判缺少灵活性．文[8]采用马尔可夫决策模型，将自主导航的轨迹计算转换为对某一驾驶策略回报函数的学习，对不同轨迹的特征回报权值进行计算和线性组合，得到特征期望值，从而定量比较机器人的导航轨迹，得到不同驾驶风格对环境因素的重视程度．文[9]利用逆向增强学习和策略不变条件下的回报函数变形原理，提出了改进的导航轨迹倾向性分析方法，并在驾驶仿真实验平台中进行了验证．但是为得到稳定的效果，基于学习的方法需要扩展较大的学习空间，因此需要较大的计算量．同时，回报函数值仅能反映出学习特征的重要程度，却无法反映不同驾驶风格下轨迹特征的稳定程度．
　　由于评测的轨迹往往不是来源于同一条测试道路，因此环境特征、障碍分布各不相同，同时机器人自身的传感器误差等也导致了自主导航轨迹具有一定的不确定性．
　　因此，本文借鉴不确定性评价中的云理论思想，从机器人导航轨迹中提取有效的评测特征，生成对应评测特征的云模型，以云理论中的云期望作为轨迹特征的基本度量，以熵和超熵表征特征稳定性．利用云模型所具有的不确定性度量优势，反映系统自主导航过程中的瞬时状态和系统稳定度，实现不同环境下的轨迹评测．
　　2 符号与原理（Symbols and principles）
　　本文提出的评测方法基于不确定性分析的云模型展开．云的独特之处就在于，确定的元素所对应的隶属度是不确定的，元素对应的定性概念具有一定的模糊性，同时也体现出元素在论域中分布的随机性．
　　设U是一个用精确数值表示的定量论域，T是U空间上的定性概念，XµU，若对于元素x2X，都存在一个有稳定倾向的随机数Cr(x)2[0;1]，称为x对T的隶属度，即Cr(x): U![0;1]，8x2X（XµU），x!Cr(x)，则概念T从论域U到区间[0;1] 的映射在数域空间的分布称为云[10]．采用云模型可以从定性信息中获得定量数据的范围和分布规律，也可以将精确的数值有效转换成恰当的定性描述，用云模型的整体形态反映出评估的整体特征．本文采用广义1维和广义2维正态云模型描述轨迹特征．如果云滴x满足x»N(Ex;En02)，En0»N(En;He2)，对于定性概念C的确定度满足mC(x) =expµ¡(x¡Ex)22En02¶则x在论域U上的分布（Ex;En;He）称为1维正态云模型．其中，Ex为云模型的期望，描述云滴在论域空间分布的期望值，代表评价信息的中心位置，反映基本度量值；En为云模型的熵，描述云的跨度，代表某一评价的接受范围，反映结果的模糊性和随机性；He为云模型的超熵，即熵的熵，描述云的厚度，反映熵的不确定度．类似地，若云滴(x1;x2)满足x1»N(Ex1;En012); x2»N(Ex2;En022)En01»N(En1;He21); En02»N(En2;He2)对于定性概念C的确定度满足mC(x1;x2) =expµ¡(x1¡Ex1)22En012¡(x2¡Ex2)22En022¶则(x1;x2)在论域U上的分布为2维正态云模型．
　　3 导航轨迹评测（Evaluation of navigationtrajectories）
　　3.1 评测模型
　　根据机器人自主导航所处的不同环境，将轨迹分为障碍区段和非障碍区段两类．在非障碍区段，重点考察机器人行驶过程中的方位偏差、方向偏离和状态稳定性；在障碍区段，重点考察机器人的避障启动距离、避障安全距离和避障状态稳定性．以轮式地面智能机器人为例，约定如下：(1)机器人检测道路两侧的路边线或结构化道路标线作为行车位置参照，尽量保持位于车道正中行驶；(2)机器人在自主行驶直行以及弯道行驶过程中，尽量保持方向的平稳，避免出现较大的方向偏移和抖动；(3)机器人在规避静态障碍过程中，需要与障碍物保持一定的安全距离．为便于讨论，假设道路类型为结构化或准结构化道路，且道路边界线已通过车道线检测算法得到．根据机器人的行驶状态和导航轨迹，建立自主行驶轨迹评测模型，并对状态特征进行参数化处理，以得到评价云的数字特征．196 机 器 人 2013年3月采用机器人车体坐标系，选取安装于机器人前部中心的前视相机所在位置为坐标原点，与车头平行方向为横坐标，垂直方向为纵坐标．xyA BOB' A'Vα βDLDR图1 非障碍区段特征分析Fig.1 Analysis of non-obstacle section features如图1所示，O为车体坐标系原点，点A、A0为左侧道路边线标记点，B、B0均为右侧道路边线标记点，V为道路边线延长线交点，即道路消失点．¡!OA为车体的坐标原点到左侧道路边线的向量，¡!OA的模即左侧方位偏差DL，¡!OB为原点到右侧道路边线的向量，¡!OB的模即右侧方位偏差DR．夹角a为左侧车道线方向¡!AA0与x轴的夹角，显然p=2¡a表示车体前进方向与左侧车道线间的方向偏差AL，同理，b为右侧车道线方向¡!BB0与x轴的夹角，p=2¡b表示车体前进方向与右侧车道线之间的方向偏差AR．因此定义方位偏差（positionwarp）特征为PW=DL¡DR=jOAj¡jOBj (1)定义方向偏离（direction warp）特征为DW=AL¡AR=a¡b (2)理想状态下，在非避障行驶过程中，机器人尽量保持位于道路正中行驶，即机器人方位偏差尽可能保持低水平范围，减少出现过度贴近路边的状况发生；同时机器人保持方向稳定性，减少或避免出现较大幅度的方向偏转．以上为非障碍区段的轨迹特征．在机器人避障行为中，与障碍物的距离保持是考察重点．受到机器人路径规划以及导航控制水平的影响，机器人的避障能力和避障风格存在较大差异．从安全角度讲，机器人避障需要与障碍物保持适当距离，过近与过远对行驶的安全性和避障效率都有较大影响．因此，如图2所示，定义机器人自主避障行为的3个特征参数为：启动避障距离（DAS）：机器人方向开始偏转时世界坐标系下车头到障碍物的距离；侧向保持距离（DAK）：机器人避障过程中，车身侧边距离障碍物的最短距离；结束避障距离（DAE）：机器人绕过障碍后开始直行时车尾到障碍物的距离．8><>:DAS=D1DAK=D2DAE=D3(3) ⹡ D1D2D3图2 障碍区段特征分析Fig.2 Analysis of obstacle section features
　　3.2 评测算法
　　根据不确定性分析的云模型理论，利用上一节提出的5个评测特征，得到各评测特征的1维正态云模型生成算法．输入：导航轨迹的特征数据xki（16i 6n，16k6K），K为轨迹特征数，n为数据量．输出：由特征数据xki 生成的评测特征云模型Ck 以及评测特征云图．步骤：(1)计算各个特征数据样本均值¯Xk、1阶绝对中心矩mk 和样本方差sk：¯Xk=1nnåi=1xki(4)mk=1nnåi=1jxki ¡¯Xkj (5)sk=1n¡1nåi=1(xki ¡¯Xk)2(6)(2)ˆExk=¯Xk．(3)ˆEnk=mkqp±2．(4)ˆHek=qs¡(pm2k±2)．(5) 得到基于特征k 的1维评测特征云模型Ck(ˆExk;ˆEnk;ˆHek)（16k6K）．(6)生成以ˆEnk 为期望、以ˆHek 为方差的正态随机数En0k j（16j 6N）．第35卷第2期 阎岩，等：基于不确定性分析的自主导航轨迹评测方法 197(7)生成以ˆExk 为期望、以En0k j为方差的正态随机数ak j．(8)计算隶属度mk j(ak j) =expá(ak j¡ˆExk)22En02k j!(7)(9)令(aki;mki)为一个云滴，重复步骤(6)～(8)，直至产生基于特征k的N个云滴为止，生成1维评测特征云模型Ck(ˆExk;ˆEnk;ˆHek)的云图．若需要联合k1 和k2 两个特征（16k16K，16k26K），生成2维评测云图，则对步骤(6)～(9)修正如下：(6’)生成以(ˆEnk1;ˆEnk2)为期望、以(ˆHek1;ˆHek2)为方差的正态随机数(En0k1; j;En0k2; j)．(7’) 生成以(ˆExk1;ˆExk2) 为期望、以(En0k1; j;En0k2; j)为方差的正态随机数(ak1; j;ak2; j)（16j 6N）．(8’)计算隶属度jk1;k2=expá(ak1; j ¡ˆExk1)22En02k1; j¡(ak2; j ¡ˆExk2)22En02k2; j!(8)(9’)重复步骤(6’)～(8’)，直至产生基于特征k1和k2 的N个云滴为止，生成2维评测特征云模型Ck1;k2 的云图．
　　4 实验与分析（Experiments and analysis）
　　采用文[7-8] 中的仿真实验环境进行算法对比验证．测试和标准环境建模为5车道，从左至右标记为0～4，其中0车道和4车道在路面之外，其余的1～3车道在路面之内．机器人以恒定速度向前方行驶．上述两文献中采用的是基于特征学习的评测方式，选取“所在车道位置”、“距离最近障碍物的距离”两类特征．模拟生成类似于文[8]的A、B、C三类风格的评测轨迹．导航轨迹基本为光滑直线段，因此仅采用行驶方位偏差、障碍区段的启动避障距离及侧向保持距离生成导航轨迹特征云．根据上节所述特征分析方法，在累计长度为300格的仿真测试环境中对导航轨迹的方位偏差值（PW）、启动避障距离（DAS）、侧向保持距离（DAK）3项特征进行数据采集，根据1维评测云生成算法得到行驶方位偏差特征云模型（PWCloud）、启动障碍避障距离特征云模型（DASCloud）和侧向保持距离特征云模型（DAKCloud），3类模型的期望、熵和超熵的数字特征如表1所示．基于行驶方位偏离得到的特征云如图3所示．显然，云模型的期望、熵和超熵是决定云形状的直观参数．前两者反映特征中心基准位置和特征分布跨度．超熵是熵的不确定度量，超熵相对于熵值过大时，云滴的离散程度显著偏大，整体上甚至呈云雾状．表1 PW、DAS、DAK云模型数字特征Tab.1 Digital characteristics ofPW, DASandDAKCloud Ex En HePWCloudA 2.5 1.2 0.4PWCloudB 0.31 0.15 0.06PWCloudC ¡0.17 0.07 0.03DASCloudA 5.2 0.3 0.1DASCloudB 7.6 0.6 0.2DASCloudC 5.5 0.2 0.1DAKCloudA 1.2 0.2 0.05DAKCloudB 2.8 0.3 0.07DAKCloudC 1.6 0.2 0.05−2 −1 0 1 2 3 400.20.40.60.81 style Astyle Bstyle C图3 基于行驶方位偏差的特征云Fig.3 Characteristics cloud model based on position wrap图4是避障行为中基于启动避障距离和侧向避障距离的特征云图．图中，最左侧的蓝色点云为风格A所得，最右侧的红色点云为风格B所得，中间位置的黑色点云为风格C所得．从云图中可知：(1)风格A与风格C的避障方式较相近，启动障碍距离和侧向保持距离的云模型Ex值和En值均接近，结果与基于马尔可夫决策模型的学习方法所得到的结果保持一致，即A和C在测试环境中具有相似的回报权值．(2)方式B通过保持较远距离来避障，因此启动障碍距离和侧向保持距离的云模型Ex值偏大，其En值偏大，反映出方式B的稳定性相比方式A、C较差．(3)在行驶方位偏差方面，方式C的方位偏差云模型Ex的值最接近0，表明其方位偏差的总体状况最好，同时En值与方式A较接近，表明A、C在方位保持的稳定性上较接近．198 机 器 人 2013年3月2 4 6 8 1000.20.40.60.81 style Astyle Bstyle C(a) 基于DAS的特征云模型1 2 3 4 00.20.40.60.81䆘Ӌؐ䲊ሲᑺstyle Astyle Bstyle C(b)基于DAK的特征云模型图4 基于行驶距离的特征云Fig.4 Characteristics cloud model based on driving distance为进一步验证方法的可行性和有效性，在真实道路导航试验中，对该方法进行了验证．采用所在实验室某地面智能机器人作为本体，对结构化或准结构化等级公路环境下的导航轨迹进行评测．机器人平台安装有可见光摄像机、单线激光雷达、里程计、全球定位系统（GPS）和陀螺仪等设备．环境感知子系统采集前视道路图像，采样频率为10 Hz；融合子系统得到道路边界和通行范围导航模型．本文的实验即利用融合子系统得到的道路模型，直接从图像坐标中计算导航特征参数信息．为便于对照，在自主机器人平台上采用人工驾驶方式，在评测路段上进行类比实验，要求人工驾驶过程尽量保持匀速直线前行，方向调整平稳，以得到基准导航轨迹．如图5所示，在图像中完成道路边线标定，得到道路消失点模型，计算图像中车体的方位偏离和方向偏差角度．由于机器人运动具有连续性，因此将图像采样频率降低到12帧／分的速率，共在3段道路上采集240帧图像．测量方位偏离和方向偏差两个特征参数，并输入评测算法，得到基于方位偏离和方向偏差两个特征参数的2维评测云模型．left_dis right_dis left_dis right_dis图5 真实环境下的导航轨迹Fig.5 Navigation trajectories in practical environment将多传感器融合得到的道路边线逆投影到通过前视摄像机得到的道路图像中．在上述道路上无障碍区段，车辆运动速度在5 km/h到30 km/h之间，融合逆投影的图像帧率为10帧／秒．采集标准国道场景中某人工驾驶路段的连续图像100帧，采集自主驾驶路段的连续图像160帧，按照非障碍区段轨迹模型计算车体的方位偏差值和方向偏离值，根据特征轨迹评测算法，得到基于方位偏差和方向偏离的2维评测云模型（如图6所示），评测云的数字特征见表2．−250255075100−2−10100.20.40.60.81 (a) 2维评测云模型−25 0 25 50 75 100−2−101  (b)投影图图6 特征参数2维云模型Fig.6 2D cloud model of feature parameters图6(a)为基于方位偏差和方向偏离的2维评测云模型，图6(b)为模型在水平面的投影．两图中，偏第35卷第2期 阎岩，等：基于不确定性分析的自主导航轨迹评测方法 199左侧的红色的点为人工驾驶云模型及在水平面的投影点，偏右侧的蓝色点为自主驾驶云模型及在水平面的投影点．从云图中可知，自主驾驶的云滴离散程度明显高于人工驾驶得到的评测云图，表明自主驾驶过程中方位偏离和方向偏差均高于人工基准驾驶过程，系统导航稳定性尚未达到人工驾驶的稳定性水平．表2 2维评测云模型数字特征Tab.2 Digital characteristics of 2D evaluation cloudCloud 人工驾驶 自主驾驶PWEx ¡0.23 ¡1.25PWEn 0.11 0.28PWHe 0.01 0.08DWEx 8.0 35.0DWEn 3.0 12.0DWHe 0.5 2.0
　　5 结论（Conclusion）
　　本文以不确定性云模型为数学工具，通过对地面智能机器人自主导航轨迹的分析，建模出多特征评测云模型以反映不同的轨迹状态．通过仿真实验和真实道路导航实验，可以得到与基于增强学习的评测方法一致的实验结果，同时能够弥补基于增强学习的评测方法在系统综合稳定性评价上的不足．由于该方法的应用和研究尚处于起步阶段，对轨迹特征的选取和计算仍有待进一步验证，同时也需要建立导航轨迹的基准模型，为评测提供更完善的参照标准．
　　参考文献（References）[1] O’Day S, Steinberg M, Yglesias C, et al. Metrics for intelli-gent autonomy[C]//Performance Metrics for Intelligent SystemsWorkshop. Gaithersburg, USA: National Institute of Standardsand Technology, 2004.[2] Huang H M, Albus J, Messina E, et al. Specifying autonomylevels for unmanned systems: Interim report[C]//Proceedingsof SPIE, vol.5422. Bellingham, USA: SPIE, 2004: 386-397.[3] Huang H M, Pavek K, Ragon M, et al. Characterizing un-manned system autonomy: Contextual autonomous capabil-ity and level of autonomy analyses[C]//Proceedings of SPIE,vol.6561. Bellingham, USA: SPIE, 2007: 1-9.[4] Hadsell R, Sermanet P, Ben J, et al. Learning long-range visionfor autonomous off-road driving[J]. Journal of Field Robotics,2009, 26(2): 120-144.[5] Procopio M J, Mulligan J, Grudic G. Learning terrain segmen-tation with classifier ensembles for autonomous robot naviga-tion in unstructured environments[J]. Journal of Field Robotics,2009, 26(2): 145-175.[6] Evans J M. Definitions and measures of intelligence in deep blueand the army XUV[C]//Performance Metrics for Intelligent Sys-tems Workshop. Gaithersburg, USA: National Institute of Stan-dards and Technology, 2007: 148-151.[7] 杨哲，张汝波．无人系统自主等级模糊评价方法[J]．小型微型计算机系统，2009，30(10)：2043-2047.Yang Z, Zhang R B. Fuzzy evaluated method for the autonomylevels of unmanned systems[J]. Journal of Chinese ComputerSystems, 2009, 30(10): 2043-2047.[8] 王勇鑫，钱徽，金卓军，等．基于轨迹分析的自主导航性能评估方法[J]．计算机工程，2011，37(6)：141-144.Wang Y X, Qian H, Jin Z J, et al. Autonomous navigationperformance evaluation method based on trajectory analysis[J].Computer Engineering, 2011, 37(6): 141-144.[9] 金卓军，钱徽，朱淼良．基于倾向性分析的轨迹评测技术[J]．浙江大学学报：工学版，2011，45(10)：1732-1737.Jin Z J, Qian H, Zhu M L. Trajectory evaluation method basedon intention analysis[J]. Journal of Zhejiang University: Engi-neering Science, 2011, 45(10): 1732-1737.[10] 李德毅，刘常昱，杜鹢，等．不确定性人工智能[J]．软件学报，2004，15(11)：1583-1594.Li D Y, Liu C Y, Du Y, et al. Artificial intelligence with uncer-tainty[J]. Journal of Software, 2004, 15(11): 1583-1594.