Differential budding: method and apparatus for path planning with moving obstacles and goals

• US 6,728,581 B1
• Filed: 04/11/1990
• Issued: 04/27/2004
• Est. Priority Date: 03/09/1988
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Inventors: Trovato, Karen Irene, Dorst, Leendert
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): PATEL, RAMESH B
• Application Number:
  US07/508,024
• Time in Patent Office: 5,130 Days
• Field of Search: 901/1, 901/50, 700/56, 700/28, 700/245, 700/250, 700/253, 700/254, 700/255, 701/23, 701/25, 701/301, 701/117, 701/118, 701/201, 701/202, 701/26, 701/210, 706/905, 706/919
• US Class Current: 700/56
• 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. A method for planning a physical path for a physical object to follow in a physical task space in which there has been a physical change in conditions comprising executing the following steps in at least one digital data processing device that includes or is coupled with at least one computer readable medium:

a. starting from an initialized configuration space data structure, embodied within the at least one computer storage medium and representing the physical task space, the configuration space data structure storing signals representing the object and its environment;

b. receiving signals indicating the physical change in conditions;

c. identifying a perimeter of a region in the configuration space data structure which is affected by the change in conditions;

d. propagating cost waves in the configuration space data structure, within the at least one computer readable medium, from the perimeter to update the signals stored in the configuration space data structure; and

e. providing parameter signals based on the updated signals, the parameter signals being usable by the physical object to follow the physical path.

2. The method of claim 1 wherein the object is a robot.

3. The method of claim 1 wherein the signals represent cost to goal and/or direction arrows values.

4. A method for planning a physical path for a physical object to follow in a physical task space in which there has been physical a change in conditions comprising executing the following steps in at least one digital data processing device that includes or is coupled with at least one computer storage medium:

a. starting from a configuration space data structure, embodied in the at least one computer readable medium, comprising a plurality of state data structures which in turn each comprise respective direction_arrows and cost_to_goal data structures for storing signals representing the physical task space as it existed prior to the change in conditions;

b. receiving signals indicating the physical change of conditions;

c. within the at least one computer readable medium, differentially budding an area in the configuration space data structure which is affected by the change in conditions, wherein differentially budding comprises the steps of;

I. identifying a perimeter of a region in the configuration space data structure which is affected by the change in conditions; and

ii. budding from the perimeter to update signals stored in the cost_to_goal and direction_arrows data structures corresponding to the change in conditions, wherein budding comprises for each affected state data structure;

A) exploring all neighbors of that affected state data structure;

B) improving neighbors of that affected state data structure by storing appropriate signals in the respective cost_to_goal and direction_arrows data structures;

C) adding improved neighbors to a storage data structure; and

D) repeating b) ii) A)-b) ii) D) for all states in the storage data structure; and

d. providing parameter signals based on the updated values, the parameter signals being usable by the physical object to follow the physical path.

5. Computer apparatus for planning a path for an object to follow in a physical task space in which there has been a change in conditions comprising:

a. means for storing a configuration space representing the object and its environment;

b. means for receiving signals indicating the change of conditions;

c. means for identifying a perimeter of a region in the configuration space which is affected by the change in conditions;

d. means for propagating cost waves from the perimeter by updating the configuration space, within the means for storing, to fill the configuration space with an updated representation corresponding to the change in conditions; and

e. means for supplying parameter signals based on the updated configuration space, the parameter signals being usable by the object to follow the path.

6. The apparatus of claim 5 wherein the object is a robot.

7. Computer apparatus for planning a path for a physical object to follow in a physical task space in which there has been a physical change in conditions comprising:

a. a computer readable medium for embodying a configuration space, as a data structure, which configuration space includes a plurality of states which in turn are for storing direction arrows and cost to goal signals representing the physical task space as it existed prior to the change in conditions;

b. means for receiving signals indicating the physical change of conditions;

c. means for differentially budding an area in the configuration space which is affected by the change in conditions, comprising;

I. means for identifying a perimeter of a region in the configuration space which is affected by the change in conditions; and

ii. means for budding from the perimeter to update stored cost to goal and direction arrows signals corresponding to the change in conditions, wherein budding comprises for each affected state;

A) means for exploring all neighbor states of that affected state;

B) means for improving neighbors of that state by storing appropriate respective cost to goal and direction arrows signals in the neighbor states;

C) second means for storing;

D) means for adding improved neighbors to the second means for storing; and

E) means for repeating b) ii) A)-b) ii) D) for all states in the second means for storing; and

d. means for supplying parameter signals based on the updated signals, the parameter signals being usable by the physical object to follow the physical path.

8. A computer readable storage medium encoded with a computer program for planning a path for an object to follow in a physical task space in which there has been a change in conditions comprising

a. means for maintaining a configuration space data structure, the configuration space data structure representing the physical task space and storing signals representing the object and its environment;

b. means for receiving signals indicating the change in conditions;

c. means for identifying a perimeter of a region in the configuration space data structure which is affected by the change in conditions;

d. means for propagating cost waves in the configuration space data structure, within the at least one storage device, from the perimeter to update the signals stored in the configuration space data structure; and

e. means for providing parameter signals based on the updated signals, the parameter signals being usable by the object to follow the path.

9. The medium of claim 8 wherein, the configuration space data structure contains direction arrow signals which reflect propagation in response to a space variant metric.

10. The medium of claim 8 wherein the change in conditions comprises at least one added obstacle in the task space.

11. The medium of claim 10 wherein

a. the configuration space comprises a plurality of states, each states being associated with

I. a direction arrow signal indicating a least cost path;

ii. a cost to goal signal;

b. the means for identifying a perimeter comprises;

I. means for locating a back edge of the obstacle;

ii. means for storing a perimeter list of states surrounding states in the affected region, the affected region being those states for which the direction arrow signals indicate a path through the added object via the back edge of the obstacle;

iii. means for clearing the cost to goal signals and the direction arrows signals from the affected regions.

12. The medium of claim 11 wherein the means for identifying the perimeter further comprises

means for second locating a front edge of the obstacle;

and

means for including the front edge in the perimeter list.

13. The medium of claim 11 wherein the means for storing comprises means for storing said perimeter list in a sifting heap.

14. The medium of claim 8 wherein the change of conditions comprises that an obstacle has been removed.

15. The medium of claim 8 wherein the change of conditions comprises that a goal has been added.