A fundamental question in a sequential decision making setting under uncertainty is “how to allocate resources amongst competing entities so as to maximize the rewards accumulated in the long run?”. The resources allocated may be either abstract quantities such as time or concrete quantities such as manpower. The sequential decision making setting involves one or more agents interacting with an environment to procure rewards at every time instant and the goal is to find an optimal policy for choosing actions. Most of these problems involve multiple (infinite) stages and the objective function is usually a long-run performance objective. The problem is further complicated by the uncertainties in the sys-tem, for instance, the stochastic noise and partial observability in a single-agent setting or private information of the agents in a multi-agent setting. The dimensionality of the problem also plays an important role in the solution methodology adopted. Most of the real-world problems involve high-dimensional state and action spaces and an important design aspect of the solution is the choice of knowledge representation. The aim of this thesis is to answer important resource allocation related questions in different real-world application contexts and in the process contribute novel algorithms to the theory as well. The resource allocation algorithms considered include those from stochastic optimization, stochastic control and reinforcement learning. A number of new algorithms are developed as well. The application contexts selected encompass both single and multi-agent systems, abstract and concrete resources and contain high-dimensional state and control spaces. The empirical results from the various studies performed indicate that the algorithms presented here perform significantly better than those previously proposed in the literature. Further, the algorithms presented here are also shown to theoretically converge, hence guaranteeing optimal performance. We now briefly describe the various studies conducted here to investigate problems of resource allocation under uncertainties of different kinds: Vehicular Traffic Control The aim here is to optimize the ‘green time’ resource of the individual lanes in road networks that maximizes a certain long-term performance objective. We develop several reinforcement learning based algorithms for solving this problem. In the infinite horizon discounted Markov decision process setting, a Q-learning based traffic light control (TLC) algorithm that incorporates feature based representations and function approximation to handle large road networks is proposed, see Prashanth and Bhatnagar [2011b]. This TLC algorithm works with coarse information, obtained via graded thresholds, about the congestion level on the lanes of the road network. However, the graded threshold values used in the above Q-learning based TLC algorithm as well as several other graded threshold-based TLC algorithms that we propose, may not be optimal for all traffic conditions. We therefore also develop a new algorithm based on SPSA to tune the associated thresholds to the ‘optimal’ values (Prashanth and Bhatnagar [2012]). Our thresh-old tuning algorithm is online, incremental with proven convergence to the optimal values of thresholds. Further, we also study average cost traffic signal control and develop two novel reinforcement learning based TLC algorithms with function approximation (Prashanth and Bhatnagar [2011c]). Lastly, we also develop a feature adaptation method for ‘optimal’ feature selection (Bhatnagar et al. [2012a]). This algorithm adapts the features in a way as to converge to an optimal set of features, which can then be used in the algorithm. Service Systems The aim here is to optimize the ‘workforce’, the critical resource of any service system. However, adapting the staffing levels to the workloads in such systems is nontrivial as the queue stability and aggregate service level agreement (SLA) constraints have to be complied with. We formulate this problem as a constrained hidden Markov process with a (discrete) worker parameter and propose simultaneous perturbation based simulation optimization algorithms for this purpose. The algorithms include both first order as well as second order methods and incorporate SPSA based gradient estimates in the primal, with dual ascent for the Lagrange multipliers. All the algorithms that we propose are online, incremental and are easy to implement. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter updates obtained from the SASOC algorithms onto the discrete set. We validate our algorithms on five real-life service systems and compare their performance with a state-of-the-art optimization tool-kit OptQuest. Being ��times faster than OptQuest, our scheme is particularly suitable for adaptive labor staffing. Also, we observe that it guarantees convergence and finds better solutions than OptQuest in many cases. Wireless Sensor Networks The aim here is to allocate the ‘sleep time’ (resource) of the individual sensors in an intrusion detection application such that the energy consumption from the sensors is reduced, while keeping the tracking error to a minimum. We model this sleep–wake scheduling problem as a partially-observed Markov decision process (POMDP) and propose novel RL-based algorithms -with both long-run discounted and average cost objectives -for solving this problem. All our algorithms incorporate function approximation and feature-based representations to handle the curse of dimensionality. Further, the feature selection scheme used in each of the proposed algorithms intelligently manages the energy cost and tracking cost factors, which in turn, assists the search for the optimal sleeping policy. The results from the simulation experiments suggest that our proposed algorithms perform better than a recently proposed algorithm from Fuemmeler and Veeravalli [2008], Fuemmeler et al. [2011]. Mechanism Design The setting here is of multiple self-interested agents with limited capacities, attempting to maximize their individual utilities, which often comes at the expense of the group’s utility. The aim of the resource allocator here then is to efficiently allocate the resource (which is being contended for, by the agents) and also maximize the social welfare via the ‘right’ transfer of payments. In other words, the problem is to find an incentive compatible transfer scheme following a socially efficient allocation. We present two novel mechanisms with progressively realistic assumptions about agent types aimed at economic scenarios where agents have limited capacities. For the simplest case where agent types consist of a unit cost of production and a capacity that does not change with time, we provide an enhancement to the static mechanism of Dash et al. [2007] that effectively deters misreport of the capacity type element by an agent to receive an allocation beyond its capacity, which thereby damages other agents. Our model incorporates an agent’s preference to harm other agents through a additive factor in the utility function of an agent and the mechanism we propose achieves strategy proofness by means of a novel penalty scheme. Next, we consider a dynamic setting where agent types evolve and the individual agents here again have a preference to harm others via capacity misreports. We show via a counterexample that the dynamic pivot mechanism of Bergemann and Valimaki [2010] cannot be directly applied in our setting with capacity-limited alim¨agents. We propose an enhancement to the mechanism of Bergemann and V¨alim¨aki [2010] that ensures truth telling w.r.t. capacity type element through a variable penalty scheme (in the spirit of the static mechanism). We show that each of our mechanisms is ex-post incentive compatible, ex-post individually rational, and socially efficient

