Apparatus and Method of Automated Manufacturing

• US 20080125893A1
• Filed: 10/30/2007
• Published: 05/29/2008
• Est. Priority Date: 10/31/2006
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations Incorporated (Motors Liquidation Co. GUC Trust)
• Inventors: Bandyopadhyay, Sandipan, Tilove, Robert Bruce
• Granted Patent: US 7,974,737 B2
• Time in Patent Office: Days
• US Class Current: 700/103
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40438 Global, compute free configuration space, connectivity graph is then searched
• CPC Class Codes: G05B 2219/40473 Using genetic algorithm GA
• CPC Class Codes: Y02P 80/40 Minimising material used in manufacturing processes

Abstract

An apparatus and method of optimizing collision free path planning comprising: initializing a plurality of feasible configuration points, sample points located in a free space, and sample points not located in the free space; determining a goodness rating of the various pluralities of points; generating new candidate points; determining if each new candidate point is a feasible configuration point and adding each to the plurality of feasible configuration points if it is; if not, determining if each new candidate point is located in the free space and adding it to the plurality of sample points located in the free space if it is; if not, adding to the plurality of sample points not located in the free space; determining an updated goodness rating of the various pluralities of points; determining if a termination criteria has been met and reporting a best solution or no solution if it has been met.

Claims

1. A method of optimizing collision free path planning for an automated manufacturing cell, comprising:

initializing a plurality of feasible configuration points;

initializing a first plurality of sample points located in a free space;

initializing a second plurality of sample points not located in said free space;

determining an initial goodness rating of said first and second pluralities of sample points and said plurality of feasible configuration points;

generating a plurality of new candidate points;

determining if each of said new candidate points is a feasible configuration point;

adding respective ones of said new candidate points to said plurality of feasible configuration points if said respective ones are feasible configuration points;

determining if said respective ones of said new candidate points are located in said free space if said respective ones are not feasible configuration points;

adding said respective ones to said first plurality of sample points if said respective ones are located in said free space and are not feasible configuration points;

adding said respective ones to said second plurality of sample points if said respective ones are not located in said free space and are not feasible configuration points;

determining an updated goodness rating of said first and second pluralities of sample points and said plurality of feasible configuration points;

updating a motion planning algorithm;

determining if a termination criteria has been met;

reporting one of a best solution and no solution if said termination criteria has been met; and

repeating said generating a plurality of new candidate points and determining if each of said new candidate points is a feasible configuration point if said termination criteria has not been met.

2. The method of claim 1, wherein said generating said plurality of new candidate points is performed using an optimization methodology.

3. The method of claim 2, wherein said optimization methodology is one of a genetic algorithm, an energy minimization technique, and an evolutionary computation method.

4. The method of claim 1, wherein said motion planning algorithm is a probabilistic roadmap path planner.

5. The method of claim 4, further comprising:

determining an initial collision free path inside said free space prior to said determining said initial goodness rating; and

determining an updated collision free path inside said free space in response to said updating of said probabilistic roadmap path planner.

6. The method of claim 5, wherein said determining an updated collision free path consists of said probabilistic roadmap path planner iteratively searching for a collision free path by adding at least one of said new candidate points to said first plurality of sample points or at least one edge to said free space, or both, at each iteration.

7. The method of claim 1, wherein said termination criteria is one of an optimized goal configuration, an optimized home configuration, an optimized weld gun orientation, an optimized collision free path, and a predetermined threshold number of iterations, or combinations thereof.

8. The method of claim 1, wherein said determining said initial and updated goodness ratings respectively include determining an initial cost function and an updated cost function.

9. The method of claim 8, wherein said goodness ratings are inversely proportional to said respective cost functions.

10. The method of claim 1, wherein said plurality of feasible configuration points is one of a plurality of home configuration points and a plurality of goal configurations points.

11. A method of automating the determination of, and assuring the realization of optimal weld gun orientations and robot paths in a robotic welding system having a weld gun and at least one predetermined weld point, comprising:

initializing a plurality of feasible configuration points;

