# US 10,503,846 B2 · Constructing flexible space-filling designs for computer experiments

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,503,846 B2
- Document ID: US10503846B2
- Status: Granted
- Kind: B2
- Application number: 16/154,332
- Filed: 2018-10-08
- Published: 2019-10-24
- Granted: 2019-12-10
- Earliest claimed: 2018-04-22
- Assignees: SAS Institute Inc.
- Applicants: SAS Institute Inc.
- Inventors: Ryan Adam Lekivetz; Joseph Albert Morgan; Bradley Allen Jones
- Web page: https://patentgrep.com/patent/US10503846B2

## CPC

- G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30)
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06N 3/02: Neural networks
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 20/00: Machine learning
- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06F 2111/02: CAD in a network environment, e.g. collaborative CAD or distributed simulation
- G06F 2111/04: Constraint-based CAD
- G06F 2111/20: Configuration CAD, e.g. designing by assembling or positioning modules selected from libraries of predesigned modules
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A computing device generates representative points, each representing a potential design point for a design space. The computing device determines for the design space primary clusters, a categorical factor, and at least two levels for the categorical factor. The computing device, for each of the primary clusters, selects a design point from each sub-cluster of the respective primary cluster. The computing device, for each of the primary clusters, allocates the at least two levels of the categorical factor, such that a level of the at least two levels is allocated to each selected design point in the respective primary cluster. The computing device modifies an initial sub-design that represents the selected design points allocated a given level of the categorical factor by increasing separation between design points allocated a same level of the categorical factor. The computing device outputs to an output device a modified design for the design space.

## Claims

### Claim 1

A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a computing device to:
receive information defining a boundary for a design space;
generate representative points, each distributed on or within the design space and representing a potential design point for the design space;
determine for the design space:
primary clusters, each containing a different set of the representative points that is mutually exclusive of representative points in other primary clusters of the design space;
a categorical factor, wherein the categorical factor defines a design category for the design space, the design category comprising discrete design options in the design category for the design space; and
at least two levels for the categorical factor, wherein each of the at least two levels defines different ones of the discrete design options in the design category for the design space;
for each of the primary clusters:
determine a plurality of sub-clusters, each containing different subsets of a respective set of the representative points that is mutually exclusive of representative points in other sub-clusters of a respective primary cluster of the primary clusters;
select a design point from each sub-cluster of the respective primary cluster based on a first criterion representing separation between design points in the design space; and
allocate the at least two levels of the categorical factor, such that a level of the at least two levels is allocated to each selected design point in the respective primary cluster;
obtain an initial sub-design that represents the selected design points in the design space allocated a given level of the categorical factor;
modify the initial sub-design by increasing separation between design points allocated a same level of the categorical factor in the design space; and
output to an output device a modified design for the design space, wherein the modified design represents locations for obtained design points in the design space in response to modification of the initial sub-design.

### Claim 2 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to modify the initial sub-design by swapping a first level allocated to a first selected design point and a second level allocated to a second selected design point of a primary cluster of the design space, wherein the swapping comprises:
replacing the first level allocated to the first selected design point and allocating it to the second selected design point; and
replacing the second level allocated to the second selected design point and allocating it to the first selected design point.

### Claim 3 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to modify the initial sub-design by:
obtaining an initial average representing separation of design points in the design space by:
for each of the at least two levels of the categorical factor, computing a second criterion representing separation between design points allocated a same level in the design space to obtain a plurality of computed second criterion, one for each of the at least two levels of the categorical factor; and
averaging the plurality of computed second criterion;
updating the initial average by:
determining a first candidate design point and a second candidate design point of selected design points of a primary cluster in the design space;
obtaining a swapped allocation for the design space by replacing a level allocated to the first candidate design point for the categorical factor with a level allocated to the second candidate design point for the categorical factor;
generating an updated sub-design based on the swapped allocation;
obtaining an updated average representing the separation of design points in the design space according to the swapped allocation; and
when a difference between the updated average and the initial average indicates that for a majority of the selected design points in the design space, the updated sub-design achieves a greater separation of design points of a same level than the initial sub-design, modifying the initial sub-design of the design space by:
replacing the initial sub-design with the updated sub-design; and
replacing the initial average with the updated average.

### Claim 4 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to modify the initial sub-design by, for a primary cluster, reselecting one or more design points of the representative points to replace corresponding ones of an initial design point to minimize a second criterion representing separation between design points allocated a given level.

### Claim 5 (depends on 4)

The computer-program product of claim 4, wherein each reselected design point replaces a corresponding initial design point in a same sub-cluster.

### Claim 6 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to modify the initial sub-design by:
receiving a weight for tuning a second criterion, different than the first criterion, the second criterion representing separation between design points in the design space;
selecting, using the weight for each level of the categorical factor, a design point location in the design space that is different than a design point location of the selected design points for the primary clusters; and
replacing a design point location of a selected design point for the primary clusters with the selected design point location.

### Claim 7 (depends on 6)

