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.     

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.     

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.     

Enhancing Randomized Motion Planners: Exploring with Haptic Hints

In this paper, we investigate methods for enabling a human operator and an automatic motion planner to cooperatively solve a motion planning query. Our work is motivated by our experience that automatic motion planners sometimes fail due to the difficulty of discovering critical configurations of the robot that are often naturally apparent to a human observer.Our goal is to develop techniques by which the automatic planner can utilize (easily generated) user-input, and determine natural ways to inform the user of the progress made by the motion planner. We show that simple randomized techniques inspired by probabilistic roadmap methods are quite useful for transforming approximate, user-generated paths into collision-free paths, and describe an iterative transformation method which enables one to transform a solution for an easier version of the problem into a solution for the original problem. We also illustrate that simple visualization techniques can provide meaningful representations of the planner's progress in a 6-dimensional C-space. We illustrate the utility of our methods on difficult problems involving complex 3D CAD Models.     

动态调整操作序列的多机器人无碰运动规划

针对共享工作空间的多台机器人,提出了一种协调无碰运动规划方法．作为离线规划的解耦法,该方法主要分为2个阶段．第1阶段,根据任务需求在不考虑机器人间相互冲突的情况下,通过概率路径地图（PRM）法规划出各机器人与静态环境的无碰路径;第2阶段,把机器人的路径描述成连续的位形序列后构造系统的状态空间,形象地把所需解决的问题转换成高维状态空间中的连续路径搜索问题．在此基础上,提出了多机器人的避碰策略、运动序列优先级的动态调整方法和改进的A^*算法,实现了多机器人系统无碰协调运动规划．通过2个仿真案例验证了该方法的可行性及有效性．结果表明,所提方法能快速、有效地得到多机器人协调无碰运动路径．     

基于改进概率地图的无人机实时避障研究

基于空间点采样的概率地图方法能够很好地表示出自由空间的连通性,该方法已在路径规划领域得到了成功的应用。但是,由于在由已得到的采样点基础上构造连通图时,需要检查图的边是否与障碍物发生碰撞,即进行相交检验,限制了概率地图的构造速度,难以满足在实际应用中的实时性要求。针对无人机路径规划问题,以等高线地图作为任务空间,提出了一种新的采样模型,在该模型框架下,依据适当的规则构造临近点集,便可以避免相交检验,提高了路径规划速度。     

Path planning for a manipulator with constraints on orientation

This paper discusses the work undertaken at the U.K. National Advanced Robotics Research Centre in the area of path planning. Experiments have been undertaken with the Best First Planner (BFP) and Random Path Planner (RPP) algorithms developed at Stanford University by Barraquand and Latombe. These look particularly suitable for solving a wide range of motion planning problems and for providing the basic mechanism for path planning in an advanced robotic architecture. From this basic mechanism higher level functional primitives have been developed to enable paths to be planned with a pre-defined orientation of the end effector at the goal location or maintaining an orientation throughout the whole path. These functions are achieved through placing additional constraints on the search through configuration space and modifying the workspace potential.     

On Intelligent Robot Motion Planning via Learning

Automatic motion planning is one of the basic modules that are needed to increase robot intelligence and usability. Unfortunately, the inherent complexity of motion planning has rendered traditional search algorithms incapable of solving every problem in real time. To circumvent this difficulty, we explore the alternative of allowing human operators to participate in the problem solving process. By having the human operator teach during difficult motion planning episodes, the robot should be able to learn and improve its own motion planning capability and gradually reduce its reliance on the human operator. In this paper, we present such a learning framework in which both human and robot can cooperate to achieve real-time automatic motion planning. To enable a deeper understanding of the framework in terms of performance, we present it as a simple learning algorithm and provide theoretical analysis of its behavior. In particular, we characterize the situations in which learning is useful, and provide quantitative bounds to predict the necessary training time and the maximum achievable speedup in planning time.     

航迹规划的一种路线图方法

该文提出一种飞行路线图上的实时三维航迹规划方法,将航迹规划过程分成两个阶段:学习阶段和查询阶段。在学习阶段,环境信息结合在路线图中,在查询阶段,采用SAS算法搜索飞行路线图,实时获得三维可行航迹。构图和航迹搜索过程中分阶段满足飞行器约束条件。通过更新路线图中边的代价,实现了动态环境中飞行器的实时规划。     

基于改进的随机路径图及和声算法的舰船航线规划

针对海上航行中障碍物躲避问题,提出改进的随机路径图及和声算法为舰船进行航线规划.该算法首先利用改进的随机路径图,在障碍物边缘、起点与终点连线等关键区域进行节点设置及扩充,根据舰船及障碍物运动特征,分阶段在海图上设置节点并连接,利用较少的节点生成完备的路径网络图,基于此选择节点生成初始全局航线;其次利用改进的和声算法对航线进行优化,障碍物的运动特性导致解空间为复杂的多峰形态,为避免节点位置变动导致新生成航线不可行,设置限定条件,仅对满足要求的航线利用航线交叉、消除节点、微调等策略进行优化.实验结果表明,相较对比算法,所提算法能够有效生成更高质量的全局航线,且在优化过程中生成的不可行航线数量远低于其余几种算法,具有更高的可靠性及稳定性.     

车型移动机器人的SPRM路径规划方法

研究车型移动机器人的路径规划问题,提出一种用局部规则路图结合随机路图,辅助建立全局复合路图的环境建模方法. 在此基础上进行路径规划,提高了在障碍物附近产生的局部路径的质量,减少了由于频繁地执行避碰校验所造成的时间消耗,并解决了可行空间丢失的问题. 仿真实验验证了这种方法在车形移动机器人路径规划应用中的有效性.     

基于改进概率路标法的虚拟吊装路径规划

针对高维空间虚拟吊装路径规划困难的问题,利用改进概率路标法对吊装路径进行规划.在考虑吊物摆动的基础上,建立起吊装系统的位姿空间模型;采用均匀随机采样策略使吊装位姿点在位姿空间中均匀分布,改进邻近节点选择方法限制相邻位姿节点的自由度变化数目,建立可行吊装路径概率路线图;以吊装路径最短、运动形式变化最少为优化目标,找出符合吊装操作的最优路径;以此为依据来对操作者的吊装过程进行指导及评价.实验结果表明,该算法能在复杂的虚拟吊装环境中找出一条最优路径并能很好地解决多自由度路径规划问题.