Modeling, Analysis, Simulation, and Control of Laboratory Automation Systems Using Petri Nets—Analysis and Control

Introduction 

In part one of this series,1 we discussed the potential of adaptive and dynamically controlled laboratory automation systems and compared these systems to those more common found in the laboratory, which are designed to use static procedures and fixed control sequences. We explained how dynamically controlled systems are susceptible to problems such as deadlock, unreachable states, buffer overruns, and unpredictable throughput rates. To make the application of dynamically controlled systems more practical, powerful tools must be available to identify potential problems and to suggest ways to avoid them through judicious controller design. The field of Petri nets offers a rich and comprehensive theory that can form the basis of one such set of tools.2, 3, 4, 5 Applications of Petri nets to automated laboratory systems have begun to emerge.6

As a graphical formalism, Petri nets are very powerful. But the true power comes from the results that can be obtained through an analysis of a mathematical description. Many useful properties can be calculated, some of which are critical to the proper design of a dynamically controlled system. For example, Petri net models of dynamically controlled laboratory automation systems can be used to determine if the system can deadlock, as well as its potential sample throughput. Analysis can also aid in the determination of controller schemes that guarantee desired behavior or avoid unwanted states.

The application of the variety of mathematical results from Petri net theory can be tedious without the help of a software tool. Fortunately, many tools exist and several are freely available.7 One particularly useful tool is called the Platform Independent Petri net Editor 2 (PIPE2).8 PIPE2 is a flexible tool for graphically sketching Petri net models and automatically performing a variety of mathematical analyses.

Background 

We begin this tutorial with a formal mathematical description. A Petri net (N) is made up of four items (a four-tuple):

(1)

P is a finite nonempty set of n places.

T is a finite nonempty set of m transitions.

P∩T=∅; that is, no single node in a Petri net can be both a place and a transition (P and T are disjoint sets).

F⊂(P×T)∪(T×P); where F is the flow relation (set of directed arcs). F is the set of directed arcs of a Petri net. These arcs can only connect places to transitions or transitions to places. Other connections are forbidden.

W: F→N+; that is, each directed arc is assigned a weight, which is a positive natural number (1, 2, 3, …).

As described in the previous installment of this tutorial series,1 places can contain tokens that flow through a Petri net as it executes. The direction of this flow is defined by F, the flow relation. The flow relation can be described in more detail using an incidence matrix. An incidence matrix, also known as a flow matrix, quantifies how the marking of a Petri net changes as each transition fires. For a Petri net with n places and m transitions, the incidence matrix C=[cij] is an n×m integer matrix defined by,

(2)

As an example, consider the matrix equation labeled (3). This is the incidence matrix for the Petri net of Figure 1. Rows and columns are labeled with the places and transitions that they represent.

(3)

View Large Image Download to PowerPoint

Figure 1 A simple Petri net with place interpretations.

A marking M of a Petri net N is the assignment of a non-negative integer to each place in N. Each non-negative integer value determines the number of tokens within the corresponding place. The initial marking of N is denoted M0. A marking is denoted as a column vector of length n, where n is the number of places in N. The number of tokens in the ith place is equal to the ith element of M. M is called the state vector of N because it represents the state of the net. The marking of the Petri net in Figure 1 is given as (4).

(4)

Given the incidence matrix C of a Petri net and a specific marking Mi, it is possible to define how the Petri net will evolve to a subsequent state Mj using a simple matrix equation often referred to as the state equation. Equation 5 is the state equation of a Petri net.

(5)

The term f in (5) is called the firing count vector. It is a vector of length m, where m is the number of transitions in a Petri net. Each element of the firing count vector determines the number of times that a specific transition is fired as it changes from state Mi to Mj. Each element of f must be ≥0. The order of the elements of the firing count vector corresponds with the transition number in the Petri net.

As an example, consider once again the Petri net in Figure 1, the incidence matrix of (3), and the initial marking of (4). We substitute the initial marking for the term Mi and the incidence matrix for the term C of (5). If we want to fire transition t1 once, we would use the firing count vector .

