A grasp‐based motion planning algorithm for character animation

The design of autonomous characters capable of planning their own motions continues to be a challenge for computer animation. We present a novel kinematic motion‐planning algorithm for character animation which addresses some of the outstanding problems. The problem domain for our algorithm is as follows: given a constrained environment with designated handholds and footholds, plan a motion through this space towards some desired goal. Our algorithm is based on a stochastic search procedure which is guided by a combination of geometric constraints, posture heuristics, and distance‐to‐goal metrics. The method provides a single framework for the use of multiple modes of locomotion in planning motions through these constrained, unstructured environments. We illustrate our results with demonstrations of a human character using walking, swinging, climbing, and crawling in order to navigate through various obstacle courses. Copyright © 2001 John Wiley & Sons, Ltd.     

Model predictive control of axial dispersion chemical reactor

This paper discusses the development of model predictive control algorithm which accounts for the input and state constraints applied to the parabolic partial differential equations (PDEs) system describing the axial dispersion chemical reactor. Spatially varying terms arising from the nonlinear PDEs model are accounted for in model development. Finite-dimensional modal representation capturing the dominant dynamics of the PDEs system is derived for controller design through Galerkin's method and modal decomposition technique. Tustin's discretization and Cayley transform are used to obtain infinite-dimensional discrete-time dynamic modal representations which are used in subsequent constrained controller design. The proposed discrete-time constrained model predictive control synthesis is constructed in a way that the objective function is only based on the low-order modal representation of the PDEs system, while higher-order modes are utilized only in the constraints of the PDEs state. Finally, the MPC formulations are successfully applied, via simulation results, to the PDEs system with input and state constraints.     

Adjustable Constrained Soft-Tissue Dynamics

Physically based simulation is often combined with geometric mesh animation to add realistic soft-body dynamics to virtual characters. This is commonly done using constraint-based simulation whereby a soft-tissue simulation is constrained to geometric animation of a subpart (or otherwise proxy representation) of the character. We observe that standard constraint-based simulation suffers from an important flaw that limits the expressiveness of soft-body dynamics. Namely, under correct physics, the frequency and amplitude of soft-tissue dynamics arising from constraints (“inertial amplitude”) are coupled, and cannot be adjusted independently merely by adjusting the material properties of the model. This means that the space of physically based simulations is inherently limited and cannot capture all effects typically expected by computer animators. For example, animators need the ability to adjust the frequency, inertial amplitude, gravity sag and damping properties of the virtual character, independently from each other, as these are the primary visual characteristics of the soft-tissue dynamics. We demonstrate that independence can be achieved by transforming the equations of motion into a non-inertial reference coordinate frame, then scaling the resulting inertial forces, and then converting the equations of motion back to the inertial frame. Such scaling of inertia makes it possible for the animator to set the character's inertial amplitude independently from frequency. We also provide exact controls for the amount of character's gravity sag, and the damping properties. In our examples, we use linear blend skinning and pose-space deformation for geometric mesh animation, and the Finite Element Method for soft-body constrained simulation; but our idea of scaling inertial forces is general and applicable to other animation and simulation methods. We demonstrate our technique on several character examples.     

视网膜显微手术机器人的约束运动规划及仿真

为了辅助医生完成视网膜显微手术中精细的手术操作,过滤颤抖、提高精度和稳定性,提出一种生成手术机器人空间运动约束的方法——虚拟固定器（VF）．首先,通过引入手术环境约束和任务约束,采用加权、线性化的多目标约束条件,根据用户的输入设置目标函数,构造了视网膜显微手术中所需的6个虚拟固定器基元．在此基础上,以远程运动中心虚拟约束（RCM VF）的生成为例,通过约束运动基元的组合,推导了复杂约束运动的实现方法．各约束运动基元算法及复杂约束运动算法的仿真结果表明,手术器械可以按照虚拟固定器的定义实现特定的约束运动．最后,在各手术步骤中引入约束运动基元的基础上,在乒乓球和离体猪眼球上进行了手术操作实验,证明了在该虚拟固定器的引导下,视网膜机器人可以完成高难度的手术操作,验证了所提出算法的合理性和有效性．     

Real-time navigation using randomized kinodynamic planning with arrival time field

