Modeling and solving sequential decision problems with uncertainty and partial information

The idea of developing General Problem Solvers (GPS) has been in Artificial Intelligence (AI) since its inception. A GPS is a computer system comprised of a general description language and algorithms used to model and solve sequential decision problems. This dissertation focuses in developing a GPS aimed at sequential decision problems involving uncertainty and partial information.; The general approach proposed here addresses the task of building a GPS from three different and orthogonal dimensions of (i) mathematical models that characterize the problems, their solutions and optimal solutions, (ii) high-level description languages used to describe the mathematical models in an economical and amenable way, and (iii) general algorithms, based on heuristic search, used to solve the resulting models.; This work starts from the mathematical models of control theory and proposes novel representation techniques and algorithmic solutions superior to the ones traditionally used. The new algorithms are the result of casting the general sequential decision problem as a search problem in a suitable space that is then tackled using basic principles from AI. The dissertation thus presents a new perspective on sequential decision making that allows for a fruitful cross-fertilization between control theory and AI.; The contributions of this work are diverse. We show new theoretical results about the existence and characterization of solutions for the mathematical theory of Markov decision processes.; On the algorithmic side, we propose new algorithms based on heuristic search that compute partial optimal policies, together with new heuristic functions. We show the correctness and complexity of the algorithms, and the formal properties of the heuristic functions. The performance of the new algorithms is shown to be superior, through a number of experiments, to the current state-of-the-art algorithms.; On the representation side, we introduce a new and very expressive representation language for planning problems involving uncertainty and partial information. This is one of the first general representation languages capable of coping with a broad range of planning problems including robot navigation, game playing, synthesis of circuits, medical diagnosis, sequential knowledge acquisition, etc.; Several extensions of the approach are also included. They give formal characterization of models known up to a certain degree of precision, and novel proposals for trading off sub-optimality of solutions against performance.; These extensions are built upon methods from qualitative decision theory (as the kappa functions proposed by Spohn and used by Pearl and others to model qualitative information), methods of propositional satisfiability, and the novel data structures used in formal verification.