Recently, stereo vision has been widely used in many applications, and depth map is important information in stereo vision. In general, depth map can be generated from the disparity using stereo matching based on two input images of different viewing positions. Due to the large computation complexity, software implementation of stereo matching usually cannot achieve real-time computation speed. In this thesis, we propose hardware implementations of stereo matching to speed up the generation of depth map. The proposed design uses a global optimization method, called dynamic programming, to find the disparity based on two input images: left image and right image. It consists of three main processing steps: matching cost computation (M.C.C.), minimum cost accumulation (M.C.A.), and disparity optimization (D.O.). The thesis examines the impact of different pixel operation orders in M.C.C and M.C.A modules on the cost of hardware. In the design of D.O. module, we use two different approaches. One is a Systolic-Like structure with streaming processing, and the other is memory-based design with low hardware cost. The final architecture with pipelining and memory-based D.O. can save a lot of hardware cost and achieve high throughput rate for processing a sequence of image pairs.

Power converters are used in many distributed energy resources (DER) applications. With proper controls, DER systems can reduce losses and achieve higher energy efficiency if various power sources and loads are integrated through DC bus. High voltage electric vehicle (EV) DC charging station is becoming popular in order to reduce charging time and improve energy efficiency. A DC EV charging station model involving photovoltaic, energy storage system (ESS), fuel cell and DC loads is studied in this work. A dynamic programming technique that considers various uncertainties involved in the system is adopted to obtain optimal dispatch of ESS and fuel cell system. The effects of different tariffs, demand response programs and contract capacities of demand in the power scheduling are investigated and the results are presented.

Compared to conventional Steiner tree signal net routing, non-tree topology is often superior in many aspects including timing performance, tolerance to open faults and variations. In nano-scale VLSI designs, interconnect delay is a performance bottleneck and variation effects are increasingly problematic. Therefore the advantages of non-tree topology are particularly appealing for timing critical net routings in nano-scale VLSI designs. We propose Steiner network construction heuristics which can generate either tree or non-tree of signal net with different slack wirelength tradeoffs, and handle both long path and short path constraints. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional tree approaches while increasing only slightly in wirelength. These results show that our algorithm is a very promising approach for timing critical net routings.

The thesis investigates the optimal expansion planning of substations for the distribution system of Taipei City District of Taiwan Power Company. The small area load forecasting is executed with the support of Outage Management System(OMS) database. The capacity expansion of distribution substations is obtained by considering the annual load growth of each service area to achieve the cost effectiveness of substation investment. The geographic information of each service zone has been retrieved form the OMS data. With the land use planning of Taipei City Government, the load density of each small area for the target year is derived according to the final floor area and development strength of the land base. The load forecasting of each small area is then solved by considering the load growth of each customer class, which is then used for the expansion planning of substations. After determining the small area load forecasting for the final target year, the center of gravity method is applied to find the geographic blocks of all substations and the corresponding service areas at the target year. The power loading of each small area is used to calculate the power loading loss of which service area to solve the optimal location within the block for each substation. Based on the annual load forecasting of all small areas, the expansion planning of distribution substations for Taipei City District is derived by Dynamic Programming(DP) and Immune Algorithm(IA) to achieve minimization of power loading loss with subject to the operation constraint. By the proposed methodology, the unit commitment of distribution substations is determined to meet the load growth of service area and achieve power loading loss minimization of distribution systems.

This thesis examines the performance of some dim target detection algorithms in low-SNR imaging scenarios. In the past research, there have been numerous attempts for detection and tracking barely visible targets for military surveillance applications with infrared sensors. In this work, two of these algorithms are analyzed via extensive simulations. In one of these approaches, dynamic programming is exploited to coherently integrate the visible energy of dim targets over possible relative directions, whereas the other method is a Bayesian formulation for which the target likelihood is updated along time to be able to detect a target moving in any direction. Extensive experiments are conducted for these methods by using synthetic image sequences, as well as some real test data. The simulation results indicate that it is possible to detect dim targets in quite low-SNR conditions. Moreover, the performance might further increase, in case of incorporating any a priori information about the target trajectory.

We consider a manufacturing system with stochastic demand and predictable production yield. The manufacturer has predetermined prices and limited production capacity in each period. The producer also has the option to save some inventory for future periods even if there is demand in the current period. The demand that is not met is lost or may be backordered for only one period. Our objective is to maximize the expected profit by choosing optimal production, save and backorder quantities in each period. We formulate this problem as a Markov Decision Process where the state of the system is represented by the net inventory and the efficiency parameter. We show that a modified (Y, S, B) policy is optimal in each period. At the end, we have some computational analysis to examine the effects of yield on the optimal decisions.