In this paper, we propose a novel path planning algorithm for a mobile robot in dynamic and cluttered environments with kinodynamic constraints. We compute the arrival time field as a bias which gives larger weights for shorter and safer paths toward a goal. We then implement a randomized path search guided by the arrival time field for building the path considering kinematic and dynamic (kinodynamic) constraints of an actual robot. We also consider path quality by adding heuristic constraints on the randomized path search, such as reducing unstable movements of the robot by using a heading criterion. The path will be extracted by backtracking the nodes which reach the goal area to the root of the tree generated by the randomized search, and the motion from the very first node will be sent to the robot controller. We provide a brief comparison between our algorithm and other existing algorithms. Simulation and experimental results prove that our algorithm is fast and reliable to be implemented on the real robot and is able to handle kinodynamic problems effectively.     

Expressive Speech Animation Synthesis with Phoneme‐Level Controls

This paper presents a novel data‐driven expressive speech animation synthesis system with phoneme‐level controls. This system is based on a pre‐recorded facial motion capture database, where an actress was directed to recite a pre‐designed corpus with four facial expressions (neutral, happiness, anger and sadness). Given new phoneme‐aligned expressive speech and its emotion modifiers as inputs, a constrained dynamic programming algorithm is used to search for best‐matched captured motion clips from the processed facial motion database by minimizing a cost function. Users optionally specify ‘hard constraints’ (motion‐node constraints for expressing phoneme utterances) and ‘soft constraints’ (emotion modifiers) to guide this search process. We also introduce a phoneme–Isomap interface for visualizing and interacting phoneme clusters that are typically composed of thousands of facial motion capture frames. On top of this novel visualization interface, users can conveniently remove contaminated motion subsequences from a large facial motion dataset. Facial animation synthesis experiments and objective comparisons between synthesized facial motion and captured motion showed that this system is effective for producing realistic expressive speech animations.     

SO-MI: A surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems

This paper introduces a surrogate model based algorithm for computationally expensive mixed-integer black-box global optimization problems with both binary and non-binary integer variables that may have computationally expensive constraints. The goal is to find accurate solutions with relatively few function evaluations. A radial basis function surrogate model (response surface) is used to select candidates for integer and continuous decision variable points at which the computationally expensive objective and constraint functions are to be evaluated. In every iteration multiple new points are selected based on different methods, and the function evaluations are done in parallel. The algorithm converges to the global optimum almost surely. The performance of this new algorithm, SO-MI, is compared to a branch and bound algorithm for nonlinear problems, a genetic algorithm, and the NOMAD (Nonsmooth Optimization by Mesh Adaptive Direct Search) algorithm for mixed-integer problems on 16 test problems from the literature (constrained, unconstrained, unimodal and multimodal problems), as well as on two application problems arising from structural optimization, and three application problems from optimal reliability design. The numerical experiments show that SO-MI reaches significantly better results than the other algorithms when the number of function evaluations is very restricted (200–300 evaluations).     

A computational method for parameter optimization problems arising in control†

A parameter optimization procedure is presented for large-scale problems arising in linear control system design that include equality and inequality constraints. The procedure is based on a novel min—max algorithm for locating a constrained relative minimum without the use of penalty functions or slack variables. This algorithm is constructed from an auxiliary minimization problem with equality constraints. Inequality constraints then are introduced using the notion of an effective constraint. Typical problem formulations are discussed, and an extensive design example is presented.     

Occam algorithms for computing visual motion

The standard approach to computing motion relies on pixel correspondence. Computational schemes impose additional constraints, such as smoothness and continuity of the motion vector even though these are not directly related to pixel correspondence. This paper proposes an alternative to the multiple constraints approach. By drawing analogy with machine learning, motion is computed as a function that accurately predicts frames. The Occam-Razor principle suggests that among all functions that accurately predict the second frame from the first frame, the best predictor is the “simplest,” and simplicity can be rigorously defined in terms of encoding length. An implementation of a practical algorithm is described. Experiments with real video sequences verify the algorithm assumptions by showing that motion in typical sequences can be accurately described in terms of a few parameters. Our particular choice of predictors produces results that compare very favorably with other image flow algorithms in terms of accuracy and compactness. It may, however, be too constrained to enable accurate recovery of 3D motion and structure     

基于实时障碍物预测的机器人运动规划

本文给出了移动机器人的虚力导航和运动规划系统．这种方法结合最小方差估计算 法（L M S E）能有效地对机器人进行实时导航和避撞．在预测过程中,根据导航的不同阶 段和预测误差的变化情况,采用Fuzzy规则动态地调整误差函数中的权重,使预测过程尽可 能准确．导航算法的基本思想是首先通过预测算法来获得移动机器人的运动信息,然后虚力 系统根据预测信息决定机器人的未来运动,仿真结果表明该方法实时性好,能准确躲避障碍 物并且到达目标点．     

