基于快速搜索随机树算法的无人船路径规划研究

无人船航行时的安全性、可靠性和稳定性至关重要。有效的路径规划技术可显著提高无人船的避碰能力和缩短航行距离,已成为无人船领域的重点研究内容。本文:首先,分析了传统的快速搜索随机树(rapidly-exploration random tree,RRT)算法的程序原理和算法流程;其次,针对其不足之处引入偏置采样的方案,增加了对目标点的引导以提高其运行效率,在此基础上采用贪心思想进一步优化无人船的路径,继而提出改进的RRT算法和RRT-connect(rapidly-exploring random tree connect)算法;最后,对几种环境复杂程度不同的地图进行仿真模拟实验,验证改进方法的可行性。验证结果表明,改进的RRT-Connect算法可减少环境复杂多变对无人船路径规划的干扰,并能有效提高路径规划效率。

基于自适应步长快速搜索随机树算法的船舶避碰路径规划

快速搜索随机树算法被广泛应用于船舶避碰路径规划。针对传统快速搜索随机树算法在复杂水域条件下搜索效率低的问题,提出了基于自适应步长快速搜索随机树算法的船舶避碰路径规划模型。首先,引入船舶领域模型,并基于《国际海上避碰规则》为让路船设置虚拟障碍。其次,引入时间序列并建立动态障碍检测机制。采用启发式采样策略,减少无效节点的生成。最后,建立障碍物密集度与搜索步长的映射关系,以上一步采样步长作为已知条件预测当前步采样步长,并利用采样点周围障碍物密集程度修正当前最优的采样步长。仿真试验结果表明,相较于传统的快速搜索随机树算法,采用自适应步长快速搜索随机树算法的船舶避碰路径规划模型在采样成功率、搜索路径耗时、路径段数和路径总长度等四个方面均表现最优,在提高算法效率的同时能够实现更高质量的路径规划。

基于蒙特卡洛树搜索算法实现轨道交通车辆多功能车辆总线周期调度表优化

目的:为改善轨道车辆MVB(多功能车辆总线)周期调度表的负载均衡度,提高MVB带宽利用率和车辆的通信系统实时性,需要对MVB周期调度表进行优化。方法:简述了MVB周期信息通信原理,明确了MVB调度表的2个约束条件,建立将MCTS(蒙特卡洛树搜索)算法应用于MVB调度表优化的理论方法,并通过Python软件编程实现该算法。明确了MCTS算法的优化目标,结合MVB调度表的约束条件设计了优化MCTS算法的预剪枝策略。选取了RMS(单调速率调度)算法、MCTS算法和GA(遗传算法)三种算法进行仿真试验,并对各算法的结果进行对比分析。结果及结论:优化后的MCTS算法有效避免了大量无效的搜索,搜索效率非常高。与RMS算法、GA相比,优化后的MCTS算法能在相同的搜索时间内获得更均衡的解。如果车辆通信设备增加,需要生成包含更多变量的调度表时,MCTS算法更能凸显其搜索优势。

基于搜索树的告警高效聚类算法和Bayes分类器的设计和研究

如何从IDS等安全产品每天产生的海量告警和日志中挖掘出有价值的信息,帮助管理员找到那些真正具有威胁的攻击,然后采取措施,有效地保护系统安全,这是入侵检测系统急待解决的问题。本文利用搜索树可以减少搜索空间和覆盖向量的特点提出了基于搜索树的高效告警聚类算法;考虑到把新来的告警事件归类到先前通过聚类得到的类中,让其与其他的告警事件可以关联起来,提出了基于贝叶斯事件分类器的告警分类方法。最后使用KDDCup1999Data的数据进行了性能测试。实验测试结果表明,此算法和方法是快速有效的。在原型系统“多信息源智能化安全强审计系统”中的实际应用也展现了其良好的应用前景。

求解三维装箱问题的启发式搜索算法

集装箱装载问题是将各种不同尺寸、数量的箱子全部装入不同尺寸的集装箱中,并使集装箱的空间利用率最大化。本文主要研究单个集装箱装载问题,以集装箱的体积、承载重量、货物方向、稳定性等作为约束条件,并以集装箱体积利用率最优作为目标函数,建立数学模型,利用启发式算法和深度优先搜索算法求解模型。采用某外贸公司的实际订单数据验证本文算法,得出三种外贸集装箱的平均体积利用率高于89%,证明了算法的有效性和可行性。

MIMO系统中树搜索检测的排序算法

提出了树搜索算法中基于对数似然比信息的排序算法,给出了使用对数似然比信息排序的一般公式.在未编码情况下,给出使用线性检测器近似的对数似然比信息排序方法;在迭代检测解码情况下,给出使用解码器反馈的比特后验信息进行对数似然比排序的方法.使用对数似然比信息的排序算法不但用到了信道信息,还利用了每帧中的接收信号矢量和先验信息,使各层信号能按照后验概率的大小进行检测.仿真结果表明,该算法在未编码情况下能显著提高系统性能;在编码情况下能加快整个系统的收敛速度.

