Dissertations / Theses on the topic 'Real-Time Dynamic Programming'

Thesis (MSc (Mathematics))--University of Stellenbosch, 2010.<br>ENGLISH ABSTRACT: In this thesis we consider the essential topics relating to stereo-vision and the correspondence problem in general. The aim is to reconstruct a dense 3D scene from images captured by two spatially related cameras. Our main focus, however, is on speed and real-time implementation on a standard desktop PC. We wish to use the CPU to solve the correspondence problem and to reserve the GPU for model rendering. We discuss three fundamental types of algorithms and evaluate their suitability to this end. We eventually choose to implement a hierarchical version of the dynamic programming algorithm, because of the good balance between accuracy and speed. As we build our system from the ground up we gradually introduce necessary concepts and established geometric principles, common to most stereovision systems, and discuss them as they become relevant. It becomes clear that the greatest weakness of the hierarchical dynamic programming algorithm is scanline inconsistency. We nd that the one-dimensional LULU- lter is computationally inexpensive and e ective at removing outliers when applied across the scanlines. We take advantage of the hierarchical structure of our algorithm and sub-pixel re nement to produce results at video rates (roughly 20 frames per second). A 3D model is also constructed at video rates in an on-line system with only a small delay between obtaining the input images and rendering the model. Not only is the quality of our results highly competitive with those of other state of the art algorithms, but the achievable speed is also considerably faster.<br>AFRIKAANSE OPSOMMING: In hierdie tesis beskou ons die noodsaaklike onderwerpe wat in die algemeen verband hou met stereovisie en die ooreenstemmingsprobleem. Die mikpunt is om 'n digte 3D toneel te rekonstrueer vanaf beelde wat deur twee ruimtelik-verwante kameras vasgelê is. Ons hoofdoel is egter spoed, en intydse implementering op 'n standaard rekenaar. Ons wil die SVE (CPU) gebruik om die ooreenstemmingsprobleem op te los, en reserveer die GVE (GPU) vir model-beraping. Ons bespreek drie fundamentele tipes algoritmes en evalueer hul geskiktheid vir hierdie doel. Ons kies uiteindelik om 'n hiërargiese weergawe van die dinamiese programmeringsalgoritme te implementeer, as gevolg van die goeie balans tussen akkuraatheid en spoed. Soos wat ons ons stelsel van die grond af opbou, stel ons geleidelik nodige konsepte voor en vestig meetkundige beginsels, algemeen tot meeste stereovisie stelsels, en bespreek dit soos dit toepaslik word. Dit word duidelik dat skandeerlyn-strydigheid die grootste swakheid van die hiërargiese dinamiese programmeringsalgoritme is. Ons vind dat die een-dimensionele LULU- lter goedkoop is in terme van berekeninge, en e ektief aangewend kan word om uitskieters te verwyder as dit dwarsoor skandeerlyne toegepas word. Ons buit die hiërargiese struktuur van ons algoritme uit en kombineer dit met sub-piksel verfyning om resultate te produseer teen video tempo (ongeveer 20 raampies per sekonde). 'n 3D model word ook gekonstrueer teen video tempo in 'n stelsel wat aanlyn loop, met slegs 'n klein vertraging tussen die verkryging van die intree-beelde en die beraping van die model. Die kwaliteit van ons resultate is nie net hoogs mededingend met dié van die heel beste algoritmes nie, maar die verkrygbare spoed is ook beduidend vinniger.

Applications of the existing steady-state plant-wide optimization and the single-scale fast-rate dynamic optimization strategies to an integrated plant with material recycle have been impeded by several factors. While the steady-state optimization formulation is very simple, the very long transient dynamics of an integrated plant have limited the optimizers execution rate to be extremely low, yielding a suboptimal performance. In contrast, performing dynamic plant-wide optimization at the same rate as local controllers requires exorbitant on-line computational load and may increase the sensitivity to high-frequency dynamics that are irrelevant to the plant-level interactions, which are slow-scale in nature. This thesis proposes a novel multi-scale dynamic optimization and control strategy suitable for an integrated plant. The dynamic plant-wide optimizer in this framework executes at a slow rate to track the slow-scale plant-wide interactions and economics, while leaving the local controllers to handle fast changes related to the local units. Moreover, this slow execution rate demands less computational and modeling requirement than the fast-rate optimizer. An important issue of this method is obtaining a suitable dynamic model when first-principles are unavailable. The difficulties in the system identification process are designing proper input signal to excite this ill-conditioned system and handling the lack of slow-scale dynamic data when the plant experiment cannot be conducted for a long time compared to the settling time. This work presents a grey-box modeling method to incorporate steady-state information to improve the model prediction accuracy. A case study of an integrated plant example is presented to address limitations of the nonlinear model predictive control (NMPC) in terms of the on-line computation and its inability to handle stochastic uncertainties. Then, the approximate dynamic programming (ADP) framework is investigated. This method computes an optimal operating policy under uncertainties off-line. Then, the on-line multi-stage optimization can be transformed into a single-stage problem, thus reducing the real-time computational effort drastically. However, the existing ADP framework is not suitable for an integrated plant with high dimensional state and action space. In this study, we combine several techniques with ADP to apply nonlinear optimal control to the integrated plant example and show its efficacy over NMPC.

In this thesis, the primary powertrain components of a power split hybrid electric vehicle are modeled. In particular, the dynamic model of the energy storage element (i.e., traction battery) is exactly linearized through an input transformation method to take advantage of the proposed optimal control algorithm. A lipschitz continuous and nondecreasing cost function is formulated in order to minimize the net amount of consumed fuel. The globally optimal solution is obtained using a dynamic programming routine that produces the optimal input based on the current state of charge and the future power demand. It is shown that the global optimal control solution can be expressed in closed form for a time invariant and convex incremental cost function utilizing the interval back propagation approach. The global optimality of both time varying and invariant solutions are rigorously proved. The optimal closed form solution is further shown to be applicable to the time varying case provided that the time variations of the incremental cost function are sufficiently small. The real time implementation of this algorithm in Simulink is discussed and a 32.84 % improvement in fuel economy is observed compared to existing rule based methods.

