Büchi自动机确定化分析工具

无限字自动机的确定化是理论计算机研究重要的一部分,在形式化验证,时序逻辑,模型检测等方面有重要应用.自Büchi自动机提出半个世纪以来,其自动机的确定化算法始终是其中的基础.有别于当初只是在理论上对其大小上下界的探索,利用日新月异的高性能计算机技术不失为一种有效的辅助手段.为了深入研究非确定性Büchi自动机确定化算法的实现过程,希望重点研究确定化过程中的索引能否继续被优化的问题,实现确定化研究工具NB2DR.可以对非确定性Büchi自动机进行高效的确定化,并通过工具提供的分析其确定化过程来达到对其确定化算法改进的目的.通过对生成的确定性无限字自动机的索引的深入分析来探索相关索引的理论.该工具还实现了可以根据需要的Büchi自动机的大小与字母表参数,生成确定化的Rabin自动机族,亦可以反向根据需要的指定索引的大小来生成全部Büchi自动机族,测试生成无限字自动机的等价性等功能.

基于多层元胞自动机的动态随机耦合映像格系统性能分析

基于多层元胞自动机的时空混沌系统设计了一款用于图像加密的伪随机数发生器.针对现有的基于耦合映像格系统仍存在参数空间有限、局部混沌行为等问题,本文提出一种基于多层元胞自动机的伪随机耦合映像格系统.在初等元胞自动机基础上设计出多层元胞自动机,将耦合系统与多层元胞自动机同时进行迭代,通过自动机的迭代输出得到耦合系统中每个格子的动态耦合方案以及伪随机扰动方法.本文通过分岔图、Kolmogorov Sinai熵和输出序列均匀性对耦合映像格系统进行对比分析,并分析了系统生成序列的随机性和任意两个格之间的相关性.理论分析和实验结果表明,与其它耦合映射格系统相比,该系统具有更好的混沌特性和更大的参数空间,系统生成的序列具有较好的遍历性、均匀性和随机性.研究结果表明该系统在密码学领域具有广阔的应用前景.

基于时间自动机的动力调度岗位培训仿真机理建模

针对大型风洞群中压空气系统存在调度机理复杂、岗位人员素质要求高、系统实操培训代价大等问题,实施基于时间自动机的动力调度岗位培训仿真机理建模。通过混杂系统理论提出适合大型风洞群中压空气调度的扩展时间自动机模型,基于先来先服务策略构建资源申请、机组工作等队列,建立调度器、就地执行器等核心机理模型,并采用UPPAAL工具对模型进行验证。结果表明:该模型的建立不仅为岗位人员掌握设备结构原理、积累实操经验提供有效手段,而且为建立风洞试验调度仿真系统、合理有效实施风洞动力调度岗位培训打下了基础。

考虑折返行为的元胞自动机人员疏散模型

为研究行人折返行为对疏散的影响,考虑多出口对行人的吸引力、人员相互作用力、火源蔓延威胁以及折返场吸引力的共同影响,在元胞自动机模型的基础上提出基于静态场、动态场、火源场以及折返场共同作用的行人疏散场域模型,研究不同折返比例、折返区域、人员密度、出口数量和位置情况下折返行为对疏散进程的影响。研究结果表明:少量折返行为对总疏散时间影响较小,而群体性折返行为的存在会增加总体疏散时间,随着折返比例的增加,疏散时间随之增加。折返区域离出口越近,对总体疏散效率的影响越小。折返行为对疏散进程的影响效果,随着人员密度的增加不断增强。在双出口条件下,对侧设置出口位置能有效减少折返行为对疏散进程的负面影响。研究结果可为提高紧急情况下的疏散效率提供参考。

基于元胞自动机的高速公路主线同侧连续入口间距研究

