Planning of collision-free paths for a reconfigurable dual manipulator equipped mobile robot

In this paper, we study the problem of finding a collision-free path for a mobile robot which possesses manipulators. The task of the robot is to carry a polygonal object from a starting point to a destination point in a possibly culttered environment. In most of the existing research on robot path planning, a mobile robot is approximated by a fixed shape, i.e., a circle or a polygon. In our task planner, the robot is allowed to change configurations for avoiding collision. This path planner operates using two algorithms: the collision-free feasible configuration finding algorithm and the collision-free path finding algorithm. The collision-free feasible configuration finding algorithm finds all collision-free feasible configurations for the robot when the position of the carried object is given. The collision-free path finding algorithm generates some candidate paths first and then uses a graph search method to find a collision-free path from all the collision-free feasible configurations along the candidate paths. The proposed algorithms can deal with a cluttered environment and is guaranteed to find a solution if one exists.     

Collision-free and smooth joint motion planning for six-axis industrial robots by redundancy optimization

Planning collision-free and smooth joint motion is crucial in robotic applications, such as welding, milling, and laser cutting. Kinematic redundancy exists when a six-axis industrial robot performs five-dimensional tasks, and there are infinite joint configurations for a six-axis industrial robot to realize a cutter location data of the tool path. The robot joint motion can be optimized by taking advantage of the kinematic redundancy, and the collision-free joint motion with minimum joint movement is determined as the optimal. However, most existing redundancy optimization methods do not fully exploit the redundancy of the six-axis industrial robots when they conduct five-dimensional tasks. In this paper, we present an optimization method to solve the problem of inverse kinematics for a six-axis industrial robot to synthesize the joint motion that follows a given tool path, while achieving smoothness and collision-free manipulation. B-spline is applied for the joint configuration interpolation, and the sum of the squares of the first, second, and third derivatives of the B-spline curves are adopted as the smoothness indicators. Besides, the oriented bounding boxes are adopted to simplify the shape of the robot joints, robot links, spindle unit, and fixtures to facilitate collision detections. Dijkstra's shortest path technique and Differential Evolution algorithm are combined to find the optimal joint motion efficiently and avoid getting into a local optimal solution. The proposed algorithm is validated by simulations on two six-axis industrial robots conducting five-axis flank milling tasks respectively.     

Dual-layer multi-robot path planning in narrow-lane environments under specific traffic policies

Collision-free path planning is indispensable for the multi-robot system. Many existing multi-robot path planning algorithms may no longer work properly in the narrow-lane environment. We propose in this paper a dual-layer algorithm to deal with the multi-robot path planning problem in the narrow-lane environment. In the first layer, the integer programming technique primarily based on distance metrics balances the optimality of the generated collision-free paths and the computation time of the algorithm. In the second layer, fast feasible heuristics are applied to make sure the solvability of the proposed integer programming approach in the first layer. In the dual-layer algorithm, specific traffic policies for each narrow lane are implemented to generate a collision-free path for every robot while maintaining the narrow lane free, besides the collision avoidance approach at the robotic level. With this, inter-robot collision in the narrow lane is avoided, and the algorithm’s efficiency in producing collision-free paths increases. Simulations have been launched considerably based on the proposed assessment metrics. According to the extensive simulation data, our algorithm suggests a higher overall performance in the narrow-lane environment when in contrast with the present optimal, sub-optimal, and polynomial-complexity algorithms.

     

基于改进双树RRT*算法的冗余机械臂末端路径规划

针对冗余机械臂的冗余特性与相关RRT*算法在规划机械臂末端路径的应用中存在的搜索效率较低、收敛性不稳定以及没有充分考虑到机械臂末端几何构型与自身运动特性对路径规划影响的问题,提出一种改进策略。首先,引入一种基于根尾节点连线夹角的采样点选择方式,并设置目标逼近区域。根据连续采样成功次数动态选择改进采样与随机采样。接着,将双树扩展策略与上述方法相结合。最后,将初始可行路径进行二次重连得到最终的优化路径。通过验证,改进双树RRT*方法能够有效地提升搜索效率、收敛性以及路径的优越性。虚拟碰撞体与胶囊碰撞体的引入也能较好地应对机械臂末端结构与运动特性带来的影响。使用Mujoco物理仿真引擎进行机械臂运动验证,证明该策略可以为冗余机械臂末端规划出一条较优的可行路径。     

