Global Formulation and Motion Planning for a Sphere Rolling on a Smooth Surface

This paper studies the motion planning problem for a rolling sphere on an arbitrary smooth manifold embedded in ?³. The sphere is allowed to roll on the surface without slipping or twisting. A mathematical model describing the kinematics of the sphere is developed in a geometric form so that the model is globally defined without singularities or ambiguities. An algorithm for constructing a path between specified initial and final configurations is presented. The algorithm utilizes the nonholonomic nature of the system. The theoretical results are specialized for two specific surfaces defined in ?³, namely a flat surface and the surface of a stationary sphere.     

Rolling Contact Motion Generation and Control of Robotic Fingers

Dexterity in human hand is connected with the fingertip rolling ability. In this work we consider rolling motion of spherical robotic fingertips as one of the control objectives together with the set point position control and force trajectory tracking. The generation of a rolling motion trajectory is proposed and a control solution is designed which achieves prescribed transient and steady state tracking behavior. The proposed control law is structurally and computationally simple and does not utilize the dynamics of the robot model or its approximation. A simulation of a five degrees of freedom robot show excellent contact rolling performance even at cases of adverse friction conditions while alternative controllers lead to contact sliding. Experiments with a KUKA LWR4 + are performed to validate the proposed method.     

Stabilization of Planar Collective Motion With Limited Communication

This paper proposes a design methodology to stabilize relative equilibria in a model of identical, steered particles moving in the plane at unit speed. Relative equilibria either correspond to parallel motion of all particles with fixed relative spacing or to circular motion of all particles around the same circle. Particles exchange relative information according to a communication graph that can be undirected or directed and time-invariant or time-varying. The emphasis of this paper is to show how previous results assuming all-to-all communication can be extended to a general communication framework.     

Speed Planning for a Maneuvering Motion

Collision-free motion among moving objects is an on-going research topic. Based on the concept of a modified path-velocity decomposition and application of the interface propagation method, a strategy for trajectory planning is proposed in this paper. In the proposed method, the global navigation paths for robots are assumed to have already been planned without any static obstacle crossing their paths. Each subtask along the global path of each controlled object contains a desired goal position and desired arrival time for reaching the position. Based on the information about each subtask, Space/Time Graphs (STGs) for the robots are created. By shifting the speed path from corresponding forbidden regions on the STG, potential collisions can be avoided. Optimal speed paths with least velocity alterations for controllable objects are derived automatically by applying the interface propagation method in the STGs. The applicability of the proposed approach is demonstrated and the results show that controllable and uncontrollable moving objects can work together in a shared environment by avoiding collisions.     

Optimal Mesh Algorithms for the Voronoi Diagram of Line Segments and Motion Planning in the Plane

The motion planning problem of an object with two degrees of freedom moving in the plane can be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional mobile object B with two degrees of freedom, determine if it is possible to move B from a start position to a final position while avoiding the obstacles. If so, plan a path for such a motion. Techniques from computational geometry have been used to develop exact algorithms for this fundamental case of motion planning. In this paper we obtain optimal mesh implementations of two different methods for planning motion in the plane. We do this by first presenting optimal mesh algorithms for some geometric problems that, in addition to being important substeps in motion planning, have numerous independent applications in computational geometry. In particular, we first show that the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane can be constructed in O(√ n) time on a √ n × √ n mesh, which is optimal for the mesh. Consequently, we obtain an optimal mesh implementation of the sequential motion planning algorithm described by Ó′Dúlainy and Yap (J. Algorithms 6 (1985), 104-111); in other words, given a disc B and a polygonal obstacle set of size n, we can plan a path (if it exists) for the motion of B from a start position to a final position in O(√ n) time on a mesh of size n. We also show that the shortest path motion between a start position and a final position for a convex object B (of constant size) moving among convex polygonal obstacles of total size n can be found in O(n) time on an n × n mesh, which is worst-case optimal.     

Motion Planning for Haptic Guidance

