Computer graphics processing and selective visual display system – Computer graphics processing – Animation
Reexamination Certificate
1996-07-22
2001-05-08
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Animation
C345S420000
Reexamination Certificate
active
06229552
ABSTRACT:
INTRODUCTION
Mundane details keep us from vigorously attacking bigger ideas. This is the motivation for achieving task-level animation. From task-level descriptions, the animation of figures in a scene can be automatically computed by an appropriate motion planner. The animator can thereby concentrate on creating imaginative graphics, rather than laboring over the chore of moving these figures in a realistic and collision-free manner. We present herein our efforts toward realizing a subset of this ultimate goal—the automatic generation of human and robot arm motions to complete manipulation tasks.
Why study manipulation with arms? Human figures often play an integral role in computer animation. Consequently, there are arm motions and more specifically manipulation motions to animate. Another major application is in ergonomics. Since most products are utilized, assembled, maintained, and repaired by humans, and require for most cases some action by the human arms, by simulating and viewing these arm motions through computer graphics, one can evaluate the design of the product in terms of its usability. This will reduce the number of mock-up models needed to come up with the final design. Again, this would allow the designer more time towards creating high-quality products.
Unlike the motion of passive systems like falling objects or bouncing balls, the motion of human and robot arms for the purpose of manipulation are “motions within intentions.” The arms move not through some predictable trajectory due to the laws of physics but with the intention of completing some task. A planner is needed to determine how the arms must move to complete the task at hand. Although there has been previous work on simulating walking and lifting motions, this is the first attempt to automatically generate complex manipulation motions.
Our problem is thus to find a collision-free path for the arms to grasp and then carry some specified movable object from its initial location to a desired goal location. This problem is known as the multi-arm manipulation planning problem. A crucial difference, relative to more classical path planning, is that we must account for the ability of the arms to change their grasp of the object. Indeed, for some task the arms may need to ungrasp the object and regrasp it in a new manner to successfully complete the motion.
We present a new planner that solves this multi-arm manipulation problem. The planner needs as input the geometry of the environment, the initial and goal configurations of the movable object and arms, a set of potential grasps of the movable object and arms, a set of potential grasps of the movable object, and the inverse kinematics of the arms. With appropriate book-keeping, the animator would simply specify the goal configuration of the movable object (a task-level description) to generate the desired animation.
The planning approach is flexible in regards to the arm types that can be considered. The only restriction is that the arms must have an inverse kinematics algorithm. In this regard we have experimented with various human kinematic models designed to emulate the “naturalness” of human movement.
FIG. 1
is a series of snapshots along a manipulation path computed by our planner. Once the necessary models of the environment are read by the planner, the input from the animator is simply the goal location for the eye glasses, in this case getting placed on the head. Note, the planner found automatically that the arms must ungrasp and regrasp the glasses in order to complete the task.
DESCRIPTION OF RELATED WORK
The novel techniques described herein for planning motions with intentions for robot and human arm manipulation are related to several different areas of research. We roughly classify this related work into two categories: (i) manipulation planning, and (ii) animation of human figures.
Manipulation Planning
Research strictly addressing manipulation planning is fairly recent. It considers a single-body robot translating in a 2D workspace with multiple movable objects. The robot, the movable objects and obstacles are modelled as convex polygons. In order for the movable objects to reach their specified goal the robot must “grasp” and carry them there. Wilfong shows that planning a manipulation path to bring the movable objects to their specified goal locations is PSPACE-hard. When there is a single movable object, he proposes a complete algorithm that runs in O(n
3
log
2
n) time, where n is the total number of vertices of all the objects in the environment. An O(n
4
) algorithm has been proposed to solve a similar problem where the robot and the movable object are both discs and the obstacles are polygonal.
Our work differs from this other research in several ways. Rather than dealing with a single robot, we consider the case of multiple human and robot arms manipulating objects in a 3D workspace. In addition, whereas the previous work is more theoretical in nature, our focus is more on developing an effective approach to solving manipulation tasks of a complexity comparable to those encountered in everyday situations (e.g. picking and placing objects on a table).
Regrasping is a vital component in manipulation tasks. A method has been described for planning a sequence of regrasp operations by a single arm to change an initial grasp into a goal grasp. At every regrasp, the object is temporarily placed on a horizontal table in a stable position selected by the planner. We too need to plan regrasp operations. However, the only regrasping motions we consider avoid contact between the object and the environment; then necessarily involve multiple arms (e.g. both human arms).
Grasp planning is potentially an important component of manipulation planning. In our planner, grasps are selected from a finite predefined set. An improvement for the future will be to include the automatic computation of grasps.
Animation of Human Figures
Human gaits have been successfully simulated. For example, a hybrid approach has been proposed to the animation of human locomotion which combines goal-directed and dynamic motion control. Similarly, the gait of a virtual insect has been simulated by combining forward dynamic simulation and a biologically-based motion coordination mechanism. Control algorithms have been successfully applied to the animation of dynamic legged locomotion. While dynamic models and the use of motor coordination models have been successfully applied to a wide range of walking motions, such a strategy has yet to be discovered to encompass human arm motions.
For simulating the motion of human arms, there exists methods for specific tasks. For example, arm motions for lifting have been simulated based on human muscle models. These methods consider such factors as comfort level, perceived exertion, and strength.
There has been previous work in applying motion planning algorithms to animating human figures. A motion planning algorithm for anthropometric figures with many degrees of freedom has been presented. Essentially, a sequential search strategy is; used to find a collision-free motion of the figure to a specified goal configuration. However, manipulation or imposing naturalness on the motions are not considered.
The AnimNL project at the University of Pennsylvania is working to automate the generation of human figure movements from natural language instructions. This principally involves determining a sequence of primitive actions from a high-level description of the task. They utilize models to create realistic motions, however complex manipulation motions have hitherto not been considered.
SUMMARY OF THE INVENTION
The present invention comprises a motion planning system for automatically determining trajectories; for motion of objects within a simulated environment in response to high-level task descriptions. The motion planning system is further capable of automatically determining the movements necessary for particular manipulative objects, such as human or other animate object entities, to move other objects to ]locations wit
Koga Yoshihito Y.
Latombe Jean-Claude
Cooley & Godward LLP
Goldman Richard M.
Higgins Willis E.
Nguyen Phu K.
The Motion Factory
LandOfFree
System and method for automatic motion generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for automatic motion generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for automatic motion generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441115