Duke Student Scholarship
Permanent URI for this community
Browse
Browsing Duke Student Scholarship by Affiliation "Computer Science"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Open Access Efficient selection of disambiguating actions for stereo vision(2010) Schaeffer, MonikaIn many domains that involve the use of sensors, such as robotics or sensor networks, there are opportunities to use some form of active sensing to disambiguate data from noisy or unreliable sensors. These disambiguating actions typically take time and expend energy. One way to choose the next disambiguating action is to select the action with the greatest expected entropy reduction, or information gain. In this work, we consider active sensing in aid of stereo vision for robotics. Stereo vision is a powerful sensing technique for mobile robots, but it can fail in scenes that lack strong texture. In such cases, a structured light source, such as vertical laser line, can be used for disambiguation. By treating the stereo matching problem as a specially structured HMM-like graphical model, we demonstrate that for a scan line with n columns and maximum stereo disparity d, the entropy minimizing aim point for the laser can be selected in O(nd) time - cost no greater than the stereo algorithm itself. A typical HMM formulation would suggest at least O(nd2) time for the entropy calculation alone.Item Open Access Non-parametric approximate linear programming for MDPs(2012) Pazis, JasonOne of the most difficult tasks in value function based methods for learning in Markov Decision Processes is finding an approximation architecture that is expressive enough to capture the important structure in the value function, while at the same time not overfitting the training samples. This thesis presents a novel Non-Parametric approach to Approximate Linear Programming (NP-ALP), which requires nothing more than a smoothness assumption on the value function. NP-ALP can make use of real-world, noisy sampled transitions rather than requiring samples from the full Bellman equation, while providing the first known max-norm, finite sample performance guarantees for ALP under mild assumptions. Additionally NP-ALP is amenable to problems with large (multidimensional) or even infinite (continuous) action spaces, and does not require a model to select actions using the resulting approximate solution.Item Open Access Uncertainty propagation through software dependability models(2011) Mishra, KesariSystems in critical applications employ various hardware and software fault-tolerance techniques to ensure high dependability. Stochastic models are often used to analyze the dependability of these systems and assess the effectiveness of the fault-tolerance techniques employed. Measures like performance and performability of systems are also analyzed using stochastic models. These models take into account randomness in various events in the system (known as aleatory uncertainty) and are solved at fixed parameter values to obtain the measures of interest. However, in real life, the parameters of the stochastic models themselves are uncertain as they are derived from a finite (limited) number of observations or are simply based on expert opinions. Solving the stochastic models at fixed values of the model input parameters result in estimates of model output metrics which do not take into account the uncertainty in model input parameters (known as epistemic uncertainty). In this research work, we address the computation of uncertainty in output metrics of stochastic models due to epistemic uncertainty in model input parameters, with a focus on dependability and performance models of current computer and communication systems. We develop an approach for propagation of epistemic uncertainty in input parameters through stochastic dependability and performance models of varying complexity, to compute the uncertainty in the model output measures. The uncertainty propagation method can be applied to a wide range of stochastic model types with different model output measures. For simple analytic stochastic dependability models, we present a closed-form analytic method for epistemic uncertainty propagation, where we derive closed-form expressions for the expectation, distribution and variance of the model output metrics due to the epistemic uncertainty in the model input parameters. We analyze the results thus obtained and study their limiting behavior. For slightly more complex analytic stochastic models, where the closed-form expressions for the expectation, distribution and variance of the model output cannot be easily obtained, we present a numerical integration based method. For large and complex stochastic models, we develop a sampling based epistemic uncertainty propagation method which also considers dependencies in the input parameter values and is an improvement over previous sampling based uncertainty propagation approaches. The sampling based epistemic uncertainty propagation method explained in this dissertation acts as a wrapper to existing models and their solution types (hence the wide applicability) and provides more robust estimates of uncertainty in the model output metrics than previous sampling based methods. We demonstrate the applicability of the uncertainty propagation approach by applying it to analytic stochastic dependability and performance models of computer systems, ranging from simple non-state-space models with a few input parameters to large state-space models and even hierarchical models with more than fifty input parameters. We further apply the uncertainty propagation approach to stochastic models with not only analytic or analytic-numeric solutions but also those with simulative solutions. We also consider a wide range of model output metrics including reliability and availability of computer systems, response time of a web service, capacity oriented availability of a communication system, security (probability ofsuccessful attack) of a network routing session, expected number of jobs in a queueing system with breakdown and repair of servers and call handoff probability of a cellular wireless communication cell.