The Rapidly-exploring Random Tree(RRT)algorithm is an efficient path-planning algorithm based on random sampling.The RRT^(*)algorithm is a variant of the RRT algorithm that can achieve convergence to the optimal solut...The Rapidly-exploring Random Tree(RRT)algorithm is an efficient path-planning algorithm based on random sampling.The RRT^(*)algorithm is a variant of the RRT algorithm that can achieve convergence to the optimal solution.However,it has been proven to take an infinite time to do so.An improved Quick-RRT^(*)(Q-RRT^(*))algorithm based on a virtual light source is proposed in this paper to overcome this problem.The virtual light-based Q-RRT^(*)(LQRRT^(*))takes advantage of the heuristic information generated by the virtual light on the map.In this way,the tree can find the initial solution quickly.Next,the LQRRT^(*)algorithm combines the heuristic information with the optimization capability of the Q-RRT^(*)algorithm to find the approximate optimal solution.LQRRT^(*)further optimizes the sampling space compared with the Q-RRT^(*)algorithm and improves the sampling efficiency.The efficiency of the algorithm is verified by comparison experiments in different simulation environments.The results show that the proposed algorithm can converge to the approximate optimal solution in less time and with lower memory consumption.展开更多
针对快速搜索随机树(rapidly-exploring random tree,RRT)路径规划算法存在的随机性大、搜索效率低等问题,结合强化学习可根据先验知识选择策略的特点,提出了一种基于深度Q网络(deep Q-network,DQN)的改进RRT优化算法。首先设计复数域...针对快速搜索随机树(rapidly-exploring random tree,RRT)路径规划算法存在的随机性大、搜索效率低等问题,结合强化学习可根据先验知识选择策略的特点,提出了一种基于深度Q网络(deep Q-network,DQN)的改进RRT优化算法。首先设计复数域变步长的避障策略,并建立RRT算法中随机树生长的马尔科夫决策过程(Markov decision process,MDP)模型;然后将避障策略和MDP模型接入RRT-Connect算法的接口,并设计训练和路径规划的具体流程;最后在MATLAB软件平台上进行仿真实验。仿真结果表明,改进后的基于深度Q网络的RRT-Connect算法(DQN-RRT-C)在快速性和搜索效率上有显著提高。展开更多
在传统运动规划算法快速扩展随机树(rapidly-exploring random trees,RRT)的基础上,引入了目标偏置策略和一种基于Q距离(Q-distance,QD)函数的避障方法.在随机树生成过程中,首先通过目标偏置策略引导随机树以一定概率朝目标点生长.若机...在传统运动规划算法快速扩展随机树(rapidly-exploring random trees,RRT)的基础上,引入了目标偏置策略和一种基于Q距离(Q-distance,QD)函数的避障方法.在随机树生成过程中,首先通过目标偏置策略引导随机树以一定概率朝目标点生长.若机械臂在新生成的路径节点所表示的位形处与环境障碍物发生碰撞,则使用Q距离函数快速高效地计算二者的嵌入距离,并利用Q距离函数的可微性,计算碰撞点的Q距离函数关于机械臂各个关节角度的梯度,对原有的路径点进行修正.这减少了RRT算法在路径扩展过程中的盲目性、随机性.使用MATLAB与CoppeliaSim机器人仿真软件对该算法进行仿真实验验证,QD-RRT算法与传统RRT算法相比,收敛速度更快,生成的路径质量更优.当环境空间障碍物较复杂或路径需要穿过狭长通道时,该算法优势更加明显.同时,该算法也可应用于RRT的某些改进算法中,例如RRT*.本文也将RRT*与QD-RRT*做出了比较.展开更多
基金This work was supported by the Natural Science Foundation of the Jiangsu Higher Education Institutions of China[grant number 19KJB510022]the Startup Research Foundation for Advanced Talents[grant number JSPIGKZ/2911119220].
文摘The Rapidly-exploring Random Tree(RRT)algorithm is an efficient path-planning algorithm based on random sampling.The RRT^(*)algorithm is a variant of the RRT algorithm that can achieve convergence to the optimal solution.However,it has been proven to take an infinite time to do so.An improved Quick-RRT^(*)(Q-RRT^(*))algorithm based on a virtual light source is proposed in this paper to overcome this problem.The virtual light-based Q-RRT^(*)(LQRRT^(*))takes advantage of the heuristic information generated by the virtual light on the map.In this way,the tree can find the initial solution quickly.Next,the LQRRT^(*)algorithm combines the heuristic information with the optimization capability of the Q-RRT^(*)algorithm to find the approximate optimal solution.LQRRT^(*)further optimizes the sampling space compared with the Q-RRT^(*)algorithm and improves the sampling efficiency.The efficiency of the algorithm is verified by comparison experiments in different simulation environments.The results show that the proposed algorithm can converge to the approximate optimal solution in less time and with lower memory consumption.
文摘在传统运动规划算法快速扩展随机树(rapidly-exploring random trees,RRT)的基础上,引入了目标偏置策略和一种基于Q距离(Q-distance,QD)函数的避障方法.在随机树生成过程中,首先通过目标偏置策略引导随机树以一定概率朝目标点生长.若机械臂在新生成的路径节点所表示的位形处与环境障碍物发生碰撞,则使用Q距离函数快速高效地计算二者的嵌入距离,并利用Q距离函数的可微性,计算碰撞点的Q距离函数关于机械臂各个关节角度的梯度,对原有的路径点进行修正.这减少了RRT算法在路径扩展过程中的盲目性、随机性.使用MATLAB与CoppeliaSim机器人仿真软件对该算法进行仿真实验验证,QD-RRT算法与传统RRT算法相比,收敛速度更快,生成的路径质量更优.当环境空间障碍物较复杂或路径需要穿过狭长通道时,该算法优势更加明显.同时,该算法也可应用于RRT的某些改进算法中,例如RRT*.本文也将RRT*与QD-RRT*做出了比较.