After substituting, the resulting state equation would look as follows.

(6)

Multiplying, we obtain the new marking M1 (7), which is a vector of length n that defines the number of tokens in each place of the system after firing t1.

(7)

A transition-firing sequence can be combined into one firing count vector by summing the individual firing count vectors in the sequence. The result of the vector summation can be substituted for f in (5) to calculate the new state Mj that results from the firing sequence, when applied to the Petri net in state Mi.

It is important to note that a firing count vector, when applied at a particular step in the evolution of a Petri net, must be supported by the Petri net's current marking. For a firing count vector to be supported, the firing transitions must be enabled at each step, and there must be a sufficient number of tokens in the corresponding input places to fully execute the firing. Otherwise, the evolution of the Petri net is not valid. If the firing of a transition is not properly supported by the current marking, the element in the firing vector corresponding to the transition must have a value of zero (i.e., it cannot fire).

Marking Mj is said to be reachable from marking Mi if there is a sequence of supported transition firings that will evolve a Petri net from Mi to Mj. It is said that Mj is in the set of reachable markings for the Petri net N, which is in the state defined by Mi. We denote this using the following notation.

(8)

Firing count vector combinations must result from the summation of individual firing count vectors that are all properly supported by the current marking when each is applied. Without this constraint on f, it is not possible to guarantee that the state Mj is reachable from a state Mi through one or more transition firings. Stated in another way, for the marking Mj to be reachable from Mi in a net N with the incidence matrix C, it is necessary (but not sufficient) for there to exist a solution for f in (5). Unfortunately, (5) may have spurious solutions for f, which cannot be constructed from a sequence of supported firing vectors, hence, the converse is not true; if a solution f of (5) exists then Mj may or may not be reachable from a Mi. We will find that these spurious solutions frequently can be eliminated or avoided in practice.

Subclasses 

Petri nets have been classified into a variety of subclasses, depending upon the details of their structure and other properties.5 Petri net subclasses are important because additional mathematical results are often available for defined subclasses. If a Petri net can be classified within a subclass, these additional mathematical results can be applied as new analytical tools.

Laboratory automation systems can be modeled as discrete event systems.5 Finite state machines have been used extensively as a tool to model, analyze, and control discrete event systems. Unfortunately, finite state machines suffer from a number of shortcomings.9 For practical systems, the number of states increases exponentially as the system gets larger, making the model increasingly difficult to visualize and analyze.

Petri nets do not suffer the same increase in complexity as the system gets larger because state is represented by the current marking. The state of a Petri net is identified by the distribution of tokens over its nodes rather than being confined to a single node, as is the case with a finite state machine. The result is a more expressive and more compact representation of state.10

In fact, when suitably restricted, a common subclass of Petri nets is equivalent to finite state machines (see Fig. 2). If the structure of a Petri net is constrained so that each transition has only one incoming arc and one outgoing arc, the Petri net is essentially a finite state machine. Typically, only one state of a simple finite state machine is active at any time. In a Petri net modeling a finite state machine, the place containing a token represents the current state of the system.

View Large Image Download to PowerPoint

Figure 2 A sample Petri net representing the finite state machine subclass.

Petri nets that limit each place to one incoming and one outgoing arc are known as event graphs. A strongly connected event graph has a directed path joining any node to any other node. Event graphs are commonly used to describe systems that operate on a cyclical basis. Event graphs are also used to model Project Evaluation and Review Technique (PERT) charts commonly used in project management.

The concept of a transition can be extended by assigning a nonzero execution duration. When durations are assigned to the transitions of an event graph, the entire Petri net is referred to as a timed event graph. Transition durations estimate the length of time it takes to execute a transition. Strongly connected timed event graphs have special properties that make them useful for cycle time estimation and optimization (Fig. 3).

View Large Image Download to PowerPoint

Figure 3 A sample Petri net representing the event graph subclass.

Invariants 