This project constructs a scheduling solution for the Emergency Department. The schedules are generated in real-time to adapt to new patient arrivals and changing conditions. An integrated scheduling formulation assigns patients to beds and treatment tasks to resources. The schedule efficiency is assessed using waiting time and total care time experienced by patients. The solution algorithm incorporates dispatch rules, meta-heuristics and a new extended disjunctive graph formulation which provide high quality solutions in a fast time-frame for real time decision support. This algorithm can be implemented in an electronic patient management system to improve patient flow in the Emergency Department.

During the past two decades desperate need for energy-efficient vehicles which has less emission have led to a great attention to and development of electrified vehicles like pure electric, Hybrid Electric Vehicle (HEV) and Plug-in Hybrid Electric Vehicles (PHEVs). Resultantly, a great amount of research efforts have been dedicated to development of control strategies for this type of vehicles including PHEV which is the case study in this thesis. This thesis presents a real-time control scheme to improve the fuel economy of plug-in hybrid electric vehicles (PHEVs) by accounting for the instantaneous states of the system as well as the future trip information. To design the mentioned parametric real-time power management policies, we use dynamic programming (DP). First, a representative power-split PHEV powertrain model is introduced, followed by a DP formulation for obtaining the optimal powertrain trajectories from the energy cost point of view for a given drive cycle. The state and decision variables in the DP algorithm are selected in a way that provides the best tradeoff between the computational time and accuracy which is the first contribution of this research effort. These trajectories are then used to train a set of linear maps for the powertrain control variables such as the engine and electric motor/generator torque inputs, through a least-squares optimization process. The DP results indicate that the trip length (distance from the start of the trip to the next charging station) is a key factor in determining the optimal control decisions. To account for this factor, an additional input variable pertaining to the remaining length of the trip is considered during the training of the real-time control policies. The proposed controller receives the demanded propulsion force and the powertrain variables as inputs, and generates the torque commands for the engine and the electric drivetrain system. Numerical simulations indicate that the proposed control policy is able to approximate the optimal trajectories with a good accuracy using the real-time information for the same drive cycles as trained and drive cycle out of training set. To maintain the battery state-of-charge (SOC) above a certain lower bound, two logics have been introduced a switching logic is implemented to transition to a conservative control policy when the battery SOC drops below a certain threshold. Simulation results indicate the effectiveness of the proposed approach in achieving near-optimal performance while maintaining the SOC within the desired range.<br>MS

We present a resource allocation perspective to Quality of Service in Distributed Virtual Environments. The user of a DVE system will have improved Quality of Service if he/she is allocated the right amount of resources at the right time. Instead of allocating resources on a static basis, we adopt a dynamic need based resource allocation scheme that provides real-time resource allocation. Optimal resource assignments are calculated o2ine and a neural network is trained with the knowledge of optimal solutions from the o2ine Operations Research Techniques and it is then used to deliver near-optimal resource allocation decisions in real-time. We also present a case study of network bandwidth allocation and prove the usefulness of the technique.<br>Master of Science

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado.<br>Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

