Motion Planning for Redundant Manipulators Using a Floating Point Genetic Algorithm

This paper deals with the trajectory planning problem for redundant manipulators. A genetic algorithm (GA) using a floating point representation is proposed to search for the optimal end-effector trajectory for a redundant manipulator. An evaluation function is defined based on multiple criteria, including the total displacement of the end-effector, the total angular displacement of all the joints, as well as the uniformity of Cartesian and joint space velocities. These criteria result in minimized, smooth end-effector motions. Simulations are carried out for path planning in free space and in a workspace with obstacles. Results demonstrate the effectiveness and capability of the proposed method in generating optimized collision-free trajectories.     

Real-Time Collision-Free Path Planning for Robots in Configuration Space

Collision-free path planning for an industrial robot in configuration space requires mapping obstacles from robot‘s workspace into its configuration space.In this paper,an approach to real-time collision-free path planning for robots in configuration space is presented.Obstacle mapping is carried out by fundamental obstacles defined in the workspace and their images in the configuration space.In order to avoid dealing with unimportant parts of the configuration space that do not affect searching a collision-free path between starting and goal configurations,we construct a free subspace by slice configuration obstacles.In this free subspace,the collision-free path is determined by the A^* algorithm.Finally,graphical simulations show the effectiveness of the proposed approach.     

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.     

基于网格法的机械臂无碰撞轨迹规划

介绍了高压带电作业机械臂在三维空间中进行无碰撞轨迹规划的一种方法,通过对整个作业空间进行网格化划分,完整的描述出自由空间与障碍物空间,并对每一个网格进行索引对应,使其在利用 A＊算法搜索路径是可以迅速准确的得到最优的无碰撞路径,减少系统的运行时间。     

Obstacle Modelling Oriented to Safe Motion Planning and Control for Planar Rigid Robot Manipulators

Trajectory planning and tracking are crucial tasks in any application using robot manipulators. These tasks become particularly challenging when obstacles are present in the manipulator workspace. In this paper a n-joint planar robot manipulator is considered and it is assumed that obstacles located in its workspace can be approximated in a conservative way with circles. The goal is to represent the obstacles in the robot configuration space. The representation allows to obtain an efficient and accurate trajectory planning and tracking. A simple but effective path planning strategy is proposed in the paper. Since path planning depends on tracking accuracy, in this paper an adequate tracking accuracy is guaranteed by means of a suitably designed Second Order Sliding Mode Controller (SOSMC). The proposed approach guarantees a collision-free motion of the manipulator in its workspace in spite of the presence of obstacles, as confirmed by experimental results.     

Dynamically-Stable Motion Planning for Humanoid Robots

We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using both simulated and real humanoid robots.     

Collision Free Motion Planning for Double Turret System Operating in a Common Workspace

Instead of using the tedious process of turret teaching, an off-line path planning algorithm has been developed for military turrets to improve their accuracy and efficiency. In the scope of this research, an algorithm is proposed to search a path in three different types of configuration spaces which are rectangular, circular and torus shaped by providing three converging options named as fast, medium and optimum depending on the application. With the help of the proposed algorithm, 4-dimensional (D) path planning problem was realized as 2-D + 2-D by using 6 sequences and their options. In order to find a heuristic path on these 2-D configuration maps, the A* algorithm is implemented, which is usually used to find a heuristic path on Cartesian Workspace. Firstly, 4-D configuration space of the double-turret system is obtained by using the method of intersection of point clouds where the bodies in the system are meshed and converted into points. With the help of random simulations, the sequences and the options of these sequences are provided in an appropriate order. A sample path planning was made to examine the performance of the algorithm and thus the converging options. The results obtained for 3 different converging options were simulated on the model of the double-turret system and it was observed that there was no collision between any bodies in these three options. Hence, a collision free motion planning can be carried out for double-turret system operating in a common workspace.

     

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.     

Robot programming using augmented reality: An interactive method for planning collision-free paths

Current robot programming approaches lack the intuitiveness required for quick and simple applications. As new robotic applications are being identified, there is a greater need to be able to programme robots safely and quickly. This paper discusses the use of an augmented reality (AR) environment for facilitating intuitive robot programming, and presents a novel methodology for planning collision-free paths for an n-d.o.f. (degree-of-freedom) manipulator in a 3D AR environment. The methodology is interactive because the human is involved in defining the free space or collision-free volume (CFV), and selecting the start and goal configurations. The methodology uses a heuristic beam search algorithm to generate the paths. A number of possible scenarios are discussed.     

