Animation of path planning

• US 5,808,887 A
• Filed: 06/07/1995
• Issued: 09/15/1998
• Est. Priority Date: 11/20/1987
• Status: Expired due to Term

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Trovato, Karen Irene, Dorst, Leendert
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US08/487,621
• Time in Patent Office: 1,196 Days
• Field of Search: 364/148, 364/424.02, 364/474.2, 364/461, 364/474.26, 364/436, 364/437, 364/438, 364/444, 364/167.01, 364/424.027, 364/424.028, 364/424.029 , 364/424.031, 364/424.032, 364/424.033, 395/80, 395/85, 395/88, 395/90, 395/919, 395/89, 395/905, 395/152, 395/161, 395/119
• US Class Current: 345/474
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 19/4061 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/35415 3-D three dimension, space input, spaceball
• CPC Class Codes: G05B 2219/39217 Keep constant orientation of handled object while moving manipulator
• CPC Class Codes: G05B 2219/40443 Conditional and iterative planning
• CPC Class Codes: G05B 2219/40448 Preprocess nodes with arm configurations, c-space and planning by connecting nodes
• CPC Class Codes: G05B 2219/40465 Criteria is lowest cost function, minimum work path
• CPC Class Codes: G05B 2219/40471 Using gradient method
• CPC Class Codes: G05B 2219/40476 Collision, planning for collision free path
• CPC Class Codes: G05B 2219/45131 Turret punch press
• CPC Class Codes: G05B 2219/49143 Obstacle, collision avoiding control, move so that no collision occurs
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A method and apparatus for path planning are presented. Path planning involves propagating cost waves in a configuration space representation of a task space. A space variant metric and budding are used for cost wave propagation. The disclosed method and apparatus are readily adaptable to robots with n degrees of freedom.

Claims

1. Computer animation device comprising

means for storing a configuration space data structure representing a physical task space, the configuration space data structure including representations of the object and its environment;

means for propagating cost waves through the configuration space data structure using a space variant metric;

means for displaying a representation of the object and the environment based on the configuration space data structure; and

means for displaying motion of the object through the representation.

2. The device of claim 1 wherein the cost waves are propagated from states of known costs.

3. The device of claim 2 wherein the states of known costs represent goals for the object.

4. The device of claim 1 wherein the configuration space data structure comprises means for representing obstacles around the object.

5. The device of claim 1 wherein the configuration space data structure comprises means for representing goals for the object to reach.

6. Computer animation device comprising

means for storing a configuration space data structure representing a physical task space, the configuration space data structure including representations of the object and its environment, wherein the configuration space data structure comprises an array of states, each state representing a pose of the object, which array comprises a dimension for each degree of freedom of the object;

means for propagating cost waves throughout the configuration space data structure, the means for propagating comprising

means for exploring all neighbors of a state in the configuration space data structure;

means for improving neighbors of the state by assigning appropriate values of cost to goal and direction arrows to the state; and

means for adding improved neighbors to a storage data structure

means for displaying a representation of the object and the environment based on the configuration space data structure; and

means for displaying motion of the object through the representation.

7. The device of claim 6 wherein each state comprises means for storing a cost to goal value.

8. The device of claim 6 wherein each state comprises means for storing a direction arrows value pointing along an optimal path.

9. The device of claim 8 wherein the direction arrows values are chosen from a set comprising values representing transitions parallel to axes of the configuration space corresponding to the configuration space data structure.

10. The device of claim 9 wherein the direction arrows values are chosen from a set which represent transitions from a first state to respective ones of a plurality of second states, which second states are the visible states in an n-cube of p states on a side, the n-cube surrounding the first state, where n is a positive integer representing a number of degrees of freedom of the object and p is a positive integer.

11. The device of claim 6 wherein the means for displaying motion comprises

means for deriving a sequence of object pose representations within the configuration space data structure;

and

means for providing the series in an electronic form.

12. The device of claim 6

wherein each state comprises

means for storing a cost to goal value;

and

means for storing a direction arrows value pointing along an optimal path; and

further comprising means for propagating cost waves throughout the configuration space data structure, the means for propagating comprising

means for exploring all neighbors of a state in the configuration space data structure;

means for improving neighbors of the state by assigning appropriate values of cost to goal and direction arrows to the state; and

means for adding improved neighbors to a storage data structure.

13. Computer software embodied in a computer readable medium comprising

means for controlling storage of a configuration space data structure representing a physical task space, the configuration space data structure including representations of the object and its environment;

means for propagating cost waves through the configuration space data structure using a space variant metric;

means for causing display of a representation of the object and the environment based on the configuration space data structure; and

means for causing display of motion of the object through the representation.

14. The software of claim 13 wherein the cost waves are propagated from states of known costs.

15. The software of claim 14 wherein the states of known costs represent goals for the object.

22. The software of claim 13 wherein

each state comprises

a field for a cost to goal value;

and

a field for a direction arrows value pointing along an optimal path; and

the means for causing derivation causes following of direction arrows values from a current state to a goal state to yield an optimal path to that goal state.

23. The software of claim 13 wherein the configuration space data structure comprises means for representing obstacles around the object.

24. The software of claim 13 wherein the configuration space data structure comprises means for representing goals for the object to reach.

16. Computer software embodied in a computer-readable storage medium comprising

means for controlling storage of a configuration space data structure representing a physical task space, the configuration space data structure including representations of the object and its environment, wherein the configuration space data structure comprises an array of states, each state representing a pose of the object, which array comprises a dimension for each degree of freedom of the object;

means for propagating cost waves throughout the configuration space data structure, the means for propagating comprising

means for exploring all neighbors of a state in the configuration space data structure;

means for improving neighbors of the state by assigning appropriate values of cost to goal and direction arrows to the state; and

means for adding improved neighbors to a storage data structure

means for causing display of a representation of the object and the environment based on the configuration space data structure; and

means for causing display of motion of the object through the representation.

17. The software of claim 16 wherein each state comprises means for storing a cost to goal value.

18. The software of claim 16 wherein each state comprises means for storing a direction arrows value pointing along an optimal path.

19. The software of claim 18 wherein the direction arrows values are chosen from a set comprising values representing transitions parallel to axes of the configuration space corresponding to the configuration space data structure.

20. The software of claim 19 wherein the direction arrows values are chosen from a set which represent transitions from a first state to respective ones of a plurality of second states, which second states are the visible states in an n-cube of p states on a side, the n-cube surrounding the first state, where n is a positive integer representing a number of degrees of freedom of the object and p is a positive integer.

21. The software of claim 16 wherein the means for causing displaying motion comprises

means for causing derivation of a sequence of object pose representations within the configuration space data structure;

and

means for causing provision of the series in an electronic form.