initializing a first plurality of sample points located in a free space;

initializing a second plurality of sample points not located in said free space;

determining an initial goodness rating of said first and second pluralities of sample points and said plurality of feasible configuration points;

generating a plurality of new candidate points using an optimization methodology;

determining if each of said new candidate points is a feasible configuration point;

adding respective ones of said new candidate points to said plurality of feasible configuration points if said respective ones are feasible configuration points;

determining if said respective ones of said new candidate points are located in said free space if said respective ones are not feasible configuration points;

adding said respective ones to said first plurality of sample points if said respective ones are located in said free space and are not feasible configuration points;

adding said respective ones to said second plurality of sample points if said respective ones are not located in said free space and are not feasible configuration points;

determining an updated goodness rating of said first and second pluralities of sample points and said plurality of feasible configuration points;

updating a probabilistic roadmap path planner;

determining if a termination criteria has been met;

reporting one of a best solution and no solution if said termination criteria has been met; and

repeating said generating a plurality of new candidate points and determining if each of said new candidate points is a feasible configuration point if said termination criteria has not been met;

wherein said termination criteria is one of an optimized goal configuration, an optimized home configuration, an optimized weld gun orientation, an optimized collision free path, and a predetermined threshold number of iterations.

12. The method of claim 11, wherein said optimization methodology is one of a genetic algorithm, an energy minimization technique, and an evolutionary computation method.

13. The method of claim 11, further comprising:

determining an initial collision free path inside said free space prior to said determining said initial goodness rating; and

determining an updated collision free path inside said free space in response to said updating of said probabilistic roadmap path planner.

14. The method of claim 13, wherein said determining an updated collision free path consists of said probabilistic roadmap path planner iteratively searching for a collision free path by adding at least one of said new candidate points to said first plurality of sample points or at least one edge to said free space, or both, at each iteration.

15. The method of claim 11, wherein said determining said initial and updated goodness ratings respectively include determining an initial cost function and an updated cost function.

16. The method of claim 15, wherein said goodness ratings are inversely proportional to said respective cost functions.

17. The method of claim 11, wherein said plurality of feasible configuration points is one of a plurality of home configuration points and a plurality of goal configurations points.

18. An apparatus for welding at least one work piece at one or more weld points, comprising:

a weld gun configured to selectively complete a welding operation at the one or more weld points;

an automated support arm operatively connected to said weld gun and configured to reposition said weld gun;

a controller operatively connected to said support arm and weld gun and configured to control said repositioning and said selective welding of said weld gun;

wherein said controller is programmed and configured to determine an optimization parameter via;

initializing a plurality of feasible configuration points;

initializing a first plurality of sample points located in a free space;

initializing a second plurality of sample points not located in said free space;

determining an initial goodness rating of said first and second pluralities of sample points and said plurality of feasible configuration points;

generating a plurality of new candidate points using an optimization methodology;

determining if each of said new candidate points is a feasible configuration point;

adding respective ones of said new candidate points to said plurality of feasible configuration points if said respective ones are feasible configuration points;

determining if said respective ones of said new candidate points are located in said free space if said respective ones are not feasible configuration points;

adding said respective ones to said first plurality of sample points if said respective ones are located in said free space and are not feasible configuration points;

adding said respective ones to said second plurality of sample points if said respective ones are not located in said free space and are not feasible configuration points;

determining an updated goodness rating of said first and second pluralities of sample points and said plurality of feasible configuration points;

updating a probabilistic roadmap path planner;

determining if a termination criteria has been met;

reporting one of a best solution and no solution if said termination criteria has been met; and

repeating said generating a plurality of new candidate points if said termination criteria has not been met.

19. The apparatus of claim 18, wherein said optimization parameter includes at least one of an optimized goal configuration, an optimized home configuration, an optimized weld gun orientation, and an optimized collision free path.

20. The apparatus of claim 18, wherein said controller is further programmed and configured to determine an initial collision free path inside said free space prior to said determining said initial goodness rating;

and determine an updated collision free path inside said free space in response to said updating of said probabilistic roadmap path planner.