One of the more useful properties of a Petri net is the invariant. Invariants are assertions that are guaranteed to be true in all reachable states of a given Petri net, regardless of how it evolves. A Petri net can possess two kinds of invariants: place invariants (p-invariants) and transition invariants (t-invariants). Invariants are used as the basis for deriving other useful Petri net properties and controller schemes.

t-Invariants are important because they identify transition-firing sequences that have the potential to evolve the marking of a Petri net away from, and then back to some initial state. It must be possible to enable all t-invariant transitions in a manner that supports the firing sequence. In reality, external factors such as equipment failures may make this impossible. If we have a sequence of supported firing count vectors that cause a Petri net to evolve from an initial marking back to that identical marking, then we say that the firing sequence is a t-invariant. t-Invariants are important in Petri net models of laboratory automation systems because they relate to the system's ability to recover from an error. If a system starts to evolve down a path, and some event occurs that requires the system to recover and move back to its original state, the existence of a t-invariant in the Petri net model guarantees that the recovery is possible.

For a t-invariant to exist, it must be true that . From (5), the following must hold.

(9)

Therefore, if we can find a solution for f that satisfies the equation C·fT=0, then f is a t-invariant of the Petri net.

p-Invariants identify closed circuits of a Petri net in which the number of tokens is conserved regardless of the Petri net's current state. In other words, the total number of tokens in all places of a circuit identified as p-invariant remains constant throughout the lifetime of a Petri net. p-Invariants are called token conservation laws for obvious reasons. Places in a closed circuit of a p-invariant are called the support of the invariant.

To understand how p-invariants are determined, multiply both sides of (5) by the vector y, which is of length n.

(10)

If y·C=0, then y·Mj=y·Mi. Because Mj and Mi can represent any two reachable markings of a Petri net, the vector y identifies a set of places in which the sum of tokens does not change, irrespective of the firing sequence. The vector y is said to be a p-invariant of the Petri net, and can be calculated by solving the following equation.

(11)

New p-invariants can be formed from linear combinations of other p-invariants. A minimal support p-invariant vector is non-negative and forms part of the basis of a vector space defining all possible p-invariants. In other words, minimal support p-invariants are such that no element of the set can be obtained from a linear combination of the others. By contrast, linear combinations of minimal support p-invariants can represent all valid p-invariants of the system.

Algorithms have been outlined for calculating the invariants of a Petri net,11 and several tools are available that perform these calculations automatically.8, 12, 13

To demonstrate the calculation of p-invariants, consider the Petri net in Figure 4.

View Large Image Download to PowerPoint

Figure 4 A Petri net with p-invariants.

This is a model of an automated laboratory system designed to move microplates from an input incubator into a microplate reader for data collection, and then to an output incubator for storage. Plates awaiting analysis are located in place p1. In the current model, there are three tokens in p1 indicating that three plates are waiting to be read. Transition t1 cannot fire unless the robot is available and there is at least one plate waiting to be read.

A token in p2 indicates that the system is currently fetching a plate from the incubator. After the plate has been fetched, if the reader is available the plate is placed in the reader (p3) and reading is initiated (p4). Note that when t3 is fired and reading begins, a token is moved back to p8 to indicate that the robot is available for other tasks.

When the reader finishes, if the robot is available, t4 fires and the robot gets the plate from the reader (p5). When the transition t5 fires, the reader (p9) is released for additional tasks and the robot moves the plate back to the incubator (p6). When t6 fires, a token is returned to p8 and the robot is available for other tasks. Transition t6 also puts a token into the output buffer p7.

Equation 12 is the incidence matrix for the model of Figure 4. Substituting (12) into (11) and solving for y, the p-invariants of (13) are obtained. By factoring in the initial number of tokens in each p-invariant circuit, we can write them as the token conservation equations of (14). These p-invariants correspond to the subnets depicted in Figure 5.

(12)

(13)

(14)

View Large Image Download to PowerPoint

Figure 5 Three subnets corresponding to the p-invariants of Figure 4.

The three subnets of Figure 5 clearly indicate which resources are being conserved. The subnet on the left of Figure 5 conserves plates in the system, the subnet in the middle conserves the robot resource, and the subnet on the right conserves the plate reader resource.

