A hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm in the 2D random environments

Traditional artificial potential field algorithm for multi-robot formation is easy to fall into local minima and the path planning efficiency is low. To this end, we propose a new method of a hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm (A*-MTIAPF) that provides the optimal collision free path and improves the efficiency for multi-robot formation path planning. The A*-MTIAPF algorithm integrates global path planning and local path planning. The novelties include combining A* with the improved artificial potential field algorithm and dividing multiple virtual sub-target points on the global optimal path of A* planning. Firstly, A* algorithm is used to complete the global path planning. Secondly, the improved artificial potential field algorithm which takes multiple sub-target points divided by the global optimal path as virtual target points is used to complete local path planning by switching target points. In addition, we propose a double priority judgment control algorithm (DPJC) to solve the collision problem among multiple robots by setting double priority to determine the movement order of each robot. Then, a new experimental method is designed by using the randomly generated 2D maps to verify the effectiveness of the proposed method. The results show that our method has advantages that it solves the local minimum problem, improves the efficiency of formation path planning and avoids collision among multiple robots over existing methods.     

求解指路标志指引路径规划问题的改进人工蜂群算法*

摘要:针对指路标志指引路径规划问题,提出了一种基于改进人工蜂群算法的求解方法。首先,基于路网拓扑表达,对指路标志指引路径规划问题进行论述;其次,考虑指路标志指引路径规划问题的离散型特点,设计了人工蜂群算法求解的具体的方法和步骤;为了提高人工蜂群算法求解指路标志指引路径规划问题的收敛速度和寻优性能,引入遗传交叉因子、精英保留策略和动态侦查蜂机制对传统人工蜂群算法进行改进;最后,选取广州市大学城作为试验区域,将改进的人工蜂群算法用于求解指路标志指引路径规划问题,试验结果表明：改进后的算法有效的解决了传统人工蜂群算法在求解指路标志指引路径规划问题时收敛速度慢、易早熟等的缺陷,更具可行性。     

一种基于改进人工蜂群算法的机器人实时路径规划方法

在移动机器人控制领域,路径规划是最重要并具有挑战性的问题之一。本文首先采用栅格法对环境进行建模,然后提出一种改进的人工蜂群算法用于机器人的路径规划。在该算法中,为了提高人工蜂群算法的收敛速度,提出自适应的搜索方式,并采用精英保留选择策略以避免机器人路径规划陷入局部最优。仿真实验结果表明,所提算法在机器人路径规划上的可行性与有效性。     

Elite artificial bees' colony algorithm to solve robot's fuzzy constrained routing problem

One of the fundamental challenges of the robotics field is robot's movement. That is, why route planning is an eminent issue of robotics research and it is used to enhance autonomy of moving robots in complex environments. The objective of route planning problem is to find the shortest route without collide from initiation point to destination point so that the amount of energy consumption by robot would not exceed a predefined amount. Because neither the amount of energy consumption nor the robot's passed distance index cannot be measured precisely due to environmental conditions, and fuzzy data is used for modeling the problem and the problem would be called “Robot Fuzzy Constrained shortest Route” problem. The main contributions of this study are fivefold: (i) The mathematical model of fuzzy constrained shortest route problem (FCSRP) is formulated; (ii) An elite artificial bees' colony (EABC) algorithm is used to solve the robot's FSCRP; (iii) The proposed EABC algorithm is simulated with two fuzzy networks; (iv) The performance of the proposed approach is compared with the performance of genetic algorithm and particle swarm optimization algorithm; and (v) The results show the convergence speed of the EABC algorithm is higher than the existing algorithms.     

Mobile robot path planning using artificial bee colony and evolutionary programming

In this paper, an evolutionary approach to solve the mobile robot path planning problem is proposed. The proposed approach combines the artificial bee colony algorithm as a local search procedure and the evolutionary programming algorithm to refine the feasible path found by a set of local procedures. The proposed method is compared to a classical probabilistic roadmap method (PRM) with respect to their planning performances on a set of benchmark problems and it exhibits a better performance. Criteria used to measure planning effectiveness include the path length, the smoothness of planned paths, the computation time and the success rate in planning. Experiments to demonstrate the statistical significance of the improvements achieved by the proposed method are also shown.     

基于ACS算法的移动机器人实时全局最优路径规划

以Ant Colony System（ACS）算法为基础提出了一种新的移动机器人实时全局最优路径规划方法.这种方法包括三个步骤:第一步是采用链接图理论建立移动机器人的自由空间模型，第二步是采用Dijkstra算法搜索出一条无碰撞次优路径，第三步是采用ACS算法对这条次优路径的位置进行优化，从而得到移动机器人的全局最优路径.计算机仿真实验的结果表明所提出的方法是有效的，可用于对移动机器人进行实时路径规划.仿真结果也证实了所提出的方法在收敛速度、解的波动性、动态收敛特征以及计算效率等方面都具有比采用精英保留遗传算法的移动机器人路径规划方法更好的性能.     

基于人工协调场的多移动机器人实时协调避碰规划

