Abstract
Automated chemical workstations capable of parallel, adaptive experimentation are well suited for performing reaction optimization. A new method for simplex-based optimization has been developed that enables multiple multidirectional search (MDS) procedures to be implemented in parallel. The MDS method employs a simplex with
Introduction
The development of automated workstations suited for experimentation in synthetic chemistry remains an ongoing challenge. 1 –15 The scope of applications of such workstations encompasses screening candidates for catalytic activity, synthesizing combinatorial libraries, synthesizing radiolabeled compounds, performing fundamental studies of chemical reactions, or searching for improved reaction conditions. Although the scope of activities is extraordinarily broad, the general design of an effective automated chemistry workstation must provide features for ease of operation, high throughput, and where appropriate, adaptive experimentation. Ease of operation requires an intuitive software environment. High throughput requires the ability to perform large numbers of reactions and analyses in parallel. Adaptive experimentation requires the ability for the user to state specific scientific objectives, the capability for on-line evaluation of incoming data from ongoing experiments, and the presence of sophisticated algorithms for automated decision making that guide experimentation in pursuit of the stated objectives. 16,17
We have been working on the development of automated chemistry workstations that are capable of parallel experimentation, adaptive serial experimentation, and selected types of parallel and adaptive experimentation, with a particular focus on performing fundamental reaction studies and optimizations in relatively clean domains of chemistry. The blend of parallel and adaptive experimentation capabilities is attractive in enabling reaction optimization to be pursued as aggressively as possible. We have developed a number of experiment-planning modules for use with the workstation 17 –26 that provide a software environment for the chemist to provide instructions about the studies to be done. Over time it is anticipated that present hardware limitations will be overcome, thereby enlarging the scope of application. 27,28
In this paper, we describe the development of a new algorithm for use in an automated chemistry workstation equipped for parallel adaptive experimentation. The algorithm is based on melding two methods that we have employed previously, a method for multiple Simplex searches in parallel and a method for multidirectional searches. The latter is a simplex-based method that affords searches in multiple directions in each cycle of experimentation (note that we use the capitalized
Results and Discussion
Overview of an Automated Chemistry Workstation
The automated chemistry workstation that we have developed is composed of hardware (multivessel reaction station, robot for moving samples and chemicals, analytical instruments, etc.) and software. The experiment manager software package includes features for composing experimental plans, managing resources (chemicals and containers), scheduling experiments (using either a rigid scheduler or a flexible scheduler) in parallel, and evaluating data. Individual experimental plans are composed in a straightforward way by drawing on a set of commands that describe operations of the robotic arm and other hardware. A timing table automatically generates the duration of each command. 30
The overall software architecture is outlined in Fig. 1.A suite of experiment-planning modules has been developed for different types of experimentation. A general-purpose (GP) module enables diverse open-loop experiments to be planned and implemented in parallel where no decision making is performed, 17,18 whereas a decision tree (DT) module enables adaptive, serial experimentation. 20 A parallel method for screening reagents or catalysts (Parascreen) has been developed as a prelude to grid searches of the active component for systematic optimization. 26 The remaining modules are designed for systematic examination of search spaces and include factorial design or grid search (FD/GS), 21 successive focused grid search (SFGS), 23 composite modified Simplex (CMS), 19 multidirectional search with mandatory points only (MDS-mo), 22 multidirectional search (MDS), 22 and parallel Simplex search (PSS). 24 Two-tiered searches can be performed whereby an initial broad survey of conditions is performed in parallel (tier 1) and then a CMS, MDS, or PSS search begins (tier 2) in the most promising area. 25 We now turn to describe the new algorithm for use in parallel adaptive experimentation.

Key components of the experiment manager software. The 10 experiment-planning modules are shown in italics in double-lined boxes. The experimental plan editor is used to compose plans for experimentation with the GP (general purpose), FD/GS (factorial design/grid search), SFGS (successive focused grid search), CMS (composite modified Simplex), MDS (multidirectional search), PSS (parallel Simplex search), PMDS' (parallel multidirectional search), and Parascreen modules, whereas a related set of functions is used in the DT (decision tree) module. *Modules fitted with the capability to perform an initial broad survey (two-tiered optimization). The resource management module and scheduler are employed to achieve parallel experimentation.
The Parallel Multidirectional Search Method
The MDS algorithm was created by Torczon 31,32,33 and Dennis and Torczon 34 to overcome the serial nature of the Simplex method. Torczon's work stemmed from considering how best to take advantage of multiple parallel processors in the computational evaluation of unconstrained optimization problems. The resulting MDS algorithm is simplex based but differs in a fundamental way from the traditional Simplex (e.g., CMS) 35 method. In a Simplex algorithm, each move occurs by reflection away from the one worst point, creating a new simplex that contains one new point regardless of search space dimension. In each move, the one worst point is discarded, and the one new point of the new simplex is evaluated. By contrast, in the MDS method, each move occurs by reflection away from all but the one best point (Fig. 2). The new simplex in

(A) The basic Simplex (i.e., CMS) move in a two-dimensional search space. In an
The MDS algorithm has a further distinction from that of a Simplex (e.g., CMS) 35 movement. In addition to those points that are required to iterate simplex projections through the space (mandatory points), exploratory points can be evaluated in each cycle of MDS to the extent that resources are available to do so. The exploratory points are identified by the look-ahead projection of possible future simplexes. Examples of the range of exploratory points that can be examined for the initial cycle are shown in Fig. 3. The number of experiments implemented per cycle depends on the dimension of the search space and the batch capacity of the workstation (which limits the number of exploratory experiments). Only one search space is investigated in a given course of experiments. The MDS method provides a means of evolutionary optimization via parallel experimentation. Thus, a Simplex search projects only one new point per cycle, whereas MDS projects at least

Projection of points in the MDS method. (A) Initial simplex. (B) The initial simplex and reflections from all vertices, with six exploratory points. (C) The initial simplex, reflections from all vertices, and expansions from all vertices, with 12 exploratory points. (D) The initial simplex, reflections from all vertices, expansions from all vertices, and reflections of all reflections, with 18 exploratory points.
The PSS method enables multiple CMS 33 searches to be performed concurrently. The Simplex searches are independent in the direction of their moves but march in lockstep. A set of experiments of number equal to m × (
The option parameters for PMDS' are identical to those in the MDS-mo method. The options are delineated below, with the range of possible values shown in parentheses. The values shown are those employed in the scenario (vide infra).
The next five options describe various termination criteria for a given experiment.
The
The
The
The
The initial starting points for PMDS' are very similar to those in PSS. Four options are available, including location in the corners, at the center of partitions, at the faces, and at the core of the space. The only difference from PSS is that the corner point simplexes must be rotated 180° from the PSS corner point projections (Fig. 4). The reason for this rotation is because the initial point projection would terminate for all simplexes (owing to out-of-boundary issues on the second cycle).

Different patterns of initial points providing different coverage of the search space (shown for a two-dimensional search space). The user can select a combination of points or define the start locations.
The PMDS' method can be applied in two distinct ways (Fig. 5). (1) Perform multiple MDS-mo searches simultaneously in one search space. The PMDS' search can terminate upon convergence of one MDS-mo search or after all MDS-mo searches converge, depending on the needs of the user. (2) Perform a single MDS-mo search in each of several search spaces. A typical application of the latter involves optimizing the reaction conditions for individual members of a set of catalysts, where each catalyst might have a different response surface.

Types of PMDS' searches. (A) Distinct concurrent MDS-mo searches in a single search space (two-dimensional). (B) Distinct search spaces each with a single MDS-mo search.
Scenario for PMDS' Operation
The potential of PMDS' was examined in the following simulation. Four individual MDS-mo searches (A-D) were performed in one search space. The options selected above cause termination to stem only from the
Template for scenarios 1 and 2
The course of each of the four individual MDS-mo searches is displayed in Fig. 6. The four searches differ because of the different starting points in the respective four quadrants of the search space. Each of the searches causes movement of the respective simplex through the search space, with moves of reflection, expansion, contraction, and fit to boundary as required. For example, search A entailed the following moves: initial simplex (cycle 1); reflect because the value of point 3 is greater than that of points 1 and 2 (cycle 2); expand because at least one of points 13 and 14 is larger than that of point 3 (cycle 3); accept the expansion and undergo reflection because point 22 has the highest value of the current simplex (cycle 4); expand because the value of point 7 is equal to that of 22 (cycle 5); reflect from the previous simplex because the expansion points 30 and 31 were less than any point in the previous simplex (cycle 6); and reject the reflection because the reflected points 31 and 37 have lesser value than point 7, and undergo a reflected contraction around the best point (point 7) in the current simplex because point 22 has higher value than any point in the prior simplex (cycle 7).
Searches B D proceed in a similar manner. Fit to boundary occurs in cycle 6 of searches B and D. In these cases, the projected point lies outside the search boundary. Accordingly, the simplex is constructed that has a point on the boundary of the search space.
Of the four parallel searches, search C first satisfies the convergence criteria, which in turn causes all other searches to stop. In so doing, all searches A D terminate at cycle 7. Indeed, the experiment to evaluate point 48 in search D was underway but was terminated when search C converged.
Each search projected 15 points (3 points in the first cycle, 2 points in each subsequent cycle), but the number actually evaluated was less than 15 because of point duplication. When points have been evaluated previously by any of the searches, the response value of the duplicate point is assumed. The duplicated points are denoted in Fig. 6. Thus, searches A and B evaluated 12 points; search C evaluated 13 points, and search D evaluated 11 points. The overall study entailed 7 cycles and required 4.8 h.

Results of the PMDS' optimization in a single search space. Four MDS-mo searches (A-D) were performed concurrently. The initial simplexes are given by points 1–3, 4–6, 7–9, and 10–12. Each cycle is color-coded (and numbered for clarity in search A). Each point that was evaluated is numbered (48 was not completed because of the convergence of the search). *Duplicate points in a given search that have been evaluated previously (points 7, 8, 13, 17, 18, 21, 22, 25, 31). † Points projected in the same cycle (points 22, 24, 28). In cycle 6 (green) of search D, the out-of-boundary projection results in projection of points 13 and 25; however, because points 13 and 25 have been previously evaluated, and given the results, contraction ensues to give points 41 and 42. The dashed green line denotes a projected simplex that was not evaluated in search D. Search C converged after 7 cycles, causing termination of searches A, B, and D.
For comparison, the overall search was again performed but was allowed to proceed until all individual MDS-mo searches converged. In this case, a total of 16 cycles was required, and the search duration was 10.3 h. Note that the four searches, if performed serially, would require 29.4 h.
Comparison of PMDS' and Related Searches
The key thesis in PMDS' is that performing multiple concurrent searches is superior to performing a single search. Multiple concurrent searches should provide more efficient attainment of the optimal region in the search space and also provide an assurance that a more global exploration of the search space has been performed. One method of benchmarking is to compare the number of cycles and duration for the overall search (PMDS') versus that for the individual searches alone.
PMDS' with the termination of any one MDS-mo search is usually slightly slower than the fastest individual MDS-mo search (search C). On the other hand, the PMDS' examination with the requirement that all MDS-mo searches terminate is generally slightly slower than the slowest individual search (search B or D). Table 2 shows that a PMDS' study with either type of termination criterion examined herein is faster than the sum of the individual MDS-mo searches if the latter are performed serially. In particular, the PMDS' study with
Comparison of efficiency of PMDS' and individual searches
No depletion of resources is premised in this simulation.
Termination criterion satisfied upon convergence of any one MDS-mo search in the set of four parallel searches.
Termination criterion satisfied upon convergence of all four of the constituent MDS-mo searches.
Totalduration.
Total duration for serial implementation of the individual searches.
In summary, we have developed a new search algorithm that blends features of the multidirectional search and the parallel Simplex search. The PMDS' method differs from the PSS method in that the former projects
Acknowledgment
The authors thank Sumitomo Chemical Co., Ltd. (Osaka, Japan) for support of this work.
