--------------------------------------------------------------------------


		     B O S T O N   U N I V E R S I T Y

			Computer Science Department

			    C O L L O Q U I U M


		       Scheduling under Uncertainty

			      David Castanon
	       Dept. of Electrical and Computer Engineering
			     Boston University

	
			   Wednesday, November 18
				  3:00pm

			 (Coffee served at 2:45pm)

			  Seminar Room / MCS 135


Planning and scheduling problems under uncertainty arise in a variety of
applications, ranging from diagnosis of failed equipment to detailed route
planning of multiple vehicles.  The presence of uncertainty can result in
partial knowledge of the problem state, plus inaccurate predictions of the
consequences of selected decisions.  In such problems, it is desirable to
collect dynamically information about the progress of the problem state,
and to use that information to adapt selection of future actions.  This
leads to a plan, which is a strategy which maps possible information about
problem states into selected actions.

When the uncertainty is captured using a probabilistic setting, there is a
rich body of literature addressing these problems under the heading of
stochastic control.  Such problems can in theory be solved using Bellman's
Principle of Optimality and dynamic programming algorithms.  However, the
computational complexity of the resulting algorithms restrict applications
to miniscule toy problems.

In recent years, there has been an increased emphasis on developing
techniques for scheduling under uncertainty that are practical for
nontrivial applications.  Techniques such as reinforcement learning,
neurodynamic programming and other variants of approximate dynamic
programming have focused on developing practical polynomial-time
approximations to the theoretically optimal algorithms, trading performance
for practical computation bounds.  In this talk, we discuss some recent
extensions of these techniques, and illustrate the resulting performance on
several scheduling applications.

Host: Prof. Steve Homer (homer@cs.bu.edu)

---------------------------------------------------------------------------
For colloquium info and directions, see http://www.cs.bu.edu/colloquium
---------------------------------------------------------------------------