Google Research

A Generic Technique for Synthesizing Bounded Finite-State Controllers

  • Yuxiao Hu
  • Giuseppe De Giacomo
Proceedings of the International Conference on Automated Planning and Scaduling, Association for the Advancement of Artificial Intelligence (2013), pp. 109-116

Abstract

Finite-state controllers are a compact and effective plan representation for agent widely used in AI. In this paper, we proposea generic framework and related solver for synthesizing bounded finite-state controllers, and show its instantiations to three different applications, including generalized planning, planning programs and service composition under partial observability and controllability. We show that our generic solver is sound and complete, and amenable to heuristics that take into account the structure of the specific target instantiation. Experiments show that instantiations of our solver to the problems above often outperform tailored approaches in the literature. This suggests that our proposal is a promising base point for future research on finite-state controller synthesis.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work