Cooperation among nodes of a wireless ad hoc network has been shown to be effective in improving the efficiency of resource usage, e.g., increasing the network throughput or reducing the energy consumption. In recent years, cooperation has been widely studied both from an information theoretic point of view and from an implementation perspective. However, there are different scenario that have still not been addressed. In this thesis, we consider wireless cooperative multi-hop networks, where nodes cooperate to deliver messages from sources to destinations. The term cooperation assumes different connotations throughout the thesis. We consider situations in which nodes cooperate in the transmission of a message, realizing a distributed space-time coding scheme or using the recent concept of “spectrum leasing via cooperation”, and the case of distributed data gathering, where source nodes reduce their acquisition rates (and costs) taking advantage of the spatial and temporal correlation between measures. The first scenario considers wireless cooperative multi-hop networks, where nodes that have decoded the message at the previous hop cooperate in the transmission towards the next hop, realizing a distributed space-time coding scheme. Our objective is to find optimal cooperator selection policies for arbitrary topologies with a single source-destination pair, with links affected by path loss and multipath fading. To this end, we model the network behavior through a suitable Markov chain and we formulate the cooperator selection process as a stochastic shortest path problem (SSP). Further, we reduce the complexity of the SSP through a novel pruning technique that, starting from the original problem, obtains a reduced Markov chain which is finally embedded into a solver based on focused real time dynamic programming (FRTDP). Our algorithm can find cooperator selection policies for large state spaces and has a bounded (and small) additional cost with respect to that of optimal solutions and allows to obtain performance bounds that can be useful for the design of practical protocols. Starting from the results of the centralized solution, we looked at the problem from a different angle, devising three online and fully distributed algorithms which only exploit local interactions for the selection of the cooperators. The proposed techniques are numerically compared against the optimal centralized strategy and competing algorithms from the literature, showing their improvement upon existing distributed approaches and achieving close-to-optimal performance. The positive results obtained for the single source-destination scenario, lead us to study the behavior of wireless networks in the presence of multi-user interference and cooperative transmissions. In this case, our focus is to assess the impact of interference among distinct data flows on optimal routing paths and related transmission schedules. In our reference scenario, all nodes have a single antenna and can cooperate in the transmission of packets. Given that, we first model the cooperative transmission problem using linear programming (LP). Thus, for an efficient solution, we reformulate the joint routing and scheduling problem as a single-pair shortest path problem, which is solved using the A∗ search algorithm through specialized heuristics. Simulation results of the obtained optimal policies confirm the importance of avoiding interfering paths and that interference-aware routing can substantially improve the network performance in terms of throughput and energy consumption, even when the number of interfering paths is small. Once again, our models provide useful performance bounds for the design of distributed cooperative transmission protocols in ad hoc networks. We then move our attention to a cognitive radio scenario and we consider a spectrum leasing strategy for the coexistence of a licensed multihop network and a set of unlicensed nodes. The primary network consists of a source, a destination and a set of additional primary nodes that can act as relays. In addition, the secondary nodes can be used as extra relays and hence potential next hops following the principle of opportunistic routing. Secondary cooperation is guaranteed via the “spectrum leasing via cooperation” mechanism, whereby a cooperating node is granted spectral resources subject to a Quality of Service (QoS) constraint. The objective of this work is to find optimal as well as efficient heuristic routing policies based on the idea outlined above of spectrum leasing via cooperative opportunistic routing. To this end, we start by formulating the problem as a Markov decision process (MDP) and we show that, in particular, the problem can be casted in the framework of stochastic routing. Based on the structure of the optimal policies we derive two heuristic routing schemes that we then numerically compare with the optimal policies. The two proposed heuristic routing policies are shown to perform close to optimal solutions and they are as well tunable in terms of end-to-end throughput vs primary energy consumption. Finally, we address the problem of distributed data gathering in a wireless sensor network powered by energy harvesting. In particular, we consider a scenario in which wireless nodes cooperatively acquire spatial correlated measurements and route the information through the network in order to reach a sink node. Before the transmission, the acquired data is compressed via adaptive lossy source coding by leveraging the spatial correlation of the measurements. By assuming that the acquisition/compression, as well as the transmission, entails energy consumption, we propose an algorithm that minimizes the global distortion level introduced by the distributed source coding technique. At the same time, the proposed algorithm achieves network data queues stability and consumes energy, either for acquisition/compression or transmission, only if it is available. By approaching the problem using the Lyapunov optimization technique, we show that the proposed algorithm determines, in an online fashion, efficient acquisition/compression and routing policies with bounded performance guarantees with respect to the optimal performance.<br>La cooperazione tra i nodi di una rete radio distribuita è stata dimostrata essere efficace nel migliorare l’efficienza dell’utilizzo delle risorse, e.g., aumentare il throughput della rete o ridurre il consumo energetico. Negli ultimi anni, la cooperazione è stata ampiamente studiata sia da un punto di vista teorico che da un punto di vista implementativo. Ciò nonostante, ci sono diversi scenari che non sono ancora stati analizzati. In questa tesi, consideriamo reti radio distribuite cooperative e multi-salto, dove i nodi cooperano per consegnare messaggi da sorgenti a destinazioni. All’interno della tesi, il termine cooperazione assume significati diversi. Consideriamo situazioni nelle quali i nodi cooperano nella trasmissione di un messaggio, realizzando un schema distribuito di codifica spazio-tempo o utilizzando il concetto recente di “spectrum leasing via cooperation”, e il caso di acquisizione distribuita di dati, dove nodi sensori riducono la quantità di dati acquisiti (e il costo) sfruttando la correlazione spaziale e temporale delle misure. Il primo scenario considera una reta radio cooperativa multi-salto, dove i nodi che hanno decodificato il messaggio cooperano nella trasmissione dello stesso, realizzando un sistema di codifica distribuita a codici spazio-tempo. Il nostro obiettivo è quello di trovare politiche ottime di selezione dei cooperatori per topologie arbitrarie nel caso di singola coppia sorgente-destinazione, con link affetti da path loss e multipath fading. A tal fine, modellizziamo il comportamento della rete attraverso una appropriata catena di Markov e formuliamo il processo di selezione dei cooperatori come un problema di cammino minimo stocastico. Inoltre, riduciamo la complessità del problema di cammino minimo stocastico attraverso una tecnica di taglio innovativa che, a partire dal problema originale, ottiene una catena di Markov ridotta che è infine integrata all’interno di un risolutore basato sulla programmazione dinamica in tempo reale. Il nostro algoritmo è in grado di determinare delle politiche di selezione dei cooperatori per problemi con grandi spazi degli stati, raggiungendo una soluzione con costo confinato (e piccolo) rispetto al costo della soluzione ottima. In questo modo il risolutore permette di ottenere dei limiti sulle prestazioni della rete che possono essere utilizzati per lo sviluppo di protocolli pratici. A partire dai risultati della soluzione centralizzata, guardiamo il problema da un punto di vista diverso, sviluppando tre algoritmi completamente distribuiti e che operano in tempo reale, sfruttando nella selezione dei cooperatori solo informazioni locali. Le prestazioni delle tecniche proposte sono confrontate numericamente con quelle della strategia ottima centralizzata e con quelle di algoritmi simili presenti in letteratura, mostrando un miglioramento rispetto alle soluzioni già esistenti e raggiungendo prestazioni vicine all’ottimo. I risultati positivi ottenuti per lo scenario a singola sorgente-destinazione, ci hanno portato a studiare il comportamento di reti radio cooperative in presenza di interferenza multi-utente. In questo caso, il nostro obiettivo è quello di valutare l’impatto dell’interferenza tra flussi di dati distinti nella determinazione del cammino di instradamento ottimo e nell’ordine con cui avvengono le trasmissioni. Nello scenario che stiamo considerando, tutti i nodi hanno una singola antenna e possono cooperare nella trasmissione dei pacchetti. Dati questi presupposti, per prima cosa modellizziamo il problema delle trasmissioni cooperative utilizzando la programmazione lineare (LP). Dopodichè, per ottenere una soluzione efficiente, formuliamo il problema congiunto dell’instradamento e della pianificazione delle trasmissioni come un problema di cammino minimo a singola coppia, che è poi risolto utilizzando l’algoritmo di ricerca A∗ ed euristiche specializzate. I risultati simulativi delle politiche ottime così ottenute, confermano l’importanza di evitare percorsi di instradamento interferenti e confermano che una pianificazione dei percorsi che tenga conto dell’interferenza può migliorare le prestazioni della rete in modo sostanziale sia in termini di throughput che di energia spesa per la trasmissione, anche quando il numero di flussi che possono interferire è piccolo. Ancora una volta, i nostri modelli forniscono limiti sulle prestazioni della rete che posso essere utilizzati per sviluppare in modo efficiente protocolli di trasmissione cooperativi in reti radio distribuite. Spostiamo poi la nostra attenzione ad uno scenario di reti radio cognitive ed in particolare consideriamo una strategia di spectrum leasing (leasing dello spettro) per la coesistenza di reti multi-salto proprietarie dello spettro con insiemi di nodi senza licenza. La rete primaria consiste di una sorgente, una destinazione e un insieme di nodi primari aggiuntivi che possono essere utilizzati come ripetitori. In aggiunta, i nodi secondari possono essere utilizzati come ripetitori aggiuntivi e quindi come potenziali salti successivi, seguendo il principio dell’instradamento opportunistico. La cooperazione dei nodi secondari è garantita dal meccanismo di “spectrum leasing via cooperation”, dove un nodo che coopera ha la garanzia di poter utilizzare risorse spettrali soggette a vincoli di Qualità del Servizio (QoS). L’obiettivo di questo lavoro è trovare politiche di instradamento ottime ed euristiche, basate sull’idea dello spectrum leasing attraverso l’instradamento cooperativo ed opportunistico. A tal fine, inizialmente formuliamo il problema come un processo decisionale di Markov (MDP) e mostriamo come, in particolare, il problema possa essere trattato come un’istanza del problema di instradamento stocastico. Basandoci sulla struttura delle politiche ottime, deriviamo due schemi di instradamento euristici che confrontiamo poi con le politiche ottime. Le due politiche di instradamento euristiche che abbiamo proposto dimostrano di raggiungere prestazioni vicine alla soluzione ottima e possono essere modificate per ottenere un particolare rapporto tra il throughput sorgente-destinazione ed il consumo di energia primaria. Infine, trattiamo il problema dell’acquisizione di dati distribuita in reti radio di sensori alimentati da fonti di energia rinnovabile. In particolare, consideriamo lo scenario nel quale i nodi radio acquisiscono in modo cooperativo una misura spazialmente correlata ed instradano le informazioni acquisite all’interno della rete al fine di raggiungere un nodo collettore. Prima della trasmissione, i dati acquisiti sono compressi utilizzando una tecnica di codifica di sorgente adattiva e con perdita dell’informazione, utilizzando la correlazione spaziale delle misure. Assumendo che l’acquisizione/compressione, oltre alla trasmissione, abbiano un consumo energetico, proponiamo un algoritmo che minimizzi il livello di distorsione globale introdotto dalla tecnica di codifica di sorgente distribuita. Allo stesso tempo, l’algoritmo proposto garantisce la stabilità delle code di dati e consuma energia, per acquisizione/compressione o trasmissione, solo quando questa è disponibile. Affrontando il problema utilizzando la tecnica di ottimizzazione di Lyapunov, mostriamo come l’algoritmo proposto determini, in tempo reale, politiche di acquisizione/compressione ed instradamento con prestazioni entro limiti stabiliti dalle prestazioni ottime.

Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais ecientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções ecientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis a partir de um estado inicial porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes de maneira compacta e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e as comparamos com soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além disso, propomos um novo algoritmo de busca heurística para MDPs fatorados baseado no algoritmo ILAO* e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011.<br>One of the most widely used models to describe probabilistic planning problems, i.e., planning of actions with probabilistic eects, is the Markov Decision Process - MDP. The traditional solutions are based on dynamic programming, whereas the most ecient solutions are based on Real-Time Dynamic Programming - RTDP, which explore only the reachable states from a given initial state. Moreover, there are ecient solutions based on search methods in a AND/OR graph, where AND nodes represent the probabilistic eects of an action and OR nodes represent the choices of alternative actions. These solutions also explore only reachable states but maintain the parcial subgraph solution, using dynamic programming for updating the cost of nodes of these subgraph. However, problems with large state spaces limit the practical use of these methods. Factored representation of MDPs allow to explore the structure of the problem, and can represent very large MDPs compactly and thus improve the scalability of the solutions. In this dissertation, we present a comparative analysis of dierent solutions for MDPs, with emphasis on heuristic search methods. We compare the solutions which are based on asynchronous dynamic programming which are also considered the state of the art. We also propose a new factored algorithm based on the search algorithm ILAO*. It is also tested by using the problems of the International Probabilistic Planning Competition IPPC-2011.

