Abstract: Planning under uncertainty is a fundamental problem in the area of artificial intelligence and robotics and has been well-studied over the years. Decision-theoretic planning is a formal approach for reasoning in stochastic domains in which the objective is to produce a course of action that maximizes expected reward, making it well-suited to this problem. In this talk I will describe some of the key models used in decision-theoretic planning, namely the Markov decision process, both the fully observable and partially observable cases, and their generalizations to the case of decentralized control of multiple agents. Next I will present a classic result on the complexity bounds for the decentralized control problems and show that even with only two agents the finite-horizon problems for these models are hard for non-deterministic exponential time.
The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.