00190.dvi April 12, 2008 15:19 00190 Journal of Information & Knowledge Management, Vol. 7, No. 1 (2008) 37–46 c© iKMS & World Scientific Publishing Co. Knowledge-Based Expert System Development and Validation with Petri Nets Madjid Tavana Management Information Systems Lindback Distinguished Chair of Information Systems La Salle University, Philadelphia, PA 19141, USA tavana@lasalle.edu http://lasalle.edu/∼tavana Abstract. Expert systems (ESs) are complex information systems that are expensive to build and difficult to validate. Numerous knowledge representation strategies such as rules, semantic networks, frames, objects and logical expressions are developed to provide high-level abstraction of a system. Rules are the most commonly used form of knowledge representation and they are derived from popular techniques such as deci- sion trees and decision tables. Despite their huge popularity, decision trees and decision tables are static and cannot model the dynamic requirements of a system. In this study, we pro- pose Petri Nets (PNs) for dynamic system representation and rule derivation. PNs with their graphical and precise nature and their firm mathematical foundation are especially useful for building ESs that exhibit a variety of situations, includ- ing: sequential execution, conflict, concurrency, synchronisa- tion, merging, confusion, or prioritisation. We demonstrate the application of our methodology in the design and development of a medical diagnostic expert system. Keywords: Petri-Net; expert system; knowledge representa- tion; rules; decision tree; decision table; knowledge map; pro- cess map. 1. Introduction Knowledge-based information systems are complex arte- facts that are expensive to build and difficult to validate, especially when the components of the system exhibit a variety of situations, including: sequential execution, con- flict, concurrency, synchronisation, merging, confusion, or prioritisation (Balduzzi et al., 2000; Mehrez et al., 1995). Sequential execution refers to the processing of precedence constraints; conflict refers to mutually exclusive activities or results; concurrency refers to simultaneous task opera- tion; synchronisation refers to multiple resource usage in a single operation; merging refers to multiple precedence constraints; confusion refers to the combination of conflict and concurrency; and prioritisation refers to the determi- nation of the priorities of activities. Lee et al. (2001) have argued the need for verifying and validating the reliability and quality of the data and processes for such complex systems. Numerous knowledge representation strategies such as rules, semantic networks, frames, objects and logical expressions are developed to provide high-level abstrac- tion of a system. Rules are the most commonly used form of knowledge representation and they are derived from popular techniques such as decision trees and deci- sion tables. The decision trees are widely used for build- ing knowledge-based systems by the inductive inference (Chen et al., 2003; Lee et al., 2007; Yang et al., 2005). Decision trees provide a useful solution for many prob- lems of classification where large datasets are used and the information contained is complex (Aitkenhead, 2008). Decision trees are easily converted into rules by deriving a rule for each path in the tree that starts at the root and ends at the leaf node (Janssensa et al., 2006). Similarly, decision tables represent an exhaustive set of mutually exclusive expressions that link conditions to particular actions. Decision tables and decision trees are practical tools that enhance clarity, conciseness and comprehensi- bility (Baesens et al., 2003; Yang et al., 2005). Knowl- edge and process maps are also used to analyse business problems in order to transfer certain aspects of knowledge into a transparent graphical form (Becerra-Fernandez and Sabherwal, 2001; Eppler, 2004; Handzic, 2003). Eppler (2001) has classified knowledge maps into five different categories, including knowledge source map, knowledge asset map, knowledge structure map, knowledge applica- tion map and knowledge development map. A knowledge map generally consists of a ground layer which represents the context for the mapping and the individual elements that are mapped within this specific context. Despite their huge popularity, decision trees, decision tables, knowl- edge and process maps are static and cannot model the dynamic requirements of a system. 37 April 12, 2008 15:19 00190 38 M. Tavana Petri Nets (PNs) are well-suited for the design, spec- ification and formal verification of complex information systems (Sakthivel and Tanniru, 1988–1989). PNs with their graphical and precise nature and their firm math- ematical foundation are commonly used to model many complex systems. Their graphical nature allows for mod- els that are easy to understand while their formal seman- tics allow for precise and unambiguous descriptions. PNs are particularly considered a richer, more versatile, and dynamic graphical tool in the development and vali- dation of expert systems (Mehrez et al., 1995; Wong, 2001). PNs were initially defined by Carl Adam Petri (1962) and later refined and named after him by Holt (1971). Peterson (1981) elegantly discusses the dynamic behaviour of PNs, while Murata’s tutorial review paper provides a thorough review of PN’s history and appli- cations (Murata, 1989). PNs are abstract, formal mod- els used to describe and analyse the flow of infor- mation and control in systems, particularly systems that exhibit asynchronous and concurrent activities, with conditions for the performance of events within the system (Bullers, 1991). They have been proven to be useful for the modelling and analysis of several classes of systems, including web-based systems (Huang et al., 2008; Zhovtobryukh, 2007), communication sys- tems (Berthelot and Terrat, 1982), knowledge-based sys- tems (Jantzen, 1980), simulation systems (Piera et al., 2004) and process control systems (Bruno and Marchetto, 1986). In addition to ordinary PNs, timed PNs, stochas- tic PNs, coloured PNs and fuzzy PNs are widely used to model engineering and business systems. Timed PNs are those with places or transitions that have time dura- tions in their activities (Liu et al., 2007). Stochastic PNs include the ability to model randomness in a sit- uation, and also allow for time as an element in the PN (Murata, 1989; Lee et al., 2001). Coloured PNs allow the user and developer to witness the changes in places and transitions through the application of colour-specific tokens, and movement through the sys- tem can be represented through the changes in colours (Chen et al., 2001). Fuzzy PNs are used to model fuzzy rule-based reasoning to handle uncertain and imprecise information (Huang et al., 2008; Li and Lara-Rosano, 2000). In the next section, we present PN principles and formalism followed by a discussion of ES modelling with PNs in Sec. 3. In Sec. 4, we use PN process modelling to develop a medical diagnostic expert system, and in Sec. 5, we present our concluding remarks and future research directions. 2. PN Principles and Formalism Classical PNs as defined by Petri (1962) and further discussed by Peterson (1981). They are identified by 5-tuples (P, T, I, O, Eµ), where P = {p1, p2, . . . , pm} is a set of places; T = {t1, t2, . . . , tn} is a set of transitions; [I ⊆ P xT ] is the input function from P to T ; [O ⊆ T xP ] is the output function from T to P ; and Eµ, called mark- ing, is a function that defines a mapping from a set of places P to Z (here Z denotes the set of all nonnegative integers). µ : P → Z where µi = µ(pi) ∈ Z, pi ∈ P i = {0, 1, . . . , m}. Mathematically, a PN is a directed bipartite graph with two different types of node called places and transi- tions. A place p is presented with a circle and a transition t is presented by a rectangle. The nodes are connected through directed arcs. Directed arcs from p to t create input places while directed arcs from t to p create out- put places. Input places are a set of places that can fire a transition, while output places are a set of places that are associated with the results (outputs) from a transition. Only the static properties of a system are presented by a PN structure; however, dynamic properties result from PN execution. Execution requires the use of tokens or markings (denoted by dots) associated with places. Each place contains zero or many tokens drawn as black dots. The execution of a PN may affect the number of tokens in a place. A transition is called enabled when each of its input places has enough tokens. A transition can be fired only if it is enabled. When a transition is fired, tokens from input places are used to produce tokens in output places. We will use the PN shown in Fig. 1 to illustrate the classical PN. With one token placed in p1 and two tokens placed in p2, transitions t2 and t3 are enabled. Firing t2 and t3 consumes three tokens (one from p1 and two from p2) and produces two tokens in p3. Now transition t1 is enabled. Firing t1 consumes one of the two tokens in p3 (leav- ing p3 with one token) and produces two tokens, one in t1 p1 t3 t2 p2 p3 Fig. 1. Simple Petri Net example. April 12, 2008 15:19 00190 Knowledge-Based Expert System Development and Validation with Petri Nets 39 p1 and one in p2. Mathematical properties of the PN shown in Fig. 1 are presented next. The PN in Fig. 1 is constructed with three places (P = {p1, p2, p3}) and three transitions (T = {t1, t2, t3}). The input and output mapping of this PN is given as: I(t1) = {p3} O(t1) = {p1, p2} I(t2) = {p1, p2} O(t2) = {p3} I(t3) = {p2} O(t3) = {p3}. Any PN can be specified in matrix form as a D− Matrix with m rows and n columns, where m is the num- ber of transitions and n is the number of places in the PN. For each position [i, j] in the matrix, a 1 is placed in the position if transition i receives input from place j. A 0 is placed if transition i does not receive input from place j: D− =   0 0 1 1 1 0 0 1 0   . Similarly a D+ Matrix with m rows and n columns can be constructed, where m is the number of transitions and n is the number of places in the PN. For each posi- tion [i, j] in the matrix, a 1 is placed in the position if transition i produces output to place j. A 0 is placed if transition i does produce output to place j: D+ =   1 1 0 0 0 1 0 0 1   . The Composite Change Matrix (Matrix D) can be computed by subtracting D− form D+: [D+] − [D−] = [D]   1 1 0 0 0 1 0 0 1   −   0 0 1 1 1 0 0 1 0   =   1 1 −1 −1 −1 1 0 −1 1   . In addition, a 1 × m matrix, representing the firing of the PN is constructed. In each position [1, j] place the number of times transition j is to fire. The Transition Matrix for our PN is Transition Matrix = [0 1 1] (t2 and t3 firing because of the tokens in p1 and p2). Finally, a 1 × n matrix is constructed showing the current marking of the PN. In each position [1, j], the identified number of tokens in position j are placed. The Marking Matrix for our PN is Marking Matrix = [1 2 0] (given one token in p1 and two tokens in p2). The marking of the PN after the transition specified in the Transition Matrix (next marking) can be found as: [Transition Matrix][D] + [Marking Matrix] = [Next Marking][0 1 1]   1 1 −1 −1 −1 1 0 −1 1   + [1 2 0] = [0 0 2]. From a modelling perspective, PNs can be char- acterised as a “conceptual model with analytical quali- ties”, where a “conceptual model” generally represents a graphical approach, while an “analytical model” expresses functional and mathematical relationships (Mehrez et al., 1995). As a hybrid modelling approach, PNs can dis- play several important properties, including the ability to model situations for simulation analysis and to describe system behaviour (Kim et al., 2001). These abilities are useful in developing and validating expert systems that are used to arrive at an “expert advice”. The user supplies a set of facts and the expert sys- tem returns advice. Expert systems consist of a knowledge base and an inference engine. The inference engine con- sults the knowledge base with the facts provided by the user to return expert advice. The building blocks of expert systems are rules. When the facts supplied by the user, comply with a particular set of rules, an expert advice is produced. The rules of an expert system are often used to form a tree structure, called a decision tree. The nodes in a decision tree describe states and branches which repre- sent the relationships between the states. 3. Expert Systems Modelling with PNs There are many frameworks, methods and tools to build and validate information systems. Some are more suited to transaction processing systems, while others are more effective when assisting in the design and validation of decision support and ES (Whitten et al., 2001). According to Van Hee et al. (1991), designing a classical information system means automating an existing, well-defined man- ual system (or set of processes). However, when designing a decision support or ES, it is unwise to automate the existing processes completely, since many of these pro- cesses rely on heuristics and are not easily replicated by a machine. Many knowledge-based systems have failed as a result of the designers’ inability to differentiate between those processes that should be automated and those that should remain manual (Van Hee et al., 1991). Problems can arise in both the design and validation phases of the development of a knowledge-management system (Whitten et al., 2001), and care must be taken to ensure that the systems’ processes and the knowledge April 12, 2008 15:19 00190 40 M. Tavana base data are correctly designed, accessed and manipu- lated. With these complex systems, prototypes are not always sufficient, since it can be difficult to simulate all the permutations of a decision process for all possible sit- uations under which an ES is expected to function (Van Hee et al., 1991). Therefore, Van Hee et al. (1991) and others (Wu and Lee, 1997; Bullers, 1991) advocate the development of a model of the target system that can reflect the performance characteristics (i.e., the effects of the decisions made by or through the ES) as well as the functionality of the system itself. PNs have been used to perform both the knowledge validation and functional- ity testing of many complex systems, and can be used to assist in designing and validating rule-based ESs, since they have been used to analyse conditional relationships (Lee and Lai, 2002; Liu et al., 1999; Liu et al., 2000; Zhu and Xudong, 2002). As detailed in Wu and Lee (1997) as well as in Bullers (1991), PNs can be used successfully to detect flaws in pro- cess as well as in the information passing from rule-based applications. PNs can address problems such as conser- vation of known and unknown facts and refraction that arise in the design and/or validation of an ES. The use of a PN model can serve as an inference model for rule- based ESs and as a platform for knowledge management and verification (Wu and Lee, 1997). According to Van der Aalst (1999), PNs are also use- ful for representing workflow processes because the PN model can be used to study the flow of control of and its relevant data. This representation enables designers to verify the correctness of the process and its manage- ment of information before the system becomes opera- tional (Verbeek et al., 2001). This benefit is an important consideration in choosing a model for the creation and validation of expert systems, since these systems generally involve complex processes and the management of consid- erable amounts of rule-based knowledge (Bullers, 1991). According to Lee et al. (1999), there are several rationales for basing the design and validation of an expert system on a PN model: • PNs achieve the structuring of knowledge within rule bases, which can express relationships among rules and help experts construct and modify rule bases, • The PN’s graphic nature provides visualisation of the dynamic behaviour of rule-based reasoning, • The PN’s analytic capability provides a basis for devel- oping a knowledge verification technique, and • Concurrency among rules can be modelled by PNs, which is an important aspect in real-time performance validation. 4. Application Problem In this section, we use PN process modelling to develop a medical diagnostic expert system at Kennedy Memo- rial Hospital.∗ The number of incorrectly diagnosed acute appendicitis cases at the emergency room (ER) at Kennedy Memorial Hospital had increased steadily over a three-year period. Several patients were misdiagnosed and sent home to develop ruptured appendicitis while some patients were incorrectly sent to the operating room (OR) for emergency appendectomy. The ER physicians and staff agreed to implement a strict system of diagnos- tic protocols for patients with right lower quadrant (RLQ) pain. After several meetings, the ER physicians and staff were able to reach consensus on the following protocols for patients with RLQ pain. If a female patient complains about abdominal pain, her temperature should be taken. Next, the patient should be examined for RLQ pain. Those with no fever and no RLQ pain, should receive a blood test to determine if their white blood cell (WBC) count is elevated or not. An elevated WBC count is suggestive of acute appendici- tis. If the patient’s WBC count is normal, she will be discharged home with instruction to return to the ER if any fever, worsening abdominal pain, or vomiting devel- ops. If the WBC count is elevated, the patient will be admitted to the hospital and receive an emergency CAT (Computerised Axial Tomography) scan of the abdomen and pelvis. If the CAT scan is positive for appendicitis, she will be taken to the OR for appendectomy. If the CAT scan is negative, she will be observed in the hospital for the next 24 h to determine the course of her disease. Patients with no fever and RLQ pain must be sent for WBC count. If the WBC count is normal, the patient will be scheduled for an outpatient ultrasound within 24 hours to rule out any other significant female pathology. If the WBC count is high, the patient will be scheduled for emergency CAT scan. If the CAT scan is positive for appendicitis, she will be taken to the OR for appendectomy. If the CAT is neg- ative, she will be observed in the hospital for the next 24 hours to determine the course of her disease. Female patients with fever are examined for RLQ pain followed by a blood test for WBC count. Those with fever, RLQ pain, and a high WBC count, will be taken to the OR for emergency appendectomy. Those with a nor- mal WBC count are sent for a CAT scan. If the CAT scan is positive for appendicitis, the patient will be taken to the OR for an appendectomy. If the CAT scan is negative, the patient will be observed in the hospital for the next 24 hours to determine the course of her disease. If the patient has fever, with no RLQ pain and a normal WBC count, ∗The hospital name has been changed to protect the anonymity of all concerned. April 12, 2008 15:19 00190 Knowledge-Based Expert System Development and Validation with Petri Nets 41 she will be discharged home with instructions to return to the ER if any fever, worsening abdominal pain, or vomit- ing develops. Those with a high WBC count are sent for a CAT scan. If the CAT scan is positive for appendicitis, the patient will be taken to the OR for appendectomy. If the CAT is negative, the patient is observed in the hospital for the next 24 hours to determine the course of her disease. For male patients, the temperature should be taken to determine if the patient has a fever or not. The abdomen should be examined in all patients for RLQ pain. Male patients with no fever and no RLQ pain are dis- charged with instructions to return to the ER if any fever, worsening abdominal pain, or vomiting develops. Those with no fever and RLQ pain are sent for an emergency CAT scan. If the CAT scan is positive for acute appen- dicitis, the patient will be taken to the OR for emergency appendectomy. If the CAT scan is negative, a WBC count will be ordered. If the count is high, the patient will be observed in the hospital for the next 24 hours to deter- mine the course of his disease. If the count is normal, he should be discharged with instructions to return to the ER if any fever, worsening abdominal pain, or vom- iting develops. Male patients with fever and RLQ pain are taken to the OR for emergency appendectomy. Those with fever and no RLQ pain are observed in the hospital for the next 24 hours to determine the course of their dis- ease. Figures 2(a) and 2(b) present the ER screening PN diagram and notations. The PN presented in Fig. 2(a) is a complex network with 31 places and 38 transitions. In this problem, it is very common for the ER staff to work on more than one patient or more than one task at a time. Concur- rent process modelling capabilities of PNs are useful in modelling this requirement. Furthermore, the arrival of patients to the system is unplanned and their condition is unknown. This requirement can be captured with the t1 p1 t3 t2 t4 t8 t5 t7 t9 t6 t11 t12 p2 p3 p4 p5 p8 p6p7 p9 p11 p12 p13 p10 p14 p15 p16 t13 t10 t14 t15 t16 t17 t18 t19 t20 t21 t22 p23 p22 p21 p20 p19 p18 p17 t27 t26 t25 t24 t23 p25 p24 p27 p26 t34 t33 t32 t31 t30 t29 t28 p31 p30 p29 p28 t35 t37 t38 t36 (a) Fig. 2. Emergency room screening (a) Petri Net diagram. April 12, 2008 15:19 00190 42 M. Tavana PLACES p1: Idle Screener p2: Male Signal p3: Female Signal p4: Male Patient p5: Female Patient p6: Fever Signal p7: No Fever Signal p8: Male with Fever p9: Female with Fever p10: Male with No Fever p11: Female with No Fever p12: Right Lower Quadrant (RLQ) Pain p13: No Right Lower Quadrant (RLQ) Pain p14: Male with No Fever and RLQ Pain p15: Female with Fever and RLQ Pain p16: Female with Fever and No RLQ Pain p17: Female with No Fever and RLQ Pain p18: Female with No Fever and No RLQ Pain p19: Elevated White Blood Cell (WBC) p20: Normal White Blood Cell (WBC) p21: Emergency Appendectomy p22: Discharge p23: Admit p24: Ultrasound p25: Positive CAT Scan Signal p26: Negative CAT Scan Signal p27: Male with No Fever and RLQ Pain and Negative CAT Scan p28: Female with No Fever and No RLQ Pain and Elevated WBC p29: Female with No Fever and RLQ Pain and Elevated WBC p30: Female with Fever and No RLQ Pain and Elevated WBC P31: Female with Fever and RLQ Pain and Normal WBC TRANSITIONS t1: Male Sex Identification t2: Female Sex Identification t3: Male Temperature Measurement t4: Female Temperature Measurement t5: Male No Fever Determination t6: Female No Fever Determination t7: Male with No Fever and No RLQ Pain Determination t8: Male with No Fever and RLQ Pain Determination t9: Male with Fever and No RLQ Pain Determination t10: Male with Fever and RLQ Pain Determination t11: Female with Fever and RLQ Pain Determination t12: Female with Fever and No RLQ Pain Determination t13: Female with No Fever and RLQ Pain Determination t14: Female with No Fever and No RLQ Pain Determination t15: Male with No Fever and No RLQ Pain Positive CAT Scan Determination t16: Male with No Fever and RLQ Pain Negative CAT Scan Determination t17: Female with Fever and RLQ Pain Elevated WBC Determination t18: Female with Fever and RLQ Pain Normal WBC Determination t19: Female with Fever and No RLQ Pain Elevated WBC Determination t20: Female with Fever and No RLQ Pain Normal WBC Determination t21: Female with No Fever and RLQ Pain Elevated WBC Determination t22: Female with No Fever and RLQ Pain Normal WBC Determination 23: Female with No Fever and No RLQ Pain Elevated WBC Determination t24: Female with No Fever and No RLQ Pain Normal WBC Determination t25: Male with No Fever and RLQ Pain and Negative CAT Scan Elevated WBC Determination t26: Male with No Fever and RLQ Pain and Negative CAT Scan Normal WBC Determination t27: Female with No Fever and No RLQ Pain and Elevated WBC Positive CAT Scan Determination t28: Female with No Fever and No RLQ Pain and Elevated WBC Negative CAT Scan Determination t29: Female with No Fever and RLQ Pain and Elevated WBC Positive CAT Scan Determination t30: Female with No Fever and RLQ Pain and Elevated WBC Negative CAT Scan Determination t31: Female with Fever and No RLQ Pain and Elevated WBC Positive CAT Scan Determination t32: Female with Fever and No RLQ Pain and Elevated WBC Negative CAT Scan Determination t33: Female with Fever and RLQ Pain and Normal WBC Positive CAT Scan Determination t34: Female with Fever and RLQ Pain and Normal WBC Negative CAT Scan Determination t35: Return from Emergency Appendectomy t36: Return from Discharge t37: Return from Admit t38: Return from Ultrasound (b) Fig. 2. (Continued ) stochastic modelling capabilities of PNs. Finally, some patients might be in a more critical state than others and require immediate treatment. This requirement can be captured by establishing priorities in the PN. Figure 3, shows the rules derived from the ER PN. In order to validate our expert system, a pilot study was designed. Seven doctors, including the chief of the ER, two staff specialists and four ER doctors partici- pated in the pilot study. Multiple teams with at least five ER and specialist doctors in each team were formed to validate the knowledge base. The dynamic properties of this PN was examined and verified with the partic- ipants in this study through execution which required the use of tokens associated with places. Tokens in dif- ferent places enable transitions. The firing of the transi- tions produces tokens which again enable transitions for firing. Repeated examinations of this dynamic behaviour showed that the PN properly exhibits the current diag- nosis protocols in the ER at the Kennedy Memorial Hospital. A total of 814 cases were used in a pre- and post-ES implementation study to develop a prototype for patients arriving at the Kennedy Memorial Hospital with severe abdominal pain. The results are presented in Table 1. As is shown in the pre-ES statistics portion of Table 1, a total of 543 patients (45.25 patients on average per month) arrived into the ER with severe abdomi- nal pain over a 12-month period. 245 patients (20.42 patients on average per month) were referred to a special- ist after the initial screening in the ER and the remain- ing 298 patients were either discharged or treated for a non-appendicitis related problem. 137 patients (11.42 patients on average per month or 55.92%) were diagnosed with appendicitis by the specialists and the remaining 108 patients (9.00 patients on average per month or 44.08%) were diagnosed with no appendicitis and were either dis- charged or treated for a non-appendicitis related prob- lem. Further follow-up observations showed that 28 (2.33 patients on average per month) of the 108 patients who were either discharged or treated for a non-appendicitis related problem, were treated for appendicitis within seven days of their initial diagnosis. As is shown in the post-ES statistics portion of Table 1, a total of 271 patients (45.17 patients on average April 12, 2008 15:19 00190 Knowledge-Based Expert System Development and Validation with Petri Nets 43 Q U A L IF IE R S : 1 S e x Id e n ti fi c a ti o n : (F e m a le /M a le ) 2 T e m p e ra tu re M e a s u re m e n t: ( F e v e r/ N o F e v e r) 3 R L Q P a in D e te rm in a ti o n : (R L Q P a in /N o R L Q P a in ) 4 W B C L e v e l D e te rm in a ti o n : (E le v a te d /N o rm a l) 5 C A T S c a n D e te rm in a ti o n : (P o s it iv e /N e g a ti v e ) C H O IC E S : 1 E m e rg e n c y A p p e n d e c to m y 2 D is c h a rg e 3 A d m it 4 U lt ra s o u n d R U L E S : R U L E N U M B E R : 1 ( T 1 :1 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 2 ( T 1 :2 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : N o rm a l a n d C A T S c a n D e te rm in a ti o n : P o s it iv e T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 3 ( T 1 :3 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : N o rm a l a n d C A T S c a n D e te rm in a ti o n : N e g a ti v e T H E N : A d m it - C o n fi d e n c e = 1 R U L E N U M B E R : 4 ( T 1 :4 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d a n d C A T S c a n D e te rm in a ti o n : P o s it iv e T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 5 ( T 1 :5 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d a n d C A T S c a n D e te rm in a ti o n : N e g a ti v e T H E N : A d m it - C o n fi d e n c e = 1 R U L E N U M B E R : 6 ( T 1 :6 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : N o rm a l T H E N : D is c h a rg e - C o n fi d e n c e = 1 R U L E N U M B E R : 7 ( T 1 :7 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d a n d C A T S c a n D e te rm in a ti o n : P o s it iv e T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 8 ( T 1 :8 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d a n d C A T S c a n D e te rm in a ti o n : N e g a ti v e T H E N : A d m it - C o n fi d e n c e = 1 R U L E N U M B E R : 9 ( T 1 :9 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : N o rm a l T H E N : U lt ra s o u n d - C o n fi d e n c e = 1 R U L E N U M B E R : 1 0 ( T 1 :1 0 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d a n d C A T S c a n D e te rm in a ti o n : P o s it iv e T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 1 1 ( T 1 :1 1 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : E le v a te d a n d C A T S c a n D e te rm in a ti o n : N e g a ti v e T H E N : A d m it - C o n fi d e n c e = 1 R U L E N U M B E R : 1 2 ( T 1 :1 2 ) IF : S e x Id e n ti fi c a ti o n : F e m a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in a n d W B C L e v e l D e te rm in a ti o n : N o rm a l T H E N : D is c h a rg e - C o n fi d e n c e = 1 R U L E N U M B E R : 1 3 ( T 1 :1 3 ) IF : S e x Id e n ti fi c a ti o n : M a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 1 4 ( T 1 :1 4 ) IF : S e x Id e n ti fi c a ti o n : M a le a n d T e m p e ra tu re M e a s u re m e n t: F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in T H E N : A d m it - C o n fi d e n c e = 1 R U L E N U M B E R : 1 5 ( T 1 :1 5 ) IF : S e x Id e n ti fi c a ti o n : M a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d C A T S c a n D e te rm in a ti o n : P o s it iv e T H E N : E m e rg e n c y A p p e n d e c to m y - C o n fi d e n c e = 1 R U L E N U M B E R : 1 6 ( T 1 :1 6 ) IF : S e x Id e n ti fi c a ti o n : M a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d C A T S c a n D e te rm in a ti o n : N e g a ti v e a n d W B C L e v e l D e te rm in a ti o n : E le v a te d T H E N : A d m it - C o n fi d e n c e = 1 R U L E N U M B E R : 1 7 ( T 1 :1 7 ) IF : S e x Id e n ti fi c a ti o n : M a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : R L Q P a in a n d C A T S c a n D e te rm in a ti o n : N e g a ti v e a n d W B C L e v e l D e te rm in a ti o n : N o rm a l T H E N : D is c h a rg e - C o n fi d e n c e = 1 R U L E N U M B E R : 1 8 ( T 1 :1 8 ) IF : S e x Id e n ti fi c a ti o n : M a le a n d T e m p e ra tu re M e a s u re m e n t: N o F e v e r a n d R L Q P a in D e te rm in a ti o n : N o R L Q P a in T H E N : D is c h a rg e - C o n fi d e n c e = 1 F ig . 3 . R u le d e ri v e d fr o m th e e m e rg e n c y ro o m P e tr i N e t. April 12, 2008 15:19 00190 44 M. Tavana Table 1. Pre- and post-pilot study statistics. Month Total patients ER diagnosis: Specialist initial Specialist initial Specialist secondary with severe referral to a diagnosis: diagnosis: diagnosis: abdominal pain specialist appendicitis no appendicitis appendicitis Pre expert system statistics 1 48 21 12 9 3 2 42 19 13 6 2 3 52 23 11 12 3 4 45 18 10 8 3 5 39 18 9 9 2 6 47 20 11 9 2 7 51 23 13 10 2 8 45 22 12 10 3 9 44 20 11 9 2 10 39 18 10 8 2 11 43 21 11 10 3 12 48 22 14 8 1 Total 543 245 137 108 28 Pre-mean 45.25 20.42 (100%) 11.42 (55.92%) 9.00 (44.08%) 2.33 Post expert system statistics 13 52 16 15 1 0 14 38 14 12 2 1 15 48 15 14 1 0 16 49 14 13 1 1 17 39 14 14 0 0 18 45 15 14 1 0 Total 271 88 82 6 2 Post-mean 45.17 14.67 (100%) 13.67 (93.18%) 1.00 (6.82%) 0.33 Pre-post expert system statistics Mean difference −0.08 −5.75 2.25 −8.00 −2.00 t statistics 0.0356 7.0769 −3.3866 12.5514 6.5320 Significant (α = 0.05) No Yes No Yes Yes per month) arrived into the ER with severe abdominal pain over a 6 month period. The ES developed in this study was used for screening patients with severe abdomi- nal pain. 88 patients (14.67 patients on overage per month) were referred to a specialist after the initial screening in the ER and the remaining 183 patients were either discharged or treated for a non-appendicitis related problem. 82 patients (13.67 patients on average per month or 93.18%) were diagnosed with appendicitis by the specialists and the remaining 6 patients (1.00 patients on average per month or 6.82%) were diagnosed with no appendicitis and were either discharged or treated for a non-appendicitis related problem. Further follow-up observations showed that 2 (0.33 patients on average per month) of the 6 patients who were either discharged or treated for a non-appendicitis related problem, were treated for appendicitis within seven days of their initial diagnosis. The average number of patients arrived into the ER room pre ES implementation was 45.25 patients versus 45.17 patients for post-ES implementation. Test of means between pre- and post-ES implementation shows that the 0.08 difference in the average number of patients arrived into the ER with severe abdominal pain is not signifi- cant (α = 0.05). In addition, the 2.25 difference between the number of patients diagnosed with appendicitis in pre- and post-ES implementation studies is not signifi- cant either. However, further test of means shows that the average number of patients referred to a specialist was dropped from 20.42 to 14.67. This 5.75 patient or a 28% reduction in the number of patients referred to a spe- cialist after the implementation of our ES is statistically significant. Furthermore, the average number of patients initially diagnosed with no appendicitis by the special- ist dropped from 9.0 patients per month to 1.0 patient per month after the implementation of our ES. This 8.00 patient or an 89% reduction in the number of patients initially diagnosed with no appendicitis by the special- ist is statistically significant. Finally, the difference in the average number of patients who were either discharged or treated for a non-appendicitis related problem but upon April 12, 2008 15:19 00190 Knowledge-Based Expert System Development and Validation with Petri Nets 45 return within seven days of their initial diagnosis were treated for appendicitis dropped by 2 patients per month. This 86% reduction in the number of patients is statisti- cally significant. In summary, this study revealed two major findings. First, the implementation of our ES resulted in significant drop in “wrong” referrals as evidenced by significant decrease in average number of referrals by 5.75, as well as increase and decrease in specialists’ percentage of initial diagnoses to 93.18% and 6.82%. Second, there was no sig- nificant increase in specialists’ diagnosis accuracy as evi- denced by similar rations (28/108 = 26% and 2/6 = 33%). 5. Conclusion and Future Research Directions ESs are complex artefacts that are difficult to design develop and validate. Various knowledge representation techniques such as decision trees and decision tables are commonly used to develop rule-based ESs. However, these static approaches cannot replicate the dynamic behaviour of systems with sequential execution, conflict, concur- rency, synchronisation, merging, confusion or prioritisa- tion. In this study, we showed that PNs have great potential for providing high-level abstraction in the ES development life cycle. The PN’s graphic nature can provide visualisation of the dynamic behaviour of rule-based reasoning to design- ers for development and to users for validation. PNs help ES designers construct, validate and modify rule bases by observing the behaviour of the rules within the knowledge base. The PN’s with their analytic capa- bilities support knowledge verification techniques and PNs can effectively model sequential execution, conflict, concurrency, synchronisation, merging, confusion or pri- oritisation among rules which are crucial in real-time performance validation. PNs are traditionally used in electrical engineer- ing for process control. Over the past decade, several researchers have focussed on the application of ordinary PNs in business. In addition to ordinary PNs, timed PNs, stochastic PNs, and coloured PNs and fuzzy PNs are pow- erful tools for modelling complex business systems. More research is necessary to expand PN research and devel- opment into other areas of knowledge-based management and artificial intelligence. References Aitkenhead, MJ (2008). A co-evolving decision tree clas- sification method. Expert Systems with Applications, 34(1), 18–25. Baesens, B, R Setiono, C Mues and J Vanthienen (2003). Using neural network rule extraction and decision tables for credit-risk evaluation. Management Science, 49(3), 312–329. Balduzzi, F, A Giua and G Menga (2000). First-order hybrid Petri Nets: A model for optimization and con- trol. IEEE Transactions on Robotics and Automation, 16(4), 382–399. Becerra-Fernandez, V and R Sabherwal (2001). Organiza- tional knowledge management: A contingency perspec- tive. Journal of Management Information Systems, 18, 23–56. Berthelot, G and R Terrat (1982). Petri-Net theory for correctness of protocols. IEEE Transactions on Com- munication, 30(12), 2497–2505. Bruno, G and G Marchetto (1986). Process-translatable Petri Nets for the rapid prototyping of process control systems. IEEE Transactions on Software Engineering, 12(2), 346–357. Bullers, WI Jr. (1991). A tripartite approach to infor- mation systems development. Decision Sciences, 22(1), 120–135. Chen, SC, YL Ke and JS Wu (2001). Coloured Petri-Nets approach for solving distribution system contingency. Proceedings of the IEEE, 148(5), 463–470. Chen, YL, CL Hsu and SC Chou (2003). Constructing a multi-valued and multi-labeled decision tree. Expert Systems with Applications, 25(2), 199–209. Eppler, M (2001). Making knowledge visible through intranet knowledge maps: Concepts, elements, cases. Proceedings of 34th Hawaii International Conference on System Sciences, pp. 1530–1539, Piscataway, NJ: IEEE. Eppler, M (2004). Facilitating knowledge communication through joint interactive visualization. Journal of Uni- versal Computer Science, 10, 683–690. Handzic, M (2003). An integrated framework of KM. In Australian Studies in Knowledge Management, Hasan, H and M Handzic (eds.), pp. 3–34, Wollongong: University of Wollongong Press. Holt, AW (1971). Introduction to occurrence systems. In Associate Information Techniques, Jacks, L (ed.), pp. 175–203, New York: American Elsevier. Huang, Y-M, J-N Chen, T-C Huang, Y-L Jeng and Y-H Kuo (2008). Standardized course generation process using Dynamic Fuzzy Petri Nets. Expert Systems with Applications, 34, 72–86. Janssensa, D, G Wetsa, T Brijsa, K Vanhoofa, T Arentzeb and H Timmermansb (2006). Integrating Bayesian net- works and decision trees in a sequential rule-based transportation model. European Journal of Operational Research, 175(1), 16–34. Jantzen, M (1980). Structures representation of knowl- edge by petri nets as an aid for teaching and research. Lecture Notes in Computer Science. Berlin: Springer Verlag. April 12, 2008 15:19 00190 46 M. Tavana Kim, CH, DS Yim and RH Weston (2001). An inte- grated use of IDEF0, IDEF3 and Petri-Net meth- ods in support of business process modeling. Proceed- ings of the Institution of Mechanical Engineers, 215(4), 317–329. Lee, J, KFR Liu and W Chiang (1999). A fuzzy Petri Net-based expert system and its application to dam- age assessment of bridges. IEEE Transactions on Sys- tems, Man, and Cybernetics — Part B: Cybernetics, 29, 350–369. Lee, J and LF Lai (2002). A high-level Petri-Nets-based approach to verifying task structures. IEEE Trans- actions on Knowledge and Data Engineering, 14(2), 316–335. Lee, J, JI Pan and JY Kuo (2001). Verifying scenarios with time Petri-Nets. Information and Software Tech- nology, 43(13), 769–781. Lee, S, S Lee and Y Park (2007). A prediction model for success of services in e-commerce using decision tree: E-customer’s attitude towards online service. Expert Systems with Applications, 33(3), 572–581. Li, X and FL Rosano (2000). Adaptive fuzzy Petri nets for dynamic knowledge representation and inference. Expert Systems with Applications, 19(3), 235–241. Liu, R, A Kumar and W van der Aalst (2007). A for- mal modeling approach for supply chain event man- agement. Decision Support Systems, 43, 761–778. Liu, KFR, J Lee and W Chiang (1999). A fuzzy Petri- Net-based expert system and its application to damage assessment of bridges. IEEE Transactions on Systems, Man and Cybernetics, 29(3), 350–369. Liu, KFR, J Lee and W Chiang (2000). High-level fuzzy Petri-Nets as a basis for managing symbolic and numer- ical information. International Journal on Artificial Intelligence Tools, 9(4), 569–588. Mehrez, A, M Muzumdar, W Acar and G Weinroth (1995). A Petri-Net model view of decision making: An operational analysis. Omega — The International Journal of Management Science, 23(1), 63–78. Murata, T (1989). Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4), 541–580. Peterson, JL (1981). Petri Net Theory and the Modeling of Systems. Morristown, NJ: Prentice-Hall, Inc. Petri, CA (1962). Kommunikation mit Automaten. Uni- versity of Bonn. English Translation by C.F. Greene (1965) Communication with automata, Supplement to Technical Report RADC-TR-65-377, Vol. 1, Rome Air Development Center, Griffith Air Force Base, Rome, N.Y. Piera, MA, M Narciso, A Guasch and D Riera (2004). Optimization of logistic and manufacturing systems through simulation: A colored Petri Net-based method- ology. Simulation, 80(3), 121–129. Sakthivel, S, MR Tanniru (1988–1989). Information verifi- cation and validation during requirement analysis using Petri nets. Journal of Management Information Sys- tems, 5(3), 33–52. Van Der Aalst, WMP (1999). Woflan: A Petri-net-based workflow analyzer. Systems Analysis, Modeling, Simu- lation, 35(3), 345–357. Van Hee, KM, LJ Somers and M Voorhoeve (1991). A modeling environment for decision support systems. Decision Support Systems, 7, 241–251. Verbeek, HMW, T Basten and WMP Van Der Aalst (2001). Diagnosing workflow processes using Woflan. The Computer Journal, 44(4), 246–279. Whitten, J, L Bentley and K Dittman (2001). Sys- tems Analysis and Design Methods. Boston, MA: Irwin McGraw-Hill. Wong, ML (2001). A flexible knowledge discovery system using genetic programming and login grammars. Deci- sion Support Systems, 31, 405–428. Wu, CH and SJ Lee (1997). Knowledge verification with an enhanced high-level Petri-Net model. IEEE Expert, October, 73–80. Yang, B-S, D-S Lim and ACC Tan (2005). VIBEX: An expert system for vibration fault diagnosis of rotating machinery using decision tree and deci- sion table. Expert Systems with Applications, 28(4), 735–742. Zhovtobryukh, D (2007). A Petri Net-based approach for automated goal-driven web service composition. Simu- lation, 83(1), 33–63. Zhu, H and H Xudong (2002). A methodology of testing high-level Petri-Nets. Information and Science Tech- nology, 44, 473–489. Madjid Tavana is a Professor of Management Informa- tion Systems and the Lindback Distinguished Chair of Information Systems at the La Salle University where he served as the Chairman of the Management Depart- ment, Director of the Center for Technology and Man- agement, and the Executive Director of the E-Commerce Institute. He has been a Faculty Fellow in Aeronautics and Space Research at the NASA’s Kennedy Space Cen- ter, developing Group Decision Support Systems for the Space Shuttle Program and Johnson Space Center, devel- oping Intelligent Decision Support Systems for Human Exploration of Mars at the Mission Control Center. In 2005, he was awarded the prestigious Space Act Award by NASA. He holds an MBA, a PMIS, and a PhD in Manage- ment Information Systems and received his Post-Doctoral Diploma in Strategic Information Systems from the Whar- ton School of the University of Pennsylvania. He is the Editor-in-Chief of the International Journal of Applied Decision Sciences and has published in journals such as Decision Sciences, Information Systems, Interfaces, Infor- mation and Management, Computers and Operations Research, among others.