User Tools

Site Tools


vidi:approach

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
vidi:approach [Monday, 16 March 2009 : 12:41:20]
lefeber
vidi:approach [Thursday, 02 April 2009 : 16:34:48] (current)
hvrooy
Line 1: Line 1:
 +====== Research proposal ======
 +=====Approach=====
 +The candidate is aware that a large amount of literature is available on stochastic
 +multi-class queueing networks, assuming stochastic inter-arrival
 +and service times. Nevertheless,​ the main emphasis of this proposal is on
 +//​deterministic// ​ flow networks, since it is necessary to first
 +understand the essence of controller ''​design'' ​ for networks of
 +switched servers.
 +That is, we consider the amount of jobs as a continuum and we assume
 +deterministic arrival and processing rates. Furthermore,​ as we would like to
 +derive tailor made controllers,​ we assume that the network is completely known
 +a priori and its structure is not subject to change. Typical examples of such
 +networks are manufacturing systems with machines serving different types of
 +jobs and urban road networks with traffic lights serving
 +cars from different directions, as illustrated in
 +Figure [vidifig1].
 +
 +The proposed approach is based on ideas from nonlinear control theory. A
 +parallel can be drawn with an autopilot for an airplane. For a given airplane,
 +first a feasible reference trajectory should be specified. Next, the autopilot
 +uses this desired reference trajectory to determine what control actions to
 +apply given the current state of the airplane (position, speed, orientation,​
 +etc.). No matter what reference trajectory is given, the autopilot comes up
 +with suitable control actions. Similarly, for a given network of switching
 +servers, first feasible network behavior should be specified. Next, this
 +desired reference can be used to determine what servers should be doing, based
 +on the current state of the system. Also in this case, no matter what
 +reference trajectory is given, suitable control actions
 +for the network should be determined.
 +
 +An approach for deriving these control actions for an autopilot is by
 +means of Lyapunov'​s direct method, cf.  [[#​References|references]]. The basic idea
 +behind Lyapunov'​s direct method is that whenever the total energy of a
 +mechanical or electrical system is continuously dissipated, the system must
 +eventually settle down to an equilibrium point. So if we are able to come up
 +with a kind of `energy-function'​ for the error-dynamics of the system under
 +consideration,​ and if we are able to design our controller such that this
 +energy is decreasing all the
 +time, the system should settle down to a constant energy level and we may
 +conclude stability of our system.
 +
 +When controlling a network of switching
 +servers towards feasible desired reference behavior we might apply similar ideas, as
 +the applicant introduced in  [[references#​References|references]]. In that paper we showed that starting from given
 +desired network behavior, it is possible to derive a Lyapunov function
 +candidate by considering the difference of the amount of work in the system with
 +respect to that of possible desired behavior. By making this Lyapunov function
 +candidate always decrease as much as possible,
 +a network controller can be derived which makes the network behavior converge to the desired
 +network behavior. In  [[references#​References|references]] we showed that the same idea can also be
 +applied when buffer constraints need to be taken into account.
 +
 +
 +The controllers resulting from the approach introduced in  [[#​References|references]] are
 +central controllers (or state-feedback controllers)
 +which determine for each server when to switch to what job type,
 +based on global state information. In a manufacturing setting, global
 +information usually is available and a central controller can be
 +implemented relatively easily. ​ However, for controlling urban road networks
 +with traffic lights, implementing a central controller is almost
 +infeasible. In the latter case, distributed controllers are needed, i.e. each
 +intersection should have its own controller which, based on local information only,
 +decides what to do. This relates to the concept of dynamic output feedback from control
 +theory.
 +
 +Consider again the problem of controlling an airplane, or any other mechanical
 +system. Usually a controller needs both position and velocity for determining
 +the required control action. However, often only position measurements are
 +available. Nevertheless,​ after measuring positions for a while, usually the velocity is
 +rather well known. So to overcome the problem of missing velocity measurements
 +an observer for the velocity is built based on both the system dynamics and
 +the position measurements. Subsequently,​ instead of velocity measurements
 +the controller uses the estimates for the velocity obtained from the
 +observer.
 +
 +As an example of this observer design, consider the dynamics
 +
 +<​math>​
 +x(k+1) = A x(k)
 +y(k)   = C x(k)
 +</​math>​
 +
 +where <​math>​x(k)\in R^n</​math>​ denotes the state-vector at time <​math>​k\in Z</​math>,​ <​math>​y(k)\in R^m</​math>​
 +the available measurements,​ and <​math>​A</​math>​ and <​math>​C</​math>​ are matrices of appropriate
 +dimensions. An observer for <​math>​x</​math>​ is given by
 +
 +<​math>​
 +\hat x(k+1) = A \hat x(k) + L[y(k)-\hat y(k)]
 +\hat y(k)   = C \hat x(k),
 +</​math>​
 +
 +where <​math>​\hat x(k)</​math>​ denotes an estimate for the state-vector at time <​math>​k</​math>,​
 +<​math>​\hat y(k)</​math>​ denotes the estimated outcome of the measurements,​ and <​math>​L</​math>​ is a matrix
 +with appropriate dimensions. ​ Notice that whenever <​math>​\hat x(k)=x(k)</​math>,​ the
 +dynamics (??) reduces to (??). Whenever <​math>​\hat x(k)\neq x(k)</​math>​ this can only be noticed by a difference between <​math>​\hat y(k)</​math>​
 +and <​math>​y(k)</​math>​. This difference is used for updating the state
 +estimate. ​ If we define the observation error <​math>​e(k)=x(k)-\hat x(k)</​math>​ we obtain
 +for the observation error dynamics
 +
 +<​math>​
 +e(k)=[A-LC]e(k).
 +</​math>​
 +
 +Therefore, the observation error converges to zero iff it is possible to choose <​math>​L</​math>​ such that all eigenvalues
 +of the matrix <​math>​A-LC</​math>​ are strictly within the complex unit disc.
 +This can be done if
 +
 +rank<​math>​
 +\begin{bmatrix}
 +C \\
 +CA \\
 +CA^2 \\
 +\vdots \\
 +CA^{n-1}
 +\end{bmatrix}
 +=n.
 +</​math>​
 +
 +We propose to use the idea of observers for deriving distributed policies for switching networks.
 +Since the layout of the network is known, as well as the controllers used in each server,
 +under certain conditions it is possible for a server to reconstruct the global state of the
 +system based on local information only.
 +To illustrate this, consider the example introduced in  [[#​References|references]].
 +
 +{{vidifig2.gif|The system introduced in [[#​References|references]].}}
 +
 +A single job-type is considered which
 +first visits machine A, then machine B, then machine B again, and
 +finally machine A again. The successive buffers visited are denoted
 +by 1, 2, 3, and 4, respectively. The constant input rate <​math>​\lambda</​math>​ into buffer 1
 +is 1 job/​time-unit,​ while the maximal process rates required at the buffers
 +are <​math>​\mu_1=1/​0.3</​math>,​ <​math>​\mu_2=1/​0.6</​math>,​ <​math>​\mu_3=1/​0.3</​math>,​ and <​math>​\mu_4=1/​0.6</​math>,​
 +respectively. Lastly, the times for setting up buffers 1 and 4 at
 +machine A are <​math>​\sigma_{41}=50</​math>​ and <​math>​\sigma_{14}=50</​math>,​ the times for
 +setting up buffers 2 and 3 at machine B are <​math>​\sigma_{32}=50</​math>​ and
 +<​math>​\sigma_{23}=50</​math>​.
 +
 +As shown in [[#​References|references]],​ the orbit which minimizes both the mean amount of jobs
 +and the mean amount of work in the system (as well as the mean flow time of jobs
 +in the system) is depicted in \figurename ---fig:​orbit---.
 +
 +{{vidifig3.gif|Evolution over time of both buffer contents and amount of work for the desired periodic behavior.}}
 +
 +As shown in  [[#​References|references]],​ the following controller can be //derived// , which achieves
 +convergence towards this desired behavior:
 +
 +  * If initially in \mode13, switch to \mode12.
 +  * If in \mode12, stay in this mode until both <​math>​x_1=0</​math>​ and  <​math>​x_2+x_3\geq 1000</​math>​. Then switch to \mode42. ​ Both machines serve at the highest possible rate (which might be  the arrival rate).
 +  * If in \mode42, stay in this mode until both <​math>​x_2=0</​math>​ and  <​math>​x_4\leq 83\frac{1}{3}</​math>​. ​ Then switch to \mode43. ​ Both machines serve at the highest possible rate (which might be  0).
 +  * If in \mode43, stay in this mode until <​math>​x_3=0</​math>​. Then switch to  \mode12. ​ Both machines serve at the highest possible rate (which might be  0).  ​
 +
 +Clearly, this controller is a central controller, since switching Machine A from buffer 1 to buffer 4 or vice versa
 +requires state information at Machine B. Also, switching Machine B from buffer 2 to buffer 3 requires state information at Machine A.
 +
 +Nevertheless,​ using the concept of observers, a distributed implementation can be made.
 +It is relatively easy to see that for Machine B the following controller can be used as well:
 +
 +  * Serve step 2 at the highest possible rate (which might be at the  arrival rate or even idling) until both <​math>​x_2=0</​math>​ and at least 1000 jobs  have been served. Then switch to step 3.  ​
 +  * Serve step 3 at maximal rate until <​math>​x_3=0</​math>​. Then switch to step 2.
 +
 +At first sight, the controller for Machine A does need global state information. However,
 +using the knowledge of the layout of the system as well as the controller implemented
 +at Machine B, the required state information can be reconstructed. For instance,
 +when jobs stop arriving from Machine B to Machine A at step 4, Machine A knows that apparently
 +buffer 3 has become empty. Since Machine A also knows when service of buffer 3 started,
 +it can even determine when Machine A started and stopped serving buffer 2 before serving
 +buffer 3. Finally, since Machine A has been sending jobs to Machine B, Machine A is able to reconstruct the
 +global state information,​ which can then be used in the controller for Machine A.
 +The estimate at Machine A can be updated as soon as jobs start or stop arriving from Machine B.
 +Applying these insights results in the following controller for Machine A, as
 +explained in  [[#​References|references]]:​
 +
 +  * If serving step 1, continue until both <​math>​x_1=0</​math>​ and at least 1000  jobs have been served. Then switch to step 4. Let <​math>​{\bar x}_1</​math>​ be the  number of jobs served during this mode.  ​
 +  * Let <​math>​{\bar x}_4</​math>​ denote the number of jobs in buffer 4 when the  setup to serving step 4 has completed. If serving step 4, continue until  <​math>​{\bar x}_4+\frac{1}{2}{\bar x}_1</​math>​ jobs have been served. Then switch to  step 1.
 +
 +It has been shown in  [[#​References|references]] that using these distributed controllers, ​
 +convergence of the system behavior towards the behavior as depicted in \figurename ---fig:​orbit--- is guaranteed.
 +
 +This example shows that it is possible to use the notion of observers from control theory to
 +derive tailor made distributed controllers for a deterministic flow network of switched servers
 +with setup times.
  
vidi/approach.txt · Last modified: Thursday, 02 April 2009 : 16:34:48 by hvrooy