Haptic devices allow a user to feel either reaction forces from virtual interactions or reaction forces reflected from a remote site during a bilateral teleoperation task. Also, guiding forces can be exerted to train the user in the performance of a virtual task or to assist him/her to safely teleoperate a robot. The generation of guiding forces relies on the existence of a motion plan that provides the direction to be followed to reach the goal from any free configuration of the configuration space (-space). This paper proposes a method to obtain such a plan that interleaves a sampling-based exploration of -space with an efficient computation of harmonic functions. A deterministic sampling sequence (with a bias based on harmonic function values) is used to obtain a hierarchical cell decomposition model of -space. A harmonic function is iteratively computed over the partially known model using a novel approach. The harmonic function is the navigation function used as motion plan. The approach has been implemented in a planner (called the Kautham planner) that, given an initial and a goal configuration, provides: (a) a channel of cells connecting the cell that contains the initial configuration with the cell that contains the goal configuration; (b) two harmonic functions over the whole -space, one that guides motions towards the channel and another that guides motions within the channel towards the goal; and (c) a path computed over a roadmap built with the free samples of the channel. The harmonic functions and the solution path are then used to generate the guiding forces for the haptic device. The planning approach is illustrated with examples on 2D and 3D workspaces. This work was partially supported by the CICYT projects DPI2005-00112 and DPI2007-63665.     

A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance

A fundamental aspect of autonomous vehicle guidance is planning trajectories. Historically, two fields have contributed to trajectory or motion planning methods: robotics and dynamics and control. The former typically have a stronger focus on computational issues and real-time robot control, while the latter emphasize the dynamic behavior and more specific aspects of trajectory performance. Guidance for Unmanned Aerial Vehicles (UAVs), including fixed- and rotary-wing aircraft, involves significant differences from most traditionally defined mobile and manipulator robots. Qualities characteristic to UAVs include non-trivial dynamics, three-dimensional environments, disturbed operating conditions, and high levels of uncertainty in state knowledge. Otherwise, UAV guidance shares qualities with typical robotic motion planning problems, including partial knowledge of the environment and tasks that can range from basic goal interception, which can be precisely specified, to more general tasks like surveillance and reconnaissance, which are harder to specify. These basic planning problems involve continual interaction with the environment. The purpose of this paper is to provide an overview of existing motion planning algorithms while adding perspectives and practical examples from UAV guidance approaches.     

运动估计快速块匹配算法

基于块的运动估计是视频压缩国际标准中广泛采用的关键技术。在对目前运动估计快速块匹配算法研究的基础上,描述了运动估计的原理;揭示了在图像质量、搜索速度和压缩码率等方面提高算法效率时存在的3类主要问题：初始搜索点的选择、匹配准则和搜索策略;分别阐述了目前常用的解决这3类问题的方法,并进行了比较和分析;提出了对运动估计算法的一些展望。     

基于自适应Kalman预测器的运动估计算法

利用图像序列估计目标运动速度是机器人视觉中的一项重要研究内容。它应用在机器人操作、导航、视觉跟踪等多项领域中。这些应用一般均要求运动估计算法具有较好的实时性和抗噪能力。卡尔曼滤波器和预测器正符合上述要求。该文基于运动图像的仿射模型,探讨从序列图像中预测目标三维平动速度的卡尔曼预测算法。首先建立运动目标的“当前”统计模型,然后根据运动图像的仿射模型找出图像运动参数与目标三维速度间的关系(图像运动参数由目标图像的几何矩计算获得)。最后结合自适应卡尔曼滤波和卡尔曼一步预测算法设计自适应卡尔曼一步预测器。为减轻预测器的发散性,对初始状态进行估计。仿真结果表明,基于“当前”统计模型和运动图像仿射模型设计出的自适应卡尔曼一步预测器具有较高的精度。     

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.     

Analytic Path Planning Algorithms for Bipedal Robots without a Trunk

This paper presents new path planning algorithms for bipedal robots without a trunk. The proposed methods can be regarded as an extension to the concept of the inverted pendulum mode (IPM). Further, they fill the gap between the IPM and concepts, based on general dynamic modeling. The swing leg motion is adjusted almost arbitrarily and the torso motion is calculated analytically in order to ensure stability. The proposed methods show a higher gait stability compared to literature approaches. This improvement is verified by measurement of the foot reaction forces during the walk of the existing biped BARt-UH and simulations.     

一类整数性目标规划的遗传算法

本文给出了以惩罚函数法将约束优化问题转化为无约束优化问题的通用算法,提出了将遗传算法和惩罚函数法相结合用于求解整数性目标规划问题的具体方法。计算机数值仿真结果表明了该方法的有效性。     

Dynamic Motion Planning using a distributed representation

