无人驾驶汽车决策系统的规则描述与代码生成方法*

兰 韵，刘万伟，董 威，刘斌斌，付 辰，刘大学

（1.国防科学技术大学计算机学院，湖南 长沙 410073；2.中国科学院软件所计算机科学国家重点实验室，北京100000；3.国防科学技术大学机电工程与自动化学院，湖南 长沙 410073）

无人驾驶汽车决策系统的规则描述与代码生成方法*

兰 韵1，刘万伟1，董 威1，刘斌斌1，付 辰2，刘大学3

（1.国防科学技术大学计算机学院，湖南 长沙 410073；2.中国科学院软件所计算机科学国家重点实验室，北京100000；3.国防科学技术大学机电工程与自动化学院，湖南 长沙 410073）

无人驾驶汽车的高层决策系统是其实现自主驾驶功能的核心，在决策系统的开发过程中，由于信号变量与状态数量庞大等原因，系统面临着可维护性与可拓展性差的难题。UNMANNED_RULE_ EDIT是面向无人车高层决策系统的规则编辑与代码自动生成辅助工具，具有图形化编辑和代码自动生成的功能，有利于开发人员清晰直观地设计规则，并摆脱繁琐的编码工作。主要讨论了 UNMANNED_ RULE_EDIT的中间语言（规则语言）设计和代码自动生成算法。目前，该工具已初步应用在国内某单位研制的无人车上，为其决策系统的开发提供便利。

无人驾驶汽车；决策系统；规则语言；代码自动生成

1 引言

无人驾驶汽车是信息技术高度发展的产物，就是由机器代替人类驾驶员驾驶汽车［1］。随着人们对提高工作效率、工作安全性、生活舒适度等需求的日益增长，无人驾驶汽车的研究正引起产业界和学术界的高度关注。近些年，国内外已经有大批科研工作者开始投入到这一领域的探索和竞争中。美国谷歌公司的Google Fleet、德国柏林大学的MIG和我国国防科学技术大学的红旗 HQ3［2］等都是无人驾驶汽车领域中具有代表性的阶段性成果。

无人驾驶系统结构大致可分为若干模块，如图1所示。其中决策模块是无人驾驶汽车系统的核心，其主要任务是根据环境感知系统获得的环境信息、车辆当前状态以及任务规划层规划的任务目标，采取恰当行为，保证车辆顺利地完成任务［3］。

Figure 1 Structure model of the unmanned vehicles图1 无人车系统结构

当前，无人车决策系统涉及到的信号变量多、状态多、规则复杂，导致开发和维护的过程中面临可拓展性与可维护性差的问题，严重制约了无人驾驶汽车决策控制系统的设计与完善，主要表现在：

（1）早期决策系统的开发工作都是从编写代码开始的，人工编写代码的时间开销在整个工程项目中占据了相当大的比重，致使开发成本居高不下。

（2）由于程序规模大，导致了程序可读性差，可拓展性差。决策系统主要由规则集构成，开发人员修改规则时需要直接修改源代码，对开发人员带来很大的负担，而且修改一处代码往往会引起另外多处代码的修改，这直接导致开发人员在维护系统时困难重重。

（3）无人驾驶汽车实时系统对安全性有极高的要求，无人驾驶汽车运行在高度复杂的动态环境中，涉及的参数变量很多，参数的取值一般根据经验或者实验获取，具有主观性，设计中很容易存在安全隐患。

1.1 研究现状

模型驱动的软件开发方法是一种用于智能决策系统开发领域的常用软件开发方法，是一种可以把模型与实现紧密相联的技术，其核心思想是图形化建模，有助于开发人员将思维精力专注于更高的抽象层面，而不是深陷到繁琐的代码实现中［4］。建立的模型可以根据一定的规则自动转化为可执行的代码，如C语言、Java等。因此，模型驱动的软件开发方法核心思想有两个，分别是图形建模和代码自动生成，其优点在于［5］：

（1）可以把需求说明以模型的方式表达出来，即将需求文档化；

（2）有助于开发人员将思维精力专注于抽象层次更高的模型层面，有利于开发人员思考；