Continuously monitoring and automatically identifying existing problems in traffic signal operation is a challenging and time-consuming task. Although data are becoming available due to the adoption of emerging detection technologies, efforts on utilizing the data to diagnose signal control are limited. The current practices of retiming signals are still periodic and based on several days of aggregated turning movement counts. This dissertation developed a framework of automatic signal operation diagnosis with the aim to support decision-making processes by assessing the signal control and identifying the signal retiming needs. The developed framework used a combination of relatively low-cost data from Wi-Fi sensors and historical signal timing records from existing signal controllers. The development involved applying multiple data matching and filtering algorithms to allow the estimation of travel times of vehicular traversals. The Travel Time Index (TTI) was then used as a measure to assess the traffic conditions of various movements. Historical signal timing records were also analyzed, and an additional signal-timing measure, referred to as the Max-out Ratio (MR), was proposed to evaluate the frequency in which the green time demand of a phase exceeded its preset value. Thresholds for the TTI and MR variables were used as a basis for the diagnosis. This diagnosis first identified the needs for assigning additional green times for individual signal phases. Further assessments were then made to determine whether or not the cycle length for the entire intersection or capacity was sufficient. The developed framework was implemented in a real-world signalized intersection and proved to be capable of identifying retiming needs, as well as providing support for the retiming process. Compared to field observations, the diagnosis results were able to reflect the signal operations of most of the movements during various time periods. Moreover, the flexibility of the developed framework allows users to select different thresholds for various movements and times of day, and thus customize the analysis to agency needs.

No description available.

No description available.

The development of connected vehicle (CV) technologies enables advanced management of individual vehicles and traffic signals to improve urban mobility and energy efficiency. In this thesis, a cooperative vehicle-signal control system will be developed to integrate an Eco-driving system and a proactive signal control system under a mixed connected environment with both connected vehicles (CVs) and human-driven vehicles (HDVs). The system utilizes CVs to conduct an accurate prediction of queue length and delay at different approaches of intersections. Then, a queue-based optimal control strategy is established to minimize the fuel usage of individual CVs and the travel time delay of entire intersections. The system applies the model predictive control to search for the optimal signal timing plan for each intersection and the most-fuel efficient speed profiles for each CV to gain the global optimum of the intersection. In this thesis, a simulation platform is designed to verify the effectiveness of the proposed system under different traffic scenarios. The comparison with the eco-driving only and signal control only algorithms verifies that the cooperative system has a much more extensive reduction range of the trip delay in the case of medium and high saturation. At low saturation, the effect of the system is not much different from that of the eco-driving algorithm, but it is still better than the signal control. Results show that the benefits of CVs are significant at all different market penetration rates of CVs. It also demonstrates the drawback of the system at high congestion levels. / Thesis / Master of Applied Science (MASc)