The computer-program product of claim 6, the instructions are operable to cause the computing device to:
map the design space onto a matrix with rows and columns; and
select the design point location by minimizing the second criterion:
min
D
⁢
ψ
⁡
(
D
)
w
=
{
1
(
n
2
)
⁢
∑
i
=
1
n
-
1
⁢
∑
j
=
1
+
1
n
⁢
I
w
⁡
(
c
i
=
c
j
)
∏
l
=
1
p
⁢
(
x
il
-
x
jl
)
2
}
1
/
p
where:
ψ(D)w is the second criterion;
i, j, l are integer counters;
w is the received weight;
n is an integer number of primary clusters for the design space;
p is an integer number of continuous variables for the design space;
xab is an entry in row a and column b of the matrix; and
Iw(cd1=cd2) is an indicator variable that is w if a categorical level cd1 allocated to a design point d1 and a categorical level cd2 allocated to a design point d2 are the same, and 1 otherwise.

### Claim 8 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device, for each primary cluster of the design space, to determine whether to change a level allocated to a design point of a sub-cluster of the respective primary cluster of the design space.

### Claim 9 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device, for each primary cluster of the design space, to determine whether to select a replacement design point location for a design point in the respective primary cluster that increases separation between design points allocated a level of the categorical factor in the design space.

### Claim 10 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to modify the initial sub-design by:
performing a first modification, the first modification comprising swapping a first level allocated to a first selected design point and a second level allocated to a second selected design point of a primary cluster of the design space;
performing a second modification, the second modification comprising replacing a representative point of the generated representative points with the first selected design point allocated a second level.

### Claim 11 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to determine the primary clusters using hierarchical clustering.

### Claim 12 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to:
map the design space onto a matrix with rows and columns; and
for each of the primary clusters, select a design point from each sub-cluster of the respective primary cluster by minimizing the first criterion:
min
D
⁢
ψ
⁡
(
D
)
=
{
1
(
n
2
)
⁢
∑
i
=
1
n
-
1
⁢
∑
j
=
1
+
1
n
⁢
1
∏
l
=
1
p
⁢
(
x
il
-
x
jl
)
2
}
1
/
p
where:
ψ(D) is the first criterion;
i, j, l are integer counters;
n is an integer number of primary clusters for the design space;
p is an integer number of continuous variables for the design space; and
xab is an entry in row a and column b of the matrix.

### Claim 13 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause a computing device to:
display, on a display device, a graphical user interface for user entry of information defining the boundary for the design space and selection of criteria related to the categorical factor and the at least two levels;
receive information defining the boundary by receiving, as user input via one or more input devices, information representing a non-rectangular boundary for the design space;
receive the selection; and
output to the output device a graphical representation of the design space with the non-rectangular boundary.

### Claim 14 (depends on 1)

The computer-program product of claim 1, wherein a dimension of the design space represents a continuous variable for the design space.

### Claim 15 (depends on 1)

The computer-program product of claim 1, wherein the design space comprises more than two dimensions.

### Claim 16 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to receive information defining an integer number of the primary clusters.

### Claim 17 (depends on 1)

The computer-program product of claim 1, wherein the instructions are operable to cause the computing device to output the modified design by outputting information to the output device representing locations of the obtained design points in a display of the design space.

### Claim 18 (depends on 1)

The computer-program product of claim 1, wherein the design space is a computer-simulated model representing a physical object or representing an environment for placement of one or more physical objects at each of the obtained design points.

### Claim 19

A computer-implemented method comprising:
receiving information defining a boundary for a design space;
generating representative points, each distributed on or within the design space and representing a potential design point for the design space;
determining for the design space:
primary clusters, each containing a different set of the representative points that is mutually exclusive of representative points in other primary clusters of the design space;
a categorical factor, wherein the categorical factor defines a design category for the design space, the design category comprising discrete design options in the design category for the design space; and
at least two levels for the categorical factor, wherein each of the at least two levels defines different ones of the discrete design options in the design category for the design space;
for each of the primary clusters:
determining a plurality of sub-clusters, each containing different subsets of a respective set of the representative points that is mutually exclusive of representative points in other sub-clusters of a respective primary cluster of the primary clusters;
selecting a design point from each sub-cluster of the respective primary cluster based on a first criterion representing separation between design points in the design space; and
allocating the at least two levels of the categorical factor, such that a level of the at least two levels is allocated to each selected design point in the respective primary cluster;
obtaining an initial sub-design that represents the selected design points in the design space allocated a given level of the categorical factor;
modifying the initial sub-design by increasing separation between design points allocated a same level of the categorical factor in the design space; and
outputting to an output device a modified design for the design space, wherein the modified design represents locations for obtained design points in the design space in response to modification of the initial sub-design.

### Claim 20 (depends on 19)

The method of claim 19, wherein the modifying the initial sub-design comprises swapping a first level allocated to a first selected design point and a second level allocated to a second selected design point of a primary cluster of the design space, wherein the swapping comprises:
replacing the first level allocated to the first selected design point and allocating it to the second selected design point; and
replacing the second level allocated to the second selected design point and allocating it to the first selected design point.

### Claim 21 (depends on 19)

