Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
  • ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

基于激光雷达的无人驾驶障碍物检测和跟踪

王涛 曾文浩 于琪

李耀, 张晓霞, 郭进, 张亚东. 铁路信号系统软件测试建模方法[J]. 西南交通大学学报, 2022, 57(2): 392-400, 424. doi: 10.3969/j.issn.0258-2724.20200530
引用本文: 王涛, 曾文浩, 于琪. 基于激光雷达的无人驾驶障碍物检测和跟踪[J]. 西南交通大学学报, 2021, 56(6): 1346-1354. doi: 10.3969/j.issn.0258-2724.20200240
LI Yao, ZHANG Xiaoxia, GUO Jin, ZHANG Yadong. Modeling Method for Testing Railway Signal System Software[J]. Journal of Southwest Jiaotong University, 2022, 57(2): 392-400, 424. doi: 10.3969/j.issn.0258-2724.20200530
Citation: WANG Tao, ZENG Wenhao, YU Qi. Obstacle Detection and Tracking for Driverless Cars Based on Lidar[J]. Journal of Southwest Jiaotong University, 2021, 56(6): 1346-1354. doi: 10.3969/j.issn.0258-2724.20200240

基于激光雷达的无人驾驶障碍物检测和跟踪

doi: 10.3969/j.issn.0258-2724.20200240
基金项目: 国家自然科学基金(51477146)
详细信息
    作者简介:

    王涛(1972—),男,教授,博士,研究方向为计算机控制技术,E-mail:wangtao618@126.com

  • 中图分类号: TP391