Methods for dynamic motion planning are presented which take into account not only geometric environmental constraints but also physical constraints on motion. The approach uses a distributed representation which allows parallel implementation of the using a cellular strength-diffusion method in the search for the motion in space-time. We consider three cases: (1) no knowledge of the motion of the obstacles is assumed so that the planning is purely reactive; (2) full knowledge of the moving obstacles is available so that the planner can deliver an optimal motion; and (3) an interleaved algorithm in which the ability to predict a short time ahead (based on an assumption of simple linear motion of the obstacles) is exploited. This last algorithm emphasizes the importance of the interaction between the planner and the environment via sensors. We conclude that to plan motion in a dynamic environment in which uncertainties abound, the only sensible strategy is to constantly sense the world and plan the motion accordingly.The experimental work reported here was carried out while the authors were at Department of Computer Science, Queen Mary and Westfield College, University of London.     

多点焊接机器人最优运动规划策略与算法研究

利用遗传算法寻找多点焊接机器人的最优运动规划的方法。第一步应用遗传算法对多点焊接工业机器人进行全局路径最优规划,确定机器人操作手终端遍历所有目标点的最短路径;然后在相邻目标点之间应用遗传算法进行关节空间的轨迹规划,寻找时间最短的最优轨迹。实验结果表明缩短了运行时间,提高了机器人的工作效率,可见方法的可行性和先进性。     

Contact Friction Compensation for Robots Using Genetic Learning Algorithms

In this paper, the issues of contact friction compensation for constrained robots are presented. The proposed design consists of two loops. The inner loop is for the inverse dynamics control which linearizes the system by canceling nonlinear dynamics, while the outer loop is for friction compensation. Although various models of friction have been proposed in many engineering applications, frictional force can be modeled by the Coulomb friction plus the viscous force. Based on such a model, an on-line genetic algorithm is proposed to learn the friction coefficients for friction model. The friction compensation control input is also implemented in terms of the friction coefficients to cancel the effect of unknown friction. By the guidance of the fitness function, the genetic learning algorithm searches for the best-fit value in a way like the natural surviving laws. Simulation results demonstrate that the proposed on-line genetic algorithm can achieve good friction compensation even under the conditions of measurement noise and system uncertainty. Moreover, the proposed control scheme is also found to be feasible for friction compensation of friction model with Stribeck effect and position-dependent friction model.     

Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we first study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. We then show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. Finally we study maximal series-parallel graphs. Here we show that O(1)-sided rectilinear polygons are not possible unless we allow holes, but 6-sided polygons can be achieved with arbitrarily small holes.     

A Fast Approach for Robot Motion Planning

This paper describes a new approach to robot motion planning that combines the end-point motion planning with joint trajectory planning for collision avoidance of the links. Local and global methods are proposed for end-point motion planning. The joint trajectory planning is achieved through a pseudoinverse kinematic formulation of the problem. This approach enables collision avoidance of the links by a fast null-space vector computation. The power of the proposed planner derives from: its speed; the good properties of the potential function for end-point motion planning; and from the simultaneous avoidance of the links collision, kinematic singularities, and local minima of the potential function. The planner is not defined over computationally expensive configuration space and can be applied for real-time applications. The planner shows to be faster than many previous planners and can be applied to robots with many degrees of freedom. The effectiveness of the proposed local and global planning methods as well as the general robot motion planning approach have been experimented using the computer-simulated robots. Some of the simulation results are included in this paper.     

Homotopic Roadmap Generation for Robot Motion Planning

Two robot paths are said to be in the same homotopic group if one can be obtained from the other by multiple small deformations. Knowledge of robot homotopic groups gives information regarding the obstacle structure and enables timely computation of optimal path. Making a roadmap which misses out on a single homotopic group in such approaches may lead to sub-optimal decisions. E.g. one may prefer to go through a very narrow corridor if that reduces the path length significantly, but not if the resulting path has too many such narrow segments. Similarly knowledge of homotopic groups may enable distribution and scheduling of robots across homotopic groups for decentralized planning of multiple robots. For an unstructured robot environment, sampling based approaches give an insight into homotopic groups. The aim of the work is to make a homotopy conscious Probabilistic Roadmap such that the roadmap is capable of generating paths corresponding to as many homotopic groups as possible. Experimental results confirm that the proposed approach gives the best results as compared to the other sampling techniques subject to the test scenarios run.     

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.     

智能算法在机器人路径规划中的应用研究

移动机器人技术研究中的一个重要领域是路径规划技术。综述了智能算法在移动机器人路径规划技术中的发展现状,指出了各种方法的优点与不足。最后对移动机器人路径规划技术的发展趋势进行了展望。