Ce mémoire présente une étude comparative de quatre stratégies de gestion énergétique temps réel, appliquées d'une part à un véhicule hybride thermique-électrique, et d'autre part à un véhicule électrique à pile à combustible : contrôle basé sur des règles empirique (RBS), minimisation de la consommation équivalente (A-ECMS), loi de commande optimale (OCL) établie à partir d'une modélisation analytique du système et programmation dynamique stochastique (SDP) associée à une modélisation des cycles de conduite par chaîne de Markov. Le principe du minimum de Pontryaguin et la programmation dynamique, applicables hors ligne, sont mis en œuvre pour fournir des résultats de référence. Les problèmes d’implémentation numérique et de paramétrage des stratégies sont discutés. Une analyse statistique effectuée sur la base de cycles aléatoires générés par chaînes de Markov permet d’évaluer la robustesse des stratégies étudiées. Les résultats obtenus en simulation, puis sur un dispositif expérimental montrent que les méthodes les plus simples (RBS ou OCL) conduisent à des consommations élevées. SDP aboutit aux meilleures performances avec en moyenne la plus faible consommation de carburant dans les conditions réelles de conduite et un état énergétique final du système de stockage parfaitement maîtrisé. Les résultats d’A-ECMS sont comparables à ceux de SDP en moyenne, mais avec une plus grande dispersion, en particulier pour l'état de charge final. Afin d'améliorer les performances des méthode, des jeux de paramètres dédiés aux différents contextes de conduite sont considérés<br>This thesis presents a comparative study between four recent real-time energy management strategies (EMS) applied to a hybrid electric vehicle and to a fuel cell vehicle applications: rule-based strategy (RBS), adaptive equivalent consumption minimization strategy (A-ECMS), optimal control law (OCL) and stochastic dynamic programming (SDP) associated to driving cycle modeling by Markov chains. Pontryagin’s minimum principle and dynamic programming are applied to off-line optimization to provide reference results. Implementation and parameters setting issues are discussed for each strategy and a genetic algorithm is employed for A-ECMS calibration.The EMS robustness is evaluated using different types of driving cycles and a statistical analysis is conducted using random cycles generated by Markov process. Simulation and experimental results lead to the following conclusions. The easiest methods to implement (RBS and OCL) give rather high fuel consumption. SDP has the best overall performance in real-world driving conditions. It achieves the minimum average fuel consumption while perfectly respecting the state-sustaining constraint. A-ECMS results are comparable to SDP’s when using parameters well-adjusted to the upcoming driving cycle, but lacks robustness. Using parameter sets adjusted to the type of driving conditions (urban, road and highway) did help to improve A-ECMS performances