The method of claim 19, wherein the modifying the initial sub-design comprises:
obtaining an initial average representing separation of design points in the design space by:
for each of the at least two levels of the categorical factor, computing a second criterion representing separation between design points allocated a same level in the design space to obtain a plurality of computed second criterion, one for each of the at least two levels of the categorical factor; and
averaging the plurality of computed second criterion;
updating the initial average by:
determining a candidate design point and another candidate design point of selected design points of a primary cluster in the design space;
obtaining a swapped allocation for the design space by replacing a level allocated to the candidate design point for the categorical factor with a level allocated to the another candidate design point for the categorical factor;
generating an updated sub-design based on the swapped allocation;
obtaining an updated average representing the separation of design points in the design space according to the swapped allocation; and
when a difference between the updated average and the initial average indicates that for a majority of the selected design points in the design space, the updated sub-design achieves a greater separation of design points of a same level than the initial sub-design, modifying the initial sub-design of the design space by:
replacing the initial sub-design with the updated sub-design; and
replacing the initial average with the updated average.

### Claim 22 (depends on 19)

The method of claim 19, wherein the modify the initial sub-design comprises, for the primary cluster, reselecting one or more design points of the representative points to replace corresponding ones of an initial design point to minimize a second criterion representing separation between selected design points allocated a given level.

### Claim 23 (depends on 22)

The method of claim 22, wherein each reselected design point replaces a corresponding initial design point in a same sub-cluster.

### Claim 24 (depends on 19)

The method of claim 19, wherein the method further comprises:
receiving a weight for tuning a second criterion, different than the first criterion, the second criterion representing separation between design points in the design space;
selecting, using the weight for each level of the categorical factor, a design point location in the design space that is different than a design point location of the selected design points for the primary clusters; and
replacing a design point location of a selected design point for the primary clusters with the selected design point location.

### Claim 25 (depends on 24)

The method of claim 24, wherein the method further comprises:
mapping the design space onto a matrix with rows and columns; and
wherein the selecting the design point location comprises minimizing the second criterion:
min
D
⁢
ψ
⁡
(
D
)
w
=
{
1
(
n
2
)
⁢
∑
i
=
1
n
-
1
⁢
∑
j
=
1
+
1
n
⁢
I
w
⁡
(
c
i
=
c
j
)
∏
l
=
1
p
⁢
(
x
il
-
x
jl
)
2
}
1
/
p
where:
ψ(D)w is the second criterion;
i, j, l are integer counters;
w is the received weight;
n is an integer number of primary clusters for the design space;
p is an integer number of continuous variables for the design space;
xab is an entry in row a and column b of the matrix; and
Iw(cd1=cd2) is an indicator variable that is w if a categorical level cd1 allocated to a design point d1 and a categorical level cd2 allocated to a design point d2 are the same, and 1 otherwise.

### Claim 26 (depends on 19)

The method of claim 19, wherein the method comprises determining, for each primary cluster of the design space, whether to change a level allocated to a design point of a sub-cluster of the respective primary cluster of the design space.

### Claim 27 (depends on 19)

The method of claim 19, wherein the method comprises determining, for each primary cluster of the design space, whether to select a replacement design point location for a design point in the respective primary cluster that increases separation between design points allocated a level of the categorical factor in the design space.

### Claim 28 (depends on 19)

The method of claim 19, wherein the modifying the sub-design comprises:
performing a first modification, the first modification comprising swapping a first level allocated to a first selected design point and a second level allocated to a second selected design point of a primary cluster of the design space;
performing a second modification, the second modification comprising replacing a representative point of the generated representative points with the first selected design point allocated a second level.

### Claim 29 (depends on 19)

The method of claim 19, wherein the method comprises determining for the design space the primary clusters using hierarchical clustering.

### Claim 30

A computing device comprising processor and memory, the memory containing instructions executable by the processor wherein the computing device is configured to:
receive information defining a boundary for a design space;
generate representative points, each distributed on or within the design space and representing a potential design point for the design space;
determine for the design space:
primary clusters, each containing a different set of the representative points that is mutually exclusive of representative points in other primary clusters of the design space;
a categorical factor, wherein the categorical factor defines a design category for the design space, the design category comprising discrete design options in the design category for the design space; and
at least two levels for the categorical factor, wherein each of the at least two levels defines different ones of the discrete design options in the design category for the design space;
for each of the primary clusters:
determine a plurality of sub-clusters, each containing different subsets of a respective set of the representative points that is mutually exclusive of representative points in other sub-clusters of a respective primary cluster of the primary clusters;
select a design point from each sub-cluster of the respective primary cluster based on a first criterion representing separation between design points in the design space; and
allocate the at least two levels of the categorical factor, such that a level of the at least two levels is allocated to each selected design point in the respective primary cluster;
obtain an initial sub-design that represents the selected design points in the design space allocated a given level of the categorical factor;
modify the initial sub-design by increasing separation between design points allocated a same level of the categorical factor in the design space; and
output to an output device a modified design for the design space, wherein the modified design represents locations for obtained design points in the design space in response to modification of the initial sub-design.