Genetic based fuzzy goal programming for multiobjective chance constrained programming problems with continuous random variables

Solution procedure consisting of fuzzy goal programming and stochastic simulation-based genetic algorithm is presented, in this article, to solve multiobjective chance constrained programming problems with continuous random variables in the objective functions and in chance constraints. The fuzzy goal programming formulation of the problem is developed first using the stochastic simulation-based genetic algorithm. Without deriving the deterministic equivalent, chance constraints are used within the genetic process and their feasibilities are checked by the stochastic simulation technique. The problem is then reduced to an ordinary chance constrained programming problem. Again using the stochastic simulation-based genetic algorithm, the highest membership value of each of the membership goal is achieved and thereby the most satisfactory solution is obtained. The proposed procedure is illustrated by a numerical example.     

Navigation with constraints for an autonomous mobile robot

This paper describes a navigation planning algorithm for a robot capable of autonomous navigation in a structured, partially known and dynamic environment. This algorithm is applied to a discrete workspace composed of a network of places and roads. The environment specification associates temporal constraints with any element of the network, and recharge or relocalisation possibilities with places. A mission specification associates several constraints with each navigation task (energy, time, position uncertainty and distance).

The algorithm computes an optimal path for each navigation task according to the optimization criterion and constraints. We introduce the notion of efficient path applied to a new best first search algorithm solving a multiple constraints problem. The path determination relies on a state representation adapted to deal with environment constraints. We then prove that the complexity chracteristics of our algorithm are similar to those of the A* algorithm.

The planner described in this paper has been implemented on a Spare station for a Robuter mobile platform equipped with ultra-sonic range sensors and an active stereo vision system. It was developed for the MITHRA family of autonomous surveillance robots as part of project EUREKA EU 110.     

Deformable Motion: Squeezing into Cluttered Environments

We present an interactive method that allows animated characters to navigate through cluttered environments. Our characters are equipped with a variety of motion skills to clear obstacles, narrow passages, and highly constrained environment features. Our control method incorporates a behavior model into well‐known, standard path planning algorithms. Our behavior model, called deformable motion, consists of a graph of motion capture fragments. The key idea of our approach is to add flexibility on motion fragments such that we can situate them into a cluttered environment via constraint‐based formulation. We demonstrate our deformable motion for realtime interactive navigation and global path planning in highly constrained virtual environments.     

渐进式约束扩展的机械臂运动规划算法

为了保证冗余机械臂带约束运动规划时的路径连续性,针对目前的直接插值和连续插值方法潜在的约束失效和路径失效问题,提出渐进式约束扩展的快速搜索随机树算法（PCE-RRT）。该算法在进行搜索树扩展时引入了一种渐进式约束扩展方法,该方法使用带有最近点信息的逆运动学计算策略,可以在保证任务约束的情况下迭代缩短最近点和扩展点的距离,让每一次扩展都能够保证搜索树的约束性和连续性。PCE-RRT可以使最终生成的搜索树很好地贴合于约束流形子空间,且树上任意两个相连节点都能满足连续条件。通过仿真实验对算法进行验证,实验结果表明该算法能够为机械臂带约束运动规划问题提供同时满足约束性和连续性条件的路径解。     

Distributed Constraint Force Approach for Coordination of Multiple Mobile Robots

A new approach to coordination of multiple mobile robots is presented in this paper. The approach relies on the notion of constraint forces which are used in the development of the dynamics of a system of constrained particles with inertia. A familiar class of dynamic, nonholonomic robots are considered. The goal is to design a distributed coordination control algorithm for each robot in the group to achieve, and maintain, a particular formation while ensuring navigation of the group. The theory of constraint forces is used to generate a stable control algorithm for each mobile robot that will achieve, and maintain, a given formation. The advantage of the proposed method is that the formation keeping forces (constraint forces) cancel only those applied forces which act against the constraints. Another feature of the proposed distributed control algorithm is that it allows to add/remove other mobile robots into/from the formation gracefully with simple modifications of the control input. Further, the algorithm is scalable. To corroborate the theoretical approach, simulation results on a group of six robots are shown and discussed.     

Robust control of mobile manipulators

