知识引导遗传算法实现机器人路径规划

针对传统遗传算法求解机器人路径规划问题存在的收敛速度较慢的缺陷,设计一种知识引导遗传算法,在染色体的编码,初始种群的产生,各种遗传算子和优化算子中加入相关的领域知识.综合考虑机器人路径的长度,安全度和平滑度等性能指标,在对机器人进行路径规划的同时,利用删除,简化,修正和平滑,种优化算子进行路径优化操作.仿真结果表明.所提方法能够有效提高遗传算法求解实际路径规划问题的能力和效率.

     

基于改进遗传算法的机器人路径规划

标准遗传算法在解决各类优化问题中获得成功,但它在具体的应用中由于缺乏对特定知识的利用,其性能有待提高.针对机器人路径规划的实际应用,通过优化设计标准遗传算法中的交叉算子和变异算子,提出一种应用于机器人路径规划的改进型遗传算法.在把地图特征信息引入遗传算子的操作过程中提高了算法的进化效率.计算机仿真实验结果证明该算法在收敛速度、最优解输出概率方面相对于基本遗传算法有了显著提高.     

基于可视图与改进遗传算法的机器人平滑路径规划

针对传统遗传算法在路径规划中存在收敛速度慢、易早熟和路径质量差等缺点,提出一种基于可视图与改进遗传算法的路径规划算法。首先,利用可视图法压缩地图信息,减少搜索节点;然后,对路径个体采用浮点数编码,引入模拟二进制交叉(simulated binary crossover,SBX)算子和多项式变异算子,并采用精英保留策略和轮盘赌相结合的选择算子以防止优质个体丢失;之后,将贝塞尔(Bezier)算子引入遗传算法,改善路径的平滑性;最后,分段优化贝塞尔控制节点,防止优化路径与障碍物碰撞。在仿真地图中进行测试,实验结果表明,所提算法相比于其他算法可以规划出一条更平滑、更短的路径。将算法应用在康复助行机器人中进行测试,实验结果表明,所提算法能有效解决机器人的全局路径规划问题,提升全局路径规划的效率。     

改进遗传算法与领航跟随法的机器人编队方法

针对传统遗传算法在求解机器人路径规划问题时存在的收敛速度慢、路径不平滑问题,对其进行了改进,在适应度函数中加入了路径平滑度因素,选择操作时平滑度较好的路径更容易被选中。在种群选择时将最优个体直接复制到下一代,有效地保留了父代优良基因。在领航机器人规划路径阶段,使用改进的遗传算法为领航机器人规划出一条安全无碰撞且平滑度较好的最优路径。在跟随机器人跟随阶段,使用领航跟随法控制每一个跟随机器人使其与领航者保持特定的距离与角度,从而形成设定的队形。最后通过MATLAB软件建立栅格地图进行仿真,验证了该算法的可行性,与传统遗传算法相比,改进遗传算法收敛速度更快,且路径更加平滑。     

基于离散灰狼算法的喷涂机器人路径规划方法

针对目前用于复杂结构实体喷涂的机器人路径规划方法存在的效率低、未考虑碰撞以及适用性差等问题,提出一种用于求解多层决策问题的离散灰狼算法,并把该算法用于该路径规划问题的求解。为了将连续域灰狼算法改为用于求解多层决策问题的离散灰狼算法,采用矩阵编码方法解决多层决策问题的编码问题,提出基于先验知识与随机选择的混合初始化方法提高算法求解效率和精度,运用交叉算子与两级变异算子定义离散域灰狼算法的种群更新策略。另外,运用图论将喷涂机器人路径规划问题简化为广义旅行商问题,并建立了该问题的最短路径模型和路径碰撞模型。在路径规划实验中,相较于粒子群算法、遗传算法和蚁群算法,提出的算法规划的平均路径长度分别减小了5.0%、5.5%和6.6%,碰撞次数降低为0,且路径更平滑。实验结果表明,提出的算法能够有效提高喷涂机器人的喷涂效率,以及喷涂路径的安全性和适用性。     

