A General Approach for Dexterous Manipulation Planning Based on Configuration Space Structuring

In this paper, we propose a new method for the dexterous manipulation planning problem, under quasi-static movement assumption. This method computes both object and finger trajectories as well as finger relocation sequence and applies to every object shape and hand geometry. It relies on the exploration of the particular subspaces GS k that are the subspaces of all the grasps that can be achieved for a given set of k grasping fingers. The originality is to use continuous paths in these subspaces to directly link two configurations. The proposed approach captures the GS k connectivity in a graph structure. The answer of the manipulation planning query is then given by searching a path in the computed graph. Another specificity of our technique is that it considers manipulated object and hand as an only system, unlike most existing methods that first compute object trajectory then fingers trajectories and thus can not find a solution in all situations. Simulation experiments were conducted for different dexterous manipulation task examples to validate the proposed method.     

Finding Narrow Passages with Probabilistic Roadmaps: The Small-Step Retraction Method

Probabilistic Roadmaps (PRM) have been successfully used to plan complex robot motions in configuration spaces of small and large dimensionalities. However, their efficiency decreases dramatically in spaces with narrow passages. This paper presents a new method—small-step retraction—that helps PRM planners find paths through such passages. This method consists of slightly “fattening” robot's free space, constructing a roadmap in fattened free space, and finally repairing portions of this roadmap by retracting them out of collision into actual free space. Fattened free space is not explicitly computed. Instead, the geometric models of workspace objects (robot links and/or obstacles) are “thinned” around their medial axis. A robot configuration lies in fattened free space if the thinned objects do not collide at this configuration. Two repair strategies are proposed. The “optimist” strategy waits until a complete path has been found in fattened free space before repairing it. Instead, the “pessimist” strategy repairs the roadmap as it is being built. The former is usually very fast, but may fail in some pathological cases. The latter is more reliable, but not as fast. A simple combination of the two strategies yields an integrated planner that is both fast and reliable. This planner was implemented as an extension of a pre-existing single-query PRM planner. Comparative tests show that it is significantly faster (sometimes by several orders of magnitude) than the pre-existing planner. Mitul Saha received the B.S. degree from the Indian Institute of Technology, Kanpur, India, in 2001 and the M.S. degree from the Computer Science Department at Stanford University, Stanford, CA, in 2005. He is currently pursuing the Ph.D. degree in mechanical engineering at Stanford University. His research interests include motion planning, computer vision, graphics, and structural biology. Jean-Claude Latombe graduated in electrical and computer engineering from the National Polytechnic Institute of Grenoble, France, in 1970. He received the M.S. degree in electrical engineering from the National Polytechnic Institute of Grenoble in 1972, and the PhD degree in computer science from the University of Grenoble in 1977. He joined the Department of Computer Science at Stanford University in 1987, where he currently is the Kumagai Professor in the School of Engineering. He does research in the general areas of artificial intelligence, robotics, and geometric computing. He is particularly interested in motion planning, computational biology, and computer-assisted surgery. Yu-Chi Chang is a Ph.D. candidate in the Mechanical Engineering at Stanford University. Yu-Chi received the B.Sc. in Mechanical Engineering and the M.Sc. in Material Science from National Taiwan University, Taiwan, and the M.Sc. in Mechanical Engineering from Stanford University, United States. His current research interests include robust design and statistical analysis for manufacturing system. Friedrich Prinz is the Rodney H. Adams Professor of Engineering and Professor of Mechanical Engineering and Materials Science and Engineering, Stanford University. Professor Prinz received his Ph.D. degree in Physics from the University of Vienna in 1975. He has been active in synergistic activities with organizations like the National Research Council Committees, the Japanese Technology Evaluation Center and World Technology Evaluation Center, as well as Portuguese Science and Technology Foundation. He was elected to the Austrian Academy of Science (foreign member), Vienna, Austria in 1996. Dr. Prinz's current research activities address a wide range of problems related to design and rapid prototyping of organic and inorganic devices. His current work focuses on the fabrication and physics of fuel cells as well as the creation of biological cell structures. His group uses atomic force microscopy and impedance spectroscopy to characterize the behavior of electrochemical systems with micro and nano-scale dimensions.     

Perception‐aware autonomous mast motion planning for planetary exploration rovers

