Patent US3158728A successfully refreshed from Google Patents.
Patent DE155000C successfully refreshed from Google Patents.
Patent US5696674A successfully refreshed from Google Patents.
US5696674A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer animation of planned path in changing space
Assignee: US Philips Corp
•
Filing: 1995-06-07
•
Granted: 1997-12-09
•
Expires: 2015-06-07
Abstract
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.
Inventors
- 👤 Karen Irene Trovato
- 👤 Leendert Dorst
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 07:34
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/10; G06F30/18; B; B25; B25J; B25J9/00; B25J9/16; B25J9/1656; B25J9/1664; B25J9/1666; G05; G05B; G05B19/00; G05B19/02; G05B19/18; G05B19/406; G05B19/4061; G05D; G05D1/00; G05D1/02; G05D1/021; G05D1/0231; G05D1/0246; G05B2219/00; G05B2219/30; G05B2219/35; G05B2219/35415; G05B2219/40; G05B2219/40443; G05B2219/40476; G05B2219/49; G05B2219/49143; Y; Y10; Y10S; Y10S706/00; Y10S706/902; Y10S706/903; Y10S706/905; Y10S706/919
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
85 words
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.
Claim 2
Dependent Claim
85 words
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.
Claim 3
Dependent Claim
42 words
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.
Claim 4
Dependent Claim
27 words
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.
Claim 5
Dependent Claim
67 words
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.
Claim 6
Dependent Claim
54 words
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.
Claim 7
Dependent Claim
82 words
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.
Claim 8
Dependent Claim
33 words
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.
Claim 9
Dependent Claim
15 words
The apparatus of claim 6 wherein the perimeter list is a sifting heap data structure.
Claim 10
Dependent Claim
48 words
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.
Claim 11
Dependent Claim
15 words
The apparatus of claim 1 wherein the change of conditions is addition of an obstacle.
Claim 12
Dependent Claim
15 words
The apparatus of claim 1 wherein the change of conditions is addition of a goal.
Claim 13
Dependent Claim
15 words
The apparatus of claim 1 wherein the change of conditions is removal of an obstacle.
Claim 14
Dependent Claim
33 words
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.
Claim 15
Dependent Claim
15 words
The apparatus of claim 1 wherein the change of conditions is removal of a goal.
Claim 16
Dependent Claim
38 words
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.
Claim 17
Dependent Claim
90 words
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.
Claim 18
Dependent Claim
99 words
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.
Claim 19
Dependent Claim
99 words
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.
Claim 20
Dependent Claim
42 words
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.
Claim 21
Dependent Claim
27 words
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.
Claim 22
Dependent Claim
73 words
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.
Claim 23
Dependent Claim
57 words
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.
Claim 24
Dependent Claim
90 words
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.
Claim 25
Dependent Claim
37 words
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.
Claim 26
Dependent Claim
15 words
The software of claim 22 wherein the perimeter list is a sifting heap data structure.
Claim 27
Dependent Claim
51 words
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.
Claim 28
Dependent Claim
15 words
The software of claim 17 wherein the change of conditions is addition of an obstacle.
Claim 29
Dependent Claim
15 words
The software of claim 17 wherein the change of conditions is addition of a goal.
Claim 30
Dependent Claim
15 words
The software of claim 17 wherein the change of conditions is removal of an obstacle.
Claim 31
Dependent Claim
36 words
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.
Claim 32
Dependent Claim
15 words
The software of claim 17 wherein the change of conditions is removal of a goal.
Claim 33
Dependent Claim
38 words
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.
Claim 34
Dependent Claim
90 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-08 | 2001-06-09 | 2001-12-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-08 | 2005-06-09 | 2005-12-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-08 | 2009-06-09 | 2009-12-09 | $7700.00 | Window Closed / Lapsed |