Modeling and verification of an intelligent tutoring system based on Petri net theory

1.   Introduction

English is a common international language. Thus, most of the countries, including Taiwan, have English courses in their formal educational institutions, such as elementary school, junior high school, senior high school and university. However, most of the students in Taiwan do not have a good environment to learn English, especially, for the students whose school is not located in the city. They do not have enough qualified teachers and financial aids to afford the tutorial classes. For that reason, we have built a tutoring system that provides a convenient environment to learn English without any real teaching aids. So, teachers and students do not need to spend much money on making the teaching aids. The important thing is the students' perspective. Some students think that English is not important because they will not use it any more in the future. However, English is required by students to pass the school or university entrance examination. It is the proof that English is really important.

Currently, in many tutoring systems, some distinguished platforms, such as Moodle, Sakai and D2L, are categorized as the ones of open source. According to SCORM (Sharable Content Object Reference Model) ^[1], teaching materials can be input and output on these platforms. However, these platforms are too complicated to be operated by school children.

Verification is an important issue in the tutoring system development. This paper aims to propose a novel method to verify the tutoring system using Petri nets. A novel environment, to change the traditional English learning method, based on Augmented Reality (AR), Text-to-Speech (TTS), and Speech Recognition (SR) was also developed. We change the traditional flash cards to AR. Since AR has been applied to different research areas and proven to be effective, more and more researchers use AR technology as an innovative tutoring method ^[2,3,4,5]. When using TTS and SR, students can know the correct pronunciation and present much courage to speak. It will enhance the students' interests in learning English. Furthermore, WoPeD (Workflow Petri net Designer) was applied to prove whether this tutoring system was working well or not.

We perform the system verification because it is susceptible to errors. This is also the important case with any engineering activity. The studies in human reliability have shown that people were trained to perform a specific operation making around 1–3 errors per hour in the best case of scenarios. In any activity, or the resulting outcome of an activity, the search for potential errors should not be neglected, regardless of whether they will happen or not. The consequences of errors could cause extremely significant failures or threats for teaching and learning ^[6].

The rest of the paper is organized as follows: The literature review of this tutoring system is discussed in Section 2. Section 3 describes the verification method of a tutoring system by using Petri nets. The simulation results, the real operation of a tutoring system, the comparison with other existing systems, learning results, and students' feedback are presented in Section 4. Finally, conclusion and future work are remarked in Section 5.

2.   Literature review

In this section, we first introduce the concepts of Petri net theory. Then the Text-to-Speech (TTS) is presented to let the tutoring system speak. The Speech Recognition (SR) is presented to let the tutoring system understand users' saying. And the Augmented Reality (AR) is introduced to let users see the virtual objects superimposed upon or composited with the real world.

2.1.   Petri net

Petri net theory was proposed by Dr. Carl Adam Petri in 1962. Petri net is defined as a five-tuple PN = (P, T, F, W, M₀).

P = {p₁, p₂, …, p_n}, n > 0, a finite set of places.

T = {t₁, t₂, …, t_m}, m > 0, a finite set of transitions.

F⊆(P×T)∪(T×P), a finite set of arcs (i.e. flow relation).

W: F→{1, 2, 3, …}, a weight function.

M₀: P→{0, 1, 2, …}, an initial marking (or state).

P∩T = Ø, P∪T≠Ø.

An ordinary Petri net is a four-variable network, PN = (P, T, F, M₀). F denotes an arc that connects the transition to the place or the place to the transition. Petri net is a directed, weighted, and bipartite graph, denoted as G = (V, E). The place and the transition are denoted as the nodes (V). A transition is enabled to fire if it meets the conditions such as weights, where a token transits from its input place i (p_i) to its output place j (p_j). It implies that the state of a system has been changed ^[7,8].

An arc is denoted as E, where G = (V, E) denotes places, transitions and arcs. An arc is used to describe the correlations between places and transitions. It runs in a uni-direction and shows the direction of the token's transition. Weight functions, denoted as w(p_i, t_j) and w(t_j, p_j), can be added to the arcs, representing the condition it needs to transit from place i (p_i) to place j (p_j).