Highly accurate real‐time localization is of fundamental importance for the safety and efficiency of planetary rovers exploring the surface of Mars. Mars rover operations rely on vision‐based systems to avoid hazards as well as plan safe routes. However, vision‐based systems operate on the assumption that sufficient visual texture is visible in the scene. This poses a challenge for vision‐based navigation on Mars where regions lacking visual texture are prevalent. To overcome this, we make use of the ability of the rover to actively steer the visual sensor to improve fault tolerance and maximize the perception performance. This paper answers the question of where and when to look by presenting a method for predicting the sensor trajectory that maximizes the localization performance of the rover. This is accomplished by an online assessment of possible trajectories using synthetic, future camera views created from previous observations of the scene. The proposed trajectories are quantified and chosen based on the expected localization performance. In this study, we validate the proposed method in field experiments at the Jet Propulsion Laboratory (JPL) Mars Yard. Furthermore, multiple performance metrics are identified and evaluated for reducing the overall runtime of the algorithm. We show how actively steering the perception system increases the localization accuracy compared with traditional fixed‐sensor configurations.     

Roadmap Coverage Improvement Using a Node Rearrangement Method for Mobile Robot Path Planning

Abstract

This paper proposes a method to efficiently abstract the traversable regions of a bounded two-dimensional environment using the probabilistic roadmap (PRM) to plan the path for a mobile robot. The proposed method uses centroidal Voronoi tessellation to autonomously rearrange the positions of initially randomly generated nodes. The PRM using the rearranged nodes covers most of the traversable regions in the environment and regularly divides them. The rearranged roadmap reduces the search space of a graph search algorithm and helps to promptly answer arbitrary queries in the environment. The mobile robot path planner using the proposed rearranged roadmap was integrated with a local planner that considers the kinematic properties of a mobile robot, and the efficiency and the safety of the paths were verified by simulation.     

Multirepresentation,Multiheuristic A* search‐based motion planning for a free‐floating underwater vehicle‐manipulator system in unknown environment

A key challenge in autonomous mobile manipulation is the ability to determine, in real time, how to safely execute complex tasks when placed in unknown or changing world. Addressing this issue for Intervention Autonomous Underwater Vehicles (I‐AUVs), operating in potentially unstructured environment is becoming essential. Our research focuses on using motion planning to increase the I‐AUVs autonomy, and on addressing three major challenges: (a) producing consistent deterministic trajectories, (b) addressing the high dimensionality of the system and its impact on the real‐time response, and (c) coordinating the motion between the floating vehicle and the arm. The latter challenge is of high importance to achieve the accuracy required for manipulation, especially considering the floating nature of the AUV and the control challenges that come with it. In this study, for the first time, we demonstrate experimental results performing manipulation in unknown environment. The Multirepresentation, Multiheuristic A* (MR‐MHA*) search‐based planner, previously tested only in simulation and in a known a priori environment, is now extended to control Girona500 I‐AUV performing a Valve‐Turning intervention in a water tank. To this aim, the AUV was upgraded with an in‐house‐developed laser scanner to gather three‐dimensional (3D) point clouds for building, in real time, an occupancy grid map (octomap) of the environment. The MR‐MHA* motion planner used this octomap to plan, in real time, collision‐free trajectories. To achieve the accuracy required to complete the task, a vision‐based navigation method was employed. In addition, to reinforce the safety, accounting for the localization uncertainty, a cost function was introduced to keep minimum clearance in the planning. Moreover a visual‐servoing method had to be implemented to complete the last step of the manipulation with the desired accuracy. Lastly, we further analyzed the approach performance from both loose‐coupling and clearance perspectives. Our results show the success and efficiency of the approach to meet the desired behavior, as well as the ability to adapt to unknown environments.     

Anticipated velocity based guidance strategy for wheeled mobile evader amidst stationary and moving obstacles in bounded environment