为克服传统人工势场在动态未知环境下机器人避碰规划中存在的缺陷,提出人工协调场法(ACF).将场函数与机器人的风险状态相结合,给出并讨论了人工协调场的基本设计.基于人工协调场,考虑机器人的运动约束,实现了多机器人之间以及机器人与环境间的实时协调避碰,提出了一个多移动机器人无死锁实时避碰规划算法.理论分析和仿真试验证明所提方法的有效性.     

基于改进蚁群算法的全向移动机器人全遍历路径规划

受全遍历环境影响, 现有方法规划得出的路径长度过长, 为提高路径规划性能, 获取最优路径, 提出基于改进蚁群算法的全向移动机器人全遍历路径规划方法. 在拓扑建模示意图的基础上, 依据移动机器人在原坐标系下的位置信息, 利用角度转换建立新的环境模型. 考虑蚁群算法存在的问题, 将递减系数引入到启发函数中, 更新局部信息素, 通过设定迭代阈值, 调节信息素的挥发系数. 最后通过路径规划流程设计, 实现对全向移动机器人全遍历路径的规划. 实验结果表明, 所设计方法不仅可以缩短全遍历路径长度, 还可以缩短路径规划时间, 获取最优路径, 从而提高了全向移动机器人的全遍历路径规划性能.     

A dynamic priority based path planning for cooperation of multiple mobile robots in formation forming

Robots that work in a proper formation show several advantages compared to a single complex robot, such as a reduced cost, robustness, efficiency and improved performance. Existing researches focused on the method of keeping the formation shape during the motion, but usually neglect collision constraints or assume a simplified model of obstacles. This paper investigates the path planning of forming a target robot formation in a clutter environment containing unknown obstacles. The contribution lies in proposing an efficient path planner for the multiple mobile robots to achieve their goals through the clutter environment and developing a dynamic priority strategy for cooperation of robots in forming the target formation. A multirobot system is set up to verify the proposed method of robot path planning. Simulations and experiments results demonstrate that the proposed method can successfully address the collision avoidance problem as well as the formation forming problem.     

基于空间数据库裁剪的机器人路径规划

本文对基于空间数据库的移动机器人路径规划算法中引入先裁剪再检索的思想,在此基础上提出一种全新的移动机器人路径规划算法。该算法能使规划的路径成功地得到短的无碰路径,而且收敛速度明显加快;除了适用于障碍物是多边形围成的图形外,还适用于障碍物是圆形的情形;允许设定不同的障碍物各条边的模拟退火初始温度,从而能够简单地避免某些局部极小值的情况。     

异构多目标差分-动态窗口算法 及其在移动机器人中的应用

为了实现在多移动机器人和多窄通道的复杂动态环境中机器人的节能运动规划,提出异构多目标差分-动态窗口法(heterogeneous multi-objective differential evolution-dynamic window algorithm,HMODE-DWA).首先,建立行驶时间、执行器作用力和平滑度的3目标优化模型,设计具有碰撞约束的异构多目标差分进化算法来获得3个目标函数的最优解,进而在已知的静态环境中获得帕累托前沿,利用平均隶属度函数获得起点与终点间最优的全局路径;其次,定义基于环境缓冲区域的模糊动态窗口法使机器人完成动态复杂环境中避障,利用所提出的HMODE-DWA算法动态避障的同时实现节能规划.仿真和实验结果表明,所提出的混合路径规划控制策略能够有效降低移动机器人动态避障过程中的能耗.     

基于改进粒子群算法的移动机器人多目标点路径规划

针对移动机器人遍历多个目标点的路径规划问题,提出了一种基于改进粒子群算法和蚁群算法相结合的路径规划新方法。该方法将目标点的选择转化为旅行商问题,并利用蚁群算法进行优化,定义了每两个目标点之间的路径规划目标函数,利用粒子群算法对其进行优化。针对粒子群算法存在的早熟现象,将反向学习策略引入粒子群算法,并对粒子群算法的惯性权重和学习因子进行改进。性能测试结果表明,改进的粒子群算法能有效避免粒子早熟现象,提高粒子群算法的寻优能力及稳定性。仿真实验结果验证了新方法能有效地实现机器人的多目标点无碰撞路径规划。真实环境下的实验结果证明了新方法在机器人多目标点路径规划的实际应用中也具有有效性。     

Dynamic mechanism-assisted artificial bee colony optimization for image segmentation of COVID-19 chest X-ray

The artificial bee colony optimization (ABC) algorithm operates efficiently and converges well but still suffers from the problem of easily falling into local optimum, and there is room for improving the convergence speed. For this reason, this paper proposes a dynamic mechanism-assisted ABC algorithm (EABC), which contains a dynamic approximation strategy for the optimal solution and a periodic variable food source number strategy. The dynamic approximation of the optimal solution strategy improves the swarm position update formulation and increases the pre-convergence speed of the ABC algorithm. Utilizing a periodic variable food source number scheme allows for more rapid algorithm convergence while simultaneously producing higher variability and diminishing the chances of the algorithm becoming trapped in local optima. In addition, this paper proposes a multi-threshold image segmentation (MTIS) model for COVID-19 X-ray chest images based on EABC. In this paper, the optimization performance of EABC is verified on the benchmark function of IEEE CEC 2017. The effectiveness of the EABC-based MTIS model is also validated on COVID-19 X-ray chest images.     