针对高速公路主线同侧连续入口处车辆行驶安全与通行效率问题,对高速公路主线同侧连续入口间距进行了研究。通过建立元胞自动机仿真模型,分析了主线与匝道设计速度的差异以及高速公路主线匝道连续入口间距各部分长度对交通冲突率、平均拥堵车辆数和平均速度的影响;提出了不同主线与匝道设计速度组合下的主线同侧连续匝道入口间距推荐值;并对不同间距组合下的工况进行了仿真对比分析。研究结果表明:当主线与匝道设计速度的差异较大时,现有规范中的高速公路主线同侧连续入口间距难以满足交通安全与通行效率要求;相比采用规范中的一般值,采用文中推荐值时的主线车辆平均速度由81.39 km/h上升到95.29 km/h,匝道车辆冲突率由0.0335次/(km·veh)下降到0.0256次/(km·veh),匝道车辆平均拥堵数由0.0077 veh/s下降到0.0022 veh/s,提高了车辆通行效率,降低了车辆发生事故的风险。

基于元胞自动机的城市内涝风险识别模型研究

【目的】目前的城市内涝模拟模型面临着资料要求高、计算量大、适用尺度小等诸多挑战,探索简便高效、操作性强的内涝模拟模型,可为缺乏资料的城市提供识别内涝风险、提升防灾水平的有力工具。【方法】集成元胞自动机对复杂系统的模拟能力和地理信息系统平台的空间数据处理能力,结合水文水力学原理定义元胞及其规则,建立城市内涝风险识别模型;利用开源数据,将模型应用于杭州主城八区;对比已有研究讨论模型的适用性和局限性。【结果】结果显示:(1)元胞边长为60 m、时间步长为4 min的模拟结果最好,参数率定与模型验证的纳什效率系数分别为0.9693和0.9714。(2)2021年研究区百年一遇短时强降雨条件下,建设用地中内涝风险区占比6.94%;将雨水管渠设计重现期由5 a一遇提升至10 a一遇,内涝风险区占比降至6.30%。(3)该模型不需要划分汇水区、数据资料要求少,在平原城市短时强降雨的内涝模拟中具有良好的实用性及和易操作性;但也存在物理机制弱、模拟结果不够精细等局限。【结论】基于CA的城市内涝风险识别模型并不是水文水力学数值模型的改进,而是在权衡数据资料要求、模型运算效率、识别结果准确性等多方面因素之后建立的简化模型,对平原城市内涝防治具有较好的适用性。

基于元胞自动机的城市快速路长距离交织区运行仿真

为了研究城市快速路长距离交织区对交通流运行特性的影响,建立多车道元胞自动机模型.根据长距离交织区内不同位置的换道车辆,考虑其各自换道行为和换道需求强度,引入3种不同换道规则,并对长距离交织区进行分段设定.基于动态安全间距、车流管理策略双重要素,构建不同管理策略下的多车道元胞模型.仿真结果表明,长距离交织区内的强制性驶出换道行为容易引发局部拥堵,形成出入口瓶颈.虽然双虚线型策略能够提供更多驶出车辆换道机会,但随着占有率的增加,这种优势逐渐减弱,相比之下,虚实线型策略更加合理.虚实线型策略-主路优先机制保证主路驶出车辆换道路权,不可避免会牺牲部分辅路通行效率.考虑到辅路的间断交通流特性,虚实线型策略1(先出后入)仍具备一定的实施价值.

基于时间自动机的无信号交叉口车路协同系统建模与验证

车路协同系统(cooperative vehicle infrastructure system,CVIS)是提高交叉口车辆通行安全的重要解决方案之一。针对CVIS现有技术规范和标准未明确系统对象状态交互的动态时序及迁移过程,无法有效保障系统的通行控制逻辑安全问题,采用形式化语言对无信号交叉口车路协同系统功能逻辑进行描述,验证系统对象的状态交互和控制逻辑安全,提高无信号交叉口的车辆通行安全性。以单车无冲突、双车冲突和多车冲突场景分别进行仿真,明确状态交互和使能迁移路径;结合工具和需求规范语句进行系统安全属性验证,证明了控制逻辑的可靠性和安全性,为研发高安全架构的车路协同系统提供了可信依据。