Marking (M) is an m-vector (k₀, k₁, …, k_m), where m denotes the number of places, and k_i > = 0 denotes the number of tokens in place p_i. Initial marking, M₀ denotes a set of tokens in the system. When a set of tokens change, it indicates that the transition is fired. It means that the action of an event, i.e. the dynamic behavior, is described in the Petri net.

A fundamental Petri net is used to describe the change of the state in a discrete event dynamic system, while a complete Petri net model includes places, transitions, and arcs. The flow of tokens is denoted as the state change of the dynamic system ^[9,10,11,12].

In summary, the interpretation of places, transitions, and arcs are shown in Table 1.

2.1.1.   Properties of Petri Nets

The properties of standard Petri net models can be divided into behavioral and structural properties ^[13]. The former refer to the initial marking functions of Petri nets, whereas the latter describe the structures of Petri nets. Furthermore, a Petri net model can be described using the following properties.

The behavioral properties include content reachability, boundedness, liveness, reversibility, coverability, persistence, synchronic distance, and fairness. The structural properties include structurally liveness, controllability, structural boundedness, conservativeness, repetitiveness, and consistency. Safeness, boundedness, deadlock and liveness are the common system behaviors which can be analyzed by using Petri net theory. The safeness means a place in a Petri net is safe if the number of tokens in that place never exceeds one. The boundedness in the Petri net means the number of tokens in a place is limited. The Petri net is K-bounded, which means the number of tokens never exceeds K. Liveness means the situations are without deadlocks.

In this paper, applying two major methods in behavioral properties and a novel method are used to analyze the tutoring system, which contains reachability tree, state equations, and WoPeD.

2.1.2.   Reachability tree

The reachability tree represents the reachability set in a Petri net. The reachability tree is constructed from an initial state M₀. The algorithm begins with the initial state and enters an iterative procedure for a state expansion.

The procedure includes the following:

(1) Generate the next state.

(2) Confirm that the next state is new. If the next state equal to the present state is discarded, it can avoid duplication of the state.

(3) In case of a new state, insert a new state into the reachability tree. By using the reachability tree, we can confirm no deadlocks occurring in this system. An example of reachability tree is shown in Figure 1.

The firing sequence is denoted as t₁, t₂, t_3.

2.1.3.   State equations

A state equation is based on a matrix in a Petri net. An alternative way to the (P, T, I, O) definition of Petri net is to define two matrices D^- and D⁺, which denote the input and output functions, respectively. Each matrix contains m rows (one for each transition) by n columns (one for each place). We define D^-[j, i] = #(p_i, I(t_j)) and D⁺[j, i] = #(p_i, O(t_j)). D^- denotes the inputs to the transition and D⁺ denotes the outputs from the transition ^[14].