实现机器人动态路径规划的仿真系统

针对机器人动态路径规划问题,提出了在动态环境中移动机器人的一种路径规划方法,适用于环境中同时存在已知和未知,静止和运动障碍物的复杂情况。采用栅格法建立机器人空间模型,整个系统由全局路径规划和局部避碰规划两部分组成。在全局路径规划中,用快速搜索随机树算法规划出初步全局优化路径,局部避碰规划是在全局优化路径的同时,通过基于滚动窗口的环境探测和碰撞规则,对动态障碍物实施有效的局部避碰策略,从而使机器人安全顺利地到达目的地。仿真实验结果说明该方法具有可行性。     

双机器人协作管管焊接的运动规划

针对中小管径管管相贯的马鞍形曲线焊缝,以双机器人协作为基础,提出一种应用于双机器人协作的焊接过程中机器人运动规划的方法。该方法基于焊缝、焊枪的数学模型,充分利用双机器人系统的冗余特性,提出了融合机器人操作度、关节位置等的多指标目标函数,以机器人关节极限为规划约束条件,采用遗传算法规划出最优机器人运动路径。在三维仿真环境中进行的仿真结果初步验证了该方法的可行性和有效性。     

A gradient-based path optimization method for motion planning

Most algorithms in probabilistic sampling-based path planning compute collision-free paths made of straight line segments lying in the configuration space. Due to the randomness of sampling, the paths make detours that need to be optimized. The contribution of this paper is to propose a basic gradient-based algorithm that transforms a polygonal collision-free path into a shorter one. While requiring only collision checking, and not any time-consuming obstacle distance computation nor geometry simplification, we constrain only part of the configuration variables that may cause a collision, and not entire configurations. Thus, parasite motions that are not useful for the problem resolution are reduced without any assumption. Experimental results include navigation and manipulation tasks, eg a manipulator arm-filling boxes and a PR2 robot working in a kitchen environment. Comparisons with a random shortcut optimizer and a partial shortcut have also been studied.     

动态环境下改进蚁群算法的多Agent路径规划

针对动态环境下的多Agent路径规划问题,提出了一种改进的蚁群算法与烟花算法相结合的动态路径规划方法。通过自适应信息素强度值及信息素缩减因子来加快算法的迭代速度,并利用烟花算法来解决路径规划过程中的死锁问题,避免陷入局部最优。在多Agent动态避碰过程中,根据动态障碍物与多Agent之间的运行轨迹是否相交制定相应的避碰策略,并利用路径转变函数解决多Agent的正面碰撞问题。仿真实验表明,该方法优于经典蚁群算法,能够有效解决多Agent路径规划中的碰撞问题,从而快速找到最优无碰路径。     

Collision avoidance for Robot manipulators: Application to Catia/IBM 7565 interface

A collision avoidance algorithm has been developed to augment the capability of an automatic (off-line) robot path planning (programming) tool. The use of off-line programming tools for robot task programming is becoming increasingly important, but the advantages to be gained by off-line programming may be lost if collision-free path planning capabilities are not included. This article addressed the problem of collision-free path planning in the context of a gantry type robot. The collision avoidance algorithm described here uses the <heuristic approach> to collision-free path planning. The manipulator and obstacles are modeled as spheres to simplify tests for collision. An important feature of this algorithm is that it permits the manipulation of objects in the robot's environment. When compared against an algorithm from the literature, given a lightly cluttered environment modelled by spheres, the new algorithm finds a collision-free path much faster. This new algorithm has been implemented as part of the CATIA/IBM 7565 interface which forms an automatic off-line programming system for the IBM 7565 robot. It has also been implemented as a supervisory collision filter to allow collision-free control of the robot from the operator's console. In both cases the algorithm has been demonstrated to provide efficient and effective collision avoidance for the IBM 7565 robot.     

基于改进RRT算法的无人车路径规划

