Planning under Uncertainty

Many real-world planning problems occur in environments where there may be incomplete information or where actions may not always lead to the same results. Examples include planning for retirement, where the state of the economy in the future is uncertain, and planning in logistics, where the duration of travel between two cities is uncertain due to potential congestion.

A Markov decision process (MDP) is a popular framework for modeling decision making in these kinds of problems, where an agent needs to plan a sequence of actions that maximizes its chances of reaching its goal. A partially observable MDP (POMDP) is an extension where the world that the agent is operating in is only partially observable, and a decentralized (PO)MDP is an extension where a team of agents needs to collectively plan their joint actions.

We are currently pursuing three orthogonal subprojects within this area:

  • We proposed the risk-sensitive MDP and POMDP models, where the objective is to find a policy that maximizes the probability of reaching a goal state. Such a model and its accompanying algorithms are useful in high-risk applications, where a single failure can be catastrophic.
  • We are investigating the topic of goal recognition design, where the objective is to find a modification of the underlying planning problem such that the goal of an agent in that environment can be recognized as early as possible.
  • We aim to bridge MDPs and POMDPs with distributed constraint optimization problems (DCOPs). DCOPs are well-suited for modeling single-shot distributed coordination problems such as distributed task/resource allocation problems. Our goal is to enrich DCOPs to handle dynamic problems with uncertainty using MDP and POMDP concepts. See DCOP project page for more info.
Group Members and Current Collaborators
Sponsors
Recent Publications