System and method for automatic motion generation

• US 6,229,552 B1
• Filed: 07/22/1996
• Issued: 05/08/2001
• Est. Priority Date: 07/21/1995
• Status: Expired due to Fees

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Motion Factory, Incorporated (Avid Technology Incorporated)
• Inventors: Latombe, Jean-Claude, Koga, Yoshihito Y.
• Primary Examiner(s): Nguyen, Phu K.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US08/681,301
• Time in Patent Office: 1,751 Days
• Field of Search: 345/473, 345/474, 345/420, 345/421, 345/424, 345/425
• US Class Current: 345/474
• CPC Class Codes: G06T 13/40 of characters, e.g. humans, animals or virtual beings

Abstract

We apply manipulation planning to computer animation. A new path planner is presented that automatically computes the collision-free trajectories for several cooperating arms to manipulate a movable object between two configurations. This implemented planner is capable of dealing with complicated tasks where regrasping is involved. We have demonstrated the capability of this planner to generate realistic human arm motions involved in the manipulation of objects.

Claims

1. In a data processing system having a display, a method for generating a collision free path for grasping and carrying a movable object from an initial location to a desired goal location on the display for a human or human-like figure having grasps and grasping arms, based on task level commands, which method comprises:

(a) specifying a geometric model of the human or human-like figure;

(b) specifying a kinematic model of the human or human-like figure including joint constraints;

(c) specifying a geometry of an environment in which object manipulation motion is to take place;

(d) specifying a desired goal location in the environment of the object to be manipulated;

(e) identifying locations within the environment at which the human or human-like figure can grasp the object to be manipulated and identifying and enumerating all sets of grasps and grasping arms which can be achieved without collision;

(f) generating a collision-free path for the object to be manipulated and the human or human-like figure to move the object to be manipulated to the desired goal location, using the geometric model of the human or human-like figure, the kinematic model of the human or human-like figure, the geometry of the environment and a search algorithm

(1) to generate a set of non-intersecting paths for motion of the human or human-like figure and the object to be manipulated,

(2) to identify locations at which the human or human-like figure may grasp objects to be manipulated, and

(3) to verify that at each said location the object may be grasped by a permitted grasp;

(g) generating movement as a series of configurations of grasps, grasping arms and the object to be manipulated on the display of the human or human-like figure to grasp the object at one of the identified locations; and

(h) generating movement as a series of configurations of grasps, grasping arms and the object to be manipulated on the display of the human or human-like figure to move the object to the specified goal location.

2. A method for generating and displaying a collision free path for a geometrically and kinematically modelled anthromorphic figure having grasps and grasping arms, to grasp and carry a movable object from an initial location to a desired goal location on a display which method comprises:

(a) specifying a geometry of an environment in which object motion is to take place;

(b) specifying the desired goal location of the object;

(c) identifying locations at which the anthromorphic figure can grasp the object;

(d) identifying and enumerating all sets of grasps and grasping arms which can be achieved without collision;

(e) generating the collision-free path for the object and the anthromorphic figure to move the object to the desired goal location, using the geometric and kinematic models of the anthromorphic figure, the geometry of the environment and a search algorithm, the models, search algorithm, and geometry

(1) generating a set of non-intersecting paths for motion of the anthromorphic figure and the object,

(2) identifying locations at which the anthromorphic figure may grasp objects, and

(3) verifying that at each location the object may be grasped by a permitted grasp; and

(f) generating movement of the anthromorphic figure and the object on the display as a series of configurations of grasps, and grasping arms to grasp the object at identified locations and move the object to the desired goal location.

3. The method of claim 2 comprising defining a finite set of grasps, each grasp describing a rigid attachment of at least one end effector of at least one grasping arm with the movable object.

4. The method of claim 2 comprising generating the collision free path, where said collision free path comprises:

(a) a series of configurations, each configuration associating a grasp and grasping arm, and

(b) a series of subpaths connecting a pair of successive configurations.

5. The method of claim 2 comprising generating and displaying the collision free path for the geometrically and kinematically modelled anthromorphic figure having grasps and grasping arms, to grasp and carry a movable object from an initial location to a desired goal location on a display by implementing a high level command.