p-Invariants are useful in a wide variety of analysis procedures. On their own, p-invariants verify that a Petri net model exhibits the expected conservation rules. In the case of the Petri net of Figure 4, we expect the robot and reader resources to be conserved. Also, we do not expect to create or destroy microplates in the model. These expectations are confirmed. Another use for p-invariants is to discover conservation laws that might not initially be obvious. Finally, p-invariants are used as an important initial set of facts for several subsequent structural analyses, as we shall see in the following.

Deadlock 

If a system has reached a state in which it is completely unable to function, such as that resulting from a misallocation of resources, the system is said to be deadlocked. As mentioned earlier, a trade-off for gaining the flexibility of dynamically controlled systems is the potential for the system to deadlock. This flaw in design can often be detected and designed out of the system right up front. In this section, one method for detecting deadlock in a Petri net model will be demonstrated.

Deadlock occurs when no transition can be enabled. The entire system stops all progress and is unable to proceed. For a Petri net to deadlock, all transitions must not be enabled. At least one input place of every transition must have an empty marking. By combining these conditions with a system's p-invariant, it is possible to calculate Petri net markings that exhibit deadlock.

Once again, consider the Petri net of Figure 4. For this model to deadlock the Petri net must be able to reach a state in which no transitions can be enabled. In other words, there must be insufficient markings in the input places of all transitions. By considering each transition of the Petri net in turn, we can write down the conditions that must be satisfied at deadlock. These are listed in Table 1.

Table 1. Conditions for deadlock in the Petri net of Figure 4

	Transition	Condition at deadlock
	t1	M(p8)=0
	t2	M(p2)+M(p9)≤1
	t3	M(p3)=0
	t4	M(p4)+M(p8)≤1
	t5	M(p5)=0
	t6	M(p6)=0

Before proceeding, a few comments are in order. Clearly, when the input incubator is emptied of all microplates, the system will deadlock. This is expected and ignored by assuming that the input incubator contains a large number of plates. Given that assumption, the only way for transition t1 to be enabled is for place p8 to contain at least one token. A lack of tokens in p8 means t1 cannot be enabled. As a result, the condition associated with t1 in Table 1 states that input place p8 must contain zero tokens. The impact of tokens in p1 is ignored.

Transitions t2 and t4 have multiple input places. These transitions cannot be enabled when any input place contains no tokens. The maximum number of tokens in any place of this Petri net, other than in p1 and p9, is 1. As a result, transitions t2 and t3 will not be enabled if the sum of tokens of their input places is less than or equal to 1 less than the number of input places. Each has two input places; therefore, the sum of tokens in both cases must be less than or equal to 1 to prevent the associated transition from being enabled.

Transitions t3, t5, and t6 each have a single input place. The number of tokens in each corresponding input place must be zero to prevent the transition from being enabled. The conditions of Table 1 combined with the p-invariants of (14) form the constraints of an integer-programming problem.14 We can complete the integer-programming problem specification by adding an optimization condition, such as the minimization of the total number of tokens in nonbuffer places. The complete integer-programming problem specification for the deadlock problem is given as LP 1. In this specification, we attempt to minimize the total number of tokens in places p2, p3, p4, p5, p6, p8, and p9. Problems such as this one are readily solved using mixed integer linear-programming (LP) solvers such as lpsolve.15

A solution to the problem of LP 1 can be found and is given as (15). This solution corresponds to the marking in the Petri net of Figure 6. If this marking is reachable from the initial marking of the system, it is possible for the Petri net to deadlock.

	Minimize	M(p2)+M(p3)+M(p4)+M(p5)+M(p6)+M(p8)+M(p9)
	p-Invariant	M(p1)+M(p2)+M(p3)+M(p4)+M(p5)+M(p6)+M(p7)=3
	p-Invariant	M(p2)+M(p3)+M(p5)+M(p6)+M(p8)=1
	p-Invariant	M(p3)+M(p4)+M(p5)+M(p9)=1
	At deadlock	M(p8)=0
	At deadlock	M(p2)+M(p9)≤1
	At deadlock	M(p3)=0
	At deadlock	M(p4)+M(p8)≤1
	At deadlock	M(p5)=0
	At deadlock	M(p6)=0

