RSD-TR-23-86 Controlled Discrete Events Generated By Diffusion-Threshold Processes by Charles J.Q Cqonrad N. Harris McClamrocht*~ and Chih-Ping Lee" ~Mictron, Inc. 1624 Meijer Drive Troy, Michigan 48084 tDept of Aerospace Engineering *Dept of Electrical Engineering & Computer Science The University of Michigan Ann Arbor, MI 48109 October 1986 CENTER FOR RESEARCH ON INTEGRATED MANUFACTURING Robot Systems Division COLLEGE OF ENGINEERING THE UNIVERSITY OF MICHIGAN ANN ARBOR, MIChIGAN 48109-1109

,~-A a f." ) "'i, I A, V i, iii Ls sv A Q',

RSD-TR-23-88 TABLE OF CONTENTS 1. Introduction............................................................................................ 2. The Diffusion-Threshold Process........................................2................... 3. A Specific Class Of Diffusion-Threshold Processes................................. 5 4. Comparison with the Intensity Characterization.................................... 6 5. Applications of Diffusion-Threshold Processes........................................ 7 6. References........................................................9....................................... I

RSD-TR-23-86 ABSTRACT A class of discrete event (or point) processes are introduced that arise from an underlying diffusion-threshold process. This approach permits the natural incorporation of control through the evolution of a controlled diffusion. The general formulation is indicated, and a specific class is described where particular control theoretic results have been obtained. This general viewpoint is consistent with many applications where the rate at which discrete events occur is influenced by an underlying dynamic process.

RSD-TR-23-88 1. Introduction In this paper, a new approach to the formulation of controlled stochastic discrete event processes is proposed. Included in this class of processes are controlled queues and controlled renewal processes. Since such stochastic processes have wide applicability as models in manufacturing, operations research and computer science (inventory, scheduling, production lines, reliability, waiting lines, etc.) an attempt to incorporate explicit control mechanisms into such processes is of substantial intellectual and practical interest. Our intention is not only to introduce control mechanisms such that discrete control parameters can be adjusted, but it is also to allow the incorporation of system adaptivity based on information feedback. Such control capability goes beyond the selection of stopping times, routing strategies, or other discrete control actions; in particular a mechanism is proposed which allows the introduction of a general class of feedback control actions which influences the rate of evolution of the discrete event process. The basic idea proposed in the paper is that discrete events arise as a result of some causal mechanism which can, in many cases, be modeled by a continuous time controlled (stochastic) dynamical system. It is a natural view that discrete events occur at times when the solution of the underlying dynamical system satisfies a specified condition. Control mechanisms can be introduced into the underlying continuous time dynamical system so that the control directly affects the Discrete Events 1

