vidi:approach

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

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

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International