View Large Image Download to PowerPoint

Figure 6 The Petri net of Figure 4 in a deadlock condition.

LP 1: Complete integer-programming problem specification for deadlock.

(15)

A careful analysis of the marking of Figure 6 reveals the state of the system at deadlock. One plate is in the plate reader waiting to be removed by the robot, but the robot is busy moving a plate from the incubator and is waiting to place it into the reader. Both the robot and plate reader resources are busy waiting for the other to be available before proceeding.

It is important to note that the existence of a solution to the problem in LP 1 does not guarantee that deadlock exists. Spurious solutions may exist, but represent states of the system that are not reachable from the initial marking. For this reason the approach described here is called a semidecision procedure; the existence of a solution is necessary but not sufficient to guarantee deadlock. On the other hand, the lack of a solution guarantees that the system will not deadlock. The existence of a reachable solution of LP 1 represents a possible flaw of the system design if it is allowed to run under dynamic control.

One way to remove deadlock from this design is to delete the arc that connects p9 to t2 and add a new arc that connects p9 to t1 (see Fig. 7). This accomplishes the same task but requires that the reader be ready before the robot initiates the process of getting a plate from the incubator.

View Large Image Download to PowerPoint

Figure 7 Deadlock designed out of the system.

To verify that this new design cannot deadlock, repeat the analysis procedure. The complete problem formulated as a new integer-programming problem is given in LP 2. Because no solution exists that satisfies these equations, the system under dynamic control will not deadlock.

	Minimize	M(p2)+M(p3)+M(p4)+M(p5)+M(p6)+M(p8)+M(p9)
	p-Invariant	M(p1)+M(p2)+M(p3)+M(p4)+M(p5)+M(p6)+M(p7)=3
	p-Invariant	M(p2)+M(p3)+M(p5)+M(p6)+M(p8)=1
	p-Invariant	M(p2)+M(p3)+M(p4)+M(p5)+M(p9)=1
	At deadlock	M(p8)+M(p9)≤0
	At deadlock	M(p2)=0
	At deadlock	M(p3)=0
	At deadlock	M(p4)+M(p8)≤1
	At deadlock	M(p5)=0
	At deadlock	M(p6)=0

LP 2: The integer-programming problem specification with deadlock designed out.

Controllers 

Petri nets have been widely studied and applied as a tool for developing controllers for a variety of discrete event systems, especially manufacturing.4 Due to the similarity between dynamically controlled laboratory automation systems and flexible manufacturing systems, results apply equally well in both cases.

The Petri net model of Figure 4 is relatively high level when considering the detailed interactions that are necessary between the robot and incubator, or the robot and plate reader. The process of coordinating the hand-off of microplates must be carefully orchestrated to ensure that no mishaps occur. This is especially true with dynamically controlled systems. Careful design of Petri net controllers can ensure desired behavior.

Consider place p2 in Figure 4, which is labeled “Get plate from incubator.” When a token occupies this place it is understood that the robot is interacting with the incubator to fetch a new plate that is destined for the plate reader. The interaction between these two devices must be carefully considered.

One common incubator design used in laboratory automation uses a small door that is opened temporarily to allow the robot to reach in and retrieve a microplate. The small door ensures that the environmental conditions within the incubator are disturbed as little as possible while providing access to the robot. When the two devices interact, the system controller must ensure that the incubator door is open before the robot attempts to reach in and remove a new plate. Likewise, the robot must remove its arm from the incubator before the incubator closes its door. Violation of either of these constraints can have catastrophic results.

Figure 8 represents the starting point for a Petri net model that will govern interaction between the robot and the incubator resources. This model will form the core of a second subordinate Petri net that executes while the primary Petri net of Figure 4 has a token in either place p2 or place p6.

View Large Image Download to PowerPoint

