Abstraction for Zooming-In to Unsolvability Reasons of Grid-Cell Problems
This work addresses the challenge of explaining unsolvability in grid-based problems for users of knowledge representation systems, though it appears incremental as it builds on prior abstraction concepts.
The paper tackles the problem of identifying reasons for unsolvability in grid-cell problems by developing a hierarchical abstraction method for Answer Set Programming, showing that it can automatically generate human-like abstractions that focus on relevant grid parts, with a user study confirming similarity between machine and human explanations.
Humans are capable of abstracting away irrelevant details when studying problems. This is especially noticeable for problems over grid-cells, as humans are able to disregard certain parts of the grid and focus on the key elements important for the problem. Recently, the notion of abstraction has been introduced for Answer Set Programming (ASP), a knowledge representation and reasoning paradigm widely used in problem solving, with the potential to understand the key elements of a program that play a role in finding a solution. The present paper takes this further and empowers abstraction to deal with structural aspects, and in particular with hierarchical abstraction over the domain. We focus on obtaining the reasons for unsolvability of problems on grids, and show the possibility to automatically achieve human-like abstractions that distinguish only the relevant part of the grid. A user study on abstract explanations confirms the similarity of the focus points in machine vs. human explanations and reaffirms the challenge of employing abstraction to obtain machine explanations.