Spatial reasoning about string loops and holes in temporal asp

Pedro Cabalar, Paulo E. Santos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publication17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020
EditorsDiego Calvanese, Esra Erdem, Michael Thielscher
PublisherInternational Joint Conference on Artificial Intelligence (IJCAI)
Pages181-191
Number of pages11
ISBN (Electronic)9781713825982
ISBN (Print)9780999241172
DOIs
Publication statusPublished - 2020
Event17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 - Rhodes, Greece
Duration: 12 Sep 202018 Sep 2020

Publication series

Name17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020
Volume1

Conference

Conference17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020
Country/TerritoryGreece
CityRhodes
Period12/09/2018/09/20

Keywords

  • spatial reasoning
  • string loops
  • temporal ASP
  • geometric reasoning
  • Logic Programming
  • answer set programming
  • temporal reasoning

Fingerprint

Dive into the research topics of 'Spatial reasoning about string loops and holes in temporal asp'. Together they form a unique fingerprint.

Cite this