Figure 8 Initial Petri net model of robot-incubator interaction.

The initial Petri net includes four places—two represent the two states of the incubator (door open and door closed) and the remaining two represent the two locations of the robot (inside incubator and outside incubator). The problem with this model is that there is nothing to prevent the forbidden states. It is possible for the robot to enter the incubator while the door is closed, or for the incubator door to close while the robot is in the incubator. The problem is to design a controller that prevents either of these occurrences.

Petri net controllers can themselves be comprised as augmentations of the original Petri net. That is to say, the controller itself can be comprised of additional places, transitions, and arcs. This has the advantage that the controller is fully part of the Petri net and therefore subject to all the same analytical procedures and other tools. One method for designing a Petri net controller makes use of the definition of p-invariants (11).

As we have seen, p-invariants are token conservation rules that are inherent to the system's behavior. They represent core properties of a given Petri net. Designing a controller can be thought of as the act of imposing new constraints on system behavior.16 If controlled behavior can be expressed as new token conservation rules, the equation that defines p-invariants can be used to back calculate the Petri net configuration that satisfies these constraints.

To illustrate the process, let's calculate the necessary controller (Petri net augmentations) to ensure that the robot and incubator do not collide in the model of Figure 8. Start by deriving the incidence matrix and calculating the p-invariants of Figure 8 using (11). The two conservation rules derived from the solutions of (16) are given in (17). It is not hard to confirm their validity.

(16)

(17)

The state that we wish to forbid in the Petri net of Figure 8 is the one in which both p1 and p3 are simultaneously occupied. This corresponds to the situation in which the robot is in the incubator while the incubator door is closed. To forbid the system from ever entering this state, we want to enforce the constraint that . If this constraint is satisfied, the system will never enter the forbidden state.

The form of this new constraint is not consistent with a p-invariant. p-Invariants are equations, not inequalities. Fortunately, we can borrow a trick from linear-programming problem formulation14 and convert the inequality to an equation by introducing a slack variable, which corresponds to the marking of a new place in the system. The new place will be called p5, and the new equation that must be satisfied is given as (18), which must be added to the p-invariants of (17). The new Petri net design that must satisfy the constraints of (17) and (18) is given in Figure 9. Note the addition of the new controller place p5. What remains to be determined is how this place is connected to the rest of the Petri net to enforce the new constraint as well as its initial marking.

(18)

View Large Image Download to PowerPoint

Figure 9 A first step in controller design.

To derive the arcs that connect this new place to the remainder of the Petri net, we can expand (16) to introduce these unknowns. The expanded form is given as (19). Note that each element of this equation has been expanded to include a fifth row to accommodate the new place p5. The new constraint that imposes the desired controller behavior is substituted into the values of the y vector on the left. The coefficients in the fifth row of the incidence matrix are the new unknowns.

Equation 19 is readily solved. The solution, given in (20) determines how the new Petri net must be configured to satisfy the controller constraint (see Fig. 10). In addition, the initial marking of p5 can be determined by substituting what we already know about the initial marking of the Petri net into (18) and solving for M(p5). In this case, the initial marking of p5 is 0.

(19)

(20)

View Large Image Download to PowerPoint

Figure 10 Controlled Petri net.

Let's verify the operation of the newly controlled Petri net of Figure 10. The only transition that is initially enabled is t1. This is the desired behavior as we expect the incubator door to open before the robot can move inside the incubator. Once t1 fires and the incubator door opens, a token is removed from place p1 and a token is added to places p2 and p5. At this point transitions t2 and t3 are both enabled. This implies that either the incubator door can now close (t2) or the robot can enter the incubator (t3). If t3 fires, the robot is moved into the incubator. Tokens are removed from places p4 and p5 and a new token is added to p3 to indicate that the robot is in the incubator. Place p5 no longer contains a token so the incubator door cannot close (t2), which is desired. When transition t4 fires, the robot is moved out of the incubator and tokens are added to places p4 and p5. Once again transitions t2 and t3 are enabled. This implies that the robot can reenter the incubator, or the incubator door can close. If transition t2 fires, the incubator door is closed and a token is removed from places p5 and p2. A new token is also added to p1. The new controller enforces the desired behavior.