车联网环境下车辆上匝道元胞自动机仿真模拟

为了验证车联网下的交通效率与安全水平,针对高水平车联网下的车辆上匝道过程进行了元胞自动机仿真。针对主道为双车道的上匝道场景,在换道规则上提出了协同换道规则,改进了强制换道规则,从而建立了考虑安全距离和互联性的元胞自动机模型。并模拟了智能网联车与普通人工车混合排列下的交通效率与安全状况。当车流密度较大时,不同车辆排列方式的指标值差异显著。在交通效率方面,当智能网联车渗透率高时,出流量较大且平均速度在20m/s处聚集。说明智能网联车对交通效率有积极影响,而普通人工车的长队列对交通效率有消极作用。在交通安全方面,碰撞时间与临界指数函数值的分布结果均表明,混行情况下智能网联车形成的长队列有利于交通安全,而普通人工车的聚集对交通安全不利。

基于可逆元胞自动机加密的扩展码索引调制方案

针对直接序列扩频系统伪随机(Pseudo Noise,PN)码资源有限且码索引调制系统误码率性能下降的问题,提出了一种基于可逆的初等元胞自动机加密的扩展码索引调制方案。首先,针对PN码资源有限的问题,提出使用混沌规则的初等元胞自动机对PN码进行迭代的方案,从而实现扩展PN码的目的;其次,针对码索引调制误码率性能下降的问题,提出了一种可逆元胞自动机加密的码索引调制方案,在发射端,把信息比特切割成调制比特和映射比特,并分别映射为调制符号和扩频码索引,使用对应索引的扩频码对同相分量进行扩频,同时使用可逆元胞自动机对映射比特进行加密,加密后的映射比特为调制符号的正交分量选取对应索引的扩频码进行扩频。仿真与分析结果表明,在相同频谱效率条件下,在加性高斯白噪声信道中,当误码率为10-5时,扩展码索引调制方案的误码率性能优于码索引调制和广义码索引调制方案约2~4 dB,优于非正交码移键控码索引调制方案约0.5 dB。

基于遗传算法的元胞自动机复杂楼宇人员疏散模型

为探究复杂楼宇人员疏散的效果,该文基于元胞自动机理论,建立了复杂楼宇人员疏散模型。选取某高校实验中心为应用场景,综合考虑了疏散路径、出口安排、人群密度和人员行为等多种因素,分析引导选择出口、引导使用连廊和基于遗传算法的适应度函数三种优化方式对疏散效果的影响,并将此模型计算结果与模拟软件Pathfinder计算结果进行对比验证。结果表明,随着优化程度的提高,疏散总时间和极度拥堵面积减少,有效地降低了高人群密度区域,提高了出口使用均衡性,疏散效果得到了显著提升。

一种基于电机旋变传感器的链式自动机定位控制器设计

需要对链式自动机闩体进行精确定位控制,以确保能够在射击结束时完成抽壳并能在确定的位置点进行供弹和弹种转换操作。提出了一种基于电机旋变的增量式位置控制器设计。通过射长、传动减速比计算绝对位置主令,通过圈数特征和旋变位置确定位置反馈,实现位置闭环控制。提出一种射长不定的特殊情况下,位置主令的计算方法。通过对位置控制环开环传递函数分析,实现高精度定位控制。研制了一套自动机驱动控制系统作为实验平台,试验结果表明,能够有效实现高精度闩体位置控制。

基于元胞自动机的航站楼离港车道边停车容量评估研究

