KR2020Proceedings of the 17th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 12-18, 2020.

Edited by

ISSN: 2334-1033
ISBN: 978-0-9992411-7-2

Sponsored by
Published by

Copyright © 2020 International Joint Conferences on Artificial Intelligence Organization

Spatial Reasoning about String Loops and Holes in Temporal ASP

  1. Pedro Cabalar(University of A Coruña, Spain)
  2. Paulo E. Santos(Flinders University, Adelaide, Australia, FEI, São Paulo, Brazil)


  1. Commonsense reasoning-General
  2. Geometric, spatial, and temporal reasoning-General
  3. Logic programming, answer set programming, constraint logic programming-General
  4. Reasoning about actions and change, action languages-General


This paper introduces a new formalism for the automated solution of spatial scenarios involving strings and holed objects. In particular, we revisit a previous formalisation that allows string loops to be treated as holes, but make a substantial modification by removing a previous limitation that prevented a string to cross its own loops. The formalisation introduced in the present paper relies on string segments as basic entities and achieves a greater degree of elaboration tolerance by using inertia to describe those parts of the physical scenario that are unaffected by a given action. As a representation language, we have used Temporal Answer Set Programming since it provides a simple and natural way to deal with time and inertia while, at the same time, it is accompanied by the automated tool 'telingo' that allows a systematic testing of the effects of any sequence of actions. As an illustrative example, we have studied the African Ring puzzle, a problem involving loops crossed by a unique string, and provided the first formalisation of its solution, to the best of our knowledge.