The matrix form of a Petri net (P, T, D^-, D⁺⁾ is equivalent to the standard form we have used but allows the definitions to be recast in vector and matrix terms. D = D⁺ - D^- denotes the composite change matrix. Also, by using mathematical formula to calculate the state after a conversion, the formula is denoted as μ' = μ + χ*D.

μ' denotes the next state (reachable from μ).

μ denotes the present state (in the beginning, it means initial marking).

χ denotes a transition vector.

An example of State Equations is shown in Figure 2.

2.1.4.   WoPeD

WoPeD is used to perform the simulation. WoPeD is an open-source software system developed by the Cooperative State University Karlsruhe under the GNU Lesser General Public License (LGPL). WoPeD is used as a simulation tool. The main goal is to provide an easy-to-use software system for modeling, simulating and analyzing processes described by workflow nets ^[15].The WoPeD interface is shown in Figure 3.

In WoPed, the semantical analysis is separated into two parts: one is Wizard and the other is Expert. Wizard part needs to check Workflow net property and Soundness. Expert part is separated into two sub-parts: one is Structural analysis and the other is Soundness. Structural analysis is divided into five parts: Net Statistics, Wrongly used operators, Free-choice violations, S-Components and Wellstructuredness. Soundness is divided into four parts: Workflow net property, Initial marking, Boundedness and Liveness.

The functions of WoPeD include the following:

(1) Process and Resource Editor

(2) PNML Compliance and Import/Export Formats

(3) Soundness Checker

(4) Interactive Simulator and Coverability Graph Visualization

(5) Quantitative Simulation and Capacity Planning

(6) Research Support Tool

(7) AProMoRe Repository Front-End

2.2.   Text-to-speech (TTS)

TTS is a computerized system, in which written texts are synthetically transformed into speech. This technology is often called "Speech Synthesis" ^[16]. The TTS system converts a normal language text into speech. However, other systems render symbolic linguistic representations like phonetic transcriptions into speech ^[17]. The users do not need to pre-record the voice, just key-in the words a computer system.

Recently, the TTS technology is more and more popular, used in daily life, like public broadcasting, automatically reported to the radio message of daily life, automatic earthquake alarm, emergency alert, and language listening tests or exercises, etc. Especially, the foreign language educational applications, in order to improve students' listening comprehension, by using TTS students can learn any language whenever they want and also have the standard pronunciation.

2.3.   Speech recognition (SR)

The main purpose of SR in a computer is to realize the human voice. Some SR systems use "training" (also called "enrollment") where an individual speaker reads text or isolated vocabulary into the system. The system analyzes the person's specific voice and uses it to fine-tune the recognition of that person's speech, resulting in the accuracy increased. Systems that do not use training are called "speaker independent" ^[18]. Systems that use training are called "speaker dependent".

Using SR allows the users to control the computer via voice commands. The SR program can also dictate texts, so that the user can enter a text by voice. It contains a simple instruction to guide the user, and provides training functions, improving the accuracy of identification.

For now, speech recognition applications include voice dialing, voice navigation, indoor device control, voice document retrieval, simple dictation data entry, and so on. In the future, speech recognition, combined with other natural language processing technologies, such as machine translation and speech synthesis, can build more complex applications, such as voice-to-speech translation.

2.4.   Augmented reality (AR)

AR allows users to see the real world, with virtual objects superimposed upon or composited with the real world. Therefore, AR supplements reality, rather than completely replaces it. Ideally, it would appear to the user that the virtual and real objects coexisted in the same space.

AR was divided into two definitions: one was defined by Ronald Azuma in 1997. AR is viewed as a system that has the following three characteristics: 1) Combining real objects and virtual objects, 2) Interactive in real time, 3) Registered in 3-D ^[19]; and the other was defined by Paul Milgram and Fumio Kishino in 1994. The concept of a "virtuality continuum" relates to the mixture of classes of objects presented in any particular display situation, as illustrated in Figure 4. The real environments are shown at the end of the continuum; and virtual environments are shown at the opposite end of the extremum. The former case, at the left, defines the environment solely consisting of real objects and includes for example what is observed via a conventional video display of a real-world scene. The latter case, at the right, defines the environment solely consisting of virtual objects ^[20].

3.   The proposed system

This Section describes the flowcharts of the tutoring system and uses WoPeD to draw the Petri net models for verification.

3.1.   Flowcharts of intelligent tutoring system

The tutoring system contains two parts: one part for teachers and the other for students. Figures 5 and 6 represent the flowcharts of the teacher system and the student system, respectively. The teacher system and the student system can communicate with each other.

In Figure 5, teachers can choose a picture from the file. The picture is shown at the center of the interface. The teacher can adjust the position where the picture appears, input the vocabulary or the short sentence in the text box, and save it into the system. Follow these steps until no more pictures are added.

In Figure 6, students can use the document that is provided by teachers. Click the Start button, the Listen button and listen to the vocabulary or the short sentences. If students cannot listen clearly, they can repeat it until they understand and speak out the vocabulary or the short sentences. Then, if the speech recognition detects that the vocabulary or the short sentence is correct, the vocabulary or the short sentence is displayed in the message box and the picture is displayed on the screen. Repeat these steps until all vocabularies or sentences are pronounced by the system.

