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.展开更多
Due to the interrelationship between the base placement of the manipulator and its operation object,it is significant to analyze the accessibility and workspace of manipulators for the optimization of their base locat...Due to the interrelationship between the base placement of the manipulator and its operation object,it is significant to analyze the accessibility and workspace of manipulators for the optimization of their base location.A new method is presented to optimize the base placement of manipulators through motion planning optimization and location optimization in the feasible area for manipulators.Firstly,research problems and contents are outlined.And then the feasible area for the manipulator base installation is discussed.Next,index depended on the joint movements and used to evaluate the kinematic performance of manipulators is defined.Although the mentioned indices in last section are regarded as the cost function of the latter,rapidly-exploring random tree(RRT) and rapidly-exploring random tree*(RRT*) algorithms are analyzed.And then,the proposed optimization method of manipulator base placement is studied by means of simulation research based on kinematic performance criteria.Finally,the conclusions could be proved effective from the simulation results.展开更多
To guide an unmanned aerial vehicle(UAV)flying in complex three-dimensional(3D)environments with unknown obstacles,a novel UAV path planning algorithm named IRRT^(∗)-C2TD3 is proposed.The algorithm combines the rapidl...To guide an unmanned aerial vehicle(UAV)flying in complex three-dimensional(3D)environments with unknown obstacles,a novel UAV path planning algorithm named IRRT^(∗)-C2TD3 is proposed.The algorithm combines the rapidly-exploring random tree star(RRT^(∗))algorithm with the twin delayed deep deterministic policy gradients(TD3)algorithm(a deep reinforcement learning algorithm).By employing exploration strategies from reinforcement learning,IRRT^(∗)-C2TD3 improves the RRT^(∗)algorithm.IRRT^(∗)-C2TD3 is a two-stage path planning algorithm comprising pre-planning and real-time planning.It performs pre-planning of paths by generating paths based on geometric connections toward the goal and smoothing them using cubic B-spline curves.By designing the network architecture and reward function of the TD3 algorithm,real-time planning in unknown environments is achieved based on the pre-planned path from the first stage.Simulation results show that IRRT^(∗)-C2TD3 demonstrates better path planning performance in 3D partially unknown environments than RRT^(∗)-C2TD3,M-C2TD3 and MODRRT^(∗)algorithms.展开更多
针对传统RRT(Rapidly-exploring Random Tree)算法在进行机械臂路径规划时存在的采样随机性过大、搜索效率低下、所规划的路径曲折等问题,提出一种基于采样区域限制的改进RRT(Sampling Area Restriction RRT,SAR-RRT)算法。首先,针对随...针对传统RRT(Rapidly-exploring Random Tree)算法在进行机械臂路径规划时存在的采样随机性过大、搜索效率低下、所规划的路径曲折等问题,提出一种基于采样区域限制的改进RRT(Sampling Area Restriction RRT,SAR-RRT)算法。首先,针对随机性过大的问题,通过引入目标偏置策略来增强随机树的目标导向性,并采用球形采样区域以及角度限制策略对算法的采样进行约束,减少算法对无用空间区域的探索。其次,为提升算法的搜索效率,对随机树的节点扩展进行自适应优化,采用多步长扩展,使算法能够充分利用环境与障碍物的信息,同时利用贪婪思想加快随机树的收敛从而缩短路径的生成时间。最后,对初始规划出的路径进行二次优化处理,在去除路径中的冗余点后以三次B样条曲线对路径进行平滑处理,提升所规划路径的质量。实验结果表明,在2维及3维场景下,SAR-RRT算法均可以顺利完成路径规划任务。对比传统RRT算法,改进算法总体上使路径长度降低27.73%,规划时间缩短85.25%,采样点数减少87.19%且所生成的路径更加平滑。展开更多
针对快速搜索随机树(rapidly-exploring random tree,RRT)算法的随机采样特征导致的收敛速度慢、路径冗余度高、采样点利用率低问题,给出一种新的解决方法。首先,根据图复杂度公式,计算出图的复杂度后确定目标偏执概率,建立偏置概率自...针对快速搜索随机树(rapidly-exploring random tree,RRT)算法的随机采样特征导致的收敛速度慢、路径冗余度高、采样点利用率低问题,给出一种新的解决方法。首先,根据图复杂度公式,计算出图的复杂度后确定目标偏执概率,建立偏置概率自适应模型;其次,在首次规划好路线后,路径中仍存在一些不必要的拐点与棱角,针对传统路径裁剪依赖局部搜索策略,可能导致次优解生成,提出PRM-Dijkstra(probabilistic roadmap-dijkstra)算法对路径进行裁剪,将改进RRT算法生成的树节点利用PRM算法相互连接起来,通过Dijkstra算法计算出一条最优路径;最后,改进RRT算法与PRM-Dijkstra种算法优势相结合,在保证有一条路径的前提下,最大概率的寻找最优路径。通过复杂图下仿真避障实验,结果显示:改进RRT算法在节点生成数量与规划用时相较传统RRT算法平均减少80%,相较于Goal-bias RRT算法均减少40%。并通过机器人操作系统(robot operating system,ROS)下的MoveIt!集成开发平台进行现实环境下避障实验,验证了算法的可行性与有效性。展开更多
针对邮轮推舱序列自动规划问题,采用投影法建立推舱路径规划模型,并提出一种基于改进双向快速搜索随机树(Bidirectional Rapidly-Exploring Random Tree,Bi-RRT)算法嵌入的贪心算法进行邮轮推舱序列规划的方法。以大型邮轮H1508船甲板...针对邮轮推舱序列自动规划问题,采用投影法建立推舱路径规划模型,并提出一种基于改进双向快速搜索随机树(Bidirectional Rapidly-Exploring Random Tree,Bi-RRT)算法嵌入的贪心算法进行邮轮推舱序列规划的方法。以大型邮轮H1508船甲板中段区域为例,在Unity3D软件中对预制模块化舱室单元(Pre-fabricated Modular Cabin Unit,PMCU)的推舱序列规划进行仿真试验。试验结果表明,该方法可兼顾避障验证与序列规划,比传统蛇形推舱序列规划具有更高的效率。展开更多
针对六自由度工业机器人在复杂的分拣环境中分拣速度慢、避障效果差等问题,提出了一种融合人工势场(Artificial Potential Field,APF)算法的快速扩展随机树(Rapidly-exploring Random Tree,RRT)改进算法。传统RRT算法路径规划随机性强...针对六自由度工业机器人在复杂的分拣环境中分拣速度慢、避障效果差等问题,提出了一种融合人工势场(Artificial Potential Field,APF)算法的快速扩展随机树(Rapidly-exploring Random Tree,RRT)改进算法。传统RRT算法路径规划随机性强、收敛速度慢,在该算法中引入APF机制引导其向目标点进行有效扩展,减少路径搜索过程中的无效分支,提高搜索效率;优化对父系节点的选择策略,对原路径局部节点进行优化重连,提高路径质量及平滑性。根据实际分拣中可能出现的状况,在MATLAB软件中建立了3个不同的仿真场景,并将所提出的改进APF-RRT算法与传统RRT算法、APF-RRT算法进行对比仿真实验。结果表明,改进APF-RRT算法于不同分拣环境中,在路径长度、搜索时间、节点个数和迭代次数4个指标上均有一定提升,能以更高的效率搜索到更高质量的路径。展开更多
针对Informed-RRT(rapidly-exploring random tree)^(*)算法收敛速度慢、优化效率低和生成路径无法满足实际需求等问题,开展了基于MI-RRT^(*)(Modified Informed-RRT^(*))算法的路径规划研究,通过引入贪心采样和自适应步长的方法提高算...针对Informed-RRT(rapidly-exploring random tree)^(*)算法收敛速度慢、优化效率低和生成路径无法满足实际需求等问题,开展了基于MI-RRT^(*)(Modified Informed-RRT^(*))算法的路径规划研究,通过引入贪心采样和自适应步长的方法提高算法的收敛率,减少路径生成时间、降低内存占用;利用最小化Snap曲线优化的方法使路径平滑的同时动力也变化平缓,达到节省能量的效果,并提供实际可执行的路径。最后通过多组不同复杂度的实验环境表明,较Informed-RRT^(*)算法MI-RRT^(*)算法稳定性更高、所得规划路径平滑可执行,并且能够减少20%的迭代次数和25%的搜索时间,得出在开阔以及密集环境中MI-RRT^(*)算法较Informed-RRT^(*)和RRT^(*)算法有明显的优势。展开更多
RRT(rapidly exploring random tree)算法是一种基于采样的路径规划算法,可以在高维环境中搜索出一条路径。传统的RRT算法存在节点利用率低、计算量偏大的问题。针对这些问题,基于快速RRT*(Quick-RRT*)算法,通过优化重选父节点与剪枝范...RRT(rapidly exploring random tree)算法是一种基于采样的路径规划算法,可以在高维环境中搜索出一条路径。传统的RRT算法存在节点利用率低、计算量偏大的问题。针对这些问题,基于快速RRT*(Quick-RRT*)算法,通过优化重选父节点与剪枝范围策略、改进采样方式、引入自适应步长,对快速RRT*算法进行改进,使得算法耗时和路径长度更短。同时,加入节点连接筛选策略,消除路径中过大的转弯角。实验结果表明,改进后的算法在三维环境下能快速找到一条距离最短的无碰撞路径,且运行时间也大幅降低。展开更多
基金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.
基金Supported by the National Science and Technology Support Program of China(No.2013BAK03B01)
文摘Due to the interrelationship between the base placement of the manipulator and its operation object,it is significant to analyze the accessibility and workspace of manipulators for the optimization of their base location.A new method is presented to optimize the base placement of manipulators through motion planning optimization and location optimization in the feasible area for manipulators.Firstly,research problems and contents are outlined.And then the feasible area for the manipulator base installation is discussed.Next,index depended on the joint movements and used to evaluate the kinematic performance of manipulators is defined.Although the mentioned indices in last section are regarded as the cost function of the latter,rapidly-exploring random tree(RRT) and rapidly-exploring random tree*(RRT*) algorithms are analyzed.And then,the proposed optimization method of manipulator base placement is studied by means of simulation research based on kinematic performance criteria.Finally,the conclusions could be proved effective from the simulation results.
基金National Natural Science Foundation of China(No.62173084)Foundation of Shanghai Committee of Science and Technology,China(Nos.23ZR1401800 and 22JC1401403)。
文摘To guide an unmanned aerial vehicle(UAV)flying in complex three-dimensional(3D)environments with unknown obstacles,a novel UAV path planning algorithm named IRRT^(∗)-C2TD3 is proposed.The algorithm combines the rapidly-exploring random tree star(RRT^(∗))algorithm with the twin delayed deep deterministic policy gradients(TD3)algorithm(a deep reinforcement learning algorithm).By employing exploration strategies from reinforcement learning,IRRT^(∗)-C2TD3 improves the RRT^(∗)algorithm.IRRT^(∗)-C2TD3 is a two-stage path planning algorithm comprising pre-planning and real-time planning.It performs pre-planning of paths by generating paths based on geometric connections toward the goal and smoothing them using cubic B-spline curves.By designing the network architecture and reward function of the TD3 algorithm,real-time planning in unknown environments is achieved based on the pre-planned path from the first stage.Simulation results show that IRRT^(∗)-C2TD3 demonstrates better path planning performance in 3D partially unknown environments than RRT^(∗)-C2TD3,M-C2TD3 and MODRRT^(∗)algorithms.
文摘针对传统RRT(Rapidly-exploring Random Tree)算法在进行机械臂路径规划时存在的采样随机性过大、搜索效率低下、所规划的路径曲折等问题,提出一种基于采样区域限制的改进RRT(Sampling Area Restriction RRT,SAR-RRT)算法。首先,针对随机性过大的问题,通过引入目标偏置策略来增强随机树的目标导向性,并采用球形采样区域以及角度限制策略对算法的采样进行约束,减少算法对无用空间区域的探索。其次,为提升算法的搜索效率,对随机树的节点扩展进行自适应优化,采用多步长扩展,使算法能够充分利用环境与障碍物的信息,同时利用贪婪思想加快随机树的收敛从而缩短路径的生成时间。最后,对初始规划出的路径进行二次优化处理,在去除路径中的冗余点后以三次B样条曲线对路径进行平滑处理,提升所规划路径的质量。实验结果表明,在2维及3维场景下,SAR-RRT算法均可以顺利完成路径规划任务。对比传统RRT算法,改进算法总体上使路径长度降低27.73%,规划时间缩短85.25%,采样点数减少87.19%且所生成的路径更加平滑。
文摘针对六自由度工业机器人在复杂的分拣环境中分拣速度慢、避障效果差等问题,提出了一种融合人工势场(Artificial Potential Field,APF)算法的快速扩展随机树(Rapidly-exploring Random Tree,RRT)改进算法。传统RRT算法路径规划随机性强、收敛速度慢,在该算法中引入APF机制引导其向目标点进行有效扩展,减少路径搜索过程中的无效分支,提高搜索效率;优化对父系节点的选择策略,对原路径局部节点进行优化重连,提高路径质量及平滑性。根据实际分拣中可能出现的状况,在MATLAB软件中建立了3个不同的仿真场景,并将所提出的改进APF-RRT算法与传统RRT算法、APF-RRT算法进行对比仿真实验。结果表明,改进APF-RRT算法于不同分拣环境中,在路径长度、搜索时间、节点个数和迭代次数4个指标上均有一定提升,能以更高的效率搜索到更高质量的路径。
文摘针对Informed-RRT(rapidly-exploring random tree)^(*)算法收敛速度慢、优化效率低和生成路径无法满足实际需求等问题,开展了基于MI-RRT^(*)(Modified Informed-RRT^(*))算法的路径规划研究,通过引入贪心采样和自适应步长的方法提高算法的收敛率,减少路径生成时间、降低内存占用;利用最小化Snap曲线优化的方法使路径平滑的同时动力也变化平缓,达到节省能量的效果,并提供实际可执行的路径。最后通过多组不同复杂度的实验环境表明,较Informed-RRT^(*)算法MI-RRT^(*)算法稳定性更高、所得规划路径平滑可执行,并且能够减少20%的迭代次数和25%的搜索时间,得出在开阔以及密集环境中MI-RRT^(*)算法较Informed-RRT^(*)和RRT^(*)算法有明显的优势。
文摘RRT(rapidly exploring random tree)算法是一种基于采样的路径规划算法,可以在高维环境中搜索出一条路径。传统的RRT算法存在节点利用率低、计算量偏大的问题。针对这些问题,基于快速RRT*(Quick-RRT*)算法,通过优化重选父节点与剪枝范围策略、改进采样方式、引入自适应步长,对快速RRT*算法进行改进,使得算法耗时和路径长度更短。同时,加入节点连接筛选策略,消除路径中过大的转弯角。实验结果表明,改进后的算法在三维环境下能快速找到一条距离最短的无碰撞路径,且运行时间也大幅降低。