The problem addressed in this research is the in-flight generation of trajectories for autonomous unmanned aircraft, which requires a method of generating pseudo-optimal trajectories in near-real-time, on-board the aircraft, and without external intervention. The focus of this research is the enhancement of a particular inverse dynamics direct method that is a candidate solution to the problem. This research introduces the following contributions to the method. A quaternion-based inverse dynamics model is introduced that represents all orientations without singularities, permits smooth interpolation of orientations, and generates more accurate controls than the previous Euler-angle model. Algorithmic modifications are introduced that: overcome singularities arising from parameterization and discretization; combine analytic and finite difference expressions to improve the accuracy of controls and constraints; remove roll ill-conditioning when the normal load factor is near zero, and extend the method to handle negative-g orientations. It is also shown in this research that quadratic interpolation improves the accuracy and speed of constraint evaluation. The method is known to lead to a multimodal constrained nonlinear optimization problem. The performance of the method with four nonlinear programming algorithms was investigated: a differential evolution algorithm was found to be capable of over 99% successful convergence, to generate solutions with better optimality than the quasi- Newton and derivative-free algorithms against which it was tested, but to be up to an order of magnitude slower than those algorithms. The effects of the degree and form of polynomial airspeed parameterization on optimization performance were investigated, and results were obtained that quantify the achievable optimality as a function of the parameterization degree. Overall, it was found that the method is a potentially viable method of on-board near- real-time trajectory generation for unmanned aircraft but for this potential to be realized in practice further improvements in computational speed are desirable. Candidate optimization strategies are identified for future research.

La pile à combustible à membrane échangeuse de protons est un convertisseur électrochimique prometteur pour la production électrique à partir du vecteur hydrogène décarboné. Toutefois, certains verrous technologiques limitent encore son déploiement, tels que sa durabilité, sa fiabilité ou son coût financier. La stratégie de contrôle tolérant aux défauts actif est une des solutions pour atténuer tout défaut suivant trois actions : un diagnostic, une décision et un contrôle. Cette étude propose d’élaborer un module contrôleur générique et adaptatif aux états de santé par le biais des réseaux de neurones. Le contrôleur par programmation dynamique, l’apprentissage par renforcement et les modèles à états échoïques sont combinés pour la construction du contrôleur adaptatif. Ce contrôleur emploie trois modèles neuronaux avec des rôles spécifiques : un acteur, un prévisionneur et un critique. Les défauts de noyage et d’assèchement de la membrane sont considérés dans cette étude. Le contrôleur a pu démontrer des capacités intéressantes en simulation pour la régulation multi-variables de la stoechiométrie en oxygène, de la différence de pression à la membrane et de la température. Les résultats montrent des performances supérieures du contrôleur proposé face à un contrôleur proportionnel intégral dérivé. Des analyses de stabilité accompagnent l’étude et prouvent de la continuité du contrôleur adaptatif. Le contrôleur a été validé expérimentalement sur un banc d’essai avec une mono-cellule. La configuration du banc d’essai a imposé des contraintes propres à une application en ligne et en temps réel. Le caractère générique du contrôleur offre ici la possibilité de passer d’une configuration à l’autre sans devoir concevoir un autre contrôleur. Plusieurs tests sont effectués avec comme consigne la différence de pression nulle à la membrane. Le contrôleur a pu être validé sur l’apparition des défauts de noyage, d’assèchement de la membrane, y compris les perturbations en courant, les non-linéarités des actionneurs et de la purge en eau cathodique. La démarche et le contrôleur générique adaptatif aux états de santé proposés dans cette thèse permettent de répondre à des besoins de régulation autour de la stratégie de contrôle tolérant aux défauts. Le premier intérêt réside dans la compensation des effets multilatéraux des défauts qui entraîne des modifications dynamiques non voulues. Un autre intérêt est de pouvoir modifier in situ les conditions opératoires de fonctionnement, les composants ou même les auxiliaires tout en étant capable d’assurer un contrôle stable et optimal<br>The proton exchange membrane fuel cell is a promising electrochemical converter for production of electricity from the decarbonated hydrogen carrier. However, some technological challenges limit its deployment, such as durability, reliability or financial cost. The active fault-tolerant control strategy is one of the solutions to mitigate any system fault according to three actions: diagnosis, decision and control. This study proposes to develop a generic controller module adaptive to health states through neural networks. Dynamic programming controller, reinforcement learning, and echo-state models are combined for the design of the adaptive controller. This controller employs three neural models with specific roles: an actor, a predictor and a critic. Flooding and membrane drying faults are considered in this study. The proposed controller was able to demonstrate interesting capabilities on a simulation fuel cell model in multi-variable regulation for oxygen stoichiometry, membrane pressure difference and temperature. The results show superior performance of the proposed controller compared to a proportional integral derivative controller. Stability analyses were conducted to prove the continuity of the adaptive controller. The controller has been validated experimentally on a single cell test-bench. The configuration of the test-bench imposed constraints specific to an on-line and real-time application. The generic nature of the controller offers the possibility to switch from one configuration to another without having to design another controller. Several tests are carried out for regulation of the zero-pressure difference at the membrane. The controller was validated on the occurrence of flooding and membrane dryness faults, including actuator and water purging disturbances. The approach and the generic controller adaptive to the states of health proposed in this thesis allow to satisfy control requirements regarding the fault-tolerant control strategy. The first interest lies in the compensation of the multilateral effects of faults that lead to unwanted dynamic changes. Another interest is to be able to modify in situ operating conditions, components or even auxiliaries while being able to ensure a stable and optimal control

碩士<br>玄奘大學<br>資訊管理學系碩士班<br>100<br>Because the application of gesture is very wide, many different methods are gradually developing. Gesture recognitions are divided into static and dynamic type. The static gesture finds the shape of gestures. Most of dynamic gesture recognition requires a lot of training process before recognition. The training process needs to spend a lot of time. In this paper we propose a gesture recognition method, which is designed without training process. We use encoding method to record the direction of movement of gesture and the dynamic gesture recognition is performed by Longest Common Subsequence (LCS). We use the web camera to take image of gestures and calculated the central region of gestures to define the movement direction and coding. We define ten kinds of dynamic gestures and twenty testing samples are used in the experiment. We applied LCS to match the sequence number of encoding and the final result is determined by the threshold value. Experimental results show that this method can recognize the online gestures and the recognition rate is almost 89%.