基于离散灰狼算法的喷涂机器人路径规划方法

针对目前用于复杂结构实体喷涂的机器人路径规划方法存在的效率低、未考虑碰撞以及适用性差等问题，提出一种用于求解多层决策问题的离散灰狼算法，并把该算法用于该路径规划问题的求解。为了将连续域灰狼算法改为用于求解多层决策问题的离散灰狼算法，采用矩阵编码方法解决多层决策问题的编码问题，提出基于先验知识与随机选择的混合初始化方法提高算法求解效率和精度，运用交叉算子与两级变异算子定义离散域灰狼算法的种群更新策略。另外，运用图论将喷涂机器人路径规划问题简化为广义旅行商问题，并建立了该问题的最短路径模型和路径碰撞模型。在路径规划实验中，相较于粒子群算法、遗传算法和蚁群算法，提出的算法规划的平均路径长度分别减小了5.0%、5.5%和6.6%，碰撞次数降低为0，且路径更平滑。实验结果表明，提出的算法能够有效提高喷涂机器人的喷涂效率，以及喷涂路径的安全性和适用性。     

自适应遗传算法在机器人路径规划的应用

针对现有遗传算法在求解机器人路径规划存在的收敛速度慢、易陷入局部最优等缺点,提出一种基于自适应遗传算法的机器人路径规划方法。该方法引入逆转算子,增加插入算子和删除算子,提出新的自适应策略对交叉和变异概率进行调整,更好地避免陷入局部最优,提高算法寻优效率。该算法在MATLAB和Inte3D平台中进行算例验证,实验结果表明改进的自适应遗传算法比现有遗传算法更为有效。     

基于改进遗传算法的无人机路径规划

针对传统遗传算法收敛速度慢、容易陷入局部最优、规划路径不够平滑、代价高等问题,提出了一种基于改进遗传算法的无人机(UAV)路径规划方法,该算法对遗传算法的选择算子、交叉算子和变异算子进行改进,从而规划出平滑、可飞的路径.首先,建立适合UAV田间信息获取的环境模型,并考虑UAV的目标函数与约束条件以建立适合本场景的更为复...     

能力风暴机器人的全局路径规划

基于Messy遗传算法(Messy GA),设计了移动机器人的通用路径规划算法,其中的优化目标包括最短路径、一定的平滑度和最优安全距离.在算法中加入了优化算子及交叉率和变异率的自适应调整,加快了收敛速度.仿真结果验证了所提方法的有效性.根据能力风暴机器人(AS-R)的实际运行要求,修改算法以扩大路径与障碍物之间的间隔度,并提出采用平滑的方法来优化路径.以AS-R为平台进行了轨迹跟踪实验.实验结果表明算法在随机摆放障碍物和实验室环境下可以实现路径规划,并能够最终实现AS-R机器人的全局路径规划.     

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

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

遗传算法在移动机器人路径规划中的应用

移动机器人的路径规划是机器人研究的重要领域。文中旨在研究遗传算法对于机器人路径规划问题的适用性。对于路径规划的目标,提出了基于路径长度、路径平滑度和路径安全度等因素综合衡量的方法,并在传统的遗传算法的交叉、变异操作的基础上,针对路径规划问题的特点,增加了捷径寻找、障碍避让、平滑优化等方法。实验表明,此算法在存在形状复杂的障碍物的静态环境中表现良好,其效率与准确性皆满足机器人路径规划的要求。     

Clear and smooth path planning

One of the challenging problems in motion planning is finding an efficient path for a robot in different aspects such as length, clearance and smoothness. We formulate this problem as two multi-objective path planning models with the focus on robot's energy consumption and path's safety. These models address two five- and three-objectives optimization problems. We propose an evolutionary algorithm for solving the problems. For efficient searching and achieving Pareto-optimal regions, in addition to the standard genetic operators, a family of path refiner operators is introduced. The new operators play a local search role and intensify power of the algorithm in both explorative and exploitative terms. Finally, we verify the models and compare efficiency of the algorithm and the refiner operators by other multi-objective algorithms such as strength Pareto evolutionary algorithm 2 and multi-objective particle swarm optimization on several complicated path planning test problems.     

