An Adaptive Rapidly-Exploring Random Tree

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.

Navigation Method Based on Improved Rapid Exploration Random Tree Star-Smart(RRT^(*)-Smart) and Deep Reinforcement Learning

A large number of logistics operations are needed to transport fabric rolls and dye barrels to different positions in printing and dyeing plants, and increasing labor cost is making it difficult for plants to recruit workers to complete manual operations. Artificial intelligence and robotics, which are rapidly evolving, offer potential solutions to this problem. In this paper, a navigation method dedicated to solving the issues of the inability to pass smoothly at corners in practice and local obstacle avoidance is presented. In the system, a Gaussian fitting smoothing rapid exploration random tree star-smart(GFS RRT^(*)-Smart) algorithm is proposed for global path planning and enhances the performance when the robot makes a sharp turn around corners. In local obstacle avoidance, a deep reinforcement learning determiner mixed actor critic(MAC) algorithm is used for obstacle avoidance decisions. The navigation system is implemented in a scaled-down simulation factory.

Global optimization of manipulator base placement by means of rapidly-exploring random tree

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.

Balance in Random Trees

We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly &#107-balanced for any &#107 &#8805 &#51. Definition: Color the vertices of graph &#71 with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored. &#71 is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.

Prediction of mechanical properties of cold rolled strip based on improved extreme random tree

Taking the 2130 cold rolling production line of a steel mill as the research object,feature dimensionality reduction and decoupling processing were realized by fusing random forest and factor analysis,which reduced the generation of weak decision trees while ensured its diversity.The base learner used a weighted voting mechanism to replace the traditional average method,which improved the prediction accuracy.Finally,the analysis method of the correlation between steel grades was proposed to solve the problem of unstable prediction accuracy of multiple steel grades.The experimental results show that the improved prediction model of mechanical properties has high accuracy:the prediction accuracy of yield strength and tensile strength within the error of±20 MPa reaches 93.20%and 97.62%,respectively,and that of the elongation rate under the error of±5%has reached 96.60%.

Improved Prediction of Slope Stability under Static and Dynamic Conditions Using Tree-BasedModels

Slope stability prediction plays a significant role in landslide disaster prevention and mitigation.This paper’s reduced error pruning(REP)tree and random tree(RT)models are developed for slope stability evaluation and meeting the high precision and rapidity requirements in slope engineering.The data set of this study includes five parameters,namely slope height,slope angle,cohesion,internal friction angle,and peak ground acceleration.The available data is split into two categories:training(75%)and test(25%)sets.The output of the RT and REP tree models is evaluated using performance measures including accuracy(Acc),Matthews correlation coefficient(Mcc),precision(Prec),recall(Rec),and F-score.The applications of the aforementionedmethods for predicting slope stability are compared to one another and recently established soft computing models in the literature.The analysis of the Acc together with Mcc,and F-score for the slope stability in the test set demonstrates that the RT achieved a better prediction performance with(Acc=97.1429%,Mcc=0.935,F-score for stable class=0.979 and for unstable case F-score=0.935)succeeded by the REP tree model with(Acc=95.4286%,Mcc=0.896,F-score stable class=0.967 and for unstable class F-score=0.923)for the slope stability dataset The analysis of performance measures for the slope stability dataset reveals that the RT model attains comparatively better and reliable results and thus should be encouraged in further research.

Mapping landslide susceptibility at the Three Gorges Reservoir, China, using gradient boosting decision tree,random forest and information value models

This work was to generate landslide susceptibility maps for the Three Gorges Reservoir(TGR) area, China by using different machine learning models. Three advanced machine learning methods, namely, gradient boosting decision tree(GBDT), random forest(RF) and information value(InV) models, were used, and the performances were assessed and compared. In total, 202 landslides were mapped by using a series of field surveys, aerial photographs, and reviews of historical and bibliographical data. Nine causative factors were then considered in landslide susceptibility map generation by using the GBDT, RF and InV models. All of the maps of the causative factors were resampled to a resolution of 28.5 m. Of the 486289 pixels in the area,28526 pixels were landslide pixels, and 457763 pixels were non-landslide pixels. Finally, landslide susceptibility maps were generated by using the three machine learning models, and their performances were assessed through receiver operating characteristic(ROC) curves, the sensitivity, specificity,overall accuracy(OA), and kappa coefficient(KAPPA). The results showed that the GBDT, RF and In V models in overall produced reasonable accurate landslide susceptibility maps. Among these three methods, the GBDT method outperforms the other two machine learning methods, which can provide strong technical support for producing landslide susceptibility maps in TGR.

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

