Automated path planning

• US 5,999,881 A
• Filed: 05/05/1997
• Issued: 12/07/1999
• Est. Priority Date: 05/05/1997
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Chang, Hsuan, Schroeder, William John, Law, Christopher Charles
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US08/851,393
• Time in Patent Office: 946 Days
• Field of Search: 701/301, 701/25, 701/26, 701/201
• US Class Current: 701/301
• CPC Class Codes: G05B 19/4061 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40443 Conditional and iterative planning
• CPC Class Codes: G05B 2219/40515 Integration of simulation and planning
• CPC Class Codes: G05B 2219/49143 Obstacle, collision avoiding control, move so that no collision occurs
• CPC Class Codes: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G05D 1/0221 involving a learning process
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

This present invention makes use of a method for automatically finds collision-free part removal paths. The system sparsely samples the high-dimensional state space and maps the rest of the space using proximity assumptions (assumptions about states near the samples). The present invention is less complex and faster than previously known methods.

Claims

1. An auto path planning method for automatically determining a path from a start state, said start state being a start point on a state diagram, to an end state, said end state being an end point on a state diagram, said planning method comprising the steps of:

a) acquiring descriptions of a plurality of obstacle locations;

b) creating a first start region about said start point, said start point being the center point of said first start region, said first start region having a start radius of predetermined value;

c) creating a first destination region about said end point, said end point being the center point of said first destination region, said first destination region having a destination radius selected such that said first destination region and said first start region overlap in part;

d) creating a first connecting path for connecting said start point and said end point;

e) testing said first connecting path to determine if said first connecting path intersects with any of said plurality of obstacle locations, each intersection of said first connecting path with any of said plurality of obstacle locations defining a collision point set;

f) adding said first start region, said first destination region, said start point and said end point to a valid space list if said first connecting path does not intersect with any of said plurality of obstacle locations, said first connecting path providing the automatically determined path;

g) creating a second start region if said first connecting path intersects with any of said plurality of obstacle locations, said second start region being created by reducing said start radius of said first start region to be less than a distance from said start point to the intersection disposed closest to said start point, said reduced start radius and said start point defining said second start region;

h) creating a second destination region if said first connecting path intersects with any of said plurality of obstacle locations, said second destination region being created by reducing said destination radius of said first destination region to be less than a distance from said end point of said first destination region to the intersection with said obstacle locations disposed closest to said end point, said reduced destination radius and said end point defining said second destination region;

i) adding said second start region, said second destination region, said start point and said end point to a valid space list;

j) adding said collision point set to a hit list;

k) determining if said second start region and said second destination region overlap in part, said first connecting path providing the automatically determined path if said second start region and said second destination region overlap in part;

l) if said second start region and said second destination region do not overlap in part, choosing a region from said valid space list, said chosen region being disposed between said second start region and said second destination region, said chosen region defining a parent region from which to spawn a plurality of child regions;

m) choosing a candidate point within said parent region as a center point of a first child region;

n) creating said plurality of child regions, each of said plurality of child regions being created to overlap in part with a previously created child region;

o) creating a second connecting path for connecting said respective center points of said plurality of child regions such that said second connecting path does not intersect with any of said plurality of obstacle locations; and

,

p) repeating steps n and o until said second start region and said second destination region are linked by said plurality of child regions that overlap in part, said second connecting path providing the automatically determined path.

2. The auto path planning method of claim 1 where the step of choosing a region from the valid space list comprises the step of:

choosing the region with the largest uncovered surface area, as the parent region.

3. The auto path planning method of claim 1 where the step of choosing a region from the valid space list comprises the step of:

choosing the region with the fewest number of neighbors, as the parent region.

4. The auto path planning method of claim 1 where the step of choosing a region from the valid space list comprises the step of:

choosing the region with the nearest non-contiguous region, as the parent region.

5. The auto path planning method of claim 1 where the step of choosing a region from the valid space list comprises the step of:

choosing the region closest to a local gap function minimum, as the parent region.

6. The auto path planning method of claim 1 where the step of choosing a region from the valid space list comprises the step of:

choosing the region closest to a user-defined guide path, as the parent region.

7. The auto path planning method of claim 1 where the step of choosing a candidate point of parent region comprises the step of:

choosing a point within the parent region, being furthest from neighbors of the parent region, as the candidate point.

8. The auto path planning method of claim 1 where the step of choosing a candidate point of parent region comprises the step of:

choosing a point within the parent region, being closest to a nearest region which is not contiguous with the parent region, as the candidate point.

9. The auto path planning method of claim 1 where the step of choosing a candidate point of parent region comprises the step of:

choosing a point within the parent region, being closest to a local gap function minimum, as the candidate point.

10. The auto path planning method of claim 1 where the step of choosing a candidate point of parent region comprises the step of:

choosing a point within the parent region, being closest to a user-defined guide path, as the candidate point.

11. The auto path planning method of claim 1 wherein the step of choosing a candidate point within parent region comprises the step of:

choosing an point within parent region on one the axes of the parent region a predefined distance from the center of the parent region which has not been previously chosen, as a center point of a child region.

13. The auto path planning method of claim 1 where the step of creating a plurality of child regions comprises the steps of:

defining said plurality of child regions by respective center points and respective radii; and

,

selecting said respective radii such that each of said plurality of child regions does not include points in said collision point set.

12. An auto path planning system for automatically determining a path from a start state, being a start point on a state diagram, to an end state, being an end point on a state diagram, comprising:

a) a valid space memory for storing a plurality of regions, respective center locations of said regions and respective radii of said regions;

b) a collision memory for storing a plurality of collision locations;

c) a region synthesis device coupled to the collision memory for creating the plurality of regions between a first region and a second region, the first region having the start point as the center location of the first region, the respective radius of the first region being less than the distance from the start point to the collision location disposed closest to the start point, the second region having the end point as the center location of the second region, the respective radius of the second region being less than the distance from the end point to the collision location disposed closest to the end point, the region synthesis device receiving respective center locations for creating the regions between the first and second regions;

d) an overlap detector coupled to the region synthesis device and the valid space memory, for detecting if any of the plurality of regions overlap with other regions, said overlapping regions defining a same network;

e) a connection path sampler coupled to the overlap detector for creating a connecting path linking the respective center locations of overlapping regions and for sampling the connecting path to provide sample points, the connection path sampler updating the valid space memory with the overlapping regions;

f) a collision detector coupled to the collision memory and the connection path sampler for receiving the sample points and for determining if the sample points indicate a collision, the collision detector reducing the regions stored in the valid space memory if a collision is indicated by reducing the respective radii of the regions to be less than the distance between the respective center locations of the regions to the collision location disposed closest to the respective center locations, and said collision detector adding new collisions to collision memory when a collision is indicated;

g) a parent selector, coupled to the valid space memory, for choosing a region from the plurality of regions stored in the valid space memory to define a parent region from which to spawn a plurality of child regions by the region synthesis device;

h) a child center point selector, coupled to the parent selector and the collision detector, for choosing a candidate point within the parent region as the respective center location of the child region, the candidate point being not contained within collision memory and defining the respective center location of the child region;

i) a path optimizer coupled to the valid space memory for finding a shortest path linking the start point and the end point, the shortest path being contained within the valid space memory, the shortest path to result in the automatically determined path; and

j) a network verification device for determining if the first and second regions are in the same network, the network verification device activating the path optimizer if the first and second regions are in the same network, and the network verification device activating the parent selector if first and second regions are not in the same network.