Planning under Uncertainty and Temporally Extended Goals

Abstract

In the last decade, we have seen an exponential increase in the number of devices connected to the Internet, with a commensurate explosion in the availability of data. New applications such as those related to smart cities exemplify the need for principled techniques for automated intelligent decision making based on available data. Many decision-making problems require reasoning in large and complex state spaces, sometimes under stringent time constraints. The nature of these problems suggests that planning approaches could be used to find solutions efficiently. Automated planning is the basis for addressing a diversity of problems beyond classical planning such as automated diagnosis, controller synthesis, and story understanding. Nevertheless, many planning paradigms make assumptions that do not hold in real-world settings. Our work focuses on exploring planning paradigms that capture properties of real-world decision-making applications. These properties include the ability to model nondeterminism in the outcome of actions, the ability to deal with complex objectives that are temporally extended (in contrast to final-state goals) some of which may be necessary and other simply desirable to optimize for. Finally, we are interested in dealing with incomplete information. Addressing this class of problems presents challenges related to problem specification, modeling, and computationally efficient techniques for generating solutions.