Random walks in generalized delayed recursive trees

Recently a great deal of effort has been made to explicitly determine the mean first-passage time （MFPT） between two nodes averaged over all pairs of nodes on a fractal network. In this paper, we first propose a family of generalized delayed recursive trees characterized by two parameters, where the existing nodes have a time delay to produce new nodes. We then study the MFPT of random walks on this kind of recursive tree and investigate the effect of the time delay on the MFPT. By relating random walks to electrical networks, we obtain an exact formula for the MFPT and verify it by numerical calculations. Based on the obtained results, we further show that the MFPT of delayed recursive trees is much shorter, implying that the efficiency of random walks is much higher compared with the non-delayed counterpart. Our study provides a deeper understanding of random walks on delayed fractal networks.

Counting and Randomly Generating <i>k</i>-Ary Trees

k-ary trees are one of the most basic data structures in Computer Science. A new method is presented to determine how many there are with n nodes. This method gives additional insight into their structure and provides a new algo-rithm to efficiently generate such a tree randomly.

基于优化快速搜索随机树算法的全局路径规划

为了改善传统快速搜索随机树(RRT)算法在全局路径规划中存在的平滑度差、具有潜在碰撞性等问题,提出了一种双重优化的RRT算法。在传统RRT算法基础上,引入自适应目标偏向策略以缩短采样时间,引入角度约束采样策略以适应车辆极限转角。得到初始路径后,建立二项优化函数(即降低路径曲率和远离障碍物),并将其作为基点进行梯度下降二次优化,生成可供车辆行驶、平滑性良好且碰撞概率低的路径,并进行仿真验证。结果表明:优化RRT算法相比于传统RRT算法、RRT-Connect算法和RRT算法,平均曲率分别降低了38.1%、36.4%和24.7%,曲率均方差分别降低了38.4%、38.4%和27.2%。

Efficiency-Controllable Random Walks on a Class of Recursive Scale-Free Trees with a Deep Trap

Controls, especially effficiency controls on dynamical processes, have become major challenges in many complex systems. We study an important dynamical process, random walk, due to its wide range of applications for modeling the transporting or searching process. For lack of control methods for random walks in various structures, a control technique is presented for a class of weighted treelike scale-free networks with a deep trap at a hub node. The weighted networks are obtained from original models by introducing a weight parameter. We compute analytically the mean first passage time （MFPT） as an indicator for quantitatively measurinM the et^ciency of the random walk process. The results show that the MFPT increases exponentially with the network size, and the exponent varies with the weight parameter. The MFPT, therefore, can be controlled by the weight parameter to behave superlinearly, linearly, or sublinearly with the system size. This work provides further useful insights into controllinM eftlciency in scale-free complex networks.

改进人工势场引导的双向扩展随机树路径规划算法

针对地面移动机器人在复杂环境之下要求规划路径实时性强、路线平滑度高、避障精确完备等需求,在快速扩展随机树算法(RRT)的基础之上,提出一种由改进人工势场法(APF)引导的双向扩展随机树算法(APF-Bi-RRT^(*))。首先,在每次迭代的过程之中两棵随机树同时分别从起始点和目标点进行扩展,以加快算法收敛速度;其次,在算法随机树生长方向上,引入目标偏置策略来优化随机子节点的选取,并在随机树和障碍物中加入人工势场分量,限制路径方向选择的随机性,改进算法克服引力和斥力过大导致陷入局部最优值或目标不可达的问题;最后,在形成锯齿型规划路径之上应用一种采样优化和关键节点平滑策略,进一步缩短和平滑原路径的总距离。对比实验结果证明,该算法既克服了传统随机树算法的节点盲目扩展的问题,又兼顾了生成路径的效率和平滑性,与目标偏置RRT算法相比,在规划路径长度上减少了9.7%左右,在运行时间上缩短了65.3%左右,在算法迭代次数上减少了78.2%左右。

位姿约束下的双向扩展机械臂路径规划方法