RSD-TR-23-86 evolution of the underlying dynamics and indirectly affects the evolution rate of the discrete event process. In addition, the control action in the underlying dynamical system may depend on feedback information consisting of the history of the discrete event process and/or the history of the underlying dynamical system. That is, feedback control may result in closed loop coupling between the discrete event process and the underlying controlled dynamics. 2. The Diffusion-Threshold Process Let *t denote the solution to the controlled stochastic differential equation dz = b(zt, ut )dt + a(xt, ut )dwt (1) corresponding to o = z o. Define the stopping time T1 > 0.by T= inf t > 0: g(;= 0 (2) where b: R2 - R is the drift function, a: R2 —, R is the diffusion function, and g: R 1.. Rl is the stopping function; here wt is a standard Brownian motion. At time T1, the diffusion process is reinitialized to ZT + = X1 and xt continues to evolve according to equation (1) until the stopping condition is again satisfied, defining T2 > T1. Continuing in this way, the processes xt, t > 0, and { T;, i=0,1,2, ~ ~ ~ } are successively defined, with To = 0. Thus, xt, t 2 0, is a controlled diffusion [5,61, satisfying equation (1) except at T;, i=0,1,2, *, where it may be discontinuous; and { Ti, i=0,1,2,. } are defined recursively by 2 Discrete Events

RSD-TR-23..86 Tj= inf t > T,1: g(xt) = (3) Assume the reinitialization sequence (Xi, i=0,1,2, ~ ~ ~ ) is a set of independent random variables. We refer to the random process;t, t > 0, as a diffusion-threshold process, to { T,, i=0,1,2, * - )*} as the event times and to ut, t > 0, as the control process. We also define a counting process Nt, for t > 0, such that Nt is piecewise constant with unit jumps at the event times T;, i=0,1,2, * *, initialized by No = 0. Note that sample paths of xt, t > 0, are piecewise continuous (left continuous) with jumps at the event times defined by the reinitialization sequence; an example sample path is shown in Figure 1. If suitable assumptions are made about the control then { 7T, i=1,2, } are controlled stopping times for the diffusion and they define a renewal process that specifies the times at which jumps in the counting process occur. Although the interevent times { Ti - T1, i=1,2, ~ ~ ~ ) may be independent their distribution is not exponential; hence the interevent times are not memoryless. Extensions to the case where the counting process is vector valued, with each scalar process evolving according to an underlying continuous time dynamical system can be made. The details are complicated but should be conceptually clear. Control action enters the diffusion-threshold model through the drift and diffusion coefficients, so that the control affects the intensity of the discrete event Discrete Events 3

RSD-TR-23-86 process. The control may be deterministic (open loop) or stochastic (closed loop). In the latter case, the control may be a stochastic process that is conditionally dependent on the event history and the history of the counting process [8]. We also mention an additional important feature of the above diffusionthreshold model for controlled discrete event processes. Since there is an underlying diffusion-threshold process explicit in the model, the control may depend on the history of that process. This allows incorporation of feedback from the diffusion-threshold process that characterizes the underlying dynamics that give rise to discrete event changes; this feature of the model has been found to be extremely important in certain applications [3,4]. The use of a diffusion-threshold model to capture the underlying dynamics of -a discrete event process provides a view different than that which is usually found in the literature. In particular, the usual viewpoint of discrete event (point) processes have been classified as moment oriented or intensity oriented [1]. Although the diffusion-threshold approach is compatible with these other views, it also offers a different viewpoint, since the model allows for the existence and utilization of information structures not normally considered in the moment or intensity formulations. Of course, this additional information exacts a cost in terms of added complexity and computational difficulty. The diffusion-threshold model also provides a closer contact with the physics of event generation than is conveyed by either the moment or intensity points of view. 4 Discrete Events

RSD-TR-23-86 3. A Specific Class Of Diffusion-Threshold Processes A class of controlled discrete event processes, defined from a diffusionthreshold process, has been studied in [3,4] where some specific control theoretic results have been obtained. This specific class is characterized by the assumption that the drift function b and the diffusion function a are independent of the diffusion-threshold process xt but may depend on the control process ut; the reinitialization sequence is X, = 0, i=0,1,2, ~ ~ ~; and the stopping condition is defined by a threshold crossing, i.e. g(z) = z-A. Assume the control ut is constant during the time between events and assume that A > 0, b(u) > 0, a(u) > 0 where the control dependence is explicitly indicated. An analytic expression for the probability density of the time between events ri = Ti - Ti_l can be obtained as an explicit function of the control. In particular, the density for ri has been derived in [3,4] as q (t;u) - A exp -(- )t) t >0 ~/-f(U) 3/2 z2(u)2t (4) 0, t < 0. where ut = u, Ti_l < t < Ti. This probability density is referred to as inverse gaussian and has been previously studied in [2,9]. Under the stated assumptions, a threshold crossing occurs almost surely, i.e. P[ri < oc] = 1, i=1,2, - -. The central moments are easily computed; we give only the mean and variance as EI[] = Ab(u)-l (5) Discrete Events 5