Obstacle Detection and Tracking for Driverless Cars Based on Lidar

  • 摘要:

    针对激光雷达动态障碍物检测与跟踪过程中聚类适应性差、实时性低和跟踪准确度不高等问题,提出一种自适应的密度聚类算法和多特征数据关联方法,分别用于检测和跟踪. 首先,对激光雷达采集的点云进行路沿检测、感兴趣区域提取和地面分割等预处理,去除无关点云;然后,基于自适应的密度聚类算法对非地面的点云进行聚类,完成障碍物点云检测;最后,利用加权多特征数据关联算法结合卡尔曼滤波器实现对动态障碍物跟踪. 通过实验表明:本算法能够根据10 Hz的激光雷达数据实现对障碍物准确、稳定的检测和跟踪,且聚类时间缩短32%.

     

  • 截止2019年底,我国高速铁路营业里程已达到3.5万公里,位居世界第一. 我国已成为世界上高铁运营里程最长、运输密度最高、运营场景最复杂的国家. 铁路信号系统软件测试是保障高铁信号系统安全运行的重要方法,能够有效地预防列车追尾和出轨等行车事故,避免造成人员伤亡及重大财产损失[1],对保障我国高铁的安全运行具有重要意义.

    目前,高铁信号系统软件测试的研究热点之一为基于形式化模型的测试案例自动编制方法,其首先建立软件的测试模型,然后研究算法自动生成满足特定目标的测试案例. 铁路信号系统软件测试中常用的建模方法包括UML状态图(UML statechart)、时间自动机(timed automata,TA)和有色Petri网(colored Petri net,CPN)等. 文献[2]以CPN为测试建模理论基础,以无线闭塞中心切换功能为例,研究基于全路径覆盖和序列优选的测试案例自动编制方法,降低测试案例的重复度. 文献[3]以CTCS-3 (Chinese Train Control System 3)级ATP (automatic train protection)设备模式转换功能为例,基于CPN建模理论,解决状态空间爆炸等问题,生成满足全路径覆盖准则的测试序列. 文献[4]以TA为基础进行测试建模,提出一种满足全状态和全变迁覆盖准则的测试案例生成方法,提高测试案例的生成效率和重用性. 文献[5]研究CTCS-3故障特点,提出了一种基于输入输出时间自动机变异模型的测试案例生成方法. 文献[6]以轨道电路编码功能为研究对象,提出图覆盖、组合覆盖和文法分析相结合的方式自动从UML状态图模型生成测试案例. 文献[7]以UML顺序图为研究基础,利用深度优先算法和网络组合算法对计算机联锁系统测试案例进行组合优化,降低测试案例的重复度. 文献[8]针对铁路信号系统软件的测试度量方法,提出对信号系统软件进行风险分级,按照风险等级递减顺序进行安全性测试的测试策略,指出了以铁路信号系统软件风险等级为基础测试的必要性. 文献[9]对CTCS-3系统安全软件进行接口危险辨识,评估危险事件的风险等级,提出列控系统安全软件黑盒测试的危险分析方法,但未对软件测试建模理论进行研究. 文献[10-12]针对铁路信号系统的形式化描述和验证,分别从时钟约束、风险等级和安全约束等几个方面提出铁路信号系统的建模方法,但这些方法结构复杂,测试模型解析和测试案例搜索算法难以展开,不易直接应用于铁路信号系统软件测试建模.

    目前,铁路信号系统软件测试的研究重点是如何以既有的测试建模方法为基础生成覆盖全面且高效的测试案例,研究提高了测试活动的自动化程度和测试效率. 但现有测试建模方法不能完整地描述软件所有的行为特征,如UML状态图和CPN等方法不能描述软件的时间约束,导致测试案例不能反映软件的时间特性. TA能够描述软件的时间约束,但不具有层次结构,对复杂功能逻辑的描述能力较差,容易出现模型难以理解,甚至错误的问题. 同时,UML状态图、CPN和TA等方法均不能描述软件测试模型中的风险特性.   本文通过分析铁路信号软件的领域特点,总结铁路信号软件测试的建模需求,结合Z规格说明语言(简称Z语言)提出风险时间状态机建模方法,满足铁路信号软件测试的建模需求.

    铁路信号系统软件测试通常采用基于模型的测试(model-based testing,MBT)[13]理论,主要包括分析软件需求、建立测试模型、生成测试案例和执行测试4个阶段,如图1所示. 首先,基于被测软件的需求规格等文件对软件功能和结构进行抽象,采用形式化建模方法建立软件的测试模型;然后,依据测试模型,采用“平坦化”和状态组合等方法对测试模型进行解析,通过广度优先等搜索算法自动生成测试案例;最后,将测试案例加载到测试环境中执行测试,观察测试结果.

    图  1  铁路信号系统软件测试主要过程
    Figure  1.  Main testing process of railway signal system software

    测试模型是编制测试案例和评判测试结果时的重要依据,直接关系到软件测试过程的全面性和有效性,铁路信号软件测试建模方法需要尽可能系统、全面地描述铁路信号系统软件的所有需求.

    铁路信号系统软件测试建模包括功能建模需求和性能建模需求两个方面. 功能建模需求描述系统的功能逻辑(function logic),性能建模需求指与系统相关的性能约束或限制,包括时钟约束(clock constraint)和风险等级(risk level)两个方面.

    1) 功能逻辑

    随着铁路信号系统的规模越来越大,软件承担的功能越来越多、逻辑越来越复杂. 如CTCS-3级列控系统包括9种工作模式,14个主要运营场景,206个功能特征. 铁路信号系统已构成一个复杂的控制系统,软件存在着大量的并发、竞争、冲突等逻辑关系,控制状态转移条件复杂.

    2) 时钟约束

    铁路信号系统软件运算结果的正确性不仅取决于系统逻辑处理的正确性,还取决于运算过程中的时钟约束,要求软件功能需要在指定时间内完成,或在规定时限之后才能发生. 如《CTCS-3级列控系统总体技术方案》[14]要求“当列车前端距分相区还有10秒走行距离时,车载设备向司机发出提示”. 铁路信号系统软件的时钟约束通常为硬实时性(hard real-time)要求,如道岔转换时间、移动授权有效时间、目视模式确认时间等,时钟约束错误或缺失,可能造成重大安全事故.

    3) 风险等级

    铁路信号系统软件由安全功能(safety function)、安全相关功能(safety-related function)和非安全功能(non-safety function)组合构成. 如 《CTCS-3级列控系统测试案例(V3.0)》[15]的功能特征CTCS3-FT-71“由于超速触发紧急制动”属于安全功能,功能特征CTCS3-FT-116“记录数据的下载”属于非安全功能. 不同安全级别的功能对系统造成的安全影响差别较大,由风险等级进行描述. 风险等级的高低是铁路信号系统软件测试案例编制的重要基础,对组织测试案例优先级及分析测试需求具有重要意义.

    根据以上分析,铁路信号系统软件测试建模方法需要描述系统复杂的功能逻辑、时钟约束和风险等级3个方面的特点,严密、准确地反应软件测试需求,且具有良好的可读性和可理解性.

    为定义风险时间状态机建模方法,首先介绍有限状态机(finite state machine, FSM),然后在FSM基础上,结合Z语言,在迁移元素中扩展出时钟约束,在状态元素中扩展出风险等级,最后给出风险时间状态机的定义.

    FSM采用可视化的方式描述系统的功能逻辑,具有清晰、直观的优点,其是表示有限状态以及状态之间转移和动作等行为的数学模型,具有精确性、可推导性和可验证性,是基于模型的测试理论中的经典建模方法[13-16].

    定义1 一个有限状态机M是一个六元组,如式(1)[17].

    M=(S,s0,δ,λ,I,O), (1)

    式中:

    S为有限状态集合;

    s0为初始状态,且s0S

    λ为状态转移函数,λ:S×IS

    δ为输出函数,δ:S×IO

    I 为有限输入符号集合;

    O 为有限输出符号集合.

    图2为一个FSM模型,包括s1s2两个状态,其中s1为初始状态,A、B、C为输入,a、b、c为输出. s1接收到输入A时输出a,转移到s2状态. 模型对应的六元组如下:  S={s1,s2},  s0=s1,  I={A,B,C},  O={a,b,c},  λ(s1,A)=s2λ(s2,B)=s1λ(s2,C)=s2,  δ(s1,A)=aδ(s2,B)=bδ(s2,C)=c.

    图  2  有限状态机模型
    Figure  2.  Example of finite state machine

    接下来结合Z语言,在FSM描述功能逻辑基础上,增加层次结构,扩展出时钟约束和风险等级两个参数,提出风险时间状态机(risk timed statechart,RTSC). 为描述方便,首先定义RTSC的基本元素,然后定义RTSC的层次结构,最后给出RTSC的形式化定义.

    RTSC包括状态、时钟、信号表达式和迁移等基本元素.

    1) 状态

    状态是铁路信号系统软件在一定时期内的存在形式. 对RTSC的非空、有限状态集合S,Z语言描述如下:

    [S]

    m:N1#S=m

    状态包括简单状态(SIMPLE),或状态(OR)和与状态(AND)3种类型,Z语言描述如下:

    P :: = SIMPLE | OR | AND

    OR状态由同一层次的状态和迁移组成,包含且仅包含一个初始状态. 初始状态无源状态,且是任意状态的源状态. 多个并发的OR状态组成AND状态.

    2) 时钟

    RTSC采用时钟描述时间的流逝,有限时钟集合记为X,Z语言描述如下:

    [X]

    m:N#X=m

    对一个时钟变量集合X,时间约束集合定义如式(2).

    Σ::=xg|σ1σ2 (2)

    式中:σ1σ2为时钟约束;xXgN∝∈{,<,,>,=}.

    RTSC时钟约束Σ的Z语言描述如下:

    [Σ]

    m:N#Σ=m

    3) 信号

    信号E具有产生和不产生两种状态,Z语言描述如下:

    [E]

    m:N#E=m

    在某一时刻,正交组件产生的信号称为动作.

    4) 信号表达式

    信号之间的与(and)关系、或(or)关系、非(not)关系构成信号表达式,记为ex如not e表示未产生信号e.

    Π为表示信号永远发生的常量.

    5) 迁移

    迁移是RTSC从源状态转移到目标状态的方式,包括源状态sc、时钟约束σ、信号表达式ex、转移时产生的信号e、重置的时钟x及目标状态st. 迁移的Z语言描述如下:

    RTSC的状态层次H包括底状态γ、为状态分配子状态的有限状态层次函数ω,定义状态类型的有限状态类型函数κ,定义状态父状态的ρ函数. H满足以下性质:

    1) ω为非SIMPLE类型的状态分配子状态;

    2) 状态之间的层次关系不能形成循环结构;

    3) γ为OR状态或AND状态,是唯一没有父状态的状态;

    4) 任意非γ的状态都具有唯一的父状态,且均可以由γ通过ω传递到达.

    H的Z模式定义如下:

    其中:F S表示集合S的所有有限子集的集合;dom ω表示ω的定义域;ran ρ表示ρ的值域;si: dom ρ; sj: dom ω表示ρ定义域中的任意状态siω定义域中的任意状态sjij为不为0的自然数,且ij.

    RTSC由状态层次和迁移集构成,采用风险等级函数η为SIMPLE状态分配风险等级,满足以下性质:

    1) η仅为SIMPLE状态分配风险等级;

    2) OR状态和AND状态的风险等级为其包含的子状态的风险等级的最大值.

    3) 对任意迁移,只能有一个同层次的源状态和目标状态,源状态和目标状态可以是AND或SIMPLE状态.

    RTSC的Z模式定义如下:

    其中:F1T表示集合T的所有非空有限子集的集合.

    一个时钟集合X的时钟解释v是指每个时钟变量x到时间序列上的一个全映射. 某时刻,RTSC能够同时处于最大的状态集结合当前的时钟解释称为格局(configuration),记为U. 在任意时刻,RTSC只有一个活动的格局,满足以下规则:

    1) U包含γ状态;

    2) U包含AND状态s,则U 包含s的每一个子状态;

    3) U包含OR状态s,则U包含s的某一个子状态;

    4) U包含非γ的状态s,则U包含s的父状态;

    5) U仅包含满足规则1) ~ 4)的所有状态.

    格局公理描述如下:

    其中:k表示不为0的自然数.

    RTSC格局转移过程记为 (us, v(X), E),其中us表示当前格局包含的状态集,v(X)表示时钟解释,E表示转移过程中产生的动作集,具体过程如下:

    1) 激励. 当RTSC接受到新的时钟解释或信号时开始格局转移:(us,v(X),)(us,v(X),e).

    2) 计算. 格局转移过程以SIMPLE状态为基础,从γ状态,通过OR状态和AND状态向下分解,包括以下2个规则:

    规则1 AND状态并行地计算其所包含的OR状态的转移.

    规则2 OR状态计算当前激活的SIMPLE状态的变迁t上的信号,产生t上的动作,重置t的时钟,离开变迁源状态τ.sc到达变迁状态t.st,满足:us=ust.sct.stG=Gt.ev(t.x)=0.

    3) 结束. RTSC根据状态类型迭代相应规则直至转移稳定,保留时钟解释,清空转移期间的信号.

    RTSC从初始格局开始,根据产生的信号或时钟的更新激活格局转移过程;依据层次结构,迭代AND状态和OR状态的规则,直到计算出下一组稳定的状态. 格局转移时,迁移的触发信号均发生,且时钟解释满足迁移上的时钟约束,同时产生迁移上的动作,重置迁移上的时钟变量.

    RTSC的语义可以由其对应的时间标记迁移系统(timed transition system,TTS)进行定义.

    定义2 一个时间标记迁移系统TTS是一个4元组:

    Ω=(L,l0,,Σ), (3)

    式中:L为状态集合;

    l0为初始状态,l0L

    →⊆L×(ΣR)×L为转移关系,且满足:1) 如果 l0l,则 l = l; 2) 如果 ldl,且 ldld,dR,则 ld + dl; 3) 如果 ldldR,则 0dd,则有 lL,满足 ldllddl.

    在时钟解释v下,如果时钟约束σ为真,则称时钟解释v满足时钟约束σ,记为v|=σ.

    定义3 对任意RTSC,其语义可以通过时间标记迁移系统Ω=(L,l0,,Σ)进行定义,其中:

    L=U×RX

    l0 = (us0,v0)us0为RTSC的初始状态集,且对任意xXv0(x)=0

    转移关系满足:1) 对(us,v)和一个迁移usex,σ,e,xus,且v|=σ,则 (us,v)ex(us,v);2) 对(us,v)和时间增量dR(us,v)d(us,v+d).

    RTSC从初始格局开始,通过动作转移或时延转移实现格局变化.

    1) 动作转移. 当前激活的信号和时钟解释满足变迁的信号表达式和时钟约束,触发动作迁移,激活变迁上的动作,重置变迁时钟为0.

    2) 时延转移. 时延转移保持格局状态不变,对所有时钟增加相同的时间增量.

    计算机联锁系统是铁路信号系统中典型的安全关键系统. 以计算机联锁系统的道岔定位选排子系统为例建立RTSC测试模型,解释RTSC的格局转移机制.

    道岔定位选排子系统根据道岔操作命令或进路请求,检查道岔当前是否处于定位. 当道岔状态与期望不一致时,选排道岔到需求位置[18]. 该系统涉及11个信号,主要信号名称及其含义见表1.

    表  1  道岔子系统信号含义
    Table  1.  Meaning of signals in switch subsystem
    信号含义信号含义信号含义
    e1 定位请求 e4 定位需求 e7 道岔定位
    e2 道岔转换 e5 道岔锁闭 e8 转换成功
    e3 转换超时 e6 反位请求 e9 选排一致
    下载: 导出CSV 
    | 显示表格

    道岔定位选排子系统的RTSC模型如图3所示,记为DRTSC,其中ran η = {0, 1, 2, 3, 4},分别对应EN 50128定义的5个安全完整度等级SIL 0~4. DRTSC包括1个时钟x1,最高风险等级为SIL 4,最低为SIL 2,底状态为s0,初始状态为{s3,s4,s5,s6,s9,s11}s1s2s3分别为SIMPLE状态、AND状态和OR状态,η(s1)=4η(s3)=max \rho \left( {{s_2}} \right) = {s_0} {\kern 1pt} {\kern 1pt} \omega \left( {{s_2}} \right){\text{ = }}\left\{ {{s_3},{s_4},{s_5}} \right\} .

    DRTSC中:迁移的表现形式为[e] [σ] / [a] [x];e为触发转移的信号;σ为时钟约束;a为转移时产生的动作;x为重置的时钟,记为 {s_1}\xrightarrow{{e,{\kern 1pt} \sigma {\kern 1pt} /{\kern 1pt} {\kern 1pt} a,{\kern 1pt} x}}{s_{\text{2}}} . 如 {s_{14}}\xrightarrow{{{e_7},{\kern 1pt} {x_{\text{1}}} < 13{\kern 1pt} {\kern 1pt} /{\kern 1pt} {\kern 1pt} {e_8},{\kern 1pt} {x_{\text{1}}}}}{s_{13}} 表示状态s14激活时,当检测到信号e7,并满足时间约束x1<13,DRTSC迁移到s13,同时产生信号e8,并重置时钟x1.

    DRTSC模型中,s3s4s5分别表示道岔转换的“安全请求”,“道岔转换”和转换的“时钟约束”状态. DRTSC主要描述以下过程:

    道岔“安全请求”状态检测到定位需求后,在道岔未锁闭、无反位请求、未处于定位时,进一步检查道岔转换状态,未处于转换过程中或转换超时时,判定定位请求安全. “道岔转换”状态接受到“定位请求”信号后,如果道岔未锁闭则重置时钟x1;条件保持1 s后,请求道岔转换. “时钟约束”状态接受道岔转换动作后,重置时钟x1并开始计时,13 s内检测到道岔转换到定位则转换成功,否则转换超时. 当“道岔转换”状态接受到“时钟约束”状态的“转换成功”信号后判定道岔转换成功. 当同时处于“定位请求”和“转换成功”状态时,判定“选排一致”. 转换过程中任意时刻,道岔子系统接受到反位请求信号立即重置时钟,返回初始状态.

    图  3  道岔子系统RTSC模型
    Figure  3.  RTSC model of switch subsystem

    DRTSC的初始格局为( ( {s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}}, {s_{\text{6}}},{s_{\text{9}}},{s_{{\text{13}}}} ), ( {\text{0}} ) ). 下面以格局 \left( {\left( {{s_{\text{0}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{14}}}}} \right){\text{,}}\left( {\text{2}} \right)} \right) ,产生信号e7 v\left( x \right) = {\text{3}} 为例,分析DRTSC的格局转移过程.

    1) DRTSC接受激励信号和更新的时钟解释:\left( {\left( {{s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{14}}}}} \right),\left( {\text{2}} \right),\left( \varnothing \right)} \right) \to ( ( {s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}}, {s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{14}}}} ){\text{,}}\left( {\text{3}} \right){\text{,}}( {{e_{\text{7}}}} ) ) .

    2) 由于s0为OR状态,根据规则 2,s0当前激活状态为s2. s2为AND状态,根据规则 1,s2并行计算 {s_{\text{3}}} , {s_{\text{4}}} , {s_{\text{5}}} ,计算过程为

    e7 v\left( x \right) = {\text{3}} 满足 {s_{{\text{14}}}} 迁移到 {s_{{\text{13}}}} 的信号表达式和时钟约束,迁移时重置时钟x1,同时产生信号e8: \left( {\left( {{s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{14}}}}} \right){\text{,}}\left( {\text{3}} \right){\text{,}}\left( {{e_{\text{7}}}} \right)} \right) \to ( ( {s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}}, {s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{13}}}} ){\text{,}}\left( {\text{0}} \right){\text{,}}( {{e_{\text{7}}},{e_{\text{8}}}} ) );

    e8信号触发s4的子状态s11,并转移到状态s12 \left( {\left( {{s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{13}}}}} \right){\text{,}}\left( {\text{0}} \right){\text{,}}\left( {{e_{\text{7}}},{e_{\text{8}}}} \right)} \right) \to ( ( {s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}}, {s_{\text{5}}},{s_{\text{8}}},{s_{{\text{12}}}},{s_{{\text{13}}}} ){\text{,}}\left( {\text{0}} \right){\text{,}} \left( {{e_{\text{7}}},{e_{\text{8}}},{e_{{\text{11}}}}} \right) );

    s3的状态s8满足自迁移变迁:( ( {s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}}, {s_{{\text{12}}}},{s_{{\text{13}}}} ),\;\left( {\text{0}} \right),\;\left( {{e_{\text{7}}},{e_{\text{8}}},{e_{{\text{11}}}}} \right) ) \to( ( {{s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}},{s_{{\text{12}}}},{s_{{\text{13}}}}} ) , ( {\text{0}} ){\text{,}}( {{e_{\text{7}}},{e_{\text{8}}},{e_{{\text{11}}}},{e_{\text{1}}}} ) ).

    s3s4s5计算结束后,DRTSC激活的信号包括( {e_{\text{7}}}, {e_{\text{8}}},{e_{{\text{11}}}},{e_{\text{1}}} ),激活s2s1的迁移:( ( {s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}}, {s_{{\text{12}}}}, {s_{{\text{13}}}} ){\text{,}}\left( {\text{0}} \right){\text{,}}\left( {{e_{\text{7}}},{e_{\text{8}}},{e_{{\text{11}}}},{e_{\text{1}}}} \right) ). \to \left( {\left( {{s_{\text{0}}},{s_{\text{1}}}} \right){\text{,}}\left( {\text{0}} \right){\text{,}}\left( {{e_{\text{7}}},{e_{\text{8}}},{e_{{\text{11}}}},{e_{\text{1}}}} \right)} \right) .

    3) 计算结束,DRTSC格局更新为 \left(\left({s}_{\text{0}},{s}_{\text{1}}\right)\text{,}\left(\text{0}\right)\right) .

    根据以上分析,DRTSC格局转移过程记为\left( {\left( {{s_{\text{0}}},{s_{\text{2}}},{s_{\text{3}}},{s_{\text{4}}},{s_{\text{5}}},{s_{\text{8}}},{s_{{\text{11}}}},{s_{{\text{14}}}}} \right),\left( {\text{2}} \right)} \right)\xrightarrow{{{e_7},v\left( x \right)\; = \;3}}\left(\left({s}_{\text{0}}, {s}_{\text{1}}\right),\left(\text{0}\right)\right), 表示道岔在处于“定位安全请求”,“道岔转换”,“道岔转换计时中”状态时,检测到道岔在第3 s转移到定位,判定道岔选排一致.

    DRTSC描述了道岔定位转移过程中的功能逻辑、时钟约束和风险等级.

    5.3.1   测试需求覆盖

    1) 功能逻辑

    DRTSC采用16个状态,19条迁移和11个信号描述道岔转换过程的功能逻辑.

    2) 时钟约束

    DRTSC通过时钟x1描述道岔转换过程中信号保持时间1 s和转换超时判断时间13 s,包括时钟约束x1>1,x1<13和x1\geqslant 13. 如\left({s}_{14}, \text{3}\right)\xrightarrow{{\rm{not}}\;{e}_{7},\;{x}_{\text{1}}\geqslant 13/{e}_{3}}\left({s}_{15}, \text{4}\right)描述道岔转换超过13 s后进入超时状态s15.

    3) 风险等级

    DRTSC描述了道岔转换过程中风险等级的变化情况,包括风险等级升高、降低以及保持不变,风险转移矩阵如图4所示. 其中,正数表示风险等级升高,负数表示风险等级降低,0表示风险等级不变,“−”表示状态之间无转移关系.

    R78 = 1描述了迁移\left( {{s_{\text{7}}},{\text{3}}} \right)\xrightarrow{{{\rm{not}}{\kern 1pt} {\kern 1pt} {e_{\text{3}}}{\kern 1pt} {\kern 1pt} {\rm{and}}{\kern 1pt} {\kern 1pt} {\rm{not}}{\kern 1pt} {\kern 1pt} {e_{10}}{\kern 1pt} {\kern 1pt} /{\kern 1pt} {\kern 1pt} {e_{\text{1}}}}} \left( {{s_{\text{8}}},{\text{4}}} \right) ,表示道岔由SIL 3的状态s7转移到SIL 4的s8,风险等级升高1个等级,软件测试时需要重点对此类变迁进行测试.

    5.3.2   与TA对比

    为检测RTSC模型的描述能力,选取铁路信号系统软件测试中广泛采用的TA建模方法进行对比. 道岔定位选排的TA模型如图5所示,记为DTA. DTA由4个TA构件组成TA网络实现道岔定位选排的测试需求,其中,为描述DRTSC的否定信号,如未接收到信号e5,在DTA中增加en5. DTADRTSC均包括1个时钟,状态、变迁和信号数量方面的比较如表2所示,DRTSCDTA节省62%的变迁数,节省54%的状态数. 其中,DRTSC的状态数为除去层次结构后的SIMPLE状态的数量.

    图  4  道岔子系统风险矩阵
    Figure  4.  Risk matrix of switch subsystem

    进一步,随机选取计算机联锁系统软件中的4个子功能,分别采用RTSC和TA进行建模,RTSC模型和TA模型在构件、状态和变迁3个方面的对比如图6所示.

    图  5  道岔子系统TA模型
    Figure  5.  TA model of switch subsystem
    图  6  RTSC模型与TA模型对比
    Figure  6.  Comparison between RTSC model and TA model

    通过表2图6,相对TA建模方法,RTSC模型具有更少的构件数、状态数、变迁数和信号数. 且随着功能逻辑复杂度的增加,RTSC节省的状态数和变迁数越多,RTSC模型更为简洁、清晰,表达能力更强,可读性更高,适合描述铁路信号系统软件复杂的功能逻辑.

    RTSC继承了FSM可视化、直观和简介的特点,其状态转移、层次性和并发性能够描述软件的功能逻辑,时钟约束能够描述软件的时间关系,风险等级能够描述软件不同功能之间的安全性关系. 具体的,RTSC与铁路信号系统软件测试建模需求之间的关系如表3所示.

    表  2  DRTSCDTA 对比
    Table  2.  Comparison between DRTSC and DTA
    模型构件/个状态/个变迁/条信号/个
    DRTSC1111911
    DTA4244918
    下载: 导出CSV 
    | 显示表格
    表  3  RTSC与测试需求的关系
    Table  3.  Relationship between RTSC and test requirements
    特性功能性实时性风险
    状态迁移 × ×
    层次性 × ×
    并发性 × ×
    时间约束 × ×
    风险等级 × ×
    注:“√”表示RTSC特性满足建模需求;“×”则相反.
    下载: 导出CSV 
    | 显示表格

    1) 铁路信号系统软件测试建模方法不能很好地描述铁路信号系统软件测试的建模需求,不能同时描述软件的功能逻辑、时钟约束和风险等级3个方面的特征.

    2) 以有限状态机理论为基础,扩展出时钟约束和风险等级属性,提出风险时间状态机建模方法,采用Z语言给出了风险时间状态机的定义,阐述了风险时间状态机的格局转移规则,满足铁路信号系统软件测试在功能逻辑、时钟约束和风险等级方面的建模需求.

    3) 以计算机联锁系统中的道岔子系统为例,利用风险时间状态机建立了道岔子系统软件的测试模型,并选取TA建模方法进行对比,结果表明风险时间状态机描述能力更强.

    4) 文章提出的方法已在计算机联锁系统的软件测试中得到应用,实践表明该方法能够满足铁路信号系统软件测试的建模需求,为铁路信号系统软件测试提供了形式化建模的理论基础.

  • 图 1  “智轨”列车平台以及株洲大道

    Figure 1.  ART Train Platform and Zhuzhou Avenue

    图 2  路沿点提取效果

    Figure 2.  Effect of curb point extraction

    图 3  地面分割效果

    Figure 3.  Effect of ground segmentation

    图 4  球型搜索和椭球型搜索示意

    Figure 4.  Illustration of spherical search and ellipsoid search

    图 5  物体发生倾斜时的示意

    Figure 5.  Schematic diagram in the case of tilted object

    图 6  椭球域及其代表对象的三维邻域

    Figure 6.  Three-dimensional neighborhood ofellipsoidal domain and its representative objects

    图 7  障碍物跟踪算法流程

    Figure 7.  Flowchart of obstacle tracking algorithm

    图 8  障碍物与激光雷达的相对位置

    Figure 8.  Relative position of obstacles and LiDAR

    图 9  第260帧的聚类结果

    Figure 9.  Clustering results at the frame 260th

    图 10  第280帧的聚类结果

    Figure 10.  Clustering results at the frame 280th

    图 11  聚类所消耗的时间对比

    Figure 11.  Comparison of time consumed by clustering

    图 12  动态障碍物跟踪效果

    Figure 12.  Effect of dynamic obstacle tracking

  • [1] 谢德胜,徐友春,王任栋,等. 基于三维激光雷达的无人车障碍物检测与跟踪[J]. 汽车工程,2018,40(8): 952-959.

    XIE Desheng, XU Youchun, WANG Rendong, et al. Obstacle detection and tracking for unmanned vehicles based on 3D laser radar[J]. Automotive Engineering, 2018, 40(8): 952-959.
    [2] AZIM A, AYCARD O. Layer-based supervised classification of moving objects in outdoor dynamic environment using 3D laser scanner[C]//2014 IEEE Intelligent Vehicles Symposium Proceedings. Dearborn: IEEE, 2014: 1408-1414.
    [3] 黄钢,吴超仲,吕能超. 基于改进DBSCAN算法的激光雷达目标物检测方法[J]. 交通信息与安全,2015,33(3): 23-28. doi: 10.3963/j.issn.1674-4861.2015.03.004

    HUANG Gang, WU Chaozhong, LYU Nengchao. A study of laser radar object detection based on improved DBSCAN algorithm[J]. Journal of Transport Information and Safety, 2015, 33(3): 23-28. doi: 10.3963/j.issn.1674-4861.2015.03.004
    [4] 包瑞胜,马新,崔熠明. 基于优化DBSCAN算法的智能车载激光雷达数据处理技术研究[J]. 中国交通信息化,2017(3): 135-140.
    [5] ZHANG J S, KEREKES J. An adaptive density-based model for extracting surface returns from photon-counting laser altimeter data[J]. IEEE Geoscience and Remote Sensing Letters, 2015, 12(4): 726-730. doi: 10.1109/LGRS.2014.2360367
    [6] CHEN J R, XU H, WU J Q, et al. Deer crossing road detection with roadside LiDAR sensor[J]. IEEE Access, 2019, 7: 65944-65954. doi: 10.1109/ACCESS.2019.2916718
    [7] LEONARD J, HOW J, TELLER S, et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics, 2008, 25(10): 727-774. doi: 10.1002/rob.20262
    [8] NAVARRO-SERMENT L E, MERTZ C, HEBERT M. Pedestrian detection and tracking using three-dimensional LiDAR data[J]. The International Journal of Robotics Research, 2010, 29(12): 1516-1528. doi: 10.1177/0278364910370216
    [9] 汪世财,谈东奎,谢有浩,等. 基于激光雷达点云密度特征的智能车障碍物检测与跟踪[J]. 合肥工业大学学报(自然科学版),2019,42(10): 1311-1317. doi: 10.3969/j.issn.1003-5060.2019.10.003

    WANG Shicai, TAN Dongkui, XIE Youhao, et al. Obstacle detection and tracking for intelligent vehicle based on density characteristics of point cloud using 3D lidar[J]. Journal of Hefei University of Technology(Natural Science), 2019, 42(10): 1311-1317. doi: 10.3969/j.issn.1003-5060.2019.10.003
    [10] HAN J, KIM D, LEE M, et al. Enhanced road boundary and obstacle detection using a downward-looking LIDAR sensor[J]. IEEE Transactions on Vehicular Technology, 2012, 61(3): 971-985. doi: 10.1109/TVT.2012.2182785
    [11] ZHOU Y, WANG D, XIE X, et al. A fast and accurate segmentation method for ordered LiDAR point cloud of large-scale scenes[J]. IEEE Geoscience and Remote Sensing Letters, 2014, 11(11): 1981-1985. doi: 10.1109/LGRS.2014.2316009
    [12] XU S, WANG R S, WANG H, et al. An optimal hierarchical clustering approach to mobile LiDAR point clouds[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(7): 2765-2776. doi: 10.1109/TITS.2019.2912455
    [13] 刘健. 基于三维激光雷达的无人驾驶车辆环境建模关键技术研究[D]. 合肥: 中国科学技术大学, 2016.
    [14] ZHANG Y S, SUN X, XU H, et al. Tracking multi-vehicles with reference points switches at the intersection using a roadside LiDAR sensor[J]. IEEE Access, 2019, 7: 174072-174082. doi: 10.1109/ACCESS.2019.2953747
  • 加载中
图(12)
计量
  • 文章访问数:  1045
  • HTML全文浏览量:  1162
  • PDF下载量:  129
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-04-26
  • 修回日期:  2020-11-15
  • 网络出版日期:  2021-01-05
  • 刊出日期:  2021-01-05

目录

/

返回文章
返回