A mobile manipulator is basically a manipulator mounted on a mobile vehicle. This arrangement has some advantages over stationary robots and mobile robots, such as the infinite workspace and the ability to avoid singularities. However, the control problem becomes a sophisticated one. This is due to the nonlinear and nonholonomic constraints governing the motion of the vehicle. Moreover, the dynamics of the manipulator and the vehicle are highly coupled; ground-surface irregularities, for example, affect the motion of the end effector kinematically and dynamically. A mobile manipulator is expected to pass through different environmental conditions, a fact which calls for a robust control scheme. Unfortunately, the robust control problem for nonholonomic systems is not well defined yet. Since the ultimate goal of control is to control the motion of the manipulator's end effector, it is proposed in this article to tackle the robustness issue by designing a manipulator decoupling controller. This controller aims at rejecting disturbances arising from the motion of the vehicle. © 1996 John Wiley & Sons, Inc.     

基于马尔可夫决策过程的群体动画运动轨迹生成

近些年来,群体动画在机器人学、电影、游戏等领域得到了广泛的研究和应用,但传统的群体动画技术均涉及复杂的运动规划或碰撞避免操作,计算效率较低.本文提出了一种基于马尔可夫决策过程（MDPs）的群体动画运动轨迹生成算法,该算法无需碰撞检测即可生成各智能体的无碰撞运动轨迹.同时本文还提出了一种改进的值迭代算法用于求解马尔可夫决策过程的状态-值,利用该算法在栅格环境中进行实验,结果表明该算法的计算效率明显高于使用欧氏距离作为启发式的值迭代算法和Dijkstra算法.利用本文提出的运动轨迹生成算法在三维（3D）动画场景中进行群体动画仿真实验,结果表明该算法可实现群体无碰撞地朝向目标运动,并具有多样性.     

Dynamics and Motion Planning of Trident Snake Robot

The trident snake robot is a mechanical device that serves as a demanding testbed for motion planning and control algorithms of constrained non-holonomic systems. This paper provides the equations of motion and addresses the motion planning problem of the trident snake with dynamics, equipped with either active joints (undulatory locomotion) or active wheels (wheeled locomotion). Thanks to a partial feedback linearization of the dynamics model, the motion planning problem basically reduces to a constrained kinematic motion planning. Two kinds of constraints have been taken into account, ensuring the regularity of the feedback and the collision avoidance between the robot’s arms and body. Following the guidelines of the endogenous configuration space approach, two Jacobian motion planning algorithms have been designed: the singularity robust Jacobian algorithm and the imbalanced Jacobian algorithm. Performance of these algorithms have been illustrated by computer simulations.     

Constrained motion planning of nonholonomic systems

This paper addresses the constrained motion planning problem for nonholonomic systems represented by driftless control systems with output. The problem consists in defining a control function driving the system output to a desirable point at a given time instant, whereas state and control variables remain over the control horizon within prescribed bounds. The state and control constraints are handled by extending the control system with a pair of state equations driven by the violation of constraints, and adding regularizing perturbations. For the regularized system a Jacobian motion planning algorithm is designed, called imbalanced. Solutions of example constrained motion planning problems for the rolling ball illustrate the theoretical concepts.     

Tactics‐Based Behavioural Planning for Goal‐Driven Rigid Body Control

Controlling rigid body dynamic simulations can pose a difficult challenge when constraints exist on the bodies' goal states and the sequence of intermediate states in the resulting animation. Manually adjusting individual rigid body control actions (forces and torques) can become a very labour‐intensive and non‐trivial task, especially if the domain includes a large number of bodies or if it requires complicated chains of inter‐body collisions to achieve the desired goal state. Furthermore, there are some interactive applications that rely on rigid body models where no control guidance by a human animator can be offered at runtime, such as video games. In this work, we present techniques to automatically generate intelligent control actions for rigid body simulations. We introduce sampling‐based motion planning methods that allow us to model goal‐driven behaviour through the use of non‐deterministic Tactics that consist of intelligent, sampling‐based control‐blocks, called Skills. We introduce and compare two variations of a Tactics‐driven planning algorithm, namely behavioural Kinodynamic Rapidly Exploring Random Trees (BK‐RRT) and Behavioural Kinodynamic Balanced Growth Trees (BK‐BGT). We show how our planner can be applied to automatically compute the control sequences for challenging physics‐based domains and that is scalable to solve control problems involving several hundred interacting bodies, each carrying unique goal constraints.