（3）可以实现代码自动生成，修改代码时只需要直接修改模型，重新生成代码即可。

近年来，IBM等大型软件公司投入到这一领域的研究，形成了一些标志性的成果，当前市场上已经可以购买到多款较为成熟的建模与代码生成软件，如基于UML建模与代码自动生成的商用软件i Model Studio，它可以使用类图、顺序图等方式进行建模并自动生成代码；又如基于状态机的建模与代码自动生成的商用软件FSME/FSMC，它可以使用画迁移图的方式构建状态机并自动生成代码。这些商用软件已经在航天等安全攸关领域的控制系统得到了应用。但是，对于无人驾驶汽车决策子系统的开发，这些商用的代码生成软件在实际应用中具有明显的缺点［6］：

（1）商用代码生成软件不是针对无人驾驶汽车系统开发的应用软件，与无人车决策模块的规则模型不相关，不能确保需求和模型的一致性，因此，这些通用的软件不能很好地保证无人驾驶汽车决策规则设计的正确性。

（2）商用代码生成软件不可以根据无人车的实际需求和特点进行相应的配置，只能生成特定格式的通用代码，因此，它们生成的代码并不能很好地满足无人驾驶汽车的实际需求。

（3）商用代码生成软件价格十分昂贵，这严重限制了代码自动生成技术在工业界的推广与使用。

（4）商用代码生成软件使用流程复杂，需要操作的元素多，不利于开发人员熟练掌握和运用。

1.2 面向无人驾驶汽车的规则建模与代码生成的

解决框架

无人车决策系统的开发是一项庞大的工程，具有高度复杂性，工作量繁重。在开发过程中，一套友好的系统开发辅助工具对于提高开发效率、保证研发进度起着不可低估的作用。因此，本文旨在针对无人驾驶汽车的特点和需求，设计一套基于状态机的规则建模和代码自动生成的规则编辑工具UNMANNED_RULE_EDIT，用以解决系统开发面临的工程难题，提高开发的效率。

针对早期系统代码量大，以及可拓展性和可维护性差的问题，开发人员在决策系统的开发过程中，可以利用规则编辑工具UNMANNED_RULE_EDIT直接在列表中编写规则，或者直接在状态机图示上编辑规则。最终由该工具自动将规则生成可执行的代码，最终实现规则与应用程序的分离。“写规则”相比“写代码”有明显的好处：（1）符合直观，不易出错；（2）达到设计上的正交，即写当前规则时不需要关心其他规则。

针对设计中难免存在安全隐患的问题，UNMANNED_RULE_EDIT运用了软件形式化方法中的模型检验技术，利用模型检验工具［7］自动查找规则设计中的BUG，保证决策系统规则的安全性。

UNMANNED_RULE_EDIT的总体设计思路如图2所示。

Figure 2 Schematic diagram of model checking for unmanned vehicles图2 模型检验用于无人驾驶汽车的原理图

规则编辑工具UNMANNED_RULE_EDIT的设计过程主要分为两部分：一是中间语言（中间语言是规则的内部表示）的格式和语法的设计；二是从中间语言到C代码的转换过程，即代码自动生成过程。以下章节，我们将对这两部分分别进行介绍。

2 无人汽车决策系统的建模与迁移规则描述

2.1 无人驾驶汽车决策系统运行时模型

决策系统的本质是一个表示行为转换的状态迁移系统，如图3所示。因此，无人驾驶汽车决策系统的运行时模型是一个五元组：，其中，

Si是signals的简写，代表信号集合；

St是states的简写，代表状态集合；

I是init的简写，代表初始状态集合；

E是final的简写，代表终止状态集合；

φ⊆St×B（Si）×St为迁移规则集合，B（Si）是Si上的布尔公式集合。

Figure 3 State transition diagram of unmanned vehicles图3 无人车状态迁移图

2.2 无人驾驶汽车决策规则描述

对于图3中的每一条状态迁移，都是一条决策判断的依据，我们称之为一条“规则”，表1是规则表范例。由表1可知，规则列表是一个三元组：A，其中A代表当前状态，B代表目标状态，conditions代表转移条件。

Table 1 Example of a rule table表1 规则表范例