碩士<br>國立中山大學<br>資訊工程學系研究所<br>105<br>Stereo vision is widely used in many computer vision applications including games, autonomous driving, object recognition, etc. Depth is the key information in stereo vision. In general, depth map is generated by stereo matching computation of two input images captured by cameras at different view angles. In this thesis, we use FPGA SoC platforms to realize a real-time dynamic programming-based stereo matching algorithm where the left and right input images are captured real-time and the computed depth maps are shown on screen. Image rectifications are also considered during the implementations. We study and analyze various hardware-software co-design options and improve the performance using different hardware platform environments.

碩士<br>國立中興大學<br>土木工程學系<br>88<br>Dynamic Programming is adopted in this study to build a reservoir operation model , and the fuzzy optimization theory which can handle the multipurpose decision-making problem more flexible is used to improve the proficiency of tradition dynamic programming in solving the multipurpose problem. To deal with the uncertaining of inflow , this study introduces the idea of Grey theory , where the inflow within a specific range is represented as a grey inflow. We combine the Fuzzy theorem and Grey theorem with the optimization approach to construct the model of “Grey Fuzzy Dynamic Programming” for the reservoir real-time operation. This model is applied to the De-Ji reservoir , and sets up Thomas & Fiering''s theorem of flow forecast pattern, which uses 10-day as a unit. Moreover, comparing with the historical results in the same conditions, it investigates the historical flow records of abundant water, average water and low water and compares the conditions of yearly electric power and drought. The results of this research in the year of abundant water, average water and low water all can effectively avoid the abnormal drought condition which is resulted from the rule-curve of De-Ji Reservoir. Comparing with past research records, the general profit has obviously increased. In the practical usage, the grey programming model has its simplicity and increases its feasibility for long term operation of reservoir. Keywords: Dynamic Programming；the fuzzy optimization theory；Grey theory ；Thomas & Fiering''s theorem of flow forecast pattern, which uses 10-day as a unit.

碩士<br>國立臺灣大學<br>農業工程學系研究所<br>86<br>Dynamic Programming is adopted in this study to build a reservoir operatio n model , and the fuzzy optimization theorem handles thedecision-making proble m in multi-purposes is used to improve theproficiency of tradition dynamic pro gramming in solving multi-purposeproblem . To deal with the uncertaining of in flow , this study introducesthe idea of Grey theorem , where the inflow withi n a specific range is represented as a grey inflow .We combine the Fuzzy theo rem and Greytheorem with the optimization approach to construct the model of " GreyFuzzy Dynamic Programmin " for the reservoir real-time operation. This model is applied to the Shi-Man Reservoir , and the M-5 curves , the operatio ning rule curves employed now in the actual reservoir operation , is chosen as the comparison method . Under the criteria ofshortage index and total shortag e amount , the results show that the "Grey Fuzzy Dynamic Programming " has bet ter performance than the M-5 curves .

碩士<br>淡江大學<br>水資源及環境工程所<br>82<br>This study used Bayesian estimator to modify the uncertainty of predicted streamflow and transition probability of the ochastic Dynamic Programming, how important of the weight ofrelease are also investgated in this study. Defining the term "the rate of inflow and demend" in this study, from which howrious the latent crisis of the shortage would be indicated.forecast technology, we could judge the feature ability of White River Reservoir in Tainan are simulated to test theeful of the mldel, it showed that this model is better than tne current operation model in dryed season and under the samendition, different weight of release,for the total shortage,difference between them are 10.59 million metric tons, there is great difference of the other indicator. The better shortage index, the better share of shortage.

碩士<br>國立臺北科技大學<br>化學工程研究所<br>95<br>The distillation column is a common and important operation unit in the chemical industry. As if the petrochemical technological certificates exam, the startup operation of distillation column is necessary for the test. However, using the distillation column as training for a beginner is not beneficial to economics. Therefore, the best solution for the problem is to use the simulation procedure of the computer on the training. Because the general commercial simulation software is with full function but costs very expensive, this research expects to develop a computer program which not only possesses simple functions but meet the teaching demands of the school laboratory. In this simulation program, VB2005 was used as a developing tool. As the simulation procedure starts, the distillation column is totally empty, and the user has to begin with filling materials. The program also includes some dangerous condition simulation. Moreover, this procedure will send out the warning while the unusual state occurs. By this way, learners can understand dangerous states of the distillation column of practical operation. In addition, beginners can learn how to operate the distillation column in the demonstration. Therefore, the training process can be time-saving and go smoothly. By virtue of this research results, the simulation procedure possesses the functions that trains beginners to operate the distillation column and let the learner learn more easily.

碩士<br>國立臺北科技大學<br>化學工程研究所<br>95<br>Although temperature processes are not very difficult tuning processes in the chemical plants, new incomer should learn how to tune the temperature controller. According to the economic benefits and learning efficiency, the best way that the beginners study them is through the process simulator. The research will develop a real time dynamic simulation window programming of temperature processes. The control strategies are feedback control, cascade control and feedforward control. Through graphic and Man-Machine interface design, all the operations of the control system could be the same as the real system is hoped. Visual Basic 2005 programming language was used to develop the programming. Finally, the simulation temperature process controlled by three different strategies was studied. As a result, our program can be used for beginners to study and compare the different control strategics of temperature process.

