California State University, Fresno, California 93740-0018

January 1991

Clustering Algorithms for Sprinkler System Layout
By Kenneth H. Solomon

The layout and design of a sprinkler system involve both art and science. For this reason, the development of computer algorithms for layout and design has been difficult, and most existing computer software addresses only parts of the problem. The normal sprinkler system layout and design process include the following steps:

- Select which sprinkler heads are to be used in the system;
- Decide where the sprinkler heads are to be placed throughout the area to be irrigated;
- Subdivide the sprinkler heads into groups, so that each of the sprinkler heads within
  agroup will be connected to, and operated by a single valve;
- Determine piping routes are to connect the heads in each group to their valve; and
- Compute the appropriate size for each of the pipe segments.

The objective of this study is to develop one or more algorithms or methodologies to identify "clusters" (groups) of full and part circle sprinkler heads in an irrigated area. It is assumed that the sprinklers to be used have been selected, and their flow rates and locations are known, but the appropriate grouping of the sprinklers is unknown. The number of clusters should be chosen to maximize the use of water source capacity, while balancing the total flow rate in each of the clusters. Each cluster may contain a different number of heads. The algorithms developed should be computationally rapid and converge quickly to realistic solutions.

Proximity is an important factor in sprinkler-valve assignment. It is natural to try to connect sprinklers that are close to each other to the same valve. Unfortunately, the entire rationale for forming clusters of sprinklers is not fully quantifiable. Judgmental factors such as aesthetics, installation and operational convenience must be considered in addition to hydraulic and cost considerations. The approach taken here will be to base the clustering process on strictly quantifiable criteria. Any interactive software employing these algorithms will allow the designer to manually adjust clusters to accommodate judgmental considerations. Thus the sprinkler heads will be clustered according to proximity.

The general solution to this clustering problem will entail three basic steps:

· Determine how many clusters to look for;
· Group sprinkler heads into clusters; and
· Evaluate the results.

The evaluation process is fairly complex, since it involves the judgmental factors mentioned above, and will be left to the user. One or more sets of results should be displayed, and the user allowed to choose between them, to manually adjust the clusters displayed, or to request an automatic re-do of the clustering process. This latter may be necessary should the user wish to view a clustering based on a different number of valves (clusters), or in the event the clustering process has resulted in impractical clusters.

In many clustering problems, the "proper" number of clusters to look for is assumed to be a property of the structure of the data set (the points to be clustered). One approach is to cluster the data set many times, assuming 2, then 3, then 4, etc. clusters are to exist, and then to compare the answers from each of these clustering subproblems using some sort of "error" measure. A common sense property of "natural" clusters is that the distances between points within a cluster are less than distances between points from different clusters. This suggests an error measure such as the total within-cluster distance between data points, or between data points and their respective cluster centroids (Solomon and Bezdek, 1980).

This criterion cannot be used exclusively, though, because these error measures decrease steadily as the number of clusters increases. To see this, consider the extreme case, where there there are n data points and one looks for n clusters. Each cluster will contain exactly one point, and all within-cluster distances and all distances between points and cluster centroids will be zero. A compromise is to use the least number of clusters possible for which the error does not become excessive. In general, these concepts must be determined subjectively, since without prior knowledge of the structure of the data set, it is impossible to predetermine an acceptable error level.

Within the present context, the physical (hydraulic) situation allows a slightly different approach. It is not desirable use more clusters than necessary, since that means additional valves and expense. Furthermore, the minimum number of valves (clusters) possible can be computed in advance.

Suppose, for example, that the water source can supply water at a flow rate not to exceed 10 GPM, and the sum of the individual flow rates of the sprinklers in an area is 25 GPM. It is easy to see that since 25 ÷ 10 = 2.5, at least 3 valves must be used. This concept can be formalized as follows.

If the maximum water supply flow rate is Q, and the sum of individual sprinkler flow rates is å qi, then there must be at least ( å qi/Q) valves. Let N equal the integer portion of ( å qi/Q). (For example if å qi/Q = 5.83, the integer portion would be 5, and N = 5.) If ( å qi/Q) should be an integer, it may be possible to get by with N valves. If ( å qi/Q) is not an integer, then N + 1 valves will be required as a minimum.

Depending on how the process of assigning heads to clusters goes, it may not be possible to get by with this theoretical minimum number of valves. Furthermore, a more natural grouping may result if one or more extra valves are allowed. Therefore, the approach to setting the number of clusters, NC, is as follows:

1. Identify the minimum number of valves possible:
a. If ( å qi/Q) is an integer, NC = N
b. If ( å qi/Q) is not an integer, NC = N + 1

2. Attempt to cluster the sprinkler heads into NC clusters.
a. If this results in an infeasible grouping (where

the total flow rate in one or more clusters exceeds Q), then increment NC and repeat

step 2.

b. If this results in a feasible grouping (the total flow