车辆状态包括进入（enter）、自由跟踪车道线（driving alone）、超车（overtaking）、车辆跟踪（following）、追赶（pursuit）、停车（stop）、离开（exit）、放弃超车（give_up）共8类行为状态，还可以往下细分21类具体状态，此处不详细列出。

conditions由“环境感知信息判断条件”、“地图信息判断条件”和“车辆自身信息判断条件”构成，其语法的BNF范式定义如下：

3 中间语言UNMANNED_RULE_ LANGUAGE

在UNMANNED_RULE_EDIT中，开发人员可以通过列表的形式编写规则，清晰简洁。但是，这些通过列表形式编写的规则在软件内部需要有一种特定的表示形式，因此我们引入中间语言的概念，即规则语言。UNMANNED_RULE_EDIT的中间语言是指规则在该软件中的内部表示形式，即将规则用该软件专用的规则语言UNMANNED_ RULE_LANGUAGE描述出来。

中间语言UNMANNED_RULE_LANGUAGE由三部分组成，分别是信号变量声明“SINGNALS”、状态声明“STATES”和迁移条件描述“TRANSITIONS”。用BNF范式定义其语法如下：

procedure：：=PROCEDURE｛ procedure_body｝

中间语言的由信号变量声明、状态声明、迁移规则三部分构成：

procedure_body：：=signals states transitions

信号变量声明部分：

signals：：=SIGNALS［ signals_list］ signals_list：：=signal；|signal；signals_list signal：：=bool var_name

|int var_name

|double var_name

|float var_name

var_name：：=［a —z］［_a —zA—Z0—9］*

状态声明部分：

states：：=STATES［ states_list］

states_list：：=state

|state states_list state：：=＜＜state_name＞＞/*注：＜＜＞＞代表

初始状态*/

|（（st ate_name） ）//注（（））代表初始状态

|［［state_name］］//注：［［］］代表初始状态

state_name：：= ［a —z］［_a —z A—Z0—9］*

迁移规则部分：

transitions：：=TRANSITIONS［ transitions_list］

transitions_list：：=transition

|transition transitions_list

transition：：=state_name：condition→state_name；

|state_name：condition→state_name，

|：condition→state_name，

|：condition→state_name；

condition：：=（“［a —z］［_！=&|a—z A—Z0—9＜＞（）—］*“）

UNMANNED_RULE_EDIT的中间语言是针对无人驾驶汽车决策系统的状态迁移系统属性，所设计的类似有限状态自动机的规则描述语言，这种中间语言有以下三个优点：

（1）能够完整简洁地描述无人驾驶汽车决策系统的规则，满足实用性。

（2）能够方便地转换为C代码。由于中间语言的框架与C语言代码的框架具有很好的对应性，所以能够方便地将中间语言转换为C语言代码。

（3）能够方便地映射为迁移模型，进而能够作为模型检验工具的输入。由于中间语言的设计是基于有限状态自动机的，所以中间语言可以方便地转化为多种模型检验软件所支持的语言，如：Spin、SMV和UPPALL等［5］，从而可以使用模型检验技术对规则的正确性进行验证。

4 规则到C代码的转换算法

4.1 映射规则定义

本节介绍从规则到C代码的转换算法，算法的核心为若干形如“中间码元语言▷（C语言语句，Action；）”的映射规则。

其中，Action是一组关于两个辅助变量_init_ 和_final_的赋值动作，这两个变量在特定的时机（比如处理TRANSITIONS关键字时）用以回填。当Action=Ø时，映射关系可以简写成：

中间码元语言 ▷C语言语句

4.2 转换算法

中间码到C代码的转换算法由四部分构成，分别是：变量模块SIGNALS到C代码的转换、状态模块STATES到C代码的转换、迁移模块TRANSITIONS到C代码的转换、总体模块PRODUCE到C代码的转换。