Path planning for manipulators based on an improved probabilistic roadmap method

An indispensable feature of an intelligent manipulator is its capability to quickly plan a short and safe path in the presence of obstacles in its workspace. Among the path planning methods, the probabilistic roadmap (PRM) method has been widely applied in path planning for a high-dimensional manipulator to avoid obstacles. However, its efficiency remains disappointing when the free space of manipulators contains narrow passages. To solve this problem, an improved PRM method is proposed in this paper. Based on a virtual force field, a new sampling strategy of PRM is presented to generate configurations more appropriate for practical application in the free space. Correspondingly, in order to interconnect these configurations to form a roadmap, a new connection strategy is designed, which consists of three stages and can gradually improve the connectivity of the roadmap. The contributions of this paper are as follows. The new sampling strategy can increase the sampling density at the narrow passages of the free space and reduce the redundancy of the samples in the wide-open regions of the free space; the three-stage connection strategy for interconnecting samples can ensure a high-connectivity roadmap; through synthesizing the above strategies, the improved PRM method is more suitable for path planning of manipulators to avoid obstacles efficiently in a cluttered environment. Simulations and experiments are carried out to evaluate the validity of the proposed method, and the method is available for manipulator of any degrees of freedom.     

A search algorithm for motion planning with six degrees of freedom

The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics we are interested in the automatic synthesis of robot motions, given high-level specifications of tasks and geometric models of the robot and obstacles. The “Movers'” problem is to find a continuous, collision-free path for a moving object through an environment containing obstacles. We present an implemented algorithm for the classical formulation of the three-dimensional Movers' problem: Given an arbitrary rigid polyhedral moving object P with three translational and three rotational degrees of freedom, find a continuous, collision-free path taking P from some initial configuration to a desired goal configuration.This paper describes an implementation of a complete algorithm (at a given resolution) for the full six degree of freedom Movers' problem. The algorithm transforms the six degree of freedom planning problem into a point navigation problem in a six-dimensional configuration space (called C-space). The C-space obstacles, which characterize the physically unachievable configurations, are directly represented by six-dimensional manifolds whose boundaries are five-dimensional C-surfaces. By characterizing these surfaces and their intersections, collision-free paths may be found by the closure of three operators which (i) slide along five-dimensional level C-surfaces parallel to C-space obstacles; (ii) slide along one- to four-dimensional intersections of level C-surfaces; and (iii) jump between six-dimensional obstacles. These operators are employed by a best-first search algorithm in C-space. We will discuss theoretical properties of the algorithm, including completeness (at a resolution). This paper describes the heuristic search, with particular emphasis on the heuristic strategies that evaluate local geometric information. At the heart of this paper lie the design and implementation of these strategies for planning paths along level C-surfaces and their intersection manifolds, and for reasoning about motions with three degrees of rotational freedom. The problems of controlling the interaction of these strategies, and of integrating diverse local experts for geometric reasoning provide an interesting application of search to a difficult domain with significant practical implications. The representations and algorithms we develop impact many geometric planning problems, and extend to Cartesian manipulators with six degrees of freedom.     

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.     

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.     

基于改进蚁群算法的三维航迹规划

针对蚁群算法在无人机（UAV）三维航迹规划中存在的收敛速度慢、空间复杂度高的缺点,提出了一种基于改进蚁群算法的无人机（UAV）三维航迹规划方法。该方法改进了局部搜索策略、初始信息素调整因子并在启发函数中加入了路径偏移因子,从而降低了航迹搜索空间的复杂度,提高了算法的搜索效率和收敛速度。在利用DEM数字高程数据建立的搜索空间中,该算法与现有算法相比,规划航迹缩短约24.08%,运行时间减少约11.56%,表明改进蚁群算法在无人机（UAV）三维航迹规划中的可行性和有效性。     

基于混合策略的轮式机器入路径规划方法