Multi-objective path planning in discrete space

Finding a path for a robot which is near to natural looking paths is a challenging problem in motion planning. This paper suggests two single and multi-objective optimization models focusing on length and clearance of the path in discrete space. Considering the complexity of the models and potency of evolutionary algorithms we apply a genetic algorithm with NSGA-II framework for solving the problems addressed in the models. The proposed algorithm uses an innovative family of path refiner operators, in addition to the standard genetic operators. The new operators intensify explorative power of the algorithm in finding Pareto-optimal fronts in the complicated path planning problems such as narrow passages and clutter spaces. Finally, we compare efficiency of the refiner operators and the algorithm with PSO and A* algorithms in several path planning problems.     

Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms

A multi-objective vehicle path planning method has been proposed to optimize path length, path safety, and path smoothness using the elitist non-dominated sorting genetic algorithm—a well-known soft computing approach. Four different path representation schemes that begin their coding from the start point and move one grid at a time towards the destination point are proposed. Minimization of traveled distance and maximization of path safety are considered as objectives of this study while path smoothness is considered as a secondary objective. This study makes an extensive analysis of a number of issues related to the optimization of path planning task-handling of constraints associated with the problem, identifying an efficient path representation scheme, handling single versus multiple objectives, and evaluating the proposed algorithm on large-sized grids and having a dense set of obstacles. The study also compares the performance of the proposed algorithm with an existing GA-based approach. The evaluation of the proposed procedure against extreme conditions having a dense (as high as 91 %) placement of obstacles indicates its robustness and efficiency in solving complex path planning problems. The paper demonstrates the flexibility of evolutionary computing approaches in dealing with large-scale and multi-objective optimization problems.     

Global path planning of mobile robots using a memetic algorithm

In this paper, a memetic algorithm for global path planning (MAGPP) of mobile robots is proposed. MAGPP is a synergy of genetic algorithm (GA) based global path planning and a local path refinement. Particularly, candidate path solutions are represented as GA individuals and evolved with evolutionary operators. In each GA generation, the local path refinement is applied to the GA individuals to rectify and improve the paths encoded. MAGPP is characterised by a flexible path encoding scheme, which is introduced to encode the obstacles bypassed by a path. Both path length and smoothness are considered as fitness evaluation criteria. MAGPP is tested on simulated maps and compared with other counterpart algorithms. The experimental results demonstrate the efficiency of MAGPP and it is shown to obtain better solutions than the other compared algorithms.     

机器人路径规划中的改进型遗传算法

提出了一种应用于机器人路径规划的改进型遗传算法。针对机器人路径规划的实际应用,优化设计了交叉算子和变异算子,引入了自定义的插入和删除两种遗传操作。通过把地图特征信息作为参与决策的已知条件来约束遗传算子的操作过程,提高了算法的进化效率。自定义遗传算子的使用,使得算法对复杂地图也表现出良好的适应能力。计算机仿真实验证明该算法在最优解输出概率方面相对于基本遗传算法有了显著提高。     

Multi-robot multi-target dynamic path planning using artificial bee colony and evolutionary programming in unknown environment

Navigation or path planning is the basic need for movement of robots. Navigation consists of two foremost concerns, target tracking and hindrance avoidance. Hindrance avoidance is the way to accomplish the task without clashing with intermediate hindrances. In this paper, an evolutionary scheme to solve the multi-agent, multi-target navigation problem in an unknown dynamic environment is proposed. The strategy is a combination of modified artificial bee colony for neighborhood search planner and evolutionary programming to smoothen the resulting intermediate feasible path. The proposed strategy has been tested against navigation performances on a collection of benchmark maps for A* algorithm, particle swarm optimization with clustering-based distribution factor, genetic algorithm and rapidly-exploring random trees for path planning. Navigation effectiveness has been measured by smoothness of feasible paths, path length, number of nodes traversed and algorithm execution time. Results show that the proposed method gives good results in comparison to others.