Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints

Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints

Blai Bonet, Giuseppe De Giacomo, Hector Geffner, Sasha Rubin

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 873-879. https://doi.org/10.24963/ijcai.2017/121

We study the characterization and computation of general policies for families of problems that share a structure characterized by a common reduction into a single abstract problem. Policies mu that solve the abstract problem P have been shown to solve all problems Q that reduce to P provided that mu terminates in Q. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Q that is local (Markovian) but misses common structure that is global. We show how such global structure can be captured by means of trajectory constraints that in many cases can be expressed as LTL formulas, thus reducing generalized planning to LTL synthesis. Moreover, for a broad class of problems that involve integer variables that can be increased or decreased, trajectory constraints can be compiled away, reducing generalized planning to fully observable non-deterministic planning.
Keywords:
Knowledge Representation, Reasoning, and Logic: Action, Change and Causality
Planning and Scheduling: Theoretical Foundations of Planning
Agent-based and Multi-agent Systems: Formal verification, validation and synthesis