Abstract

Abstract: In the not too distant future, delivery robots will distribute parcels in office buildings and exploratory robots will roam the surface of other planets. Such situated agents must exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, limited or noisy perception, or insufficient reasoning speed. In this thesis, we develop efficient general-purpose decision-making methods for one-shot (that is, single-instance) planning tasks that enable situated agents to exhibit goal-directed behavior in the presence of incomplete information. The decision-making methods combine search and planning methods from artificial intelligence with methods from operations research and utility theory. We demonstrate how to use Partially Observable Markov Decision Process (POMDP) models to act, plan, and learn despite the uncertainty that results from actuator and sensor noise and missing information about the environment. We show how to use exponential utility functions to act in the presence of deadlines or in high-risk situations and demonstrate how to perform representation changes that transform planning tasks with exponential utility functions to planning tasks that standard search and planning methods from artificial intelligence can solve. Finally, we show how to decrease the planning time by interleaving planning and plan execution and present a real-time search method that allows forfifine-grained control over how much planning to do between plan executions, uses heuristic knowledge to guide planning, and improves its performance over time as it solves similar planning tasks. We use goal-directed robot-navigation tasks to illustrate the methods throughout the thesis, and present theoretical analyses, simulations, and experiments on a real robot.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.