Title: Advancing the Use of Sparse Knowledge for Qualitative Models and Simulations
Abstract: Computer simulations are used on a large scale, but it is often the case that we lack precise numerical data and have instead sparse or incomplete descriptions of systems. Qualitative reasoning is used to address the gap between the infinite complexity of the world and our partial knowledge of it, which defies traditional numerical modelling and generalises the reasoning to the qualitative behaviour capturing the key aspects. Modelling and simulation in qualitative setups have been successfully used in a variety of fields, such as physics, ecology, engineering, robotics and education. However, performing qualitative simulations is a computationally expensive task, and there is always the question of how to maximise the information inferable from the available sparse knowledge.
In this presentation I will talk about my master thesis, where my supervisors and I take a theoretical approach to this problem, and make the following contributions. First, we develop a new partial axiomatisation that is better suited for simulation analysis. Second, using this axiomatisation, we identify inconsistencies of state graphs resulted from the use of sparse knowledge, and suggest solutions for these. Third, we introduce the problem of early inconsistency detection, requiring non-trivial inequality reasoning in the context of partial knowledge. Fourth, we formulate a generalisation of this problem, called the "combining changes problem," and analyse it from a complexity theoretic perspective, proving it to be polynomial under reasonable assumptions. Fifth, we derive a practical procedure for the early identification of contradictory relations, making qualitative reasoning simulations more efficient by reducing the number of eligible compound terminations early. As a general result, our work demonstrates the value of a theoretical approach to this problem when grounded by practical examples, realised using Garp3, clarifying the concepts and problems, and motivating the methods we developed.