abstract: A principal goal of this dissertation is to study stochastic optimization and real-time scheduling in cyber-physical systems (CPSs) ranging from real-time wireless systems to energy systems to distributed control systems. Under this common theme, this dissertation can be broadly organized into three parts based on the system environments. The first part investigates stochastic optimization in real-time wireless systems, with the focus on the deadline-aware scheduling for real-time traffic. The optimal solution to such scheduling problems requires to explicitly taking into account the coupling in the deadline-aware transmissions and stochastic characteristics of the traffic, which involves a dynamic program that is traditionally known to be intractable or computationally expensive to implement. First, real-time scheduling with adaptive network coding over memoryless channels is studied, and a polynomial-time complexity algorithm is developed to characterize the optimal real-time scheduling. Then, real-time scheduling over Markovian channels is investigated, where channel conditions are time-varying and online channel learning is necessary, and the optimal scheduling policies in different traffic regimes are studied. The second part focuses on the stochastic optimization and real-time scheduling involved in energy systems. First, risk-aware scheduling and dispatch for plug-in electric vehicles (EVs) are studied, aiming to jointly optimize the EV charging cost and the risk of the load mismatch between the forecasted and the actual EV loads, due to the random driving activities of EVs. Then, the integration of wind generation at high penetration levels into bulk power grids is considered. Joint optimization of economic dispatch and interruptible load management is investigated using short-term wind farm generation forecast. The third part studies stochastic optimization in distributed control systems under different network environments. First, distributed spectrum access in cognitive radio networks is investigated by using pricing approach, where primary users (PUs) sell the temporarily unused spectrum and secondary users compete via random access for such spectrum opportunities. The optimal pricing strategy for PUs and the corresponding distributed implementation of spectrum access control are developed to maximize the PU's revenue. Then, a systematic study of the nonconvex utility-based power control problem is presented under the physical interference model in ad-hoc networks. Distributed power control schemes are devised to maximize the system utility, by leveraging the extended duality theory and simulated annealing.<br>Dissertation/Thesis<br>Ph.D. Electrical Engineering 2012

Mineral processing plan ts, such as LONMIN's Eastern Platinum B-stream, typically have few on-line measurements, and key measures of performance such as grade only become available after samples have been analysed in the laboratory. More immediate feedback from a dynamic observer model promises enhanced understanding of the process, and facilitates prompt corrective actions, whether in open or closed loop . Such plant s easily enter sub-optimal modes such as large , uselessly re-circulating loads as the feed conditions change. Interpretation of such modes from key combinations of the variables deduced by an observer model , using a type of expert system, would add another level of intelligence to benefit operation. The aim of this thesis was to develop and implement a dynamic observer model of the LONMIN Eastern Platinum B-Stream into one of the existing control platforms available at the plant , known as PlantStar®, developed by MINTEK. The solution of the system of differential and algebraic equations resulting from this type of flowsheet modelling is based on an extended Kalman filter, which is able to dynamically reconcile any measurements which are presented to it, in real time. These measurement selections may also vary in real time, which provides flexibility of the model solution and the model 's uses. PlantStar passes the measurements that are available at the plant, to the dynamic observer model through a "plugin" module, which has been developed to incorporate the observer model and utilise the PlantStar control platform. In an on-line situation, the model will track the plant's behaviour and continuously update its position in real-time to ensure it follows the plant closely. This model would then be able to run simulations of the plant in parallel and could be used as a training facility for new operators, while in a real-time situation it could provide estimates of unmeasurable variables throughout the plant. An example of some of these variables are the flotation rate constants of minerals throughout the plant, which can be estimated in real time by the extended Kalman filter. The model could also be used to predict future plant conditions based on the current plant state , allowing for case scenarios to be performed without affecting the actual plant's performance. Once the dynamic observer model and "plugin" module were completed, case scenario simulations were performed using a measured data set from the plant as a starting point because real-time data were unavailable as the model was developed off-site .<br>Thesis (M.Sc.Eng.)-University of Natal, Durban, 2004.

Train scheduling is a critical activity in rail traffic management, both off-line (timetabling) and on-line/in real-time (dispatching). This research aims at the design and development of advanced optimization models and methods for the real-time re-scheduling. The study covers two overlapping areas: managing the train service plans in an increasingly dynamic management scenario; and ensuring the safety and reliability of the railway system in case of major disruptions. Although the real-time re-scheduling problem is relatively easy to depict, due to the interdependent nature of trains moving along the networks lines, a huge challenge looms in the search for an optimal schedule. A great variety of approaches have been proposed over the years, but here we are interested in those based on Mixed Integer Linear Programming, which are the most widely adopted in the literature. The main issue that such approaches must face is how to represent the fact that two trains cannot occupy simultaneously the same track (or other pairs of incompatible railway resources). Typically, Time-Indexed (TI) formulations for scheduling problems are stronger than other classical formulations, like big-M models. Moreover, they can be easily adapted to cope with complicating constraints and non-linear objectives. Unfortunately, their size grows usually very large with the size of the scheduling instance. As a consequence, TI formulations are not suitable for attacking real-life instances, especially when fast, on-line responses are required. Further, the approximation introduced by time discretization often leads to solutions which cannot be realized in practice. The Dynamic Discretization Discovery (DDD), introduced by Boland for the continuous-time service network design problem, is a novel technique to keep at bay the growth of TI formulations (and thus their response times) and, at the same time, ensure the necessary modelling precision. Exploiting and extending the DDD paradigm, we develop a primal-dual exact approach to train dispatching. The result is a restricted TI formulation and a procedure with running times comparable with the best alternatives presented in the literature on our real-life instances of train dispatching. Furthermore, the method implemented does not suffer by the approximation error introduced by a standard time discretization. In our comparisons the big-M approach maintains the lead on average, but the distance is getting smaller. Even though the method developed in this research is at its early stage, it is very promising not only in a railway context but, more generally, for the broader field of job-shop scheduling. In addition, it offers many hints and opportunities for enhancements that will be investigated in future works. On the other hand, when major disruptions occur in a rail network a simple rescheduling is not sufficient to re-ensure the viability of the network. Indeed, parts of the network may become unavailable for inbound trains, and decisions must be taken to mitigate the impact on the overall traffic. Arguably the most critical point is to avoid creating deadlocks, a situation that arises when a group of trains is positioned in such a way that none can move due to other trains in the group blocking their path. The infrastructure manager and train operating companies in these cases may be forced to stop trains until the normal status is recovered. A crucial aspect is thus to identify, for each train, a location where the train can hold during the disruption, avoiding to disconnect the network and allowing for a quick recovering of the original plan, at restart. A good location for holding a train is called a safe place and it additionally serves the purpose of preventing trains to drive past the last location where they can be safely parked, which could otherwise lead to further blockages and deadlocks. We outline some necessary and sufficient conditions to achieve the desired safe places properties. We then translate such conditions into constraints for a binary formulation of the problem, which we named Safe Place Assignment Problem (SPAP). The SPAP finds an application in the current usage of Advanced Traffic Management Systems (ATMSs). This digital train management solutions are called to solve instances of a hard optimization problem in very limited computational time and they may fail to return a plan for different reasons. Finding a solution to the SPAP in these cases adds an additional level of safety, as dispatchers are provided with the last safe location for a train to drive within the plan's horizon. Computational results on a set of instances provided by a Class I U.S. railroad company show how the approach can be used effectively in the real-life setting that motivates the study, by returning optimal assignments in fractions of second. Both research outputs are very innovative and off the beaten track. The achievements regards both the theoretical and methodological point of view and present in addition a practical relevance.

