多机器人并行动态包围体层次树碰撞检测算法

针对现有多机器人间碰撞检测算法耗时过多的问题,提出上层动态剔除层、中间连杆层、底层3层结构的并行动态包围体层次树碰撞检测算法.首先采用3层结构构建机器人两两间动态包围体层次树;然后依次对上、中、底各层设计并行加速的并行架构,采用OpenMP的3种并行结构实现碰撞检测并行计算.通过6或8个机器人工作站进行实验并分析算法的时间复杂度,结果表明,在相同实验条件下,动态包围体层次树中间连杆层、底层并行处理后碰撞检测效率是原动态包围体层次树的2倍左右,是RAPID的4倍以上;所提出的并行架构能够发挥出动态包围体层次树的层次结构优势,并行计算下的动态包围体层次树算法能有效地提高多机器人间碰撞检测效率.     

基于时空相关性的快速碰撞检测算法

针对如何提高碰撞检测算法实时性的问题,提出一种空间分解与层次包围盒相结合的碰撞检测算法,并利用物体运动的时空相关性来加速物体之间的碰撞检测速度。首先用空间分割的方法确定相邻物体,然后用基于时空相关性的层次包围盒方法检测物体之间的碰撞情况,在包围盒碰撞检测时采用加入预判的OBB相交测试方法,减少了包围盒的相交测试计算。实验结果表明,该算法能够实现多个物体同时发生碰撞的检测,并且提高碰撞检测的实时性。     

基于改进粒子群的快速碰撞检测算法研究

针对碰撞检测算法精度低、实时性差等问题,提出了一种基于改进粒子群的快速碰撞检测算法。将粒子群优化算法引入到随机碰撞检测问题中,通过混合层次包围盒缩小粒子搜索空间。利用特征采样将虚拟空间内复杂的碰撞检测转换为二维离散空间中的搜索问题。算法对标准粒子群方程进行了优化处理,通过去除速度项来加快算法后期的收敛速度,在算法中引入高斯扰动缩短粒子跳出局部最优的时间,有效提高了算法的精度。通过实验验证,该算法具有较高的精度、实时性好,能够满足碰撞检测的应用要求。     

融合智能算法的变形体碰撞检测算法研究

针对变形体碰撞检测算法的准确性与实时性问题,提出了一种融合智能算法的变形体碰撞检测算法。在随机碰撞检测的基础上,使用层次包围技术缩小粒子搜索空间,采用一种融合基于量子行为的粒子群算法与差分进化算法的混合智能算法进行搜索。该方法以局部吸引子作为差分变异基础,在扩大种群多样性的同时加快了算法收敛速度,有效地解决了传统智能算法不适应离散空间计算问题以及早熟收敛问题。针对随机碰撞粒子搜索空间特点,混合算法的引入大大提高了碰撞检测算法的检测效率,解决了检测过程中的穿刺与遗漏现象。经实验验证该方法在很大程度上提高了变形体碰撞检测的实时性与准确性。     

自适应进化多目标粒子群优化算法

提出一种自适应进化粒子群优化算法以求解多目标优化问题．采用非支配排序策略和动态加权法选择最优粒子,引导种群飞行,提高Ｐａｒｅｔｏ解的多样性．采用动态惯性权重,提高其全局寻优能力．当种群的寻优能力减弱时,采用变异操作以引导粒子群跳出局部最优．通过ＺＤＴ１～ＺＤＴ４ 基准函数验证,该算法能够在保持优化解多样性的同时实现较好的收敛性．与其他多目标进化算法和多目标粒子群优化算法相比,该算法具有较好的性能．     

一种改进AABB包围盒的碰撞检测算法

详细分析比较基于包围盒的碰撞检测算法中的轴向包围盒法、方向包围盒法、离散方向多面体法的检测原理和检测效率,并改进了轴向包围盒碰撞检测算法,提出利用简化包围盒边缘节点实现碰撞检测的新设想,其可行性已被初步试验证实。不仅显著提高了碰撞检测的速度,并且可以便捷地得到更为详细的碰撞检测信息,满足了进一步进行碰撞响应处理的需要。使飞行模拟机的视景系统能够实时、准确地检测出虚拟物体间的碰撞。     

一种快速的可变形物体的碰撞检测算法

为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树,对刚体建立Sphere和OBB混合包围盒层次树;每个物体的混合包围盒层次树又分成上层、中层和下层,每层使用不同的包围盒;在碰撞检测遍历时,上层使用Sphere和Sphere相交检测快速排除不相交物体,在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性,在下层使用AABB和OBB的相交检测较精确地确定物体是否相交;采用多线程技术,在多核设备上实现并行碰撞检测算法。实验结果表明,与经典的AABB算法相比较,该算法在效率方面具有明显优势,能够满足可变形物体与刚体的碰撞检测要求。     