3.2.   Tutoring system architecture on WoPeD

In this Sub-section, WoPeD is used to verify the workflow of the tutoring system.

We divide the tutoring system into two parts, including the WoPeD architectures of the teacher system and the student system.

3.2.1.   Architecture of teacher system

The architecture of teacher system is clearly illustrated in Figure 7. p₇ denotes the end-of-system, where the teacher can choose whether to exit the system or not.

The teacher system with interpretation of places and transitions is shown in Tables 2 and 3, respectively.

3.2.2.   Architecture of student system

The student can choose to listen to the vocabulary or short sentences repeatedly. If it is not this case, the student has to pronounce the vocabulary or short sentences through speech recognition process. Figure 8 illustrates the tutoring system architecture for students.

Tables 4 and 5 describe the interpretation of places and transitions in the student system, respectively.

3.3.   Intelligent tutoring system analysis using reachability tree

Applying reachability tree for verification, we need to find the initial marking. By firing transitions t₁, t₂, t_3, …, t_n, the reachability tree is generated accordingly.

3.3.1.   Teacher system

The initial marking is denoted as M_0.

The firing sequence is denoted as t₁, t₂, t₃, t₄, t₅, t₆, t₇, t₈, t_9.

The marking changed sequence is shown as follows:

3.3.2.   Teacher System

The initial marking is denoted as M_0.

The firing sequence is denoted as t₁, t₂, t₃//t₄, t₅, t₆, t₇, t₈, t₉, t₁₀, t_11, t₁₂, t_13.

The marking changed sequence is shown as follows:

3.4.   Tutoring system analysis using state equations

By using formula μ' = μ + χ*D and D = D⁺-D^- to verify the system, we check whether this tutoring system has a deadlock or not.

3.4.1.   Teacher system

In the first step, we calculate the D⁺ and D^-, and get the result of D.

By following the D = D⁺-D^-, we get the result of D, and proceed to the next step by using formula μ' = μ + χ*D. We need to calculate the next state μ', so we denote the χ as t₁ = $\left[\begin{array}{lllllllll}{1} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0}\end{array}\right]$.

Firing t₁, we get

Firing t₁, the next state is μ' = $\left[\begin{array}{lllllllll}{0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} & {0}\end{array}\right]$. It represents that the next state is available to p_2. When firing t2, t3, t4, t5, t6, t7, t8, t9 sequentially, it is verified to be deadlock free.

3.4.2.   Student system

Similarly, by following the operating procedure of the teacher system, we can find the D⁺ and D^- immediately and find the D.

By following the D = D⁺-D^-, we get the result of D. We proceed to the second step by using formula μ' = μ + χ*D. Since we need to calculate the next state μ', we denote χ as $\left[\begin{array}{lllllllllllll}{1} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0}\end{array}\right]$.

Firing t₁, we get

Firing t₁, the next state is μ' = $\left[\begin{array}{lllllllllll}{0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0}\end{array}\right]$. It represents that the next state is available to p_2. When firing t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13 sequentially, it is also verified to be deadlock free.

4.   Experimental results

In this Section, we focus on the WoPeD simulation results. Also, we propose a deadlock example, introduce the tutoring system operating procedure, compare with other existing systems, and obtain the learning results and students' feedback.

4.1.   Simulation results

In this sub-section, the simulation results of the proposed model are discussed. This system uses WoPeD based on the Petri net model. The simulation results of the teacher and the student systems are shown in Figures 9 and 10, respectively. Figure 9 shows the experimental results of the teacher system. This system contains 9 places (with one source place and one sink place), 9 transitions, and 18 arcs. The experimental results of the student system are shown in Figure 10. The student system contains 11 places (with one source place and one sink place), 13 transitions, and 26 arcs. The simulation results indicate that the proposed model can prevent the deadlock from occurring in the tutoring system.

4.1.1.   Teacher system

The semantical analysis contains two parts, namely, Structural analysis and Soundness analysis.

