Computer animation of planned path in changing space

• US 5,696,674 A
• Filed: 06/07/1995
• Issued: 12/09/1997
• Est. Priority Date: 03/09/1988
• 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,619
• Time in Patent Office: 916 Days
• Field of Search: 364/167.01, 364/148, 364/461, 364/436, 364/437, 364/438, 364/444, 364/474.2, 364/424.02, 364/578, 364/424.029, 364/424.031, 364/424.032 , 364/424.033, 364/444.1, 364/444.2, 364/449.3, 364/449.4, 364/449.5, 395/80, 395/85, 395/88, 395/90, 395/919, 395/89, 395/905, 395/152, 395/174, 395/958
• US Class Current: 345/473
• 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/40443 Conditional and iterative planning
• CPC Class Codes: G05B 2219/40476 Collision, planning for collision free path
• 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: 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
• CPC Class Codes: Y10S 706/905 Vehicle or aerospace
• CPC Class Codes: Y10S 706/919 Designing, planning, programming, CAD, CASE

Abstract

A method is presented for path planning after changes in task space. In one embodiment, the method is applied to planning a path for a robot arm. The method identifies areas in the configuration space which are affected by the changes in task space. Cost waves can then be repropagated in these affected areas to allow for planning in N dimensions and using space variant metrics. The method is also adapted to use in the presence of phantom obstacles.

Claims

1. Computer apparatus for creating animation comprising

memory means for storing a configuration space data structure representing an object and its environment;

means for receiving signals indicating a change in the environment;

means for identifying a perimeter of a region in the configuration space data structure;

means for propagating cost waves in the configuration space data structure from the perimeter in order to create an updated configuration space data structure; and

means for displaying motion of the object based on the updated configuration space data structure.

2. The apparatus of claim 1 wherein the configuration space data structure is an array of states, which array has a dimension for each degree of freedom of the object, each state being a data structure corresponding to a pose of the object.

3. The apparatus of claim 2 wherein each state comprises a field for storing a cost to goal value and a field for storing a direction arrows value.

4. The apparatus of claim 3 wherein the means for propagating cost waves comprises

means for exploring all neighbors of an affected state;

means for improving neighbors of that affected state by storing appropriate signals in the respective cost to goal and direction arrows fields;

means for adding improved neighbors to a storage data structure; and

means for causing iteration until all states in the storage data structure.

5. The apparatus of claim 3 wherein the means for displaying

includes means for following direction arrows values from a current state to a goal state to produce a sequence of states along an optimal path to the goal state;

and

displays a sequence of poses of the object corresponding to the sequence of states.

6. The apparatus of claim 3 wherein the means for identifying comprises

means for locating a back edge of a new obstacle;

means for storing a perimeter list of states surrounding states in the affected region, the affected region being those states for which the direction arrows indicate a path through the new obstacle; and

means for clearing cost to goal and direction arrows values from the affected region; and

wherein the means for propagating propagates from the states on the perimeter list.

7. The apparatus of claim 6 wherein the means for identifying further comprises

means for second locating a front edge of the obstacle;

and

means for including the front edge in the parameter list.

8. The apparatus of claim 6 wherein the perimeter list is a sifting heap data structure.

9. The apparatus of claim 1 further comprising

means for treating a portion of the change of conditions as the change of conditions, which portion is actually encountered by the object;

and

means for iterating for each newly encountered portion, until all of the change of conditions is encountered.

10. The apparatus of claim 1 wherein the change of conditions is addition of an obstacle.

11. The apparatus of claim 1 wherein the change of conditions is addition of a goal.

12. The apparatus of claim 1 wherein the change of conditions is removal of an obstacle.

13. The apparatus of claim 12 wherein the means for propagating clears cost values from the states corresponding to the removed obstacle and propagates from a set of neighbor states of the removed obstacle.

14. The apparatus of claim 1 wherein the change of conditions is removal of a goal.

15. The apparatus of claim 3 wherein the means for identifying stores at least one state corresponding to an added goal in a sifting heap data structure and the means for propagating propagates from that at least one state.

16. The apparatus of claim 3

wherein the storage data structure is a heap;

further comprising;

means for checking any added obstacles and any removed goals;

means for clearing the influence of added obstacles and removed goals; and

means for second checking removed obstacles and added goals;

wherein the means for identifying stores

a perimeter list in the heap in response to the added obstacle removed goals; and

neighbor states of the added obstacles and removed goals; and

wherein the means for propagating propagates from all the states on the heap.

17. Computer software, embodied in a computer-readable medium, for creating animation comprising

means for causing storage of a configuration space data structure representing an object and its environment;

means for causing reception of signals indicating a change in the environment;

means for causing identification of a perimeter of a region in the configuration space data structure;

means for causing propagation of cost waves in the configuration space data structure from the perimeter in order to create an updated configuration space data structure; and

means for causing display of motion of the object based on the updated configuration space data structure.

18. The software of claim 17 wherein the configuration space data structure is an array of states, which array has a dimension for each degree of freedom of the object, each state being a data structure corresponding to a pose of the object.

19. The software of claim 18 wherein each state comprises a field for storing a cost to goal value and a field for storing a direction arrows value.

20. The software of claim 17 wherein the means for propagating cost waves comprises

means for causing exploration of all neighbors of an affected state;

means for causing improvement of neighbors of that affected state by storing appropriate signals in the respective cost to goal and direction arrows fields;

means for causing addition of improved neighbors to a storage data structure; and

means for causing iteration until all states in the storage data structure.

21. The software of claim 19 wherein the means for causing display

includes means for causing following of direction arrows values from a current state to a goal state to produce a sequence of states along an optimal path to the goal state;

and

displays a sequence of poses of the object corresponding to the sequence of states.

22. The software of claim 19 wherein the means for identifying comprises

means for causing location of a back edge of a new obstacle;

means for causing storage of a perimeter list of states surrounding states in the affected region, the affected region being those states for which the direction arrows indicate a path through the new obstacle; and

means for causing clearing of cost to goal and direction arrows values from the affected region; and

wherein the means for causing propagation, causes propagation from the states on the perimeter list.

23. The software of claim 22 wherein the means for identifying further comprises

means for causing second location of a front edge of the obstacle;

and

means for causing inclusion of the front edge in the parameter list.

24. The software of claim 22 wherein the perimeter list is a sifting heap data structure.

25. The software of claim 17 further comprising

means for causing treatment of a portion of the change of conditions as the change of conditions, which portion is actually encountered by the object;

and

means for causing iteration for each newly encountered portion, until all of the change of conditions is encountered.

26. The software of claim 17 wherein the change of conditions is addition of an obstacle.

27. The software of claim 17 wherein the change of conditions is addition of a goal.

28. The software of claim 17 wherein the change of conditions is removal of an obstacle.

29. The software of claim 28 wherein the means for causing propagation causes clearance of cost values from the states corresponding to the removed obstacle and propagates from a set of neighbor states of the removed obstacle.

30. The software of claim 17 wherein the change of conditions is removal of a goal.

31. The software of claim 19 wherein the means for identifying stores at least one state corresponding to an added goal in a sifting heap data structure and the means for propagating propagates from that at least one state.

32. The software of claim 19

wherein the storage data structure is a heap;

further comprising;

means for checking any added obstacles and any removed goals;

means for clearing the influence of added obstacles and removed goals; and

means for second checking removed obstacles and added goals;

wherein the means for identifying stores

a perimeter list in the heap in response to the added obstacle removed goals; and

neighbor states of the added obstacles and removed goals; and

wherein the means for propagating propagates from all the states on the heap.