Performance 

A Petri net model of a laboratory automation system can be used to better understand the expected throughput performance of a design, as well as to optimize a design for a prespecified performance level. The subclass of Petri nets called event graphs with timed transitions, introduced previously, is suitable for this purpose.

By definition, timed event graphs are conflict free. Because each place is limited to at most one input and one output arc, a timed event graph will never include constructs like the one depicted in Figure 11. Tokens in place p1 enable both transition t1 and transition t2. The transition that is fired is selected by an external agent, a priority scheme, random choice, or some other means external to the Petri net model. This level of nondeterminism makes purely analytical throughput analyses difficult.

View Large Image Download to PowerPoint

Figure 11 Petri net construct modeling conflict.

Although this limitation of timed event graphs removes some of its power to model the dynamic execution of an automated system, in practice it is less of problem. Frequently, once a model has been constructed and analyzed, and a control scheme has been imposed upon the Petri net, a few additional reasonable assumptions can generate a timed event graph representation of the model that is useful for estimating and optimizing performance.

A Petri net is said to be strongly connected when there exists a directed path joining any node to any other node. The key to performance analysis of strongly connected timed event graphs is the identification of its elementary circuits. An elementary circuit is a path that goes from one node back to the same node while not visiting any other node more than once. It is interesting to note that elementary circuits are p-invariants of the associated event graphs.

Consider the laboratory automation system schematically diagramed in Figure 12. The input incubator is an automated device. It delivers stored microplates to its external nest. The input robot then fetches a microplate from the input incubator and moves it to the dispenser where a reagent is added to its wells. When dispensing has completed, the output robot fetches plates from the dispenser and moves them to the nest of the output incubator, which transports the microplate to an available storage location. Figure 13 is a Petri net model for this system. Because we are interested in steady state behavior of this system, in all subsequent analysis we will assume that places p1 and p8 are sufficiently large to have no impact and therefore they will be neglected.

View Large Image Download to PowerPoint

Figure 12 Diagram of a two robot—two incubator—single dispenser system.

View Large Image Download to PowerPoint

Figure 13 Petri net model of the two robot—two incubator—single dispenser system.

The first step in analyzing this model is to determine its elementary circuits. Algorithms have been developed to perform this task automatically.17 Once all elementary circuits are enumerated the total number of tokens and total time associated with all nodes of each circuit is calculated. The total circuit time divided by the number of tokens in each elementary circuit gives the circuit cycle time. The circuit with the maximum circuit cycle time is called the critical circuit, which represents the bottleneck that limits the pace for the entire system.

The Petri net of Figure 13 has five elementary circuits. These circuits along with the number of contained tokens, total circuit time, and circuit cycle time, are listed in Table 2. Circuit 3 is the critical circuit because it has the largest cycle time of six time units. It is this circuit that will govern the rate at which the entire system runs.

Table 2. Elementary circuits of Figure 13, with properties

	#	Elementary circuit	# Tokens	Circuit time	Cycle time
	1	[t1, p2, t2, p9]	1	5	5
	2	[t2, p3, t3, p10]	1	2	2
	3	[t3, p4, t4, p5, t5, p12, t8, p11]	1	6	6
	4	[t5, p6, t6, p13]	1	2	2
	5	[t6, p7, t7, p14]	1	5	5

The performance of this system can be improved by eliminating the bottleneck represented by the critical circuit. From its definition, it follows that cycle time can be reduced by decreasing the overall circuit time or increasing the number of resources (tokens) in the circuit. No structural changes to the Petri net are necessary. Note that the token in circuit 3 corresponds to the dispenser instrument. Therefore, we can reduce the cycle time of circuit 3 by adding a second dispenser token to the model. The new cycle times are listed in Table 3. Circuit 3 is no longer the critical circuit with a new cycle time of three time units. The bottleneck has shifted to circuits 1 and 5. The tokens in these circuits correspond to the incubator mechanism for moving plates into and out of storage. Let's add a second input and a second output incubator to the design. The new cycle times are given in Table 4. The two new incubators may add unnecessary storage capacity. This new design suggests that multiple smaller incubators may be more efficient than fewer larger ones.