This paper is concerned with a class of pursuit‐evasion game problems amidst stationary and moving obstacles in a bounded environment. We concentrate on evader's strategy taking into account the following challenges: (i) pursuer and evader are nonholonomic wheeled mobile robots and the evader is slower than the pursuer; (ii) pursuer follows a proportional navigation law; and (iii) geometry of the environment is not known to the players, a priori. We propose an efficient evader‐centric anticipated velocity based guidance strategy. Pursuer's trajectory is anticipated at each step by the evader using quadratic polynomial interpolation. The aim of the evader is to escape interception with the pursuer for maximum possible time. To deal with static obstacles, a technique based on a well‐known tangent bug algorithm is presented. While dealing with dynamic obstacles, a recently introduced reciprocal orientation method is employed to avoid collision in situations when the dynamic obstacle also cooperates in the process. In case dynamic obstacles do not participate in the process of collision avoidance, a well‐known velocity obstacle method is employed for planning safe collision‐free paths. Efficiency of the proposed algorithms is analyzed with respect to the interception time and the distance traveled by the players. Copyright © 2014 John Wiley & Sons, Ltd.     

A decoupled designing approach for sampling consensus of multi‐agent systems

This paper introduces the motion‐planning approaches to solve the distributed consensus problems via sampling measurements. First, for first‐order multiagent systems, a class of sampled‐data–based algorithms are developed with arbitrary sampling periods, which solve the asymptotic consensus problem under both directed fixed and random switching topologies. Then, a new kind of distributed consensus algorithms is designed based on sampling measurements for second‐order multiagent systems. Under both the directed fixed and periodical switching topologies, asymptotic consensus problems of second‐order multiagent systems can be solved by using the proposed algorithms. Compared with existing continuous‐time consensus algorithms, one of remarkable advantages of proposed algorithms is that the sampling periods, communication topologies, and control gains are decoupled and can be separately designed, which relaxes many restrictions in controller designs. Finally, some numerical examples are given to illustrate the effectiveness of the analytical results.     

Fuzzy Logic Based Behavior Fusion for Navigation of an Intelligent Mobile Robot

This paper presents a new method for behavior fusion control of a mobile robot in uncertain environments.Using behavior fusion by fuzzy logic,a mobile robot is able to directly execute its motion according to range information about environments,acquired by ultrasonic sensors,without the need for trajectory planning.Based on low-level behavior control,an efficient strategy for integrating high-level global planning for robot motion can be formulated,since,in most applications,some information on environments is prior knowledge.A global planner,therefore,only to generate some subgoal positions rather than exact geometric paths.Because such subgoals can be easily removed from or added into the plannes,this strategy reduces computational time for global planning and is flexible for replanning in dynamic environments.Simulation results demonstrate that the proposed strategy can be applied to robot motion in complex and dynamic environments.     

A configuration deactivation algorithm for boosting probabilistic roadmap planning of robots

We present a method to improve the execution time used to build the roadmap in probabilistic roadmap planners. Our method intelligently deactivates some of the configurations during the learning phase and allows the planner to concentrate on those configurations that are most likely going to be useful when building the roadmap. The method can be used with many of the existing sampling algorithms. We ran tests with four simulated robot problems typical in robotics literature. The sampling methods applied were purely random, using Halton numbers, Gaussian distribution, and bridge test technique. In our tests, the deactivation method clearly improved the execution times. Compared with pure random selections, the deactivation method also significantly decreased the size of the roadmap, which is a useful property to simplify roadmap planning tasks.     

Vision‐based control architecture for human–robot hand‐over applications

Human–robot collaboration will be an essential part of the production processes in the factories of tomorrow. In this paper, a human–robot hand‐over control strategy is presented. Human and robot can be both giver and receiver. A path‐planning algorithm drives the robotic manipulator towards the hand of the human and permits to adapt the pose of the tool center point of the robot to the pose of the hand of the human worker. The movements of the operator are acquired with a multi 3D‐sensors setup so to avoid any possible occlusion related to the presence of the robot or other dynamic obstacles. Estimation of the predicted position of the hand is performed to reduce the waiting time of the operator during the hand‐over task. The hardware setup is described, and the results of experimental tests, conducted to verify the effectiveness of the control strategy, are presented and discussed.     

Gaussian sampling of lattices for cryptographic applications

Gaussian sampling is the major class of algorithms for solving the close vector problem(CVP)of lattices.In this paper we present a novel Gaussian sampling algorithm,which has the same cryptographic applications with original Gaussian sampling algorithms.Our novel Gaussian sampling algorithm has smaller deviations,meaning smaller space sizes of lattice based public-key ciphers.The shape of our novel algorithm is almost repeated implementations of original algorithm,with random repeating times.Major result is that the deviation can be reduced to 0.64～0.75 of that of original Gaussian sampling algorithm without clearly increasing the average time cost.     