改进的基于AABB包围盒的碰撞检测算法

介绍了一种改进的基于AABB包围盒的碰撞检测算法,通过对对象不断的分割逐步构造出贴近对象的层次包围盒,在碰撞检测阶段对其逐层遍历以实现精确而快速的碰撞检测.实验结果表明,与层次包围球算法相比,该方法在构造二叉树和进行精确的碰撞检测时,性能都有较为明显的提高.     

一种新的基于混合层次包围盒的碰撞检测算法

为了实现物体间快速精确的碰撞检测,提出了一种新的基于混合层次包围盒的碰撞检测算法,充分利用了包围球计算简单和K-DOPs包围盒紧密性好的优点,来构建物体的混合层次包围盒结构。在包围盒树的上层采用Sphere包围盒,能快速排除不相交的物体,下层采用K-DOPs包围盒,进行更加精确的相交测试,提高了碰撞检测实时性。实验结果表明,该算法是有效可行的,具有较强的实时性及鲁棒性,性能优于传统碰撞检测算法。     

基于虚拟环境中织物碰撞检测仿真研究

研究织物碰撞检测真实性问题.碰撞检测应体现织物碰撞真实性.织物仿真方法普遍存在实时性不高、真实感不强等问题.针对传统的质点-弹簧模型容易产生超弹性现象,特别是在织物动感仿真中,为了实现真实性和快速性,提出了一种改进型的建模方法.先采用质点弹簧的方法对织物进行建模.首先对织物采用质点弹簧建模,然后采用混合层次包围盒的碰撞检测算法进行碰撞检测,对检测到得碰撞加以响应,用改进算法建模简单,充分利用包围球计算简单和紧密性好的优点来构建物体的混合层次包围盒结构.仿真结果表明,算法是有效可行的,提高了实时性和鲁棒性,性能优于传统碰撞检测算法,并实现了较强的真实感.     

基于未知环境碰撞冲突预测的群机器人多目标搜索研究

群机器人在未知动态环境下进行多目标搜索时,存在碰撞预测和搜索效率不高等问题。提出了一种碰撞几何锥和改进惯性权重的粒子群优化算法相结合的多目标搜索策略。首先,根据静、动态威胁物的不同分别引入碰撞锥(CC)和速度障碍法(VO),提出了简化复杂障碍物的膨胀几何法(SG)和一种改进CC和VO的碰撞几何锥模型(CGC);有效解决了复杂不规则威胁物的避碰预测问题,并根据CGC模型作出威胁评估报告以确定最优避障方向。其次,提出一种改进惯性权重的粒子群优化算法(IWPSO),提高了搜索效率同时有效解决了粒子群优化算法易陷入局部最优的问题。最后,将两种改进的方法(CGC-IWPSO)相结合以实现群机器人的多目标任务搜索,相比于简化虚拟受力(SVF)、自适应机器人蝙蝠算法(ARBR)、具有运动学约束的粒子群算法(KCPSO),本文方法在搜索时耗、能耗以及避障次数上分别至少减少了15.59%、10.14%、14.12%。     

一种适用于多机器人搜索动态目标的改进粒子群算法

粒子群算法引导机器人搜索跟踪动态目标时,在迭代后期易出现收敛停滞现象。为了改善上述情况,本文提出了结合牛顿法的改进粒子群算法。为了结合粒子群算法与牛顿法,我们在算法中引入了马尔科夫链,这使得机器人在每一次迭代时以一定的概率随机选择牛顿法或粒子群算法搜索跟踪目标。为了模拟机器人搜索动态目标的真实环境,本文还利用了通信项使机器人以一定的方式努力与基站保持通信,用来实时更新目标信息。仿真结果表明,改进的粒子群算法能有效的寻找并跟踪动态目标。     

A hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm in the 2D random environments

Traditional artificial potential field algorithm for multi-robot formation is easy to fall into local minima and the path planning efficiency is low. To this end, we propose a new method of a hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm (A*-MTIAPF) that provides the optimal collision free path and improves the efficiency for multi-robot formation path planning. The A*-MTIAPF algorithm integrates global path planning and local path planning. The novelties include combining A* with the improved artificial potential field algorithm and dividing multiple virtual sub-target points on the global optimal path of A* planning. Firstly, A* algorithm is used to complete the global path planning. Secondly, the improved artificial potential field algorithm which takes multiple sub-target points divided by the global optimal path as virtual target points is used to complete local path planning by switching target points. In addition, we propose a double priority judgment control algorithm (DPJC) to solve the collision problem among multiple robots by setting double priority to determine the movement order of each robot. Then, a new experimental method is designed by using the randomly generated 2D maps to verify the effectiveness of the proposed method. The results show that our method has advantages that it solves the local minimum problem, improves the efficiency of formation path planning and avoids collision among multiple robots over existing methods.     