Table 3. Cycle times with two dispensers

	#	# Token	Circuit time	Cycle time
	1	1	5	5
	2	1	2	2
	3	2	6	3
	4	1	2	2
	5	1	5	5

Table 4. Cycle times with two input and two output incubators

	#	# Tokens	Circuit time	Cycle time
	1	2	5	2.5
	2	1	2	2
	3	2	6	3
	4	1	2	2
	5	2	5	2.5

As indicated by the fact that circuit 3 is once again the critical circuit, the new design shifts the bottleneck back to the dispenser. We make one last design change and add a third dispenser to obtain the new cycle times of Table 5. At this point, we will consider the cycle times to be adequately balanced. A schematic of the new design is given in Figure 14.

Table 5. Cycle times for the four incubator—three dispenser—two robot design

	#	# Tokens	Circuit time	Cycle time
	1	2	5	2.5
	2	1	2	2
	3	3	6	2
	4	1	2	2
	5	2	5	2.5

View Large Image Download to PowerPoint

Figure 14 Optimized four incubator—three dispenser—two robot design.

A more general way to optimize a system such as this is to express it as an integer-programming problem that minimizes the number of tokens in the system under desired performance constraints.

As we saw, the cycle time of a circuit was determined by dividing the total time of the circuit by the total number of tokens in all nodes of that circuit (21).5 γ Denotes the elementary circuit, C(γ) the cycle time of circuit γ, μ(γ) the sum of all firing times in γ, and M(γ) the number of tokens in all nodes of γ. Given a target cycle time C', we can calculate the minimum number of required tokens to achieve that target (22).

(21)

(22)

Equation 22 forms a set of conditions that must be satisfied, one for each elementary circuit in a given timed event graph. The minimization objective must be one that does not change with the state of the system. We choose the sum of all p-invariants as the objective as this cannot change, by definition. For an event graph, this is the sum of all token sums from each elementary circuit. The associated integer-programming problem formulation for the timed event graph of Figure 12 is given as LP 3, where all markings are integers greater than or equal to zero. A distribution of resources that satisfies a maximum cycle time C' can be computed by substituting a chosen value for C' into the constraints of LP 3 and solving the entire problem for optimum place markings. If we choose C'=2.5 and solve, we find the identical distribution as that given in Table 5 and depicted in Figure 14.

	Minimize	(M(p2)+M(p9))+(M(p10)+M(p3))+(M(p11)+M(p4)+M(p5)+M(p12))+(M(p13)+M(p6))+(M(p7)+M(p14))
	Performance constraint	M(p2)+M(p9)≥5/C'
	Performance constraint	M(p10)+M(p3)≥2/C'
	Performance constraint	M(p11)+M(p4)+M(p5)+M(p12)≥6/C'
	Performance constraint	M(p13)+M(p6)≥2/C'
	Performance constraint	M(p7)+M(p14)≥5/C'

LP 3: Integer-programming formulation for optimizing the design of Figure 12.

Performance optimization using a linear-programming formulation has advantages over ad hoc approaches. Linear-programming formulations allow system optimizations to be performed automatically, thereby making it possible for the technique to be applied more broadly by implementing it in a Petri net-based software design and analysis tool for laboratory automation systems.

Conclusion 

Petri nets are excellent tools for the modeling and mathematical analysis of discrete event system models, including models of dynamically controlled laboratory automation systems. The collected body of results in the field of Petri nets is extensive. A few representative results have been outlined to demonstrate applicability and utility to laboratory automation systems. Results demonstrated include the identification of deadlock situations, throughput performance analysis and optimization, and supervisory control development. Dynamically controlled laboratory automation systems represent a new class of systems that promise to transform the automated laboratory. Petri nets represent one essential tool for modeling, analyzing, and designing these systems to ensure optimal performance.