Conflict free coordinated path planning for multiple robots using a dynamic path modification sequence

In this paper, a practically viable approach for conflict free, coordinated motion planning of multiple robots is proposed. The presented approach is a two phase decoupled method that can provide the desired coordination among the participating robots in offline mode. In the first phase, the collision free path with respect to stationary obstacles for each robot is obtained by employing an A* algorithm. In the second phase, the coordination among multiple robots is achieved by resolving conflicts based on a path modification approach. The paths of conflicting robots are modified based on their position in a dynamically computed path modification sequence (PMS). To assess the effectiveness of the developed methodology, the coordination among robots is also achieved by different strategies such as fixed priority sequence allotment for motion of each robot, reduction in the velocities of joints of the robot, and introduction of delay in starting of each robot. The performance is assessed in terms of the length of path traversed by each robot, time taken by the robot to realize the task and computational time. The effectiveness of the proposed approach for multi-robot motion planning is demonstrated with two case studies that considered the tasks with three and four robots. The results obtained from realistic simulation of multi-robot environment demonstrate that the proposed approach assures rapid, concurrent and conflict free coordinated path planning for multiple robots.     

基于变步长蚁群算法的移动机器人路径规划

针对传统蚁群算法以及双层蚁群算法在路径规划中存在搜索效率低、收敛性较慢以及成本较高的问题,本文提出了变步长蚁群算法。该算法扩大蚁群可移动位置的集合,通过对跳点的选择以达到变步长策略,有效缩短移动机器人路径长度;初始化信息素采用不均匀分布,加强起点至终点直线所涉及到栅格的信息素浓度平行地向外衰减;改进启发式信息矩阵,调整移动机器人当前位置到终点位置的启发函数计算方法。试验结果表明:变步长蚁群算法在路径长度及收敛速度两方面均优于双层蚁群算法及传统蚁群算法,验证了变步长蚁群算法的有效性和优越性,是解决移动机器人路径规划问题的有效算法。     

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.     

基于ABC-SA混合算法的群控电梯优化调度

为解决电梯群控系统（Elevator group control system,EGCS）时间和能耗性能不理想的问题,提出一种基于改进人工蜂群的电梯群控多目标优化调度算法。首先,针对EGCS控制目标复杂性,建立具有多评价指标的群控电梯调度模型,依据该模型的适应度值进行合理派梯选择;其次,引入模拟退火准则优化基本人工蜂群算法结构以解决算法易陷入局部最优解的问题,使用混合改进的人工蜂群算法进行多目标优化调度。仿真结果表明,所提算法在侯梯时间、乘梯时间和停靠次数三个性能指标上对比基本人工蜂群算法均有所提高,有效说明该方法在求解柔性多目标群控电梯优化调度时具有一定的优越性。     

分组教学蚁群算法改进及其在机器人路径规划中应用

针对蚁群算法收敛速度慢、易陷入局部最优问题,提出一种基于分组教学优化改进蚁群算法。该算法从3个角度对蚁群算法进行改进。首先,利用分组教学优化算法改进蚁群算法适应度函数,提高算法全局求解能力。同时,引进一种新的回退策略,通过该策略处理U型障碍死锁问题,确保算法求解可行性。其次,采用一种新的动态信息素更新策略,滚动更新每轮迭代后路径信息素值,避免算法陷入局部最优。最后,引入路径简化算子,将冗余角简化为直线路径,缩短路径长度。仿真实验证明改进算法能有效提高移动机器人路径规划收敛速度和精度。     

多仓储机器人协同路径规划与作业避碰

针对多仓储移动机器人协同作业问题,提出了一种基于全局规划和局部调整的路径规划方法,以获得较短、无碰、避障的可行路径.在路径规划时根据当前节点到终点的距离和局部路径与起点至终点的欧氏路径的夹角设计新启发式函数,驱使机器人沿最短路行进;根据可选节点的数量提出避障规则,提高避障能力;依据路径长度对信息素进行比较更新,以精炼搜索空间、提高收敛性能,对蚁群算法加以改进寻找各自最优路径.在作业避碰时设计避碰规则有效解决仓储机器人间作业碰撞,找到最优或近优路径组合.实验结果表明了本方法的可行性、有效性.     

基于遗传模拟退火算法的移动机器人路径规划

针对移动机器人路径规划的难题,运用了一种基于遗传模拟退火算法的移动机器人最优路径规划方法,对移动机器人的路径规划进行了设计,采用了栅格法对环境进行建模.为了提高路径规划的效率,采用了一种改进的避障算法来生成初始种群.将遗传算法与模拟退火算法相结合形成遗传模拟退火算法,新算法具有较强的全局和局部搜索能力.仿真实验结果证明算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高.