The solution to the following problem is proposed
Calvin has to cross several signals when he walks from his home to school. Each of these signals operate independently. They alternate every 80 seconds between green light and red light. At each signal, there is a counter display that tells him how long it will be before the current signal light changes. Calvin has a magic wand which lets him turn a signal from red to green instantaneously. However, this wand comes with limited battery life, so he can use it only for a specified number of times.
a. If the total number of signals is 2 and Calvin can use his magic wand only once, then what is the expected waiting time at the signals when Calvin optimally walks from his home to school?
b. What if the number of signals is 3 and Calvin can use his magic wand only once?
Under a number of paths can appear, all of them have a certain probability (which depends on the parent path) and an associated waiting time.
On each traffic light, three situations can happen
$ p(T=0) = P(green) = 0.5 $
$ p(0< T <= L) = P( 0< T_w <= L | red) = P(0 < T_w <=L ) p(red) = {{L}\over{80}} 0.5 $
$ p(L < T <= 80) = P( L< T_w <= 80 | red) = P(L < T_w <=80 ) p(red) = {{80-L}\over{80}} 0.5 $
Since those probabilities depend on the parent path (from where it is coming) the probabilty of such path has to be multiplied by its parent's probability.
$ p(X_i = x / X_p = y ) = p(x) p(y) $
The mean waiting time for a single traffic light is given by the addition of the three cases above
$ E(T_w ) = \sum_{i=1}^{3} p(i)E(T_i) $
$ E(T / green) = 0 $
$ E(T / 0< T <= L ) = {{L}\over{2}} $
$ E(T / L< T<= 80) = {{80-L}\over{2}} $
Now, this is considering that Calvin has still some magic wands left to use. Otherwise if it is red, he needs to wait 40 seconds (uniform mean).
Under these assumptions the total waiting time is given by the addition of all the branches. Each branch is positioned on a certain level l.
$ T_{total} = \sum_{l=1}^{N_l} \sum_{i=1}^{3} \Pi_{j=1}^{l} p_{i,j} E(T_i) $
The following code proposes a recursive class that calls itself to compute the path and eventually the total waiting time.
In [9]:
MAX_TIME = 80. # max time waiting at traffic light
class TrafficLightPath:
'''Class that computes the probabilities of a traffic light path over itself and the
future (children) traffic lights.
'''
p = 0 # probability of this path
T = 0 # expected time of this path
Nw = 0 # remaining uses of the magic wand
Nl = 0 # remaining traffic lights
Lvec = [] # vector of thresholds when waiting for the red light
childrenPaths = [] # array of TrafficLightPath with the future path
def __init__ (self, p, T, Nw, Nl, Lvec):
'''Creates the current path and recursively compute the path
'''
self.p = p
self.T = T
self.Nw = Nw
self.Nl = Nl
self.Lvec = [float(x) for x in Lvec]
self.childrenPaths = []
if self.getCurrentPosInPath()==-1:
self.p = 1
self.T = 0
if Nl > 0:
self.computeChildrenPaths ()
def computeChildrenPaths (self):
'''Creates the future path possibilities
'''
if self.Nw >= self.Nl:
# no need to wait, use magic wand
self.childrenPaths.append(TrafficLightPath(1, 0, self.Nw-1, self.Nl-1, self.Lvec))
else:
# don't have a magic wand
if self.Nw == 0:
# green light
self.childrenPaths.append(TrafficLightPath(0.5, 0, self.Nw, self.Nl-1, self.Lvec))
# red light
self.childrenPaths.append(TrafficLightPath(0.5, MAX_TIME/2 , self.Nw, self.Nl-1, self.Lvec))
else:
# can decide whether to wait or stay
# green ligth
self.childrenPaths.append(TrafficLightPath(0.5, 0, self.Nw, self.Nl-1, self.Lvec))
# wait, don't use wand
L = self.Lvec[self.getCurrentPosInPath()+1]
self.childrenPaths.append(TrafficLightPath(L/(2*MAX_TIME), L/2, self.Nw, self.Nl-1, self.Lvec))
# don't wait, use wand
self.childrenPaths.append(TrafficLightPath((MAX_TIME-L)/(2*MAX_TIME), 0, self.Nw-1, self.Nl-1, self.Lvec))
def getCurrentPosInPath(self):
'''Returns the current position in the path
'''
return len(self.Lvec)-self.Nl-1
def printPath (self):
'''Prints the path and future paths with indentation
'''
pos = self.getCurrentPosInPath()+2
print '-'*4*pos + ' pos=' + str(pos-2)
print '-'*4*pos + ' p=' + str(self.p)
print '-'*4*pos + ' T=' + str(self.T)
print '-'*4*pos + ' Nw=' + str(self.Nw)
print '-'*4*pos + ' Nl=' + str(self.Nl)
print '-'*4*pos + ' L=' + str(self.Lvec[pos-2])
print '-'*4*pos
for item in self.childrenPaths:
item.printPath()
def computeMeanWaitingTimes (self, a_total_time=[], prob_path=1):
'''Computes the mean waiting time for this path including the children
The probability of the current path is the probability of this
path times the probability of the children
'''
a_total_time.append(self.p*prob_path*self.T) # total time for this light
new_prob_path = prob_path * self.p # prepare the prob path for children
for item in self.childrenPaths:
a_total_time = item.computeMeanWaitingTimes(a_total_time=a_total_time, prob_path=new_prob_path)
return a_total_time
def computeTotalMeanWaitingTime (self):
times = self.computeMeanWaitingTimes(a_total_time=[])
return sum(times)
Now let's try the path for a single path of 2 lights and 1 wand and assuming a waiting time of 0 seconds. This is, he will not consider for how many seconds he needs to wait, he will automatically use the magic wand even if he needs to wait 1 second.
In [10]:
path = TrafficLightPath(1, 0, 1, 2, [0, 0])
path.printPath()
print 'Total waiting time ' + str(path.computeTotalMeanWaitingTime()) + ' seconds'
Now, let's optimize this, let's see which would be the optimal value he needs to wait to use the magic wand. For this we compute all the possible waiting times from (0 to 80) and see where the optimal value is.
In [7]:
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
TwL = pd.Series(index=np.arange(0,80,0.1))
N_WANDS = 1
N_LIGHTS = 2
for i in TwL.index:
path = TrafficLightPath(1, 0, N_WANDS, N_LIGHTS ,[i, np.nan])
TwL.loc[i] = path.computeTotalMeanWaitingTime()
TwL.plot()
plt.hlines(TwL.min(), 0, TwL.index[TwL==TwL.min()][0], linestyles='--')
plt.vlines(TwL.index[TwL==TwL.min()][0], 0, TwL.min(), linestyles='--')
plt.title ('Mean waiting time')
plt.xlabel('Time to wait for using the magic wand [s]')
plt.ylabel('Total mean waiting time')
plt.show()
print 'Optimal waiting time is ' + str(TwL.min()) + ' seconds.'
One can see that the problem presents a multidimensional optimization problem, being the dimension the number of traffic lights minus 1. Now, let's optimize the case for 3 traffic lights:
In [8]:
N_WANDS = 1
N_LIGHTS = 3
[L1vec, L2vec] = np.meshgrid(np.arange(0,80, 1), np.arange(0,80, 1))
Tw = np.zeros(L1vec.shape)
for i in range(Tw.shape[0]):
for j in range(Tw.shape[1]):
path = TrafficLightPath(1,0, N_WANDS, N_LIGHTS, [L1vec[i,j], L2vec[i,j], np.nan])
Tw[i,j] = path.computeTotalMeanWaitingTime()
min_ind = np.unravel_index(Tw.argmin(), Tw.shape)
path = TrafficLightPath(1, 0, N_WANDS, N_LIGHTS,[L1vec[min_ind[0], min_ind[1]], L2vec[min_ind[0], min_ind[1]], np.nan])
if path.computeTotalMeanWaitingTime() == Tw.min():
print 'Min time = ' + str(Tw.min())
print 'L1 = ' + str(L1vec[min_ind[0], min_ind[1]])
print 'L2 = ' + str(L2vec[min_ind[0], min_ind[1]])
plt.imshow(Tw)
plt.hlines(min_ind[0], 0, min_ind[1], linestyles='--')
plt.vlines(min_ind[1], 0, min_ind[0], linestyles='--')
plt.colorbar()
plt.show()
print 'Optimal waiting time is ' + str(Tw.min()) + ' seconds.'