Future space missions, such as Mars Science Laboratory, suggest the engineering of some of the most complex man-rated autonomous software systems. The present process-oriented certification methodologies are becoming prohibitively expensive and do not reach the level of detail of providing guidelines for the development and validation of concurrent software. Time and concurrency are the most critical notions in an autonomous space system. In this work we present the design and implementation of the first concurrency and time centered framework for product-oriented software certification of autonomous space systems. To achieve fast and reliable concurrent interactions, we define and apply the notion of Semantically Enhanced Containers (SEC). SECs are data structures that are designed to provide the flexibility and usability of the popular ISO C++ STL containers, while at the same time they are hand-crafted to guarantee domain-specific policies, such as conformance to a given concurrency model. The application of nonblocking programming techniques is critical to the implementation of our SEC containers. Lock-free algorithms help avoid the hazards of deadlock, livelock, and priority inversion, and at the same time deliver fast and scalable performance. Practical lock-free algorithms are notoriously difficult to design and implement and pose a number of hard problems such as ABA avoidance, high complexity, portability, and meeting the linearizability correctness requirements. This dissertation presents the design of the first lock-free dynamically resizable array. Our approach o ers a set of practical, portable, lock-free, and linearizable STL vector operations and a fast and space effcient implementation when compared to the alternative lock- and STM-based techniques. Currently, the literature does not offer an explicit analysis of the ABA problem, its relation to the most commonly applied nonblocking programming techniques, and the possibilities for its detection and avoidance. Eliminating the hazards of ABA is left to the ingenuity of the software designer. We present a generic and practical solution to the fundamental ABA problem for lock-free descriptor-based designs. To enable our SEC container with the property of validating domain-specific invariants, we present Basic Query, our expression template-based library for statically extracting semantic information from C++ source code. The use of static analysis allows for a far more efficient implementation of our nonblocking containers than would have been otherwise possible when relying on the traditional run-time based techniques. Shared data in a real-time cyber-physical system can often be polymorphic (as is the case with a number of components part of the Mission Data System's Data Management Services). The use of dynamic cast is important in the design of autonomous real-time systems since the operation allows for a direct representation of the management and behavior of polymorphic data. To allow for the application of dynamic cast in mission critical code, we validate and improve a methodology for constant-time dynamic cast that shifts the complexity of the operation to the compiler's static checker. In a case study that demonstrates the applicability of the programming and validation techniques of our certification framework, we show the process of verification and semantic parallelization of the Mission Data System's (MDS) Goal Networks. MDS provides an experimental platform for testing and development of autonomous real-time flight applications.

A generalized dynamic programming based algorithm and a local search heuristic are used to solve the Two Runway Departure Scheduling Problem that arises at an airport. The objective of this work is to assign the departing aircraft to one of the runways and find a departing time for each aircraft so that the overall delay is minimized subject to the timing, safety, and the ordering constraints. A reduction in the overall delay of the departing aircraft at an airport can improve the airport surface operations and aircraft scheduling. The generalized dynamic programming algorithm is an exact algorithm, and it finds the optimal solution for the two runway scheduling problem. The performance of the generalized dynamic programming algorithm is assessed by comparing its running time with a published dynamic programming algorithm for the two runway scheduling problem. The results from the generalized dynamic programming algorithm show that this algorithm runs much faster than the dynamic programming algorithm. The local search heuristic with k − exchange neighborhoods has a short running time in the order of seconds, and it finds an approximate solution. The performance of this heuristic is assessed based on the quality of the solution found by the heuristic and its running time. The results show that the solution found by the heuristic for a 25 aircraft problem has an average savings of approximately 15 percent in delays with respect to a first come-first served solution. Also, the solutions produced by a 3-opt heuristic for a 25 aircraft scheduling problem has an average quality of 8 percent with respect to the optimal solution found by the generalized dynamic programming algorithm. The heuristic can be used for both real-time and fast-time simulations of airport surface operations, and it can also provide an upper limit for an exact algorithm. Aircraft arrival scheduling problems may also be addressed using the generalized dynamic programming algorithm and the local search heuristic with slight modification to the constraints.

While decision-making under uncertainty is a major universal problem, its implications in the field of transportation systems are especially enormous; where the benefits of right decisions are tremendous, the consequences of wrong ones are potentially disastrous. In the realm of highway systems, decisions related to the highway configuration (number of lanes, right of way, etc.) need to incorporate both the traffic demand and land price uncertainties. In the literature, these uncertainties have generally been modeled using the Geometric Brownian Motion (GBM) process, which has been used extensively in modeling many other real life phenomena. But few scholars, including those who used the GBM in highway configuration decisions, have offered any rigorous justification for the use of this model. This thesis attempts to offer a detailed analysis of various aspects of transportation systems in relation to decision-making. It reveals some general insights as well as a new concept that extends the notion of opportunity cost to situations where wrong decisions could be made. Claiming deficiency of the GBM model, it also introduces a new formulation that utilizes a large and flexible parametric family of jump models (i.e., Lévy processes). To validate this claim, data related to traffic demand and land prices were collected and analyzed to reveal that their distributions, heavy-tailed and asymmetric, do not match well with the GBM model. As a remedy, this research used the Merton, Kou, and negative inverse Gaussian Lévy processes as possible alternatives. Though the results show indifference in relation to final decisions among the models, mathematically, they improve the precision of uncertainty models and the decision-making process. This furthers the quest for optimality in highway projects and beyond.