基于非确定性Monad的纯函数式树搜索算法

纯函数式语言缺乏处理非确定性功能，本文给出了一个非确定性Ｍｏｎａｄ，用此Ｍｏｎａｄ在纯函数式语言中加入了非确定性处理功能，描述卫个基于非确定性Ｍｏｎａｄ的纯函数式树搜索算法，并证明了一些有用的代数性质。

MIMO系统中的低复杂度迭代树搜索算法

提出了应用于Turbo-MIMO系统的基于比特的迭代树搜索检测算法．利用自然二进制映射和扩展信道矩阵的OR分解，使迭代树搜索算法（ITS）中的度量计算转换为逐比特进行，这样大大减小了树中每层需要进行的度量更新和排序的运算量．在此基础上，再利用先验信息进一步减小度量更新的计算量．由于扩展信道矩阵的秩等于发射天线数，该算法对信道缺秩的情况不敏感．仿真结果表明：在误码率性能上，该算法略次于使用自然二进制映射的基于符号的ITS算法，与使用格雷映射的基于符号的ITS算法只有1dB左右的差距；而该算法的计算量在高信噪比时只相当于基于符号的ITS算法的6％～40％．

基于改进快速搜索随机树算法的包裹分拣路径规划算法

针对现有快递包裹分拣系统存在的传输速度慢,准确率低等问题,提出一种改进的快速搜索随机树(RRT)算法。该算法以RRT算法为基础,首先建立了包裹环境模型,引入人工势场法引力分量使节点的扩展更具方向性。其次,对于节点进入障碍物区域需多次重新采样的问题,采用扇形区域法避障以提高算法生成质量,并在路径规划结束后采取二次优化,以获得平滑的路径。仿真结果表明,改进后的算法相比于传统的RRT算法,包裹传输速度提高73.22%,与加入人工势场法的改进算法相比,包裹传输速度提高94.46%。

基于GPU的多维树搜索算法在管道流体仿真中的应用

为提高邻近粒子搜索速度,使水力压裂过程中注入管道内的水流现象更好地满足实时性要求,在图形处理器(GPU)上基于光滑粒子流体动力学(SPH)算法,将结合GPU的并行操作能力和多维树搜索算法优点的多维树搜索算法应用在水力压裂管道流体模拟中。首先,给出了流体粒子的受力分析及更新颗粒位置的方法;然后,给出了该算法在管道流体模拟中的具体实现过程。最后,通过实验近似模拟水力压裂过程中管道与水流交互过程,并与其他算法进行对比分析。结果表明将本文算法应用于大规模管道流体模拟中,执行速度快了几倍,实现了水流模拟在管道中的实时性。

快速搜索随机树算法在航空电缆布线中的应用

针对航空电缆布线中面临的电缆线路分支多、路径复杂等问题,提出一种改进的快速搜索随机树算法。应用这一算法对各电缆线路分支进行计算,进而得出最优路径轨迹,以及各电缆线路分支轨迹的长度。对所提出的算法进行样机试验,确认电缆布线包装机能够达到包装技术标准中无褶皱冗余、路径最短、表面绝缘层无磨损等要求。应用所提出的改进快速搜索随机树算法,可以有效提高航空电缆布线效率,降低劳动量和报废率。

基于IAPF与多层Morphin搜索树的移动机器人路径规划

针对传统人工势场法(artificial potential field,APF)的易出现振荡、死区、局部极小值等缺陷。提出一种结合机器人位置、速度、加速度及障碍物位置等信息的改进人工势场法(improved artificial potential field,IAPF)。利用Morphin算法计算效率高、易结合全局路径规划算法的优点,提出一种多层Morphin搜索树算法。首先,利用改进人工势场法完成路径的全局规划,在此基础上在障碍物附近用多层Morphin搜索树算法进行路径规划。利用MATLAB仿真测试表明,所提出的改进人工势场法与多层Morphin搜索树的混合算法,在移动机器人自主路径规划中,能有效缩短路径长度,提高到达目标点的效率,高效完成路径规划。

多时隙的二进制搜索防冲突算法

针对RFID系统的标签冲突问题,文章在二进制搜索树算法和Aloha算法的基础上,提出了一种新颖的算法,在二进制树的每个节点处动态地估计标签的数量,根据标签的数量使用相应的时隙数;进一步对算法的性能进行了理论分析,并且通过仿真比较了该算法与二进制搜索树算法的性能,结果证明该算法能够有效地节约能量。

动态帧时隙的二进制树RFID防碰撞算法研究

