Predictive Statistic Network Control (PSNC)

Aims:      close to optimum allocation of resources. minimization of required data flow. Assumptions:      future use of specified resources are approximately predictable. the network can tolerate small differences in allocated and actually used resources: the network offers sufficient buffer capacity such as queues at stops or exchangers, cabin and carrier stores or a track with variable density of carriers. the local control subsystems can deal with a buffer overflow, such that the user will not notice it.

Advantages:      universal: almost independent of applied carrier/track technology. tolerant: isolated, small prediction errors do not effect the logistics, but future congestion can be identified and avoided in a linear fashion. Disadvantages:      Possibility of sub-optimum operation compared with a completely deterministic approach.

The previous considerations of the logistic concept where more of a technical nature: which module is doing what and exchanging which information with other modules.

In the sequel we discuss methods on

• how the future of a module can be estimated in terms of required resources.
• how to find the criteria whether a allocation request for the future is granted or refused.

The Predictive Statistic Network Control (PSNC) is one possible method that needs to be verified by realistic system-level computer simulations.

The random buffered network model

A buffer can be any track element , such as lines, stops, carrier exchanger, or cabin and carrier stores. Property:

• a cabin or carrier enters the buffer at connecting point 1 and at time t=0 and
• the cabin leaves the buffer at connecting point 2 and at time $t=\tau_{1,2}$, where $\tau_{1,2}$ is randomly distributed with the probability density function $g_{1,2}(\tau_{1,2})$.

Each estimation is based on a model that represents the reality ``good enough'' for the purpose of the respective estimation. Other models may be more realistic, but more difficult to analyse and to compute. The probability density function $g_{1,2}(\cdot)$ could also depend on other parameters $\psi_{1}(\tau_{1,2}), \psi_{2}(\tau_{1,2}), \cdots$ that are known or can be estimated at time $\tau_{1,2}$ such that the characteristics of the buffer are determined by

$$g_{1,2}\left(\tau_{1,2}, \psi_{1}(\tau_{1,2}), \psi_{2}(\tau_{1,2}), \cdots\right)$$

Examples of $g_{1,2}(\tau_{1,2})$ for different buffer types:

Input-Output behavior of random buffer

Assumption: the entrance time t₁ of cabin or carrier is random and represented by the probability density function $\rho_{1}(t_{1})$.

Then the I/O behavior is characterized by the convolution

$$\begin{eqnarray*}\rho_{2}(t_{2})&=& \int_{\tau=-\infty}^{+\infty}\!\!\!\!\! g_... ...ho_{1}(t_{2}-\tau) d\tau \\ &=&(g_{1,2} \star \rho_{1})(t_{2}) \end{eqnarray*}$$

The convolution $\rho_{2}(t_{2})= (g_{1,2} \star \rho_{1})(t_{2})$ is only valid if $g_{1,2}(\cdot)$ and $\rho_{1}(\cdot)$ are statistically independent, which is a reasonable assumption.

I/O behavior of random buffer chain

The Input-Output behavior of the buffer chain is characterized by

$$\rho_{c}(t_{c})=(g_{c-1,c} \star \cdots \star g_{2,3} \star g_{1,2} \star \rho_{1}) (t_{c})$$

Average arrival time $\bar{t}_{c}$ at connecting point c:

$$\bar{t}_{c}=\bar{\tau}_{c-1,c} + \cdots + \bar{\tau}_{2,3} +\bar{\tau}_{1,2} +\bar{t}_{1}$$

Variance $\mbox{Var}\left[t_{c}\right]$ of arrival time t_c at connecting point c:

$$\mbox{Var}\left[t_{c}\right]=\mbox{Var}\left[\tau_{c-1,c}\rig... ...mbox{Var}\left[\tau_{1,2}\right] +\mbox{Var}\left[t_{1}\right]$$

where $\mbox{Var}\left[\tau_{c-1,c}\right]$ is the variance of $\tau_{c-1,c}$.

Gaussian distribution of arrival time after a chain of buffers

Example of network model for cabins

Time estimations with random buffers

Estimated arrival time:

$$\hat{t}_{3}=\bar{t}_{3}=\bar{\tau}_{4,5}+\bar{\tau}_{5,7}+\ba... ...+\bar{\tau}_{9,14}+\bar{\tau}_{14,17}+\bar{\tau}_{17,18}+t_{0}$$

Variance of estimated arrival time:

$$\mbox{Var}\left[t_{3}\right]\!\!=\!\!\mbox{Var}\left[\tau_{4,... ...tau_{14,17}\right]\!\!+\!\!\mbox{Var}\left[\tau_{17,18}\right]$$

Time slots

The predictions are time discretized in time slots of duration T. The duration T depends on the dynamics on a specific track element. The probability p_i,m(k) that vehicle i enters connecting point c_i,m during the time slot k is determined by

$$p_{i,m}(k)=\int_{kT}^{(k+1)T}\!\!\!\!\!\!\!\!\!{\rho_{i,m}(t)dt}$$

where $\rho_{i,m}(t)$ is the probability density function of vehicle i at connecting point c_i,m .

Time slots is a concept that is know in air-traffic control: the air traffic controller (which are still humans) assign a time-slot to each airplane, that wants to start or land, whereby one airplane is assigned to one times-lot. For the PSNC we want to automate this process, and a first step is to estimate the probability that a vehicle occurs in a certain time-slot at a certain place. The difference between PSNC and the air traffic control is that we can enlarge the time interval of a time slot and allow multiple vehicles to occupy it. The exact sequence of the vehicles and the distance between the vehicle is then a task of the local control subsystem and depends on the carrier-track technology. Also in case of an over-assignment by the logistics, the local control subsystem needs to deviate vehicles or, if necessary, slow them down in order to prevent an emergency break. However, the probability of that event can be reduced arbitrarily (as shown later on). In case of such a buffer-overflow, all concerned vehicles will make the transient from a the nominal operation to a steady state. The user in the vehicles will not notice this transition because all comfort criteria will be respected. However, he may notice that his vehicle will not take the shortest way. The concerned vehicles will flip back to nominal operation as soon as their trip has been rerouted and reallocated.

PSNC for track allocation

Simple analogy:

The analogy with the hotel reservation illustrates the problem of probabilistic slot allocation. With a hotel, one time slot corresponds to one night and the hotel capacity (here 10 persons) corresponds to the maximum number of vehicles allowed per time slot.

What is controlled with PSNC and how does it work ?

Controlled quantities: using the random buffer network model, it is necessary to control two critical quantities for each buffer:

• The number n₁(k) of cabins or carriers per time-slot at the input.
• The number q_1,2(k) of cabins or carriers inside the buffer.

Aim: to maximize the number of allocations to guarantee that the probability of congestion at entrance: $n_{1}(k)>N_{\max}$ buffer overflow: $q_{1,2}(k)>Q_{\max}$ remains below the limit probability $P_{\max}$.

In the hotel-example before, we assumed that the hotel were completely empty for that concerned day. However, there may also be some guests that have been there before. This cumulative quantity is defined by q_1,2(k). Another difference is that a hotel is usually not limited by the influx of people, as long as the reception can handle all arriving or leaving guests before closing. A transport network, where all guideways have a limited carrying capacity this flux (vehicles entering n₁(k) or leaving n₂(k) per time-slot) needs also to be taken into consideration. In the following we determine the estimations of future q_1,2(k), and n₁(k) and thereafter propose a possible criteria on how to decide whether or not to grand an allocation.

Slot occupancy estimation with random buffer model

Estimated number of vehicles $\hat{n}_{c}(k)$ that enter connecting point c during time slot k:

$$\hat{n}_{c}(k)= \!\!\!\!\!\!\sum_{\forall i,m\vert c_{i,m}=c}\!\!\!\!\!\!{p_{i,m}(k)}$$

Variance $\mbox{Var}\left[n_{c}(k)\right]$ of n_c(k):

$$\mbox{Var}\left[n_{c}(k)\right]=\hat{n}_{c}(k)- \!\!\!\!\!\!\sum_{\forall i,m\vert c_{i,m}=c}\!\!\!\!\!\!{p^{2}_{i,m}(k)}$$

Buffer occupancy estimation with random buffer model

Estimated number of vehicles $\hat{q}_{1,2}(k)$ that are inside the buffer in k time-slots ahead:

$$\hat{q}_{1,2}(k)=Q_{0}+ \sum_{\ell=0}^{k}\! \hat{n}_{1}(\ell)- \hat{n}_{2}(\ell)$$

where Q₀ is the present number of vehicles inside the buffer.

Variance $\mbox{Var}\left[q_{1,2}(k)\right]$ of q_1,2(k) :
complex and numerically intensive to compute because cross-correlation matrices need to be determined.

Simulation example:

• 120 vehicles move through an initially empty buffer.
• Random arrival times t₁ at buffer during 180s.
• A priori known probability distribution of arrival time t₁:
  $t_{1}\pm 20$s, $\rho(t)$ is equally distributed.
• A priori known delay time of buffer: $60\pm 5$s, $g_{1,2}(\tau)$ equally distributed.
• Slot time: T=5s

Comparison of estimation and one realization of q(k)

Comparison of estimation and one realization of n₁(k)

Comparison of histogram and Gauss-shaped probability distribution of n₁(k)

Proposed PSNC allocation criteria

The critical probabilities are:

PSNC allocation criteria: if there exist a future time-slot k for which

$P_{1}(k)+P_{q}(k) > P_{\max}$

then any new allocation for this times-lot is refused or rerouting/reallocation is requested.

Predicted probability P₁(k) for congestion at buffer entrance

Probability P₁(k) for congestion at buffer entrance

Example for track allocation

Remark:

• The track management does also the track cluster internal routing and there may be several buffers between c_1,m and c_1,m+1.
• if the allocation is refused then the cabin management needs to reroute.

Example of time evolution of control process at connecting point c