Decidable Verification of Golog Programs over Non-Local Effect Actions

Benjamin ZarrießBenjamin Zarrieß, Jens ClaßenJens Claßen

Download

Benjamin Zarrieß, Jens Claßen
Decidable Verification of Golog Programs over Non-Local Effect Actions
In Dale Schuurmans, Michael Wellman, eds., Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16), to appear. AAAI Press

Details
Bibtex

KurzfassungAbstract
The Golog action programming language is a powerful means to express high-level behaviours in terms of programs over actions defined in a Situation Calculus theory. In particular for physical systems, verifying that the program satisfies certain desired temporal properties is often crucial, but undecidable in general, the latter being due to the language's high expressiveness in terms of first-order quantification and program constructs. So far, approaches to achieve decidability involved restrictions where action effects either had to be context-free (i.e. not depend on the current state), local (i.e. only affect objects mentioned in the action's parameters), or at least bounded (i.e. only affect a finite number of objects). In this paper, we present a new, more general class of action theories (called acyclic) that allows for context-sensitive, non-local, unbounded effects, i.e. actions that may affect an unbounded number of possibly unnamed objects in a state-dependent fashion. We contribute to the further exploration of the boundary between decidability and undecidability for Golog, showing that for acyclic theories in the two-variable fragment of first-order logic, verification of CTL* properties of programs over ground actions is decidable.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ZC2016,
  author    = {Benjamin Zarrie{\ss} and Jens Cla{\ss}en},
  title     = {Decidable Verification of Golog Programs over Non-Local Effect
               Actions},
  editor    = {Dale Schuurmans and Michael Wellman},
  booktitle = {Proceedings of the Thirtieth {AAAI} Conference on Artificial
               Intelligence (AAAI-16)},
  publisher = {AAAI Press},
  year      = {2016},
  month     = {February}
}