基于改进粒子群算法的电路板测试路径规划

针对飞针测试机检测电路板时检测时间长、测试效率低、单针检测容易撞针等问题,提出了一种基于改进粒子群算法的测试路径规划算法.首先,使用分区检测的方式解决两针相撞问题;其次,提出一种改进的粒子群算法,在粒子群算法的基础上加入混沌初始化公式用于约束和更新搜索的最大速度,引入遗传算法的交叉、变异的思想,改进粒子群算法易于趋于局部最优的缺陷,提升了算法的全局搜索能力.与粒子群算法、遗传算法进行有效性的对比分析与实机测试.结果表明:此算法可以有效解决测试时两针相撞问题;比起其他两种算法改进粒子群算法在更少的迭代数的同时全局搜索能力更强,可以减少30%算法运算时间、降低10%的测试距离,具有一定的工程应用价值.     

基于协同多目标算法的多机器人路径规划

多机器人路径规划是群体机器人协同工作的前提,其特点是在防碰撞与避障的前提下追求多方面资源的最小消耗.针对这一特点,提出协同非支配排序遗传算法,解决具有多个优化目标的多机器人路径规划问题;运用改进的多目标优化算法,克服多目标优化取权值的不足,同时考虑机器人能源与时间两大资源,以多机器人的路径总长度、总平滑度、总耗时为规划目标.同时引入合作型协同算法框架,将难以求解的多变量问题分组求解.每个机器人的路径视为子种群,子种群通过带精英策略的非支配排序遗传算法,进化并筛选出子种群的部分进入协同进化,每次迭代更新外部的精英解集,最终生成一组非支配路径解.仿真结果表明,在栅格地图环境下,本文算法可有效实现多移动机器人的多优化目标路径规划.     

栅格地图中多机器人协作搜索目标

目标搜索是多机器人领域的一个挑战.本文针对栅格地图中多机器人目标搜索算法进行研究.首先,利用Dempster-Shafer证据理论将声纳传感器获取的环境信息进行融合,构建搜索环境的栅格地图.然后,基于栅格地图建立生物启发神经网络用于表示动态的环境.在生物启发神经网络中,目标通过神经元的活性值全局的吸引机器人.同时,障碍物通过神经元活性值局部的排斥机器人,避免与其相撞.最后,机器人根据梯度递减原则自动的规划出搜索路径.仿真和实验结果显示本文提及的算法能够实现栅格地图中静态目标和动态目标的搜索.与其他搜索算法比较,本文所提及的目标搜索算法有更高的效率和适用性.     

基于并列选择遗传算法的多机器人协作探测

多机器人系统在执行探测任务时,存在多个机器人同时选择相同探测区域而造成碰撞几率增加和探测效率降低的问题.在原有并列选择遗传算法的基础上,提出了一种改进的遗传算法.仿真和实验结果表明,将该算法应用于多机器人协作区域探测,可以减小机器人之间的碰撞几率,提高多机器人系统的探测效率.     

一种新的求解动态连续优化的分层粒子群算法

为了高效求解动态连续优化问题,提出一种分层粒子群优化算法。该算法将动态函数定义域分成Q个子空间,每个空间用一个粒子群作为第一层进行独立搜索,Q个子空间的最优粒子再组成一个全局粒子群进行全局搜索,以达到全局牵引的作用,同时提出探测环境和响应环境的策略。利用经典的动态函数对算法进行测试,结果表明所提出算法能够迅速适应环境变化和跟踪最优解的变化,效果令人满意。     

基于帕累托改进的多机器人动态任务分配算法

针对多机器人系统动态任务分配中存在的优化问题,在使用合同网初始任务分配的基础上提出了一种使用帕累托改进的任务二次分配算法。多机器人系统并行执行救火任务时,首先通过初始化任务分配将多机器人划分为若干子群;然后,每个子群承包某一救火任务,子群在执行任务的同时与就近子群进行帕累托改进确定需要迁移的机器人,实现两子群之间帕累托最优;最后,使用后序二叉树遍历对所有子群进行帕累托改进实现全局帕累托最优。理论分析和仿真结果表明,相较于强化学习算法和蚁群算法,所提算法的救火任务时间分别减少26.18%和37.04%;相较于传统合同网方法,所提算法在时间方面能够高效完成救火任务,在系统收益方面也具有明显优势。