针对无人车在复杂环境中进行全局路径规划时存在的盲目搜索、节点冗余、路径不光滑及不安全等问题,提出一种基于快速扩展随机树(RRT,rapidly-exploring random tree)的综合改进路径规划算法;首先引入目标动态概率采样策略和人工势场引导随机树扩展机制;其次根据汽车运动学模型,对规划的路径进行转角约束和碰撞检测,保证路径的安全性;然后引入Reeds-Sheep曲线用于直接与目标位姿进行连接,避免多余的位姿调整;最后对路径进行剪枝和平滑处理,得到一条更短更光滑的路径;在实验部分,针对不同仿真环境,以规划时间、路径长度和节点数目作为评价指标,对比了RRT算法、RRT*算法和文章算法的路径规划效果;实验结果显示,文章算法相比于RRT算法和RRT*算法,节点数目分别减少了58.94%和85.22%,规划时间分别缩短了61.20%和79.23%,且路径长度相比于RRT算法缩短了17.26%,并和RRT*算法规划的最优路径长度相近。     

Collision-free motion planning of dual-arm reconfigurable robots

Dual-arm reconfigurable robot is a new type of robot. It can adapt to different tasks by changing its different end-effector modules which have standard connectors. Especially, in fast and flexible assembly, it is very important to research the collision-free planning of dual-arm reconfigurable robots. It is to find a continuous, collision-free path in an environment containing obstacles. A new approach to the real-time collision-free motion planning of dual-arm reconfigurable robots is used in the paper. This method is based on configuration space (C-Space). The method of configuration space and the concepts reachable manifold and contact manifold are successfully applied to the collision-free motion planning of dual-arm robot. The complexity of dual-arm robots’ collision-free planning will reduce to a search in a dispersed C-Space. With this algorithm, a real-time optimum path is found. And when the start point and the end point of the dual-arm robot are specified, the algorithm will successfully get the collision-free path real time. A verification of this algorithm is made in the dual-arm horizontal articulated robot SCARATES, and the simulation and experiment ascertain that the algorithm is feasible and effective.     

基于改进概率栅格分解的路径规划算法

栅格分解法是目前研究最广泛的路径规划方法之一,但随着机器人自由度增加会出现“维数灾难”问题,不太适合于解决高自由度机器人在复杂环境中的路径规划。该文提出了基于改进概率栅格分解的路径规划算法,将随机采样应用到栅格分解算法中,虽然不能保证算法的最优性,却极大地提高了算法的效率,使其适合于解决高自由度机器人在复杂环境下的路径规划问题。仿真试验表明该算法可以在较短时间内获得可通行的路径。     

动态环境下基于概率模型检测的路径规划方法

提出了一种动态复杂环境下采用概率模型检测技术进行路径规划的新方法。考虑到实际应用中机器人其移动行为总是受到外界因素的影响,将机器人移动行为看作一个不确定事件,提取环境中的影响因素,构建马尔可夫决策过程模型。采用时态逻辑语言描述机器人目标任务,表达复杂多样的需求行为。运用工具PRISM验证属性,得到满足任务需求的全局优化路径。另外,在全局路径的基础上提出了一种动态避障策略,实现避障局部规划的同时尽量保证机器人最大概率完成任务。通过理论和仿真实验结果证明该方法的正确性和有效性。     

A simple algorithm for intelligent manipulator collision-free motion

The collision-free planning of motion is a fundamental problem for artificial intelligence applications in robotics. The ability to compute a continuous safe path for a robot in a given environment will make possible the development of task-level robot planning systems so that the implementation details and the particular robot motion sequence will be ignored by the programmer.A new approach to planning collision-free motions for general real-life six degrees of freedom (d.o.f.) manipulators is presented. It is based on a simple object model previously developed. The complexity of the general collision detection problem is reduced, and realistic collision-free paths are efficiently found onCS planes. A heuristic evaluation function with a real physical sense is introduced, and computational cost is reduced to the strictly necessary by selecting the most adequate level of representation. A general algorithm is defined for 6 d.o.f. robots that yields good results for actual robot models with complex design structures with the aid of various heuristic techniques. The problem of adaptive motion is also considered.     

Real-time Velocity Alteration Strategy for Collision-free Trajectory Planning of Two Articulated Robot Manipulators

