Research Overiew

Richard Goodwin

My research interests include artificial intelligence and the creation of intelligent agents. In particular, my thesis research focuses on decision-theoretic planning, meta-level reasoning and autonomous indoor and outdoor mobile robots. My masters work includes research on formal specifications of agent properties and inductive logic learning. Prior to graduate school, I helped develop intelligent database access applications for bibliographic and corporate databases at Bell Northern Research. Throughout my research, my aim has been to combine theoretical and empirical investigations to generate novel solutions to real problems. I believe that empirical evidence leads to theoretical insight, which, in turn, suggests directions for further experimentation. In the end, approaches and ideas are validated when successfully applied to solving a real problem.

Consider the problem of developing a mobile robot to operate efficiently and robustly in an office environment. This is a problem that I use to ground my thesis research. A mobile robot is dynamic, has noisy sensors, and unreliable actuators. It has to deal with a limited sensing range and limited computation. Early attempts to apply symbolic AI planning techniques to mobile robots showed that simple, STRIPS-like planning approaches are impoverished, but still lead to calculations that are intractable or even undecidable. To deal with the complexities of planning for mobile robots, many researchers have adopted probability theory and have borrowed ideas from economics to create decision-theoretic planners. The result is a richer planning language and task representation that more accurately describes the planning problem, but exacerbates the computation problems.

My thesis work addresses these computation problems by explicitly allocating resources to efficiently accomplish the task at hand rather than just trying to create the best plan. Building on the decision-theoretic planning approach, my thesis research examines the meta-level planning problem of how to effectively allocate computation and the meta-level question of when to plan and when to act. I have shown how a decision-theoretic planner can make some planning decisions optimally, and I have advanced the state-of-the-art for using sensitivity analysis in planning search control. I identified a limitation in a proposed idealized algorithm for deciding when to act and devised a new idealized algorithm without the limitation. Using my mathematical results, I created a planner that can efficiently route our mobile robot, Xavier, around our research building. The planner takes into account the robot's performance characteristics and plans for contingencies, like locked doors. I have also applied the same mathematical results to a domain independent planner, DRIPS, developed at the University of Wisconsin. As a result, the planner's performance has more than doubled when the planner is used to create treatment policies for a domain taken from the medical literature. The planner can now consider a larger range of treatments and determine the optimal treatment policy.

As computers get faster and networks grow larger, it is becoming apparent that simply building larger, faster machines is not a panacea for all our computation problems. We use faster computers to solve larger problems, with more detailed models. We use larger networks to provide access to vast amounts of data that can be used to build better models or monitor ongoing processes. The questions of how detailed a model to use and how much data to collect remain critical to performance. Computer resources need to be allocated effectively and must adapt to specific problem instances. This observation holds for a broad range of applications from traditional operations research optimization problems to database accesses and dynamic network reconfiguration. The meta-level reasoning techniques I have developed in my thesis are applicable whenever computation can be traded for solution quality, or resource use can be traded for latency. For example, machine shop scheduling and logistics planning are areas where where my techniques are applicable and where small improvements in efficiency translate into significant financial advantages.

Selected Papers