航站楼车道边是旅客实现陆空转换的关键节点,其规模对陆侧交通的正常运行有着至关重要的作用。针对航站楼离港车道边送客车辆的个体行为,基于元胞自动机提出一种改进型离港车道边停车容量仿真模型并利用实测数据对模型的准确性进行验证,最后利用文中模型分析了不同停车方式及停靠时间对停车容量的影响。试验结果表明,仿真结果与实测数据基本一致,可用于评估离港车道边停车容量;在车道边规模不变的前提下,竖向停车方式可以显著增加车道边停车容量;两种停车方式的车道边停车容量都随停靠时间的增加而减小。

点融合系统航班进场排序优化元胞自动机模型

针对点融合系统中航班调度问题,构建航班进场排序的二维元胞自动机模型,模拟先来先服务(first come first service, FCFS)和滑动窗口(sliding window, SDW)策略下的航班排序过程,对比不同策略下的终端区运行效率。实验结果表明:若都采用FCFS,使用中国民航航空器尾流重新分类标准(RECAT-CN)代替现行尾流间隔,进场航班流在点融合系统中的总运行时间减少了98 s,运行效率提升了4.3%;若都使用RECAT-CN间隔标准,采用SDW优化后的航班进场序列,较FCFS的总运行时间减少了193 s,运行效率提升了8.5%;点融合技术和RECAT-CN间隔标准可以实现终端区运行安全和效率的同步提升。

移动机器人全覆盖路径的BINN-元胞自动机规划

为了实现机器人对工作区域的全覆盖,提出了基于生物激励神经网络-元胞自动机系统的全覆盖路径规划方法。介绍了生物激励神经网络算法的基本原理,分析了该算法在机器人陷入死区时无法逃逸的问题。基于元胞自动机系统设计了机器人逃逸机制,包括逃逸点的确定和逃逸路径的规划方法。在仿真环境下,将元胞系统逃逸机制与基本RRT、文献[10]的BINN-RRT逃逸机制进行对比,结果表明元胞系统逃逸机制的规划时间比基本RRT小2个数量级,比BINN-RRT小1个数量级,且逃逸路径短于另外两种方法,验证了元胞系统逃逸机制的有效性和优越性。基于BINN和元胞系统的全覆盖路径比BINN-RRT规划路径更加平滑,验证了全覆盖方法的优越性和有效性。

基于元胞自动机的文体馆人员疏散仿真

为研究封闭环境火情下人员疏散行为,提高文体馆内人员疏散效率,文章以西安某文体馆火灾疏散为例,基于元胞自动机模型,根据环境熟悉度将人员进行分类,引入随机运动,跟随运动,墙壁指示运动,通过matlab进行仿真模拟,研究了环境熟悉度、不熟悉环境人员占比和场景等因素对人员疏散时间的影响。结果表明,当不熟悉环境人员占比较小时,人员向出口移动,容易在出口附近聚集;当不熟悉环境人员占比较大时,则容易向两侧墙壁移动,造成出口利用率降低;当人数一定时,不熟悉环境人员占比约为60%时,疏散时间相对较少;相对于出口横向摆放设施易使人们在疏散时聚集,导致不熟悉环境人员盲目跟随,设施纵向摆放时,疏散时间平均降低9.3%,更易于人员应急疏散。

盐雾环境对典型步枪自动机运动影响

盐雾环境对自动步枪战术技术性能和作战效能有着重要影响,但目前对盐雾环境对自动机运动特性和故障的影响机理尚不明确。以某小口径自动步枪为试验对象,设计并进行盐雾全寿命试验,在每次盐雾后通过高速摄影非接触测量自动机运动、高精度天平测量枪机框质量、簧力测试仪测量复进簧参数;对枪机框及导轨表面形貌特征进行拍照,统计全寿命过程中故障情况,获得自动机运动典型故障类型。研究结果表明:随着盐雾时间增长,枪机框质量逐渐增加;复进簧自由长度及预压力逐渐减小,工作压力先减小、后趋于平缓;自动机后坐到位速度先减小、后增大;复进开始及复进到位速度逐渐减小,且二者具有相同变化趋势。盐雾使自动机后座到位速度减小,自动机运动故障次数增多,盐雾环境引起的多参数变化对自动机故障频次影响明显。在试验研究的基础上,构建枪机框质量、复进簧参数、特征点速度随时间变化定量关系公式,为推断盐雾环境自动机运动件参数变化状况和分析其对故障的影响提供参考依据。