为解决无线射频识别(Radio Frequency Identification,RFID)系统多标签碰撞问题,在分析动态帧时隙ALOHA算法和二进制搜索树算法基础上,提出一种基于动态帧时隙的二进制树RFID防碰撞算法(Dynamic Framed Binary Tree,DFBT)。采用Vogt算法预先估计待识别标签总数,利用动态帧时隙ALOHA算法对标签进行识别,阅读器将未识别的标签提取出来进行最高碰撞位的判断,根据最高碰撞位的情况结合二进制搜索树算法进行碰撞标签分裂。仿真结果表明:DFBT算法提高了识别效率和稳定性,减少了总时隙数,降低了标签成本。当标签数目达到1 000左右,算法识别效率可以达到64%左右,比动态帧时隙ALOHA算法和后退式二进制搜索树算法分别提高了210%和30%。

基于改进RRT算法的智慧小区物料小车路径规划

针对快速搜索随机树(RRT)算法在物料小车路径规划算法中路径转折点多、路径较长、算法运行速度慢等问题,开展了一种基于改进RRT算法的物料小车路径规划算法研究。首先分析了RRT算法与RRT-C算法的原理与优缺点;然后,提出针对优化目标点寻找的采样优化策略、步长优化策略以及保证物料小车运行安全的转角约束条件;最后,采用剪枝优化以及圆切角路径平滑策略来优化所得路径以符合物料小车实际运行线路,并将障碍物进行膨胀化处理,进而规避安全性不足的问题。优化后的RRT算法比初始方法在规划时长和路径长度上分别有着40%~60%和15%~30%的提升,证明了所提方法的有效性。基于改进RRT算法的智慧小区物料小车路径规划研究具有重要的理论和应用意义,并对未来智慧小区动态物流管理系统的优化提供了基础。

树搜索优化算法在FPGA中的应用与实现

针对组合电路的智能化设计速度慢、复杂度高的问题,利用基于人工智能的自主搜索优化策略,将树搜索优化算法与组合逻辑电路中相邻最小项合并定理融合,并在可编程门阵列(Field Programmable Gate Array,FPGA)进行硬件加速的方法进行组合电路的智能设计。该方法把需要设计的逻辑电路最小项作为一级节点,搜索本级中可以合并消项的节点并把合并后的项作为子节点,逐级向下搜索直到本级节点均不能合并消项,最后把所有叶子节点项相加即得到组合逻辑电路的最简逻辑表达式,从而完成组合逻辑电路的智能设计过程。算法通过使用启发式策略,简化了搜索过程,提高了搜索速度。实验结果证明了与传统算法作比较,该算法具有空间复杂度低,速度快等特点。

基于树搜索算法的多用户MIMO系统的自由度分配

针对最大化多用户MIMO系统的和速率的问题,提出了将迭代式干扰对齐技术(Iterative Interference Alignment:IIA)和系统自由度(DoF)分配策略相结合的一种算法。系统的DoF分配是通过树搜索算法(Tree search)来实现的。理论分析及实验仿真结果表明,该算法获得的系统容量,接近遍历法(exhausting search:EX)的结果,但是在算法复杂性及收敛时间上明显优于遍历法。

基于树的多关键词搜索算法在网络监控系统中的应用

介绍了基于树的多关键词快速文本搜索算法,并针对该算法在实际应用中的问题提出了改进措施,在不增加预处理时间和内存空间消耗的前提下有效避免搜索中漏搜和多搜,无损于该算法的高效性。

基于随机搜索树法的机械臂视觉伺服研究

在当今的工业应用中,机械臂完成某一特定作业任务的基础是进行轨迹规划。针对单纯基于图像的视觉伺服(the image-based visual servoing,IBVS),不能直接对相机或机械臂的运行轨迹进行控制,容易造成跟踪目标脱离视野、机械臂与工作空间障碍物相碰撞的问题,本文提出了三维随机搜索树算法(the three-dimensional Rapidly-exploring Random Trees algorithm,3D-RRT)实现机械臂的轨迹规划,将轨迹规划与视觉伺服相融合,使机械臂在跟踪移动过程中,满足图像视野范围限制和空间障碍物约束问题。在MATLAB平台建立算法仿真实验,结果表明三维随机搜索树算法(3D-RRT)可以较好解决基于图像的视觉伺服(IBVS)中存在的问题。

一种用于无人车路径规划的改进双向快速扩展随机树算法研究

快速扩展随机树(RRT)算法在生成采样点时,采用随机扩展策略进行盲目搜索,导致路径生长过程中缺乏方向性且规划速度缓慢。针对此问题,提出了一种改进双向快速扩展随机树算法(Bi-RRT)。首先,在节点的生成方式上,同时生成两个采样点,通过舍弃距离目标点较远的采样点来提高采样效率,确保采样点的有效性,加快路径规划速度;然后,结合自适应采样目标偏向策略,使路径的规划更具有方向性,能够逃离局部极小值。同时在规划过程中,两棵随机树分别选择对方生成的最新节点作为目标,以降低众多繁杂节点的产生,使路径生成更具有目的性;接着利用Matlab软件,将改进Bi-RRT算法同基本RRT和Bi-RRT两种路径规划算法进行对比分析。仿真结果表明,研究算法能缩短规划时间、减少迭代次数,具有较好的可行性和有效性。最后进行了样车实验,验证了研究算法的可靠性。