Two articulated robots working in a shared workspace can be programmed by planning the tip trajectory of each robot independently. To account for collision avoidance between links, a real-time velocity alteration strategy based on fast and accurate collision detection is proposed in this paper to determine the step of next motion of slave (low priority) robot for collision-free trajectory planning of two robots with priorities. The effectiveness of the method depends largely on a newly developed method of accurate estimate of distance between links. By using the enclosing and enclosed ellipsoids representations of polyhedral models of links of robots, the minimum distance estimate and collision detection between the links can be performed more efficiently and accurately. The proposed strategy is implemented in an environment where the geometric paths of robots are pre-planned and the preprogrammed velocities are piecewise constant but adjustable. Under the control of the proposed strategy, the master robot always moves at a constant speed. The slave robot moves at the selected velocity, selected by a tradeoff between collision trend index and velocity reduction in one collision checking time, to keep moving as far as possible and as fast as possible while avoid possible collisions along the path. The collision trend index is a fusion of distance and relative velocity between links of two robots to reflect the possibility of collision at present and in the future. Graphic simulations of two PUMA560 robot arms working in common workspace but with independent goals are conducted. Simulations demonstrate the collision avoidance capability of the proposed approach as compared to the approach based on bounding volumes. It shows that advantage of our approach is less number of speed alterations required to react to potential collisions.     

Analysis of an efficient rule-based motion planning system for simulating human crowds

This paper proposes a rule-based motion planning system for agent-based crowd simulation, consisting of sets of rules for both collision avoidance and collision response. In order to avoid an oncoming collision, a set of rules for velocity sampling and evaluation is proposed, which aims to choose a velocity with an expected time to collision larger than a predefined threshold. In order to improve the efficiency over existing methods, the sampling procedure terminates upon finding an appropriate velocity. Moreover, the proposed motion planning system does not guarantee a collision-free movement. In case of collision, another set of rules is also defined to direct the agent to make a corresponding response. The experiment results show that the proposed approach can be applied in different scenarios, while making the simulation execution efficient.     

基于位姿空间栅格扩展及变维搜索的\=机器人运动规划新策略

本文首先对机器人运动规划算法中的栅格扩展策略及次序规划法进行了探讨,并提 出了相应的改进方法,在此基础上提出了一种新的机器人运动规划策略——基于位姿空间栅 格扩展及变维空间搜索算法,该算法可有效地在复杂环境中找出无碰撞路径．     

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

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

Mobile robot with a self-positioning system

This paper describes a general method using configuration space for planning a collision-free path of a manipulator with 6 degrees of freedom (DOF). The basic approach taken in this method is to restrict the free space concerning path planning and to avoid executing unnecessary collision detections, based on the idea that a collision-free path can be planned using only partial information of the configuration space. The configuration space is equally quantized into cells, and the cells concerning path planning are efficiently enumerated based on a heuristic graph search algorithm. A heuristic function which characterizes the search strategy can be defined to give priority to the gross motion using the first few joints. A bi-directional search strategy is also introduced to improve efficiency. The memory is allocated only to the portion of the configuration space concerning path planning, and the data of the free space defined in the 6-dimensional configuration space can be efficiently stored. This algorithm of free space enumeration is independent of the kinematic characteristics of the manipulator. Therefore, this method is generally applicable to any type of manipulator. It has actually been implemented and has been applied to a 6-DOF articulated manipulator.     

基于改进蝙蝠算法和三次样条插值的机器人路径规划

为更好地解决移动机器人路径规划问题, 改进蝙蝠算法的寻优性能, 拓展其应用领域, 提出了一种具有反向学习和正切随机探索机制的蝙蝠算法. 在全局搜索阶段的位置更新中引入动态扰动系数, 提高算法全局搜索能力; 在局部搜索阶段, 融入正切随机探索机制, 增强算法局部寻优的策略性, 避免算法陷入局部极值. 同时, 加入反向学习选择策略, 进一步平衡蝙蝠种群多样性和算法局部开采能力, 提高算法的收敛精度. 然后, 把改进算法与三次样条插值方法相结合去求解机器人全局路径规划问题, 定义了基于路径结点的编码方式, 构造了绕避障碍求解最短路径的方法和适应度函数. 最后, 在简单和复杂障碍环境下分别对单机器人和多机器人系统进行了路径规划对比实验. 实验结果表明, 改进后算法无论在最优解还是平均解方面都要优于其他几种对比算法, 对于求解机器人全局路径规划问题具有较好的可行性和有效性.