快速扩展随机树方法（R RT）是解决具有非完整性约束的轮式机器人路径规划问题的一种有效途径。R RT能够在规划过程中引入机器人动力学约束,但是当环境中存在大量障碍物时,R RT算法的路径搜索效率将会降低。另一方面,R RT算法不具有最优性,限制了其在轮式机器人路径规划中的应用。针对经典R RT算法的不足,提出一种混合的路径规划策略,首先通过路径导引点扩展多树R RT结构,利用多树R RT的局部探索与合并特性快速寻找可通行的区域范围,利用启发式搜索算法在可通行区域内快速寻找动力学可行的机器人运动轨迹。仿真与实车实验表明,该方法能够快速有效地解决复杂障碍物环境下的机器人路径规划问题。     

基于雅可比转秩-RRT法的冗余机械手路径规划

针对核反应堆检修用机械手在末端任务给定的无碰撞路径规划问题进行研究.提出一种将雅可比转秩控制算法与快速搜索随机树法相结合的混合算法,通过选择距目标点工作空间距离最近的位姿点作为树的扩充节点,避免对逆运动学进行求解.利用雅可比转秩控制算法计算出最优扩充方向,采用二分梯度下降扩充方法对末端工具速度加以限制,避免关节速度发生突变.仿真结果表明该混合算法的快速性和有效性.     

一种实时多目标路径规划方法

提出一种利用实时搜索思想的多目标路径规划方法.首先设计并实现局部路径规划算法,在有限的局部空间内执行启发式搜索,求解所有局部非支配路径;在此基础上,提出实时多目标路径规划方法,设计并实现相应的启发式搜索算法,在线交替执行局部搜索过程、学习过程与移动过程,分别用于求解局部空间内的最优移动路径,完成状态的转移和更新状态的启发信息,最终到达目标状态.研究表明,实时多目标启发式搜索算法通过限制局部搜索空间,避免了大量不必要的计算,提高了搜索效率,能够高效地求解多目标路径规划问题.     

基于循环寻优RRT算法的无人机航迹规划

针对快速扩展随机树（RRT）算法在无人机在线自主航迹规划中的寻优性问题,提出基于循环寻优RRT算法。将航迹长度代价约束作为启发条件引入RRT算法,可以有效地剪除搜索空间的无用节点,获得较优航迹。通过引入已规划可行航迹的航迹长度代价约束作为下一次算法运行的启发条件,采用循环迭代策略有效地剪除搜索空间的无用节点,使得算法每次运行后的航迹长度代价减小,多次运行后最终得到的航迹接近最优航迹,充分利用航迹长度代价的启发性,克服了RRT算法的缺点,同时获得了一系列不同航迹代价的可行备选航迹,在协同任务中可以根据协同到达时间进行快速选择。仿真结果表明该算法能够快速生成安全并且满足无人机动力学约束的较优航迹。     

DETERMINING THE PATH SEARCH GRAPH AND FINDING A COLLISION-FREE PATH BY THE MODIFIED A* ALGORITHM FOR A 5-LINK CLOSED CHAIN

Two tightly coordinated 2-link planar manipulators and the straight line between their two bases can be considered as a 5-link closed chain. Since the coordination of robot manipulators has broad applications in manufacturing, hazardous material handling, undersea operation, and space exploration, automatic collision-free path planning for a 5-link closed chain is an important unsolved engineering problem. This paper describes a collision-free path planning algorithm for a 5-link closed chain with revolute joints. In the algorithm the 5-link closed chain is first represented by a path search graph that is built on the basis of the concept of the newly developed C subspace model. Subsequently, a collision-free path is searched upon the graph by the modified A* algorithm. The significance of this path planning algorithm is its convergence and efficiency. The convergence is guaranteed by the C subspace model, which constructs unique mapping between the planned path in C subspaces and that in the world space. The way we build the path search graph and evaluation functions of the A* algorithm is designed to increase the search speed and to preserve the maneuverability of the 5-link closed chain.     

机械手三维操作空间建立与路径规划

针对传统路径规划算法在机械手路径规划中未考虑机械臂干涉、搜索效率低、路径不合理等问题,在建立了机械手空间模型,采用二次投影法分析和计算机械手操作空间的基础上,将障碍模型和操作空间栅格化,并提出了改进的遗传算法。在遗传算法的设计中,使用实数编码和三维坐标编码相结合的编码方式将栅格进行编码,改进交叉算子,定义最小基因交叉片段数量比,提高了搜索效率,简化了计算过程。通过Matlab建立了机械手仿真模型,验证了算法的有效性,且在实验条件和实验对象等各项参数相同的情况下,相对于传统路径规划算法,搜索效率,最优路径比等得到明显提升。