Sub-optimal automated transportation control systems incur high mobility, human health and environmental costs. With society reliant on its transportation systems for the movement of individuals, goods and services, minimizing these costs benefits many. Intersection traffic signal controllers are an important element of modern transportation systems that govern how vehicles traverse road infrastructure. Many types of traffic signal controllers exist; fixed time, actuated and adaptive. Adaptive traffic signal controllers seek to minimize transportation costs through dynamic control of the intersection. However, many existing adaptive traffic signal controllers rely on heuristic or expert knowledge and were not originally designed for scalability or for transportation’s big data future. This research addresses the aforementioned challenges by developing a scalable system for adaptive traffic signal control model development using deep reinforcement learning in traffic simulation. Traffic signal control can be modelled as a sequential decision-making problem; reinforcement learning can solve sequential decision-making problems by learning an optimal policy. Deep reinforcement learning makes use of deep neural networks, powerful function approximators which benefit from large amounts of data. Distributed, parallel computing techniques are used to provide scalability, with the proposed methods validated on a simulation of the City of Luxembourg, Luxembourg, consisting of 196 intersections. This research contributes to the body of knowledge by successfully developing a scalable system for adaptive traffic signal control model development and validating it on the largest traffic microsimulator in the literature. The proposed system reduces delay, queues, vehicle stopped time and travel time compared to conventional traffic signal controllers. Findings from this research include that using reinforcement learning methods which explicitly develop the policy offers improved performance over purely value-based methods. The developed methods are expected to mitigate the problems caused by sub-optimal automated transportation signal controls systems, improving mobility and human health and reducing environmental costs. / Thesis / Doctor of Philosophy (PhD) / Inefficient transportation systems negatively impact mobility, human health and the environment. The goal of this research is to mitigate these negative impacts by improving automated transportation control systems, specifically intersection traffic signal controllers. This research presents a system for developing adaptive traffic signal controllers that can efficiently scale to the size of cities by using machine learning and parallel computation techniques. The proposed system is validated by developing adaptive traffic signal controllers for 196 intersections in a simulation of the City of Luxembourg, Luxembourg, successfully reducing delay, queues, vehicle stopped time and travel time.

Dilemma zone (DZ), also called decision zone in other literature, is an area where drivers face an indecisiveness of stopping or crossing at the yellow onset. The DZ issue is a major reason for the crashes at high-speed signalized intersections. As a result, how to prevent approaching vehicles from being caught in the DZ is a widely concerning issue. In this dissertation, the author addressed several DZ-associated issues, including the new stochastic safety measure, namely dilemma hazard, that indicates the vehicles' changing unsafe levels when they are approaching intersections, the optimal advance detector configurations for the multi-detector green extension systems, the new dilemma zone protection algorithm based on the Markov process, and the simulation-based optimization of traffic signal systems with the retrospective approximation concept. The findings include: the dilemma hazard reaches the maximum when a vehicle moves in the dilemma zone and it can be calculated according the caught vehicles' time to the intersection; the new (optimized) GES design can significantly improve the safety, but slightly improve the efficiency; the Markov process can be used in the dilemma zone protection, and the Markov-process-based dilemma zone protection system can outperform the prevailing dilemma zone protection system, the detection-control system (D-CS). When the data collection has higher fidelity, the new system will have an even better performance. The retrospective approximation technique can identify the sufficient, but not excessive, simulation efforts to model the true system and the new optimization algorithm can converge fast, as well as accommodate the requirements by the RA technique. / Ph. D.