RSD-TR-23-86 Var[r; = Aa(u)2b(u)-3 (6) Thus the mean time between events is equal to the "distance" A divided by the positive drift rate b. Note that this distribution is explicitly parameterized by the value of the control action through the drift and diffusion coefficients. It is this explicit parameterization that provides a clear means for dealing with controlled discrete event processes, for this class. The above expression for the interevent density also holds if the control is constant between events, but with random values that are conditionally dependent on the event history and the history of the counting process. However, the interevent times may no longer be a renewal process. 4. Comparison with the Intensity Characterization Our formulation of controlled discrete event processes is in contrast with the developments in [1,8] where control mechanisms are abstractly formulated as influencing the intensity of the counting process. Here the control mechanism is explicitly formulated through the underlying diffusion-threshold process. For the specific case described in Section 3 it is possible to characterize the discrete event process in terms of an intensity that can be explicitly computed using the inverse-gaussian density. Thus it is possible to compare the diffusionthreshold characterization and the intensity characterization. 8 Discrete Events

RSD-TR-23-86 For our purposes, the history will be the event time record, denoted by {F, t < 0); this is the usual history considered. Then, heuristically, the intensity X, of the discrete event process is defined by Xt dt = P[dNt = I Ft (7) where dNt = 1 denotes a unit change in the counting process. The intensity Xt is necessarily a stochastic process. However; it is easily characterized in terms of the inverse gaussian density. The intensity Xt, Tj-1 < t < Ti, given Ti_l and ut = ui_l, Ti.1 < t < T7 is q,(t - Tij; uji) Xt = o, Ti_ < t < Ti (8) f qi (q; ui -l) dq t- ToT-1 The key feature of the intensity is that it is a stochastic process with sample paths that are piecewise continuous with discontinuities at the event times; its functional dependence on the control is indicated in equation (8). It can also be viewed as a regenerative process. An example sample path for the intensity is shown in Figure 2. 5. Applications of Diffusion-Threshold Processes It is important to make the case that diffusion-threshold models for controlled discrete event processes do represent, in a natural way, many physical situations. Our formulation has the advantage that it imposes a proper perspective in terms of model development; one simply examines the physical causal Diuscrete Events 7

RSD-TR-23-86 mechanisms that give rise to discrete events as a part of the modeling effort. This approach has been effectively used in [3,4] to model failures in drilling operations, where drill failure is assumed to be caused by drill wear reaching a fixed threshold. In this case, the tool wear is the diffusion-threshold process, the cutting speed is the control variable with is assumed to influence the tool wear according to a simple diffusion with drift as indicated in Section 3. The tool wear is reinitialized to zero when a failure event occurs, corresponding to replacement of a new tool. The model in Section 3 was used to formulate and solve a stochastic optimal (feedback) control problem corresponding to economic selection of the cutting speed. The results in [3,41 also incorporate several additional features, including the notion of discrete parts and tool replacement before failure; details are given in [3,4]. In [3] diffusion-threshold models have been developed for failure control of multi-tooled machines by selection of cutting speed, for failure control of serial transfer lines by selection of operating speeds of individual machines, and for. productivity control through supervision. A diffusion-threshold process has also been used to model the service timlres in a M/IG/1 queue, so that the service time distribution is inverse gaussian and depends on a control "work rate". Our formulation in Section 3 is the basis for formulation and solution of the (open loop) optimal control problem of minimizing the weighted sum of sojourn time and control effort. Preliminary results are given in [7]. 8 Discrete Events

RSD-TR-23-86 These efforts represent initial attempts to exploit the proposed framework for controlled discrete event processes. It is expected that this proposed framework can provide a basis for examination of many additional problems in manufacturing, operations research, and computer science. 6. References [1] Bremaud, P., Point Processes and Queues, Springer-Verlag, New York, 1981. [2] Chhikara, R.S. and Folks, J.L., "The Inverse Gaussian Distribution as a Life Time Model," Technometrics, 19, 1977, 461-468. [3] Conrad, C.J., Stochastic Modeling and Control of Some Problerns in Manufacturing, Ph.D. dissertation, The University of Michigan, July, 1986. [4] Conrad, C.J. and McClamroch, N.H., "The Drilling Problem: A Stochastic Modeling and Control Example in Manufacturing," to appear in IEEE Transactions on Automatic Control. [51 Fleming, W.H. and Rishel, R.W., Deterministic and Stochastic Optimal Control, Springer-Verlag, New York, 1975. [6] Krylov, N.V., Controlled Diffusion Processes, Springer-Verlag, New York, 1980. Discrete Events 9

RSD-TR-23-86 [7] Lee, C.P., "Control of Queues with Service Times Modelled by Diffusion Threshold Processes," Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, September, 1986. [8] Snyder, D.L., Random Point Processes, John Wiley, New York, 1975. [9] Tweedie, M.C.K., "Statistical Properties of Inverse Gaussian Distributions, I" Ann. Math. Stat., 28, 1957, 362-377. 10 Discrete Events

UNIVERSITY OF MICHIGAN 1IIIIli'l'llllli iillll ll RSD.TR- 23-86 3 9015 02656 7191 Figure 1 Figure 2 Discerete Events