17 October 2019, ILLC Lecture, Alvaro Torralba

Abstract:

AI Planning is a model-based approach to intelligent sequential decision making. Given a model of the environment, a rational agent can automatically decide what actions to perform to achieve its goals with minimal cost. The aim is to decouple the description of the problem and the mechanism to make intelligent decisions, so that the same algorithm can be applied to solve any domain (e.g. logistics, space exploration, chemistry, natural language generation).

In classical planning, this is formally represented as finding a path in the state space: a graph implicitly given by the model that describes the outcome of all possible actions of the agent. However, this graph is often exponential in the size of the model, so it is unfeasible to explore it completely. The key is to exploit the structure of the task, finding its individual properties.

This talk introduces dominance analysis, a novel technique to unveil the structure of a planning task in the form of a relation that compares pairs of states, proving that one of them is preferable to achieve the agent's goal. This can be used in different ways, e.g., to eliminate states that are dominated by others, or identify actions leading to better states. This provides a speed-up of up to several orders of magnitude on tasks where dominance can be discovered.