变量模块SIGNALS映射为变量赋值语句。设sig为单条信号声明语句“datatype var_ name；”，其对应的C语言代码”datatype var_ name=car_struct.var_name；”为Csig。状态模块STATES映射为状态枚举变量定义、初始状态赋值、用于决策的while循环与switch-case框架。设“＜＜state_name＞＞或（（state_name））或［［state_name］］”为单条状态声明语句，其对应的C语言代码为Csta。迁移模块TRANSITIONS中的一 组 迁 移 规 则映 射 为case语。设“A：（condition1）→B”为一组迁移语句trans，其对应的C语言代码为Ctrans。总体模块PRODUCE映射为头文件、库文件引用、函数名等框架代码。设SIGNALS模块对应的C语言代码为CSIGNALS，设STATES模块对应的C语言代码为CSTATES，设TRANSITIONS模块对应的C语言代码为CTRANSITIONS，设生成的头文件为PHEAD，设生成的库函数引用等代码为PINCLUDE。

因此，中间码到 C代码的转换算法可以描述为图4所示。

规则sig_dec用于处理单条信号声明的转换，规则sig_mod代表SIGNALS模块的转换。规则sta_dec代表单条状态声明的转换，其中状态声明的转换又分为初始状态、中间状态、终止状态三种不同状态类型的声明转换。规则sta_ini代表初始状态的转换，规则sta_int代表中间状态的转换，规则sta_fin代表终止状态的转换。规则sta_mod代表STATES模块的转换。规则trans_dec代表迁移条件到CASE语句的转换，规则trans_mod代表迁移模块TRANSITIONS的转换。规则produce_mod代表总体模块PRODUCE的转换。

5 案例分析

我们以无人驾驶车执行超车动作为例，分析UNMANNED_RULE_EDIT从构建相关的规则到生成相应的代码的过程。

无人车的超车动作分为五个状态，如图5所示，分别是初始状态（init）、超车进行中（overtaking）、紧急停车（stop）、放弃超车（give_up）、超车完成（end），其中每条状态迁移都是一条规则。

该过程的中间语言描述如下：

依据中间语言到C语言的转换算法，生成的C语言代码如下：

6 结束语

本文介绍了面向无人驾驶汽车决策系统的辅助开发工具UNMANNED_RULE_EDIT，重点阐述了中间语言（规则语言）的设计和代码自动生成算法。UNMANNED_RULE_EDIT特别适合于有复杂控制逻辑的系统开发，在机器人、无人控制等领域有较大的应用潜力。它实现了软件开发便捷性与可靠性的统一：一方面，利用它友好的图形化规则编辑功能，使开发人员能够直观方便地设计规则；另一方面，利用它强大的代码自动生成功能，可以由规则自动生成关键代码，大大提高开发效率，缩短开发周期，保证软件质量。目前，UNMANNED_RULE_EDIT的应用也存在一些缺陷，表现在两方面：一是自动生成的代码灵活性不足，为应用带来了一定的困难；二是该工具的模型检验功能尚未能成功地应用，还需完善，这两方面的不足都是将来我们需要不断研究的重点。

［1］ Huang Yan，Wu Jun，Liu Chun-ming，et al.Overview and key technologies of autonomous vehicles［J］，Ordnance Industry Automation，2010，29（11）：8-13.（in Chinese）

［2］ Wang Bin-long.The design and research of unmanned intelligent vehicle［D］.Jinan：Shandong University of Science and Technology，2012.（in Chinese）

［3］ Sun Zhen-ping.The intelligent control system for autonomous land vehicle［D］.Changsha：National University of De-fense Technology，2004.（in Chinese）

［4］ Liu Ran，Chen Ying，Zhao Xiao-lin.Code generation of a visual CASE platform based on UML［J］.Journal of Beijing Institute of Technology，2002，22（2）：196-200.（in Chinese）

［5］ Wang Yun-hua，Chen Wei-wei.Application research on advanced model driven developing method［J］.Computer Engineering，2006，32（13）：63-65.（in Chinese）

［6］ Wang Xue-bin.Research on model driven architecture based model transformation technologies in software engineering ［D］.Changsha：National University of Defense Technology，2008.（in Chinese）

［7］ Holzman G J.The SPIN model checker-primer and reference manual［M］.Boston，USA：Addison-Wesley，2003.

［8］ Holzmarm G J.The model checker SPIN［J］，IEEE Transactions on Software Engineering，1997，23（5）：279-295.

附中文参考文献：

