Abstract: In the field of probabilistic planning, the problem of decentralized control of cooperative systems is well known to be intractable. Deciding models including Decentralized Markov Decision Processes (Dec-MDP) and Decentralized Partially Observable Markov Decision Processes (Dec-POMDP) has been shown to be NEXP-complete in general. In this talk, I will discuss a variety of Dec-POMDP variants which have historically been proposed with the intention of identifying useful subclasses with lower complexity, and will give an overview of the results which have been achieved.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco 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.