The first part is to perform the Structural analysis, which includes the Net statistics, Wrongly used operators, Free-choice violations, S-Components and Wellstructuredness. In Figure 11, Net statistics show 9 places (p₁, p₂, p_{3, ,} …, p_9.), 9 transitions (t₁, t₂, t_3, …, t_9.), 0 operator, 0 subprocess, and 18 arcs.

The second step of checking procedure is Wrongly used operators. Following the analysis, there are no errors in this analysis. The third step is to check Free-choice violations. We do not find the violations in it, either. The fourth step shown in Figure 12 is to check S-Components. Following the analysis procedure, we have 1 set of S-Components and the S-Components shows 18, including p₁, p₂, p₃…, p₉, t₁, t₂, t_3, …, t₉. It means that all P and T are in S-Components, and also means that no other Places are covered by S-Components.

The fifth step shown in Figure 13 is to check Wellstructuredness, which includes PT-Handles and TP-Handles. Following the analysis, there are no any other errors in it.

The second part is to perform the Soundness analysis which includes the Workflow net property, Initial marking, Boundedness, and Liveness. In the Workflow net property, the first step is to check the Source place, p₁; and in the second step the sink place is p₉, as shown in Figure 14. The third and four steps are transitions with empty preset and transitions with empty postset, which have no any errors, either. The fifth step is to check the Connected components. The Connected components contain the whole P and T, places (p₁, p₂, p₃, …, p₉) and transitions (t₁, t₂, t₃, …, t₉); totally, 18 Connected components. The sixth step is to check the Strongly connected components, and the result is the same as Connected components, as shown in Figures 15 and 16.

In the initial marking, there are no other Wrongly marked places. In the Boundedness, there are no other Unbounded places. In Liveness, there is no any dead transition in it. Therefore, following this step to check the system, the proof without deadlocks in it is completed. The total results are shown in Figure 17.

4.1.2.   Student system

In Figure 8, based on the semantical results, the Net statistics have 11 Places, 13 Transitions and 26 Arcs, and have one S-Component. There are p₁, p_2, p_3, …, p₁₁ and t₁, t₂, t_3, …, t₁₃, totally, 24 S-Components. In the Workflow net property, Source place is p₁, and Sink place is p₁₁. The connected components and strongly connected components are all ones. The Strongly connected components have 24 nodes, including p₁, p₂, p₃, …, p₁₁ and t₁, t₂, t₃, …, t₁₃. The initial marking, boundedness and liveness show that there are no wrongly marked places, unbounded places, dead transitions and non-live transitions.

Thus, based on the same checking steps on the Teacher system, we can get the experimental results of the student system, which does not have deadlocks inside the system, either. The resulting semantical analysis is shown in Figure 18.

4.2.   Experimental results of the intelligent tutoring system

By following the procedure of Petri net verification, users can know how to operate this tutoring system correctly.

4.2.1.   Teacher system operation

Figure 19 shows our teacher system with initial visual screen. Then, we click Open File to choose which one is the picture we need to show on the screen, as shown in Figure 20.

Setting the position of the picture shown on the screen is to follow the center of a face, as shown in Figure 21. This function is completed by face recognition in an AR mark. The next step is to adjust the position we want. Let the Cloud on the top right-hand side of a face, as shown in Figure 22.

Key-in the corresponding vocabulary in the Text box. For example, we key-in the Cloud inside, and click the Save button, as shown in Figure 23.

By following this procedure, we can add more vocabularies and pictures in the teacher system, as shown in Figure 24. If users finish the operating procedure, then the system is closed.

4.2.2.   Student system operation

In the student system, we can just click the Start button. Figure 25 shows the student system with initial visual screen.

After clicking the Start button in the student system, we can just click the Listen button to listen to the vocabulary based on the teacher system setting, as shown in Figure 26.

Users can listen repeatedly if they are not sure what the system is talking about until they can understand clearly, as shown in Figure 27. When users know what the vocabulary is, they can click the Speech Recognition button to speak. When the Speak Now button is clicked, users can speak out the vocabulary they heard, as shown in Figure 28.

