Sampling-based planning algorithms play an important role in high degree-of-freedom motion planning(MP)problems,in which rapidly-exploring random tree(RRT)and the faster bidirectional RRT(named RRT-Connect)algorithms ...Sampling-based planning algorithms play an important role in high degree-of-freedom motion planning(MP)problems,in which rapidly-exploring random tree(RRT)and the faster bidirectional RRT(named RRT-Connect)algorithms have achieved good results in many planning tasks.However,sampling-based methods have the inherent defect of having difficultly in solving planning problems with narrow passages.Therefore,several algorithms have been proposed to overcome these drawbacks.As one of the improved algorithms,Rapidlyexploring random vines(RRV)can achieve better results,but it may perform worse in cluttered environments and has a certain environmental selectivity.In this paper,we present a new improved planning method based on RRT-Connect and RRV,named adaptive RRT-Connect(ARRT-Connect),which deals well with the narrow passage environments while retaining the ability of RRT algorithms to plan paths in other environments.The proposed planner is shown to be adaptable to a variety of environments and can accomplish path planning in a short time.展开更多
为了完成对电力杆塔运行状态的有效监测与故障诊断,要求无人机规划最优三维航线。文章基于快速探索随机树(rapidly exploring random trees,RRT)算法,提出一种启发策略的无碰撞三维航线规划方法,该方法集成启发式搜索策略进行代价函数设...为了完成对电力杆塔运行状态的有效监测与故障诊断,要求无人机规划最优三维航线。文章基于快速探索随机树(rapidly exploring random trees,RRT)算法,提出一种启发策略的无碰撞三维航线规划方法,该方法集成启发式搜索策略进行代价函数设计,加速算法收敛,确保航线最优。在仿真环境与实际场景下的实验结果表明,同传统的RRT与改进的RRT*算法相比,本方法针对电力杆塔所规划的无碰撞三维航线,具有稳定可靠的最短路径长度,能够满足智能监测的应用需求。展开更多
This study focuses on the improvement of path planning efficiency for underwater gravity-aided navigation.Firstly,a Depth Sorting Fast Search(DSFS)algorithm was proposed to improve the planning speed of the Quick Rapi...This study focuses on the improvement of path planning efficiency for underwater gravity-aided navigation.Firstly,a Depth Sorting Fast Search(DSFS)algorithm was proposed to improve the planning speed of the Quick Rapidly-exploring Random Trees*(Q-RRT*)algorithm.A cost inequality relationship between an ancestor and its descendants was derived,and the ancestors were filtered accordingly.Secondly,the underwater gravity-aided navigation path planning system was designed based on the DSFS algorithm,taking into account the fitness,safety,and asymptotic optimality of the routes,according to the gravity suitability distribution of the navigation space.Finally,experimental comparisons of the computing performance of the ChooseParent procedure,the Rewire procedure,and the combination of the two procedures for Q-RRT*and DSFS were conducted under the same planning environment and parameter conditions,respectively.The results showed that the computational efficiency of the DSFS algorithm was improved by about 1.2 times compared with the Q-RRT*algorithm while ensuring correct computational results.展开更多
针对传统航路规划算法存在速度慢、航路可飞性差、动态调整能力不足的问题,提出一种基于改进快速扩展随机树(Rapidly Exploring Random Tree,RRT)的无人机动态航路规划算法。首先,引入RRT方法进行全局航路规划,同时为加快算法收敛,在随...针对传统航路规划算法存在速度慢、航路可飞性差、动态调整能力不足的问题,提出一种基于改进快速扩展随机树(Rapidly Exploring Random Tree,RRT)的无人机动态航路规划算法。首先,引入RRT方法进行全局航路规划,同时为加快算法收敛,在随机树待扩展节点的选取上引入目标启发信息,并在新节点生成和添加过程中融入无人机动力学约束,确保生成的航路具有现实可飞性;其次,为了应对突发威胁情况,提出一种动态扩展随机树的方法来对原有随机树进行剪枝和重构,进而快速避开威胁,生成一条安全航路。实验结果表明,相较于传统RRT算法,改进算法的规划速度提升约20%,节点扩展数减少32%,且规划所得航路符合无人机基本动力学约束条件;当面对突发威胁时,其可以快速进行航路动态调整,实现航路重规划。展开更多
多智能体路径规划旨在解决多个智能体在同一工作空间内生成无碰撞路径的问题,是智能体无人化工作的关键支撑技术。基于回溯思想和自适应局部避障策略,提出了一种双阶段多智能体路径规划算法。在全局路径规划阶段,基于回溯思想改进的RRT*...多智能体路径规划旨在解决多个智能体在同一工作空间内生成无碰撞路径的问题,是智能体无人化工作的关键支撑技术。基于回溯思想和自适应局部避障策略,提出了一种双阶段多智能体路径规划算法。在全局路径规划阶段,基于回溯思想改进的RRT*(rapidly-exploring random trees star)算法(back tracking rapidly-exploring random trees star,BT-RRT*),减少无效父节点,并确保各智能体生成优化的无碰撞路径。在协作避障阶段,智能体依据自身的任务优先级制定局部避障策略,避开动态障碍物和其他智能体。实验结果表明,该算法可成功寻找较优路径,还可降低避障时间。展开更多
针对多关节机械手路径优化问题,提出一种改进快速搜索随机树(Rapidly-exploring random trees,RRT)优化算法。利用标准RRT算法规划初始可行路径,根据路径长度与路径安全性计算出该路径代价。在后期搜索树生长过程中,中间目标点并非随机...针对多关节机械手路径优化问题,提出一种改进快速搜索随机树(Rapidly-exploring random trees,RRT)优化算法。利用标准RRT算法规划初始可行路径,根据路径长度与路径安全性计算出该路径代价。在后期搜索树生长过程中,中间目标点并非随机采样,而是选择能使当前路径代价低于其之前路径代价的节点,同时对该节点进行距离检测,避免产生过于密集的节点集。为加快搜索树向未知区域的扩充速度,从最近节点向中间目标点扩充过程中,采用一种贪婪启发式扩充算法:节点以一定步长循环扩充,直至扩充到达目标节点或产生不连通节点。最后对6自由度检修机械手进行路径规划仿真试验,结果表明相对于标准RRT算法,规划路径的质量得到大幅提高。展开更多
针对多自由度机械臂在三维空间中轨迹规划的高复杂性、安全性和可靠性等问题,基于快速扩展随机树(rapidly-exploring random trees,RRT)算法在高维空间中的概率完备性和计算轻量性等优势,提出了一种基于均匀概率的目标启发式RRT(target ...针对多自由度机械臂在三维空间中轨迹规划的高复杂性、安全性和可靠性等问题,基于快速扩展随机树(rapidly-exploring random trees,RRT)算法在高维空间中的概率完备性和计算轻量性等优势,提出了一种基于均匀概率的目标启发式RRT(target heuristic RRT based on uniform probability,PH-RRT)方法.首先,该方法基于均匀概率的分配机制选取概率采样阈值作为节点标准,并与随机采样值进行比较.当随机采样值在设定的阈值范围内时,确定目标点为随机点进行节点扩展.当随机采样值在设定的阈值范围外时,随机生成随机点,在目标重力和随机点重力的目标启发式作用下进行节点扩展.然后,在已规划出的路径的基础上,进一步引入广度优先搜索思想,针对规划出的路径进行优化处理,提高了路径平滑度并减少了路径长度.实验结果表明,该方法能较好地解决传统RRT方法固有的盲目搜索问题,减少路径规划时间和路径长度,提高机械臂的路径规划效率.展开更多
UAV online path-planning in a low altitude dangerous environment with dense obstacles, static threats(STs)and dynamic threats(DTs), is a complicated, dynamic, uncertain and real-time problem. We propose a novel method...UAV online path-planning in a low altitude dangerous environment with dense obstacles, static threats(STs)and dynamic threats(DTs), is a complicated, dynamic, uncertain and real-time problem. We propose a novel method to solve the problem to get a feasible and safe path. Firstly STs are modeled based on intuitionistic fuzzy set(IFS) to express the uncertainties in STs. The methods for ST assessment and synthesizing are presented. A reachability set(RS) estimator of DT is developed based on rapidly-exploring random tree(RRT) to predict the threat of DT. Secondly a subgoal selector is proposed and integrated into the planning system to decrease the cost of planning, accelerate the path searching and reduce threats on a path. Receding horizon(RH) is introduced to solve the online path planning problem in a dynamic and partially unknown environment. A local path planner is constructed by improving dynamic domain rapidly-exploring random tree(DDRRT) to deal with complex obstacles. RRT* is embedded into the planner to optimize paths. The results of Monte Carlo simulation comparing the traditional methods prove that our algorithm behaves well on online path planning with high successful penetration probability.展开更多
Assembly path planning is a crucial problem in assembly related design and manufacturing processes. Sampling based motion planning algorithms are used for computational assembly path planning. However, the performance...Assembly path planning is a crucial problem in assembly related design and manufacturing processes. Sampling based motion planning algorithms are used for computational assembly path planning. However, the performance of such algorithms may degrade much in environments with complex product structure, narrow passages or other challenging scenarios. A computational path planner for automatic assembly path planning in complex 3D environments is presented. The global planning process is divided into three phases based on the environment and specific algorithms are proposed and utilized in each phase to solve the challenging issues. A novel ray test based stochastic collision detection method is proposed to evaluate the intersection between two polyhedral objects. This method avoids fake collisions in conventional methods and degrades the geometric constraint when a part has to be removed with surface contact with other parts. A refined history based rapidly-exploring random tree (RRT) algorithm which bias the growth of the tree based on its planning history is proposed and employed in the planning phase where the path is simple but the space is highly constrained. A novel adaptive RRT algorithm is developed for the path planning problem with challenging scenarios and uncertain environment. With extending values assigned on each tree node and extending schemes applied, the tree can adapts its growth to explore complex environments more efficiently. Experiments on the key algorithms are carried out and comparisons are made between the conventional path planning algorithms and the presented ones. The comparing results show that based on the proposed algorithms, the path planner can compute assembly path in challenging complex environments more efficiently and with higher success. This research provides the references to the study of computational assembly path planning under complex environments.展开更多
为了解决快速搜索随机树(Rapid-exploration Random Tree,RRT)算法在机器人路径规划中效率低、复杂度高、趋向性差等问题,提出了一种目标偏向性的改进RRT算法。首先,建立复杂的多障碍物环境模型,并利用KD-Tree算法将待规划空间进行多级...为了解决快速搜索随机树(Rapid-exploration Random Tree,RRT)算法在机器人路径规划中效率低、复杂度高、趋向性差等问题,提出了一种目标偏向性的改进RRT算法。首先,建立复杂的多障碍物环境模型,并利用KD-Tree算法将待规划空间进行多级分割;其次,在RRT算法的基础上引入变权重的人工势场法,算法的主要作用是实现避开障碍物和启发式搜索;最后,实现对RRT算法的改进。通过对改进的RRT算法进行仿真验证,结果表明:该算法缩短了路径规划的时间,减少采样点数目,使生成的路径更加平滑,更适用于机器人在多障碍物环境中的路径规划。展开更多
核退役机器人工作过程中,传统快速扩展随机树(Rapidly-exploring Random Tree,RRT)路径规划算法缺乏导向性,路径规划效率低,避障能力弱;为此,提出改进RRT路径规划算法,以提高作业效率和准确率。首先,引入目标偏置函数,并提出自适应步长,...核退役机器人工作过程中,传统快速扩展随机树(Rapidly-exploring Random Tree,RRT)路径规划算法缺乏导向性,路径规划效率低,避障能力弱;为此,提出改进RRT路径规划算法,以提高作业效率和准确率。首先,引入目标偏置函数,并提出自适应步长,使RRT路径规划具有导向性,避免陷入局部最优;其次,采用启发式搜索思想,保留优于其父节点的随机搜索点为新节点;最后,修剪路径中的冗余节点,并采用贝塞尔曲线对路径进行平滑处理。在MATLAB平台上进行仿真,结果表明,改进RRT路径规划算法较传统RRT路径规划算法、RRT-connect路径规划算法效率更高,收敛性更强,可以很好地提高核退役机器人的避障能力。展开更多
基金supported in part by the National Science Foundation of China(61976175,91648208)the Key Project of Natural Science Basic Research Plan in Shaanxi Province of China(2019JZ-05)。
文摘Sampling-based planning algorithms play an important role in high degree-of-freedom motion planning(MP)problems,in which rapidly-exploring random tree(RRT)and the faster bidirectional RRT(named RRT-Connect)algorithms have achieved good results in many planning tasks.However,sampling-based methods have the inherent defect of having difficultly in solving planning problems with narrow passages.Therefore,several algorithms have been proposed to overcome these drawbacks.As one of the improved algorithms,Rapidlyexploring random vines(RRV)can achieve better results,but it may perform worse in cluttered environments and has a certain environmental selectivity.In this paper,we present a new improved planning method based on RRT-Connect and RRV,named adaptive RRT-Connect(ARRT-Connect),which deals well with the narrow passage environments while retaining the ability of RRT algorithms to plan paths in other environments.The proposed planner is shown to be adaptable to a variety of environments and can accomplish path planning in a short time.
文摘为了完成对电力杆塔运行状态的有效监测与故障诊断,要求无人机规划最优三维航线。文章基于快速探索随机树(rapidly exploring random trees,RRT)算法,提出一种启发策略的无碰撞三维航线规划方法,该方法集成启发式搜索策略进行代价函数设计,加速算法收敛,确保航线最优。在仿真环境与实际场景下的实验结果表明,同传统的RRT与改进的RRT*算法相比,本方法针对电力杆塔所规划的无碰撞三维航线,具有稳定可靠的最短路径长度,能够满足智能监测的应用需求。
基金the National Natural Science Foundation of China(Grant No.42274119)the Liaoning Revitalization Talents Program(Grant No.XLYC2002082)+1 种基金National Key Research and Development Plan Key Special Projects of Science and Technology Military Civil Integration(Grant No.2022YFF1400500)the Key Project of Science and Technology Commission of the Central Military Commission.
文摘This study focuses on the improvement of path planning efficiency for underwater gravity-aided navigation.Firstly,a Depth Sorting Fast Search(DSFS)algorithm was proposed to improve the planning speed of the Quick Rapidly-exploring Random Trees*(Q-RRT*)algorithm.A cost inequality relationship between an ancestor and its descendants was derived,and the ancestors were filtered accordingly.Secondly,the underwater gravity-aided navigation path planning system was designed based on the DSFS algorithm,taking into account the fitness,safety,and asymptotic optimality of the routes,according to the gravity suitability distribution of the navigation space.Finally,experimental comparisons of the computing performance of the ChooseParent procedure,the Rewire procedure,and the combination of the two procedures for Q-RRT*and DSFS were conducted under the same planning environment and parameter conditions,respectively.The results showed that the computational efficiency of the DSFS algorithm was improved by about 1.2 times compared with the Q-RRT*algorithm while ensuring correct computational results.
文摘针对传统航路规划算法存在速度慢、航路可飞性差、动态调整能力不足的问题,提出一种基于改进快速扩展随机树(Rapidly Exploring Random Tree,RRT)的无人机动态航路规划算法。首先,引入RRT方法进行全局航路规划,同时为加快算法收敛,在随机树待扩展节点的选取上引入目标启发信息,并在新节点生成和添加过程中融入无人机动力学约束,确保生成的航路具有现实可飞性;其次,为了应对突发威胁情况,提出一种动态扩展随机树的方法来对原有随机树进行剪枝和重构,进而快速避开威胁,生成一条安全航路。实验结果表明,相较于传统RRT算法,改进算法的规划速度提升约20%,节点扩展数减少32%,且规划所得航路符合无人机基本动力学约束条件;当面对突发威胁时,其可以快速进行航路动态调整,实现航路重规划。
文摘多智能体路径规划旨在解决多个智能体在同一工作空间内生成无碰撞路径的问题,是智能体无人化工作的关键支撑技术。基于回溯思想和自适应局部避障策略,提出了一种双阶段多智能体路径规划算法。在全局路径规划阶段,基于回溯思想改进的RRT*(rapidly-exploring random trees star)算法(back tracking rapidly-exploring random trees star,BT-RRT*),减少无效父节点,并确保各智能体生成优化的无碰撞路径。在协作避障阶段,智能体依据自身的任务优先级制定局部避障策略,避开动态障碍物和其他智能体。实验结果表明,该算法可成功寻找较优路径,还可降低避障时间。
文摘针对多关节机械手路径优化问题,提出一种改进快速搜索随机树(Rapidly-exploring random trees,RRT)优化算法。利用标准RRT算法规划初始可行路径,根据路径长度与路径安全性计算出该路径代价。在后期搜索树生长过程中,中间目标点并非随机采样,而是选择能使当前路径代价低于其之前路径代价的节点,同时对该节点进行距离检测,避免产生过于密集的节点集。为加快搜索树向未知区域的扩充速度,从最近节点向中间目标点扩充过程中,采用一种贪婪启发式扩充算法:节点以一定步长循环扩充,直至扩充到达目标节点或产生不连通节点。最后对6自由度检修机械手进行路径规划仿真试验,结果表明相对于标准RRT算法,规划路径的质量得到大幅提高。
文摘针对多自由度机械臂在三维空间中轨迹规划的高复杂性、安全性和可靠性等问题,基于快速扩展随机树(rapidly-exploring random trees,RRT)算法在高维空间中的概率完备性和计算轻量性等优势,提出了一种基于均匀概率的目标启发式RRT(target heuristic RRT based on uniform probability,PH-RRT)方法.首先,该方法基于均匀概率的分配机制选取概率采样阈值作为节点标准,并与随机采样值进行比较.当随机采样值在设定的阈值范围内时,确定目标点为随机点进行节点扩展.当随机采样值在设定的阈值范围外时,随机生成随机点,在目标重力和随机点重力的目标启发式作用下进行节点扩展.然后,在已规划出的路径的基础上,进一步引入广度优先搜索思想,针对规划出的路径进行优化处理,提高了路径平滑度并减少了路径长度.实验结果表明,该方法能较好地解决传统RRT方法固有的盲目搜索问题,减少路径规划时间和路径长度,提高机械臂的路径规划效率.
基金supported by National Natural Science Foundation of China(61175027)
文摘UAV online path-planning in a low altitude dangerous environment with dense obstacles, static threats(STs)and dynamic threats(DTs), is a complicated, dynamic, uncertain and real-time problem. We propose a novel method to solve the problem to get a feasible and safe path. Firstly STs are modeled based on intuitionistic fuzzy set(IFS) to express the uncertainties in STs. The methods for ST assessment and synthesizing are presented. A reachability set(RS) estimator of DT is developed based on rapidly-exploring random tree(RRT) to predict the threat of DT. Secondly a subgoal selector is proposed and integrated into the planning system to decrease the cost of planning, accelerate the path searching and reduce threats on a path. Receding horizon(RH) is introduced to solve the online path planning problem in a dynamic and partially unknown environment. A local path planner is constructed by improving dynamic domain rapidly-exploring random tree(DDRRT) to deal with complex obstacles. RRT* is embedded into the planner to optimize paths. The results of Monte Carlo simulation comparing the traditional methods prove that our algorithm behaves well on online path planning with high successful penetration probability.
基金supported by National Natural Science Foundation of China(Grant No. 51275047)Fund of National Engineering and Research Center for Commercial Aircraft Manufacturing of China(Grant No. 07205)Specialized Research Fund for the Doctoral Program of Higher Education of China(Grant No. 20091101110010)
文摘Assembly path planning is a crucial problem in assembly related design and manufacturing processes. Sampling based motion planning algorithms are used for computational assembly path planning. However, the performance of such algorithms may degrade much in environments with complex product structure, narrow passages or other challenging scenarios. A computational path planner for automatic assembly path planning in complex 3D environments is presented. The global planning process is divided into three phases based on the environment and specific algorithms are proposed and utilized in each phase to solve the challenging issues. A novel ray test based stochastic collision detection method is proposed to evaluate the intersection between two polyhedral objects. This method avoids fake collisions in conventional methods and degrades the geometric constraint when a part has to be removed with surface contact with other parts. A refined history based rapidly-exploring random tree (RRT) algorithm which bias the growth of the tree based on its planning history is proposed and employed in the planning phase where the path is simple but the space is highly constrained. A novel adaptive RRT algorithm is developed for the path planning problem with challenging scenarios and uncertain environment. With extending values assigned on each tree node and extending schemes applied, the tree can adapts its growth to explore complex environments more efficiently. Experiments on the key algorithms are carried out and comparisons are made between the conventional path planning algorithms and the presented ones. The comparing results show that based on the proposed algorithms, the path planner can compute assembly path in challenging complex environments more efficiently and with higher success. This research provides the references to the study of computational assembly path planning under complex environments.
文摘为了解决快速搜索随机树(Rapid-exploration Random Tree,RRT)算法在机器人路径规划中效率低、复杂度高、趋向性差等问题,提出了一种目标偏向性的改进RRT算法。首先,建立复杂的多障碍物环境模型,并利用KD-Tree算法将待规划空间进行多级分割;其次,在RRT算法的基础上引入变权重的人工势场法,算法的主要作用是实现避开障碍物和启发式搜索;最后,实现对RRT算法的改进。通过对改进的RRT算法进行仿真验证,结果表明:该算法缩短了路径规划的时间,减少采样点数目,使生成的路径更加平滑,更适用于机器人在多障碍物环境中的路径规划。
文摘核退役机器人工作过程中,传统快速扩展随机树(Rapidly-exploring Random Tree,RRT)路径规划算法缺乏导向性,路径规划效率低,避障能力弱;为此,提出改进RRT路径规划算法,以提高作业效率和准确率。首先,引入目标偏置函数,并提出自适应步长,使RRT路径规划具有导向性,避免陷入局部最优;其次,采用启发式搜索思想,保留优于其父节点的随机搜索点为新节点;最后,修剪路径中的冗余节点,并采用贝塞尔曲线对路径进行平滑处理。在MATLAB平台上进行仿真,结果表明,改进RRT路径规划算法较传统RRT路径规划算法、RRT-connect路径规划算法效率更高,收敛性更强,可以很好地提高核退役机器人的避障能力。