基于混合自动机模型和模糊逻辑的多自主车避碰规划
刘小梅1，田彦涛1, 2，王磊1
(1. 吉林大学 通信工程学院，吉林 长春，130025；
2. 吉林大学 工程仿生教育部重点仿生实验室，吉林 长春，130025)
摘要：基于混合自动机模型理论对动态环境中的多自主车系统避碰控制进行建模，分别对速度调整、路径调整和速度路径调整相结合的过程进行建模分析，明确控制输入下自主车的模式状态及其切换关系。设计了1种基于模糊逻辑控制的十字路口多车避碰规划方法。将两车行径路线的角度、两者之间的距离以及到达预碰点的时间差作为控制器输入，小车的速度和路径调整角度作为输出，实现自主车安全有效的运行。实验结果验证了控制算法的有效性。
关键词：多自主车系统；混合自动机模型；避碰规划；模糊逻辑
中图分类号：TP24 文献标志码：A 文章编号：1672-7207(2011)S1-0544-07
Collision avoidance planning of multiple autonomous vehicles based on hybrid automata and fuzzy logical
LIU Xiao-mei1, TIAN Yan-tao1, 2, WANG Lei1
(1. School of Communication Engineering, Jilin University, Changchun 130025, China;
2. Key Laboratory of Bionics Engineering, Ministry of Education, Jilin University, Changchun 130025, China)
Abstract: Collision avoidance control of multiple autonomous vehicle system in dynamic environment was modeled based on hybrid automaton theory. The speed adjustment, path adjustment, and combination of them were modeled and analyzed respectively. The mode state of autonomous vehicles under control and the switching relationship between them were explicated. Besides, a collision avoidance planning method based on fuzzy logic control in crossroad environment was designed. Let the angle between the paths, the distance and the time difference of arriving the pre-collision point between two vehicles as inputs of the fuzzy controller, and the speed and path adjusting angle as outputs, safe and effective operation of the autonomous vehicles was achieved. Experimental results verify the effectiveness of the control algorithm.
Key words: multiple autonomous vehicle system; hybrid automata; collision avoidance planning; fuzzy logical
ITS的车辆协作安全控制相关技术一直是各国研究的重点之一，主要有避碰指标合作企业CAMP[1]，车辆基础设施整合联盟VIIC[2]等。随着计算机等技术的发展，车辆的主动安全[3]逐渐得到重视，即智能车通过感知周围环境和相关车辆的信息控制自身的行为，从而主动预防事故的发生。车辆安全系统的研究也朝着智能化和主动型安全系统及其技术方向发 展[4]，由此而产生的多车协作安全控制问题引起了人们的广泛兴趣，其最重要的目标之一是实现智能车的安全避碰。由于智能车也可称为移动机器人，因此，可以借鉴关于机器人的动态避碰方法进行研究，比较典型的有Takeshi[5]利用3层模糊控制方法调节速度和方向实现动态避障；Rude[6]将二维动态环境转化为三维静态环境下的静态避碰问题；Ge等[7]改进人工势场法的智能机器人避碰以及张凤等[8]提出的基于相对坐标系的动态避障算法等都有效的实现了避碰。
实际生活中交通路口是事故频发区域[9]，在对多自主车系统进行研究时，碰撞也主要发生在路径的交叉区。本文作者主要研究十字路口中简单多车系统的避碰环境建模及其算法实现。多车协作主动安全控制同时涉及智能车辆的离散状态和连续状态，本研究在前人工作基础上提出基于混合自动机模型的方法来描述小车的状态、目标及决策方法，并综合智能小车的基本模式和模糊逻辑控制算法，实现多车多路径的安全行驶。
1 建模分析
假定两辆智能车在公路环境下执行任务，主动安全控制的关键技术之一就是避碰控制。交叉十字路口的碰撞环境如图1所示，智能车在执行任务时共有3种行为动作，包括静态障碍物避碰、动态障碍物避碰和趋向目标点，根据实际情况，避碰行为比趋向目标点行为具有优先性。如图1所示，若小车Car 1和Car 2同时到达区域B，则会发生碰撞，因此避碰控制有3种方法：速度调整、路线调整、速度和路线调整相结合。
图1 两辆车在十字路口的运行环境
Fig.1 Environment of two cars at crossroad
速度调整：在小车速度可控范围内加速或减速，即保持小车行经路线不变，只对小车有纵向加速度输入，使得2辆车不会同时进入碰撞区域。
路线调整：以能耗最小即绕行路程最短为原则，保持速度不变，只对小车有横向转角的输入，分为单车调整路线和双车同时调整路线，如图2所示。
图2 2车同时调整路线示意图
Fig.2 Schematic diagram of adjusting routes of two cars
速度与路线调整相结合：对小车同时有纵向加速度和横向转角的输入。
1.1 智能车动力学模型
智能车的动力学模型包括纵向和横向动力学模型2部分，考虑路面附着状况较好的公路行驶环境，对模型进行假设和简化[10]，汽车纵向动力学方程为：
(1)
其中：δ是汽车旋转质量换算系数；M为车的总质量；v为径向车速；Td和Tb分别指驱动力矩和制动力矩；rw为轮胎半径；Fi，Fa和Ff分别表示坡度阻力、空气阻力和滚动阻力。化简得：
，
令
，u1=Td-Tb，
，b1=(-Fi-Fa- Ff)/ (δM)，则小车的纵向动力学方程即可简化为：
(2)
横向动力学是研究驾驶员给系统以转向指令后汽车在曲线行驶过程中的运动学和动力学特性，影响着汽车操作的方便性和稳定性。假设汽车只做平行于路面的平面运动，则汽车就简化为1个具有侧向及横摆运动的2自由度计算模型[11]。只考虑角度输入的横向动力学模型为：
(3)
其中：β和ω分别表示横摆角度和角速度；Kα1和 Kα2分别为前、后轮的侧偏刚度；Is为车身的转动惯量；M为车的总质量；v为小车径向质心速度；La和Lb为前、后轴到质心间的距离；δ是扰动输入。令
，
，
则有：
(4)
综合小车的横向和纵向动力学模型，令
，则有：
(5)
其中：
,其值可根据系统辨识实验方法和最小二乘法获得。
1.2 混合自动机模型
混合自动机是由美国Henzinger[12]于20世纪90年代提出的，是1种描述混合系统的计算模型，可用来描述和计算具有连续和离散变量混合系统的行为。在混合自动机中，状态被看作是在微分方程控制下一组连续变量的连续变化过程，而将状态的切换视作事件的驱动。
定义1[13]：带有输入和连续状态信息的混合自动机
，其中：X是欧式空间中子集的连续变量；Q是模式的有限集合；U是输入的连续变量；O是输出的连续变量；
是1个向量场；
是模式重置映射，
；
是输出映射，其中
是X的幂集，即X的所有子集的集合。
1.2.1 速度调整的混合自动机模型
以智能车Car1为例，状态变量意义为：
为位 移，
为速度，
为加速度。仅有速度调整的Car1有3种模式状态[11]q1、 q2 和q3，如式(6)所示，其切换关系如图3所示。
由图3可知：若无需调整速度则控制输入u=0，小车匀速行驶；若需减速，则使控制输入
，即状态切换为
或
，最小车速为vmin，
；反之，若需加速则使控制输入
，即状态切换为
或
，最大车速为vmax。
(6)
图3 速度调整模式转换图
Fig.3 Mode shift map of speed adjustment
速度调整的混合自动机模型
(X, Q, U, O, f, R, h)，其中：连续变量集合
，即 
；模式集合Q ={q1, q2, q3}；输入集合
，
；输出集合
，是状态变量X的子集的集合；映射
，即在模式Q和状态X下，加上输入U，可得到新的位移和速度，对q1有
；对q2和q3有
；表示当前状态在控制输入的作用下对应到一个模式的映射；映射是输出到状态变量X的子集集合的映射。
1.2.2 路线调整的混合自动机模型
小车的状态变量
，设小车向右转为正，即
，左转时
，保持路线不变时
。由于小车的最终目标是趋向于目标点，因此基于小车直线路径的局部路线调整的向量和为0。小车的横向动力学模型求解的是小车横向转角的角速度和角加速度，对于整个系统而言，转向时间可以忽略不计，推导出小车转向调整的3个模式状态p1，p2和p3，如式(7)所示，其切换关系如图4所示。
(7)
由图4可知：若无需转向速度，则控制输入u=0，小车保持路线不变；若需转向，则加控制输入u且 u≠0，从模式p1跳转到p2，直至适宜的转向角度θmax或-θmax，接着，小车保持当前的转向角度开始0角度输入的运行，即跳转至模式p3，当以输入u=0行驶至指定位置，就令控制输入u≠0，使得小车开始恢复原行驶路线，即从模式p3跳转回到模式p1，小车恢复原行驶路线，则路线调整过程中的一轮模式转换结束。
图4 路线调整模式转换图
Fig.4 Mode shift map of route adjustment
路线调整的混合自动机模型
，其中：
，
；模式集合
。
1.2.3 速度和路线调整相结合的混合自动机模型
对整个系统而言，小车从开始转向到转到合适角度的时间可以忽略不计，即在这段时间内，设定速度保持不变，因此，此时小车有3种模式状态Q1，Q2和Q3，如式(8)所示，其切换关系如图5所示。
(8)
图5 速度路线调整相结合模式转换图
Fig.5 Mode shift map of combination of speed and route adjustment
由图5可知：小车角度调整完成之后实施速度调整，即在模式p3状态下加入模式q1，模式转换图与图4类似，在此不再赘述，同时混合自动机模型为
，其中：
；
。
各种复杂路况和复杂车辆状态的情况，都可以分解为两辆车之间的协作，这里只考虑2个并行的混合自动机的情况，但是，结论可以扩展到任意数量的并行混合自动机模型。
定义2[14]：对于
，
是混合自动机的集合。它们是并行结构，用
描述，混合自动机
，其中：
；
；
；
；
。
N车系统可以被建模成N阶映射的混合自动机并行结构。即
，对于每1个Hi，可以是上述3种
中的任意1种，并行结构模型如图6所示。N=2时，
，2辆小车在无相互碰撞威胁时，分别独立运行，即2个独立的混合自动机模型，令
，则模型为
的任意组合集合。若2辆车有相互碰撞威胁，则可视情况而定，采取有效的避碰策略。以省时节能为目标，若单靠调整速度无法避碰时，则采用速度调整和路线调整相结合进行避碰。
图6 并行结构模型
Fig.6 Parallel model
2 避碰算法实现与分析
2.1 基本避碰算法
以两辆同构小车中Car1避开动态障碍物的行为决策为例，小车尺寸长和宽分别为l和w，则避碰算法如下。
Step1：根据全局信息或者小车的传感器和两车当前的速度v1和v2，计算两辆车行径路线之间的夹角φ，2辆车质心点与碰撞点之间的距离d1和d2。
Step2：计算
。
(a) 若
且令Car1加速至vmax，Car2减速，使Car1在通过碰撞点后，Car2仍未或刚到碰撞点，则可仅依靠速度调整实现避碰；
(b) 若无法通过速度调整实现避碰，则需实施路线调整，调整角度θmax计算方法如图4所示。其中：
，或
；
；ρ是静态障碍物最大半径。
Step3：若
，则将Car2作为控制对象，方法与Step2的相同。
Step4：通过碰撞区域后，小车以最大速度趋向于目标点，至接近目标点时减速停车。
基于建模分析的基本避碰算法是比较简单的，需要建立在环境信息实时精确的基础上才能实现。而在实际实验及生活中，传感器的信息采集范围及精确度都有限制，因此，本研究引入基于模糊控制的避碰算法，进行比较切合实际的实验。
2.2 基于模糊逻辑的避碰算法分析
智能车主动安全控制是基于传感器信息的局部路径规划，即障碍物的尺寸、形状和位置等信息必须通过传感器局部范围内获取。自主小车系统的挑战就是在此种情况下，达到实际生活中城市交通路口驾车运行状态的适应性。模糊逻辑算法[15]是基于实时传感器的信息，参考人类的驾驶经验设计规则表，通过查表获得所需要的信息，其计算量小，实用性大。主要原理是小车在由起始点到目标点的运动过程中，每隔一定时间检测障碍物的信息，参考行为规则，给出小车下一步的行动决策。
2.2.1 输入输出变量的选择及其模糊化
选取小车与其他小车(动态障碍物)行进路线夹角φ、两车间距d和两车到达预碰点的时间差Δt作为模糊控制输入量，如图7所示。其中：φ反映了小车的速度方向信息；时间差Δt=t1-t2包含小车的速度大小信息，t1和t2分别为小车本身和其他小车到达碰撞点所需的时间；
表示其他小车先到达碰撞点。模糊控制系统的输出量是小车下一步行为的速度v和转角θ。
图7 模糊控制结构图
Fig.7 Fuzzy control structure
在对输入输出精确变量进行模糊化时，除Δt的Z集合采取(-2.5, 2.5)的范围外，其他变量均根据各自的范围，建立标准对称三角形的隶属度函数，并采用经典的Mamdani模糊模型。控制结构图如图7所示，模糊化结果如表1所示。
表1 各变量的模糊集合及其变量范围
Table 1 Fuzzy set of each variable and variable range
2.2.2 模糊规则的制定
模糊推理过程是借鉴人的驾驶经验，根据小车所拥有的最大速度，同时参照其他小车的位置和速度，来估测小车能否无碰撞地通过欲碰撞地点，制定小车的行为策略，即全力加速优先通过欲碰撞地点或者采取避让等待的策略让过其他小车。下面以其他小车处于左前方为例，制定模糊规则。
输出转角θ的模糊规则为：当时，小车左转，转角幅度与φ和d有关，d越小转动角度的幅度越大；当
时，φ越小，则转动角度的幅度越大；当
时，
越大，则转动角度的幅度越大；当
时，小车右转，模糊规则与左转时类似。输出速度v的模糊规则为：当时，小车减速，d越小，减速的幅度越大；当时，φ越小，则减速的幅度越大；当
时，φ越大，则减速的幅度越大；反之，当Δt≤0时，小车加速，模糊规则与减速时的类似，具体规则如表2~5所示。
在输入条件相同的情况下，其他小车处于右前方时，转角输出与其处于左前方时大小相同、符号相反；速度输出与其他小车处于左前方时的相同。
表2 
时输出变量θ的模糊规则
Table 2 Fuzzy rules of output variable θ when
表3 
时输出变量θ的模糊规则
Table 3 Fuzzy rules of output variable θ when
表4 时输出变量v的模糊规则
Table 4 Fuzzy rules of output variable
when
表5 时输出变量的模糊规则
Table 5 Fuzzy rules of output variable v when
3 实验结果与分析
关于避碰算法的实验验证主要有纯路径精确调整实现避碰，实验结果如图8所示，以及基于模糊逻辑的十字路口避碰控制，实验结果如图9所示。
图8所示为基于虚拟环的时间最短路径规划的避碰控制实验结果。在通过传感器得到可能发生碰撞的信息后，在预碰撞区规划一个虚拟圆形区域，其半径取决于智能车的尺寸，使得小车能安全通过该区域且无额外等待时间，这里，然后，计算小车的路径调整角度，通过该区域之后恢复原始行径路径，趋向目标点。
图8 “追尾式”路径规划避碰
Fig.8 Rear-end-style path planning collision avoidance
图9 基于模糊逻辑的避碰控制
Fig.9 Collision avoidance control based on fuzzy
图9所示为基于模糊逻辑实现避碰的控制实验研究结果。针对实际工况中可能出现车祸和路面维修等状况，在实验中设置了2处静态障碍物(黑色区域)，小车本身相对于其他小车来说作为动态障碍物处理。实验中小车初始状态均为以速度
匀速行驶，以趋向目标点为前提，以与障碍物的避碰为原则，实现速度路径调整规划。Car2和Car3在通过模糊逻辑算法，调整速度和路径避开静态障碍物之后，检测到两车可能会以
的夹角发生碰撞，则继续根据模糊规则，调整运行状态通过预碰点，恢复行驶。同时在Car1运行过程中，其传感器检测到与Car3有比较小可能的碰撞威胁，为确保安全，Car1减速通过交叉口，然后恢复正常速度，匀速行驶。最后3车实现避碰，分别趋向各自的目标点，保证整个系统的安全性。
4 结论
(1) 采用混合自动机模型对避碰控制进行建模分析，包括速度调整、路径调整和速度路径调整相结合3种方式的建模，对避碰控制中自主车的状态模式转换进行剖析，从本质上分析了避碰方法中控制输入与状态的关系，给后续工作提供了前提基础。
(2) 针对模糊逻辑计算量小且实时控制的特点，设计了1种多车避碰规划算法，将2车行径路线的角度、两者之间的距离和到达预碰点的时间差作为输 入，小车调整后的速度及速度方向改变的角度作为输出，实现安全有效的实时控制。
参考文献：
[1] Schagrin M. Cooperative Intersection Collision Avoidance Systems (CICAS) [EB/OL]. 2011- 06-06, http://www.its.dot. gov/cicas.
[2] Vehicle Infrastructure Integration (VII) [EB/OL]. 2010-10-30, http://www.vehicle-infrastructure.org/.
[3] 谢建平. 基于多车协作感知的主动安全技术研究[D]. 上海: 上海交通大学电子信息与电气工程学院, 2009: 63-70.
XIE Jian-ping. Research on active safety based on multi-vehicle collaborative perception[D]. Shanghai: Shanghai Jiaotong University. School of Electronics and Electric Engineering, 2009: 63- 70.
[4] 刘涛. 智能型汽车行驶主动安全系统研究[D]. 重庆: 重庆大学自动化学院, 2003: 9-13.
LIU Tao. Study on initiative safety system of smart vehicle[D]. Chongqing: Chongqing University. College of Automation, 2003: 9-13.
[5] Takeshi A. Motion planning for multiple obstacles avoidance of autonomous mobile robot using hierarchical fuzzy rules[C]// Proceedings of the IEEE International Conference on MFI. Las Vegas, 1994: 265-271.
[6] Rude M. Collision avoidance by using space time representations of motion processes[J]. Autonomous Robots, 1997, 4(1): 101-119.
[7] Ge S S, Cui Y J. Dynamic motion planning for mobile robots using potential field method[J]. Autonomous Robots, 2002, 13(3): 207-222.
[8] 张凤, 谈大龙. 一种基于相对坐标系下移动机器人动态实时避碰的新方法[J]. 机器人, 2003, 25(1): 31-35.
ZHANG Feng, TAN Da-long. A new real-time and dynamic collision avoidance method of mobile robots based on relative coordinates[J]. Robot. 2003, 25(1): 31-35.
[9] Miura J, Itoh M, Shirai Y. Toward vision-based intelligent navigator: its concept and prototype[J]. IEEE Transactions on Intelligent Transportation System, 2002, 3(2): 136-146.
[10] 詹军. 用于自适应巡航控制的汽车纵向动力学模型的建立. 吉林大学学报: 工学版, 2006, 36(2): 157-160.
ZHAN Jun. Setup of vehicle longitudinal dynamic model for adaptive cruise control[J]. Journal of Jilin University: Engineering and Technology Edition, 2006, 36(2): 157-160.
[11] 方兴.智能车动力学模型参数辨识方法研究[D]. 上海: 上海交通大学电子信息与电气工程学院, 2009: 61-66.
FANG Xing. Research on identification of dynamic parameters for intelligent vehicle[D]. Shanghai: Shanghai Jiaotong University. School of Electronics and Electric Engineering, 2009: 61-66.
[12] Thomas A, Henzinger Z. The theory of hybrid automata[C]// Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science. New Brunswick: IEEE Press, 1996: 278-292.
[13] Desaraju V, Ro H C, Yang M, et al. Partial order techniques for vehicle collision avoidance: application to an autonomous roundabout test-bed[C]// Proceedings of the IEEE international conference on robotics and automation. Kobe: IEEE Press, 2009: 82-87.
[14] Verma R, Vecchio D D. Continuous control of hybrid automata with imperfect mode information assuming separation between state estimation and control[C]// Proceedings of the 48th Conference on CDC/CCC. Shanghai: IEEE Press, 2009: 3175-3181.
[15] Sugeno M, Nishida M. Fuzzy control of model car[J]. Fuzzy Sets and Systems, 1985, 16(2): 103-113.
(编辑 何运斌)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：国家自然科学基金资助项目(60675057)；吉林大学“985工程”仿生科技创新平台项目(2010)
通信作者：田彦涛(1958-)，男，吉林四平人，博士，教授，从事分布式智能系统研究；电话：0431-85095769；E-mail: tianyt@jlu.edu.cn
