[Brown CS Talks] Brown CS Thesis Defense: Jim Kurien in Lubrano on August 15, 2002 at 1 pm

[talks-admin@list.cs.brown.edu]

		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			      Jim Kurien

			    Thesis Defense

		 Thursday, August 15, 2002 at 1:00 pm
	       Lubrano Conference Room (CIT 4th floor)

	       
	   Diagnosis and Planning with Resource Constraints
 

			       Abstract

Consider the task of selecting actions that will move a complex
physical system such as a spacecraft from its current state to a state
that achieves a set of desired goals.  In practice, this task is
complicated by the possibility of failures.  When a failure occurs,
the system enters an unanticipated state and subsequent actions may
not have the expected effect.  The exact state of the system may not
be directly observable, and some of the goals may no longer be
achievable.  Intuitively, we'd like to choose actions that move the
system from the states it's likely to be in to a state that achieves
the goals that remain achievable.  This work consists of a novel
diagnosis algorithms for determining the likely states of a system
even when failures are not immediately observable, and novel planning
algorithms for achieving as many goals as possible even when the
initial state of the system is not exactly known.  The quality of the
diagnoses and plans produced degrades gracefully as the time available
for computation is reduced.  The systems presented has been
implemented and results on examples from the domain of spacecraft
control and the planning literature are presented.

The diagnosis algorithms generate approximate belief states for a
restricted but relevant class of partially observable Markov decision
processes with very large state spaces. The algorithm incrementally
generates, rather than revises, an approximate belief state at any
point by abstracting and summarizing segments of the likely past
trajectories of the system. This enables applications to efficiently
maintain a partial belief state when it remains consistent with
observations and revisit past assumptions about the system's evolution
when the belief state is ruled out by the delayed evidence of a
failure.

Conformant planning is the problem of generating a plan that moves a
system from any of a number of possible initial states to a goal
state.  The dominant approach to conformant planning is to consider
the effects of actions in all states simultaneously. In this work, we
attempt to find a plan for one possible state and incrementally extend
it to work in all states.  We then move beyond conformant planning to
find plans that optimize the goals that are achieved and the initial
states from which they are achieved according to their priorities.
Thus we are able to find good plans when there is insufficient time to
find a conformant plan or when a conformant plan does not exist due to
system failures.


		     Host: Professor John Hughes