［1］ 黄岩，吴军，刘春明，等.自主车辆发展概况及关键技术［J］.兵工自动化，2010，29（11）：8-13.

［2］ 王斌龙.无人驾驶智能车设计与研发［D］.济南：山东科技大学，2012.

［3］ 孙振平.自主驾驶汽车智能控制系统［D］.长沙：国防科学技术大学，2004.

［4］ 刘然，陈英，赵小林.基于UML的CASE平台的代码自动生成［J］.北京理工大学学报，2002，22（2）：196-200.

［5］ 王赟华，陈蔚薇.模型驱动开发方法的应用研究［J］.计算机工程，2006，32（13）：63-65.

［6］ 王学斌.软件工程中基于模型驱动框架的模型转换技术研究［D］.长沙：国防科学技术大学，2008.

兰韵（1989），男，四川宜宾人，硕士，CCF会员（E200036590G），研究方向为自动机理论和可信软件。E-mail：542567880 @qq.com

LAN Yun，born in 1989，MS，CCF member（E200036590G），his research interests include automata theory，and reliable software.

刘万伟（1980 ），男，山东平原人，博士，讲师，CCF会员（E200012491S），研究方向为自动机理论、时序逻辑和模型检验。E-mail：wwliu@nudt.edu.cn

LIU Wan-wei，born in 1980，PhD，lecturer，CCF member（E200012491S），his research interests include automata theory，temporal logic，and model checking.

董威（1976），男，陕西咸阳人，博士，教授，研究方向为软件工程，软件分析与验证。E-mail：wdong@nudt.edu.cn

DONG Wei，born in 1976，PhD，professor，his research interests include software engineering，software analysis and verification.

刘斌斌（1992），男，吉林公主岭人，硕士生，研究方向为自动机理论、时序逻辑和模型检验。E-mail：liubinbin0032@sina. com

LIU Bin-bin，born in 1992，MS candidate，his research interests include automata theory，temporal logic，and model checking.

付辰（1991），男，河北大城人，硕士生，研究方向为概率并发系统的建模与检验。E-mail：fuchen789@foxmail.com

FU Chen，born in 1991，MS candidate，his research interests include modeling and checking of probabilistic concurrent system.

刘大学（1978 ），男，山东章丘人，博士，讲师，研究方向为移动机器人、运动规划、行为决策和 激光雷达数 据处理。E-mail：13508495034@139.com

LIU Da-xue，born in 1978，PhD，lecturer，his research interests include mobile robot，motion planning，decision，and lidar data processing.

Research on rule editing and code generation for the high-level decision system of unmanned vehicles

LAN Yun1，LIU Wan-wei1，DONG Wei1，LIU Bin-bin1，FU Chen2，LIU Da-xue3
（1.College of Computer，National University of Defense Technology，Changsha 410073；
2.State Key Laboratory of Computer Science，Institute of Software，Chinese Academy of Sciences，Beijing 100000；
3.College of Electric Engineering and Automotive，National University of Defense Technology，Changsha 410073，China）

High-level decision systems are the central module of unmanned vehicles.Due to the extremely large amount of states and signals，the development process of the intelligence decision system is very complex，and maintaining such a system will encounter great difficulties.To overcome these problems，we design and implement a rule editing and code generation tool，called UNMANNED_RULE_ EDIT.It features GUI-based editing and automatic code generation and can help developers to generate controlling codes via editing a series of state-transition rules rather than writing codes，thus great succinctness and intuitiveness can be yielded.The paper mainly focuses on the discussion of the rule language and the code generation algorithm.As a preliminary application，this tool has been used in an unmanned vehicle system in China and facilitated the development of its decision system.

unmanned vehicles；intelligence decision system；rule language；code generation

TP311.51

A

10.3969/j.issn.1007-130X.2015.08.014

1007-130X（2015）08-1510-07

2014-10-28；

2014-12-16

国家973计划资助项目（2009CB723803）；国家自然科学基金资助项目（60873120，61103012）

通信地址：410073湖南省长沙市国防科学技术大学计算机学院计算机系 刘万伟

Address：College of Computer，National University of Defense Technology，Changsha 410073，Hunan，P.R.China