基于元胞自动机方法与欧拉多相流技术的激光沉积IN718组织形貌模拟

为研究激光沉积过程中沉积层微观枝晶外延生长及转向机制,基于欧拉多相流技术与元胞自动机方法相结合,建立了激光沉积IN718二维熔化凝固模型;获得了沉积层温度场、流场以及微观凝固组织的演变过程,对比了模拟与实验所得沉积层枝晶外延生长区厚度,分析了顶部枝晶转向的机制。结果表明:温度场与流场相互影响,模型对沉积层厚度预测误差约为7.0%。沉积层顶部和中部晶体织构取向不同,枝晶的生长方向更偏向于局部热梯度方向,在沉积层顶部,局部热梯度的方向接近水平方向,枝晶的生长方向与局部热梯度偏角较小,因此,形成平行于激光扫描方向的枝晶区。

随机波动驱动的异步元胞自动机及其计算通用性

元胞自动机被广泛认为是基于分子自组装技术制造量子计算机、纳米计算机的基本架构,而元胞自动机的复杂度直接影响其并行分布式计算效率以及物理实现的可行性.现有复杂度最低的异步元胞自动机使用3个元胞状态和3条变迁规则能够构造所有逻辑电路,具备与图灵机等价的计算通用性(图灵通用性).为进一步降低通用异步元胞自动机的复杂度,本文提出新型电路元件以及基于该元件的逻辑电路设计方法.不同于同步电路的逻辑门元件,新型电路元件能够有效处理信号的随机波动,对单电子隧道晶体管等纳米材料技术有积极的应用价值.据此,本文提出新的异步元胞自动机模型,该模型仅需3个元胞状态和2条规则,比现有的通用模型复杂度低.除图灵通用性外,本文通过设计大规模分布式逻辑电路,进一步证明所提的异步元胞自动机具备与所有同步元胞自动机同等的计算能力.

基于改进的王正非模型结合元胞自动机的林火蔓延预测

【目的】针对当前我国林火蔓延预测仍存在预测精度不高、普适性差等问题,基于王正非速度模型结合多维元胞自动机的林火蔓延预测模型进行改进,研究了不同区域和分辨率下该模型的有效性,增强了该模型对于不同分辨率数据的适应能力,从而更好地对森林火灾蔓延进行预测,并为林区的火灾蔓延预测和管理提供一种科学合理的技术手段。【方法】使用黑龙江省大兴安岭地区2011年10月28日发生的森林火灾(分辨率500 m)与四川省凉山地区2022年3月29日发生的森林火灾(分辨率30 m)作为数据源,提取发生火灾时刻以及蔓延过程的火线。引入归一化植被指数(NDVI)对王正非模型进行改进,并利用反卷积算法对元胞自动机算法进行改进,将改进后模型输出的结果与实际结果进行精度对比,并比较不同分辨率下的模型精度表现。【结果】改进后的模型精度有明显的提升,其中,黑龙江省大兴安岭试验改进后模型的kappa系数提高了0.0297,面积误差率降低了21.33%,火场预测火点170个,平均过火速度0.75 m/min。四川省木里县试验改进后模型的kappa系数提高了0.1165,面积误差率降低了37.08%,火场预测火点1795个,平均过火速度为4.00 m/min。【结论】改进后的林火蔓延预测模型可以更有效地预测火灾蔓延并计算出最可能过火的火点位置,其预测结果具有高度的一致性和准确性,提高了林火蔓延模拟预测的实用性。与原始模型相比,改进后的模型很好地提高了在不同分辨率数据下的预测精度,能为林火预防和管理提供科学依据。