On generating the motion of industrial robot manipulators

In this study, an intelligent search algorithm is proposed to define the path that leads to the desired position and orientation of an industrial robot׳s manipulator end effector. The search algorithm gradually approaches the desired configuration by selecting and evaluating a number of alternative robot׳s configurations. A grid of the robot׳s alternative configurations is constructed using a set of parameters which are reducing the search space to minimize the computational time. In the evaluation of the alternatives, multiple criteria are used in order for the different requirements to be fulfilled. The alternative configurations are generated with emphasis being given to the robot׳s joints that mainly affect the position of the end effector. Grid resolution and size parameters are set on the basis of the desired output. High resolution is used for a smooth path and lower for a rough estimation, by providing only a number of the intermediate points to the goal position. The path derived is a series of robot configurations. This method provides an inexperienced robot programmer with flexibility to generate automatically a robotic path that would fulfill the desired criteria without having to record intermediate points to the goal position.     

在未知环境中基于模糊逻辑的移动机器人行为控制

本文介绍了一种在未知环境中基于模糊逻辑的移动机器人行为控制方法．传统的行为控制方法存在两个弱点：①行为不易描述；②多个行为之间的冲突和竞争难以协调．这篇文章的主要思想是将模糊逻辑控制与行为控制相结合致使这两个问题得到有效的解决．仿真实验结果表明：所提的方法通过多个行为如避障边沿行走和目标导向的融合，能够有效地对机器人在复杂和未知环境中导航．另外，该方法还适用于多传感器的融合与集成．     

Survey of advanced general-purpose software for robot manipulators

This paper surveys the main trends of the development of advanced general-purpose software for robot manipulators. It consists of three main sections: robot planning, robot programming, and robot vision.     

Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's tactile sensor. This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.Supported in part by the National Science Foundation Grant DMC-8519542.     

仿人机器人足迹规划建模及算法实现

足迹规划是仿人机器人运动规划领域的一个新思想.本文建立了仿人机器人足迹规划的模型,并通过构建启发式成本函数,利用A*算法予以实现.针对复杂多障碍物环境,特别提出了基于可变落地足迹数量的复合足迹转换模型的方法.仿真实验证明了规划模型和算法的有效性和完备性,规划效果达到仿人机器人在线运动规划的要求.同时,数值实验也证明了在复杂多障碍物环境下复合足迹转换模型的必要性和优越性.     

基于红外传感皮肤的多关节机器人自主运动方法研究

本文研究了障碍环境下多关节机器人自主实时避碰运动理论、技术与方法. 研制的新型红外传感皮肤, 可以为多关节机器人提供所需要的周围环境信息. 针对非结构化环境下的多关节机器人实时避障问题, 提出了一种未知环境下的机器人模糊路径实时规划新方法. 实验结果表明: 基于研制的红外传感皮肤和模糊运动规划算法, 多关节机器人可以在未知或时变环境下自主工作.     

Selection of Strategies for Collision-free Motion in Multi-manipulator Systems

Strategy-based path planning was introduced by the authors as a way to give robotic manipulators some sort of reactive behaviour in dynamic and unpredictable environments. This approach is based on making robots react to moving obstacles using a restricted subset of the configuration space, and on using an off-line pre-planning stage to choose the restricted subset. In this paper, strategy-based path planning is applied and explored, focusing our attention on the off-line stage. It is applied to the joint motion of two and three robots that perform pick and place tasks sharing common working areas.     

期望时间下的移动机器人目标搜索路径规划

不确定环境下移动机器人目标搜索问题中,目标在观测点被发现的概率常被设为理想的均匀分布,其路径优化指标通常为最短距离,但最短距离路径不等同于最优期望时间路径.针对此问题,本文提出了一种以期望时间为优化指标的概率多目标搜索算法.针对观测点的访问顺序不同会导致期望时间不同的现象,采用分层式路径优化策略.首先,构造一个新的非均匀目标分布概率测算模型;然后,在上层序列规划中,采用改进的改良圈算法生成期望观测点序列;最后,在下层特征地图的观测点间可行路径规划中,采用改进的快速随机生成树算法(GBC–RRT).实验结果表明:本文所提方法可显著缩短移动机器人目标搜索的期望时间,且能在目标不确定、非均匀分布的工作空间中得到最优期望时间的搜索路径.