针对机械臂路径规划方法存在的规划效率低、连杆通过性差、路径粗糙等问题,以渐进最优快速随机搜索树RRT*为基础,提出一种位姿约束下的双向扩展机械臂路径规划方法(PCO-BT-RRT*)。首先,设计目标偏置引导的双向扩展RRT*算法(BT-RRT*),改进了RRT*算法的初始化过程,将起始点和目标点分别作为两棵随机树的初始节点,并通过目标偏置策略引导其以一定概率相向生长,加快探索未知区域,在保证路径代价较低的同时提升路径生成速度。其次,提出一种位姿约束路径优化策略(PCO),采用机械臂运动学模型和碰撞检测规则共同约束新节点扩展过程,寻找机械臂可达空间内的避障路径;对生成路径剪枝剔冗,缩短可行路径长度,同时对消冗节点以迭代调整的方式进行平滑优化,提高路径生成质量。通过仿真实验分析,验证了所提方法在路径规划问题上的显著性成效;在自主研发的BIM信息融合下建筑砌筑系统进行真机避障测试,验证了该方法的实用性。

近海复杂环境下UUV动态路径规划方法研究

为解决近海环境下水下无人航行器(unmanned underwater vehicle,UUV)的动态路径规划问题,本文提出一种结合全局和局部动态路径规划的算法。首先,本文提出一种基于自适应目标引导的快速拓展随机树算法,以增加随机树生长的方向性,并通过转向和重选策略减少无效拓展加快算法的收敛速度。接着,获得全局路径之后使用自适应子节点选取策略获取动态窗口法的子目标点,将复杂的全局动态任务规划分解为多个简单的动态路劲规划,从而防止动态窗口法陷入局部极小值。最后,通过UUV出港任务仿真实验验证了算法的有效性和实用性。

Improving path planning efficiency for underwater gravity-aided navigation based on a new depth sorting fast search algorithm

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.

不确定采摘环境下改进RRT算法的机械臂路径规划研究

由于果蔬采摘环境的不确定性和复杂性,机械臂在复杂环境中完成采摘,其路径规划需考虑实时避障。为实现采摘机械臂在不确定环境下安全采摘,提出一种改进RRT的动态避障算法,以提升机械臂在不确定采摘环境的适应性。针对基本快速扩展随机树算法(Rapidly-exploring Random Trees,RRT)在动态环境下迭代时间长、路径长、适应性差等问题,在RRT算法的基础上,引入目标导向策略,把终点以一定概率作为随机采样点的采样方向,提高算法的迭代效率;引入动态检测机制,对已完成规划的初始路径进行实时检测,使算法适应动态变化的环境。通过仿真分析改进RRT算法,结果表明:改进RRT算法的路径减少16%,迭代时间缩短86.5%;同时,动态检测机制使算法适应动态环境。

改进RRT^(*)算法的无人艇局部路径规划方法

文中提出一种改进RRT^(*)算法,该算法依据国际海上避碰规则计算本船与他船间DCPA与TCPA并判断会遇场景,限制采样空间.通过偏置采样在采样空间中选取采样点,增强目的性,加快搜索速度.依据线段公理和锚点采样的方式重新选择父节点,去除中间冗余的节点,减少路径转向次数和路径长度,使得最终生成的路径相对平滑.结果表明:改进RRT^(*)算法减少了81%以上的转向点和5%以上的路径长度.

基于大数据分析课、赛衔接的课程体系结构优化研究——以ERP沙盘相关课、赛衔接的经管类课程体系为例

课程体系建设作为培养人才素质与专业能力的核心环节,其整体结构优化急需多元化评价体系改革,尤其弥补大数据相关客观评价。本文以某高校ERP沙盘衔接的相关竞赛成绩和经管类课程成绩(含个人成绩和竞赛团队成绩)为线索,通过依托决策树算法和随机森林算法的大数据挖掘分析方法,探明经管类课程对竞赛成绩的影响,并结合专业教学大纲变革展开相关经管类课程体系的结构优化分析。研究结果既为经管类课程体系结构优化提供建议,又为宏观层次的课程体系结构优化提供立足大数据客观分析的优化范例,一种衔接更多形成性评价的范例。

基于随机森林的电子档案资源快速分类研究

传统的电子档案分类方法存在资源差异化分类系数偏小、分类误差大的问题,为此,设计基于随机森林的电子档案资源快速分类方法。首先设计控制器运算结构和数据接口,然后通过随机森林算法构建电子档案样本决策树,并根据电子档案资源分类特征优化决策树参量,最后设计电子档案资源分类决策输出模型。测试结果表明,相较于传统分类方法,所提方法的分类效果更好,更适用于电子档案资源快速分类工作。