New version page

Modeling of, and Reasoning with Recurrent Events with Imprecise Durations

Upgrade to remove ads

This preview shows page 1-2-3-4 out of 12 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Modeling of, and Reasoning with Recurrent Events with Imprecise Durations Stanislav Kurkovsky1 and Rasiah Loganantharaj2 Department of Computer Science1, Columbus State University, [email protected] Automated Reasoning Laboratory, Center for Advanced Computer Studies2 University of Louisiana at Lafayette, [email protected] Abstract. In this paper we study how the framework of Petri nets can be extended and applied to study recurrent events. We use possibility theory to realistically model temporal properties of the recurrent processes being modeled by an extended Petri net. Such temporal properties include time-stamps stored in tokens and durations of firing the transitions. We apply our method to model the recurrent behavior of an automated manufacturing cell. 1. Introduction Many events occurring in the real world are of repetitive in nature, that is, an event occurs more than once over a span of time. There are numerous attempts to study recurrent events in terms of qualitative relations among events and tasks. It is possible to have infinite relations among tasks in repetitive events [21]. In this paper, we focus on a repetitive event, in which the task sequence satisfies the given quantitative constraints of the event. While the sequence of tasks in the repetitive event remains the same, the duration of each repetition may differ since each task in each cycle may take different time to complete due to availability of different equipment, environmental factors, etc. The impreciseness of the task duration must be modeled. Further, we need a formal mechanism to model sequence of tasks or to maintain the partial order constraints imposed by the event. Once each task is appropriately represented with imprecise duration and we have a formal mechanism to maintain the task precedence relation in an event, we need to reason with the duration for a given specified cycle of the repetitive events. In this paper, we use fuzzy logic to represent imprecise duration and extend Petri net framework to maintain precedence requirements among the tasks and as well as to reason with distance among repetitions of events. The paper is organized as follows. We provide the background information on Petri nets and representing recurrent events in section 2, which is followed by a review on timed Petri nets. In section 4, we describe possibilistic representation of time, which is followed by presenting algorithms for timed Petri nets with possibilistic time. Section 6 presents the results of experiments on modeling a system exhibiting a recurrent behavior. In section 7 we summarize the conclusion of this paper.2. Background Information of Petri Net Theory Ever since the introduction of the Petri net theory by Petri in his Ph.D. dissertation, it was widely used for modeling dynamic systems in the most diverse domains. Petri net is a graph-based structure consisting of places and transitions. Each transition is connected by, and connected to at least one place. When modeling tasks using Petri network, each place that connects to a transition corresponds to a pre-condition and the transition corresponds to a task. When a token is in a place, then the precondition denoted by the place is said to be satisfied. Consider a partial order of tasks A < C, B < C (the tasks A and B must be completed before C). When transition TA fires (task A completes), it generates a token and it is placed in PA. Similarly, when transition TB fires (task B completes), it generates a token and it is placed in PB. When there is at least one token in both PA and PB, the transition TC is enabled. Thus the following Petri network models the partial order of tasks A<C, B<C (Figure 1). PA PB TA TB TC PC Fig. 1. Petri net graph Modeling Non-deterministic Behavior Let us use an automated manufacturing cell shown in Figure 2 to illustrate how to model non-deterministic behavior of a dynamic system. The cell is composed of three machines, a robot and, input (In) and output (Out) buffers. Parts are coming into the cell and are stored in buffer In of unlimited capacity. Parts can be processed by any one of the three machines (determined non deterministically), namely, Machine 1 (M1), Machine 2 (M2), or Machine 3 (M3). Each processed part is removed from the buffer of the respective machine and is placed in buffer Out of unlimited capacity. Robot transfers parts between the buffers and machines. Robot is non-preemptive and at each moment it can be used to either load a part from buffer In to any of the machines, or to unload a processed part from any of the machines to buffer Out. RobotInOutMachine 1Machine 2Machine 3 p2 p3 t1 t2 t7 t8 p4 t3 t9 p1 p12 p8 p9 t4 p10t5 p11t6 p5 p6 p7 Fig. 2. An automated manufacturing cell and the corresponding Petri net graph. A cyclic event has the following tasks: the robot arm picks a part from the In buffer and then transfers it to the buffer of one of the three machines, M1, M2, and M3. Oncethe part is processed by the selected machine, the robot picks the part and leaves it in the output buffer. Let us consider a portion of the Petri net that models the robot picking a part from the In buffer and leaving it in the buffer of any one of the three machines. Once the part is placed in the buffer of a machine, the robot becomes free for other activities. The availability of a part in the In buffer is modeled as a token placed in p1. Similarly, the availability of the robot is modeled by placing a token in place p8. The transitions t1, t2 and t3 respectively represent activity of placing a part in the buffer of machines 1, 2 and 3. Initially the three transitions, t1, t2 and t3 are enabled, but only one can be fired at a time. When more than one transition is enabled, a transition from the enabled ones is selected either randomly or using some heuristic bias. This is how one models non-deterministic process in Petri network model. Once a transition is fired, a token from each incoming place is removed and a token is placed to each outgoing place. When t2 fires, a pair of tokens, one from p1 and another from p8 are removed and a token is placed in each outgoing places (p3 and p8). The problem is somewhat complicated if we impose a constraint that the buffer size of machines 1, 2 and 3 is exactly one. Modeling Recurrent Events We have described the tasks that occur in an instance of the event. It an event repeats continually, the robot is free to take parts and place it in an empty buffer of a


Download Modeling of, and Reasoning with Recurrent Events with Imprecise Durations
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Modeling of, and Reasoning with Recurrent Events with Imprecise Durations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Modeling of, and Reasoning with Recurrent Events with Imprecise Durations 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?