The continuous conduction mode (CCM) boost, buck-boost and buck-boost derived pulse-width modulation dc-dc converters suffer from the large-signal control-to-output nonlinearity. Without feedback control, the large-signal control-to-output nonlinearity would lead to output overregulation and even damage the components. The control gain is defined as the ratio of output voltage to control signal. The small-signal control gain is defined as differentiating output voltage with respect to control signal. Feedback control helps to make the output trace the reference signal. A large-signal control-to-output linearity is established. Compared with open loop control, the feedback loop design is complex; and the feedback control might suffer from the instability caused by the negative small-signal control gain, which is due to the loss and parasitic in practice. Except feedback control, open loop linearization methods can also realize the large-signal control-to-output linearity. A modulated-ramp pulse-width modulation generator is introduced in [6]. A current source works as the control signal. A capacitor is charged by the current source, whose voltage works as the carrier and compared with a constant dc bias voltage to determine the duty cycle. When applying this method to boost, buck-boost and buck-boost derived PWM dc-dc converters, a large-signal control-to-output linearity is established. However, the control gain is dependent on the input voltage; it cannot maintain constant when input voltage varies. A feedforward pulse width modulator is introduced in [39] to realize a large-signal control-to-output linearity. The static conversion ratio is divided into numerator and denominator as the functions of duty cycle. An integrator with reset clock signal helps to determine the right timing. The control gain is ideally constant and independent of input voltage. However, the mismatch between the integrator time constant and the switching period would result in a nonlinear control gain, which is dependent on the input voltage. In the thesis work, a self-oscillating unified linearizing modulator is introduced. It first provides a unified procedure to establish a large-signal control-to-output linearity for different pulse-width modulation dc-dc converters. Feedforward is employed to mitigate the impact from line voltage. Self-oscillation is adopted to provide the internal clock signal and to determine the switching frequency. A constant control gain is obtained, independent on the input voltage or the mismatch between clock signals. The modulator is constructed by three simple and standard building blocks. With the considerations of parasitic components and loss, how to design the constant gain, which excludes the negative small-signal control gain within the entire control signal range, is analyzed and discussed. The performance of this self-oscillating unified linearizing modulator is verified by experiments. The impacts from propagation delay in practical components are taken into considerations, which improves the quality of generated signals. Combined with a boost converter, a good large-signal control-to-output linearization is demonstrated. In the future work, the small-signal control-to-output transfer function is first deduced based on the SOUL modulator. Bode plots show the unique characteristic based on the SOUL modulator compared with the conventional modulator. Next, the impacts from this unique characteristic to feedback loop design and dynamic performance are discussed. / Master of Science

Traffic signal cycle lengths are traditionally optimized to minimize vehicle delay at intersections using the Webster formulation. This thesis includes two studies that develop new formulations to compute the optimum cycle length of isolated intersections, considering measures of effectiveness such as vehicle delay, fuel consumption and tailpipe emissions. Additionally, both studies validate the Webster model against simulated data. The microscopic simulation software, INTEGRATION, was used to simulate two-phase and four-phase isolated intersections over a range of cycle lengths, traffic demand levels, and signal timing lost times. Intersection delay, fuel consumption levels, and emissions of hydrocarbon (HC), carbon monoxide (CO), oxides of nitrogen (NOx), and carbon dioxide (CO2) were derived from the simulation software. The cycle lengths that minimized the various measures of effectiveness were then used to develop the proposed formulations. The first research effort entailed recalibrating the Webster model to the simulated data to develop a new delay, fuel consumption, and emissions formulation. However, an additional intercept was incorporated to the new formulations to enhance the Webster model. The second research effort entailed updating the proposed model against four study intersections. To account for the stochastic and random nature of traffic, the simulations were then run with twenty random seeds per scenario. Both efforts noted its estimated cycle lengths to minimize fuel consumption and emissions were longer than cycle lengths optimized for vehicle delay only. Secondly, the simulation results manifested an overestimation in optimum cycle lengths derived from the Webster model for high vehicle demands. / Master of Science

Although concepts of the XDL intersection or CFI (Continuous Flow Intersection) have been around for approximately four decades, users do not yet have a simplified procedure to evaluate its traffic performance and compare it with a conventional intersection. Several studies have shown qualitative and quantitative benefits of the XDL intersection without providing accessible tools for traffic engineers and planners to estimate average control delays, and queues. Modeling was conducted on typical geometries over a wide distribution of traffic flow conditions for three different design configurations or cases using VISSIM simulations with pre-timed signal settings. Some comparisons with similar conventional designs show considerable savings in average control delay, and average queue length and increase in intersection capacity. The statistical models provide an accessible tool for a practitioner to assess average delay and average queue length for three types of XDL intersections. Pre-timed signal controller settings are provided for each of the five intersections of the XDL network. In this research, a "real-time" traffic signal control strategy is developed using genetic algorithms and neural networks to provide near-optimal traffic performance for XDL intersections. Knowing the traffic arrival pattern at an intersection in advance, it is possible to come up with the best signal control strategy for the respective scenario. Hypothetical cases of traffic arrival patterns are generated and genetic algorithms are used to come up with near-optimal signal control strategy for the respective cases. The neural network controller is then trained and tested using pairs of hypothetical traffic scenarios and corresponding signal control strategies. The developed neural network controller produces near-optimal traffic signal control strategy in "real-time" for all varieties of traffic arrival patterns. / Master of Science