Sven Koenig

Goal-Directed Acting with Incomplete Information Degree Type: Ph.D. in Computer Science
Advisor(s): Reid Simmons
Graduated: December 1997

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 for fine-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.

Keywords:
Actuator uncertainty, agent architecture, agent-centered search, artificial intelligence, Baum-Welch method, deadlines, decision theory, decomposability of planning tasks, delivery robots, discounting, dynamic programming, Edge Counting method, Euler graphs, exponential utility functions, grid-worlds, high-stake decision making, interleaving of planning and plan execution, landmark-based navigation