US 6,526,373 B1Granted

Optimization tool for robot placement

AssigneeDassault Systemes

InventorDavid Barral

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and system for optimizing the placement of a robot in a workplace so as to minimize cycle time is defined. A modified simulated annealing method (SA) is applied to the problem of robot placement in CAD systems, in the context of welding tasks. The objective function for optimization is cycle time, which can be obtained from available robotic CAD software. The research domains are simplified, and the SA method is applied to yield an optimal or near-optimal solution to each problem. To obtain the optimal placement of the robot, the research domain is first simplified by determining an acceptable base location domain, then obstacle shadows, which are subtracted from the previous domain to give the free acceptable base location domain. A modified SA method is applied to this domain, using task feasibility tests before simulating the cycle time, in order to save CPU time. The modified SA technique gives a set of near-optimal placements, together with other local minima, and an estimate of an efficient region where the robot may be positioned.

Claims4

Dependent claims

A CAD/CAM computer system comprising:

an input device;
a central processing unit;
and
a memory device for storing data;
wherein the central processing unit runs an application program comprising code for determining a discrete set of locations within a workcell for the placement of a robot, said discrete set of locations being locations that would allow the robot to complete a given workplan in less time than if the robot were placed elsewhere in the workcell and without hitting obstacles in the workcell, said code comprising means for:
a) determining an acceptable base location domain defining an area in which the robot base may be placed so that an end-effector of the robot may reach all work points in the workplan, said acceptable base location domain being determined by:
i) performing a simulation wherein the end-effector of the robot is fixed to a work point;
ii) selecting a discrete set of positions of a wrist joint of the robot while the end-effector is fixedly attached to the work point;
iii) for each discrete wrist position, sweeping a primary arm of the robot through its range of motion while recording the area in which the robot base travels;
iv) performing steps i) to iii) for each work point;
and
v) choosing as the acceptable base location domain the area which is common to all of the areas recorded in step iv);
b) determining obstacle shadows defining regions of robot base placement within the acceptable base location domain which would result in collisions between the robot and objects in the workcell;
c) determining a free acceptable base location domain by subtracting the obstacle shadows from the acceptable base location domain;
and
d) searching said free acceptable base location domain for said discrete set of locations using a modified simulated annealing technique, said modifications comprising:
i) storing local minima as they are encountered during the simulated annealing process;
ii) storing attraction areas corresponding to each of said local minima, comprising areas surrounding a local minimum data point;
iii) performing a gradient descent, by setting a temperature function of the simulated annealing method to a value of zero, when a data point from the free acceptable base location domain is encountered that is not within an attraction area;
and
iv) redefining and storing an attraction area when a gradient descent generates data points falling within an attraction area so that the attraction area includes the data point from which the gradient descent began.

18 more elements

Computer executable code stored on a computer readable medium, the code comprising means for causing a CAD/CAM computer system to determine a discrete set of locations within a workcell for placement of a robot, said discrete set of locations being locations that would allow the robot to complete a given workplan in less time than if the robot were placed elsewhere in the workcell, and would allow the robot to complete the workplan without hitting obstacles in the workcell, said code further comprising means for causing the computer system to execute the method comprising:

a) determining an acceptable base location domain defining an area in which the robot base may be placed so that an end-effector of the robot may reach all work points in the workplan, said acceptable base location domain being determined by:
i) performing a simulation wherein the end-effector of the robot is fixed to a work point;
ii) selecting a discrete set of positions of a wrist joint of the robot while the end-effector is fixedly attached to the work point;
iii) for each discrete wrist position, sweeping a primary arm of the robot through its range of motion while recording the area in which the robot base travels;
iv) performing steps i) to iii) for each work point;
and
v) choosing as the acceptable base location domain the area which is common to all of the areas recorded in step iv);
b) determining obstacle shadows defining regions of robot base placement within the acceptable base location domain which would result in collisions between the robot and objects in the workcell;
c) determining a free acceptable base location domain by subtracting the obstacle shadows from the acceptable base location domain;
and
d) searching said free acceptable base location domain for said discrete set of locations using a modified simulated annealing technique, said modifications comprising:
i) storing local minima as they are encountered during the simulated annealing process;
ii) storing attraction areas corresponding to each of said local minima, comprising areas surrounding a local minimum data point;
iii) performing a gradient descent, by setting a temperature function of the simulated annealing method to a value of zero, when a data point from the free acceptable base location domain is encountered that is not within an attraction area;
and
iv) redefining and storing an attraction area when a gradient descent generates data points falling within an attraction area so that the attraction area includes the data point from which the gradient descent began.

13 more elements

Dependencies are inferred from the claim text.