This thesis is to investigate the power system operation strategy for an electrified mass rapid transit¡]MRT¡^network with the load transfer among main transformers by considering load growth and due to annual ridership increase, the loading factors of main transformers are improved so that the power system loss can be reduced. For the conventional planning of an electrified MRT system to serve the public transportation for the metropolitan area, the transformer capacity is often designed to meet the criterion of not only covering the peak demand but also providing the 100% fully capacity reserve for the system operation of target year. With such a high backup capability, the transformers are very lightly loaded for most of the operation time and significant core loss will be introduced over the lifecycle. In this thesis the train motion equation has been applied to find the mechanical power required, the proper strategy of unit commitment of main transformers and network reconfiguration by switching operation has been considered to enhance the operation efficiency of an MRT power system. To demonstrate the effectiveness of the proposed methodology, the Taipei MRT network is selected for computer simulation. It is found that the loading factors of main transformers can be improved dramatically and the load balance among the transformers can be obtained by the proper switching operation. An efficient strategy for transformer planning by taking into account the growth rate of load so that the overall investment cost of main transformers can be justified. The load characteristics and load growth rate of mass rapid transit¡]MRT¡^are derived by an Energy Management Model (EMM) and the AC load flow analysis is used to solve the transformer copper loss and core loss over the study period. To obtain optimal planning and operation strategy of main transformers for the MRT power system, the transformers initial investment cost and depreciation cost, peak power loss and energy loss, and reliability cost of distribution transformers are combined to form the overall cost function .By performing the dynamic programming (DP) the unit commitment of main transformers by considering the annual peak and off peak power loading of whole MRT system is derived. It is found that more efficient system operation can be obtained by the proposed methodology.

Based on Hidden Markov Models (HMM) with One-Stage Dynamic Programming Algorithm, a continuous-speech and speaker-independent Mandarin digit speech recognition system was designed in this work. In order to implement this architecture to fit the performance of hardware, various parameters of speech characteristics were defined to optimize the process. Finally, the ¡§State Duration¡¨ and the ¡§Tone Transition Property Parameter¡¨ were extracted from speech temporal information to improve the recognition rate. Via using the test database, experimental results show that this new ideal of one-stage dynamic programming algorithm , with ¡§state duration¡¨ and ¡§ tone transition property parameter¡¨ , will have 18% recognition rate increase when compare to the conventional one. For speaker-independent and connect-word recognition, this system will achieve recognition rate to 74%. For speaker-independent but isolate-word recognition, it will have recognition rate higher than 96%. Recognition rate of 92% is obtained as this system is applied to the connect-word speaker-dependent recognition.

In recent years Boolean Networks (BN) and Probabilistic Boolean Networks (PBN) have become popular paradigms for modeling gene regulation. A PBN is a collection of BNs in which the gene state vector transitions according to the rules of one of the constituent BNs, and the network choice is governed by a selection distribution. Intervention in the context of PBNs was first proposed with an objective of avoid- ing undesirable states, such as those associated with a disease. The early methods of intervention were ad hoc, using concepts like mean first passage time and alteration of rule based structure. Since then, the problem has been recognized and posed as one of optimal control of a Markov Network, where the objective is to find optimal strategies for manipulating external control variables to guide the network away from the set of undesirable states towards the set of desirable states. This development made it possible to use the elegant theory of Markov decision processes (MDP) to solve an array of problems in the area of control in gene regulatory networks, the main theme of this work. We first introduce the optimal control problem in the context of PBN models and review our solution using the dynamic programming approach. We next discuss a case in which the network state is not observable but for which measurements that are probabilistically related to the underlying state are available. We then address the issue of terminal penalty assignment, considering long term prospective behavior and the special attractor structure of these networks. We finally discuss our recent work on optimal intervention for the case of a family of BNs. Here we consider simultaneously controlling a set of Boolean Models that satisfy the constraints imposed by the underlying biology and the data. This situation arises in a case where the data is assumed to arise by sampling the steady state of the real biological network.

Branch-price-and-cut algorithms are among the most successful exact optimization approaches for solving many routing and scheduling problems. This is due, in part, to the availability of extremely efficient and effective dynamic programming algorithms for solving the pricing problem, and the availability of efficient and effective branching schemes and cutting planes that drive integrality. In terms of branch-price-and-cut, two obstacles we face today are (1) being able to solve harder and larger pricing problems, and (2) solving mixed-integer column generation formulations that suffer from relatively weak LP bounds compared to the more traditional 0-1 set partitioning type. As part of the work presented in this thesis, we encounter column generation formulations motivated by real life problems that require overcoming both types of challenges. The first part of this thesis is dedicated to solving the resource constrained shortest path problem (RCSPP) arising in column generation pricing problems for formulations involving extremely large networks and a huge number of local resource constraints. We present a relaxation-based dynamic programming algorithm that alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search, and between consecutive searches, the relaxation is tightened over a set of critical resources and arcs. The second part of this thesis focuses in the fixed charge shortest path problem (FCSPP) in which the amount of resource consumed is itself a continuous bounded variable. By exploiting the structure of optimal solutions to FCSPP, we design and implement a solution approach that relies on solving multiple RCSPPs, and therefore can again make use of extremely efficient and effective dynamic programming algorithms. In the third and final part of this thesis, we present a branch-price-and-cut algorithm for the inventory routing problem (IRP). We extend a class of cuts known for the vehicle routing problem, and develop a new class of cuts specifically for IRP to tighten the formulation. Both the branching schemes and cuts preserve the structure of the pricing problem making them efficiently implementable within a branch-price-and-cut algorithm.