If users speak a correct vocabulary, the student system will show the message box, as shown in Figure 29. After clicking the Sure button, the picture is shown on the screen and the position and the big or small size is set in the teacher system, which is not changed in the student system, as shown in Figure 30. The total number of questions and those questions which users have already answered correctly are also shown on the underneath screen.

In other cases, if the system can't recognize users' speaking, the system will not show anything on it, as shown in Figure 31.

By following the operating procedure, we can do more and more exercises, as shown in Figure 32.

We can use the student system to give tests after the teacher taught in class. Let students practice English at home, or let the students with insufficient English ability have a good tutor at home. By using AR, TTS and speech recognition technology in this system will increase the student's interests in learning English and not shy to speak out English.

4.2.3.   Comparison with other existing systems

Comparing with other existing systems in ^[21,22,23], we can find they did not provide convenient usage for teachers and students because most of the systems have already set the vocabularies and made the QR code for the augmented reality of 3D shapes. This tutoring system is aimed to build a convenient environment for the users. Especially, the students' families cannot afford the high cost of Internet system. When teachers teach whenever they can key-in the vocabularies or short sentences immediately without making any 3D shapes first. When students want to learn the new vocabularies or the short sentences by using teacher system at home, they do not need to create the QR code and just need to download the picture they want and use the student system to practice. The most important difference is that other existing systems cannot use the short sentences to further practice but we can, as shown in Figure 33.

4.2.4.   Learning results and students' feedback

Feedbacks on the satisfaction degree of this tutoring system are achieved by asking the students to fill in a questionnaire on the Google Form. Each student may complete the questionnaire once. Each question has ten options that score from one to ten, and there are 21 junior high school students invited to answer the questions below.

Q1-"What overall grade would you give to this tutoring system?" (80.95%)

Q2-"The tutoring system has improved my understanding of English."(82.85%)

Q3-"The tutoring system has helped my understanding of the correctly pronouncing English."(83.80%)

Q4-"The tutoring system has helped me increase the interest in learning English."(78.09%)

Q5-"The tutoring system has helped me learn English whenever I want."(81.42%)

Q6-"The tutoring system has provided me with a convenient environment without any teaching aids." (82.85%)

Q7-"The tutoring system has helped me learn English by myself without teachers." (87.38%)

Q8-"By using this tutoring system, I won't be shy to speak out English." (84.04%)

Q9-"By using this tutoring system, I can control the speed when I am learning English." (85.95%)

Q10-"By using this tutoring system, I love this novel way to learn English than the traditional way. " (80.47%)

Q11-"I will use this tutoring system to practice my English in the future." (78.09%)

Q12-"I will invite my friends to use this tutoring system." (81%)

According to the above results, if the satisfaction level 79% is set to be a successful criterion, then those items except Q4, Q11 have achieved the successful criteria.

5.   Conclusion

This paper has proposed a novel method to verify the intelligent tutoring system by applying Petri nets. We first build a workflow using WoPeD, and apply two major Petri net analysis methods to verify the intelligent tutoring system. The first method is reachability trees and the second method is state equations, which are used in WoPeD to get the simulation results. We also build a tutoring system for teachers and students based on Augmented Reality (AR), Text-to-Speech (TTS), and Speech Recognition (SR). The contributions of this paper are presented as follows:

(1) Using reachability trees of Petri net can verify the tutoring system immediately.

(2) The tutoring system can be proved to have no deadlocks by using the state equations.

(3) The Petri net model built by a simulation tool, WoPeD, is analyzed to ensure that there is no overflow and deadlock problems caused in the tutoring system.

(4) By using WoPeD, we can build the tutoring system easier.

By following the students' feedback, this tutoring system has shown to provide a convenient environment where students can practice English at home.

In the future, we will achieve the goal with a more powerful tutoring system in order to help students learn other languages.

Acknowledgments

The authors are very grateful to the anonymous reviewers for their constructive comments which have improved the quality of this paper. Also, this work was supported by the Ministry of Science and Technology, Taiwan, under grant MOST 107- 2221- E-845- 002-MY3.

Conflict of interest

The authors have declared that no conflict of interest in this paper.