Author name cluster

Heshan Du

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

JAIR Journal 2023 Journal Article

A Logic of East and West

Heshan Du
Natasha Alechina
Amin Farjudian
Brian Logan
Can Zhou
Anthony G. Cohn

We propose a logic of east and west (LEW ) for points in 1D Euclidean space. It formalises primitive direction relations: east (E), west (W) and indeterminate east/west (Iew). It has a parameter τ ∈ N>1, which is referred to as the level of indeterminacy in directions. For every τ ∈ N>1, we provide a sound and complete axiomatisation of LEW, and prove that its satisfiability problem is NP-complete. In addition, we show that the finite axiomatisability of LEW depends on τ: if τ = 2 or τ = 3, then there exists a finite sound and complete axiomatisation; if τ > 3, then the logic is not finitely axiomatisable. LEW can be easily extended to higher-dimensional Euclidean spaces. Extending LEW to 2D Euclidean space makes it suitable for reasoning about not perfectly aligned representations of the same spatial objects in different datasets, for example, in crowd-sourced digital maps.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

A Logic of Directions

Heshan Du
Natasha Alechina
Anthony G. Cohn

We propose a logic of directions for points (LD) over 2D Euclidean space, which formalises primary direction relations east (E), west (W), and indeterminate east/west (Iew), north (N), south (S) and indeterminate north/south (Ins). We provide a sound and complete axiomatisation of it, and prove that its satisfiability problem is NP-complete.

PDF Details DOI

AAAI Conference 2019 Conference Paper

Qualitative Spatial Logic over 2D Euclidean Spaces Is Not Finitely Axiomatisable

Heshan Du
Natasha Alechina

Several qualitative spatial logics used in reasoning about geospatial data have a sound and complete axiomatisation over metric spaces. It has been open whether the same axiomatisation is also sound and complete for 2D Euclidean spaces. We answer this question negatively by showing that the axiomatisations presented in (Du et al. 2013; Du and Alechina 2016) are not complete for 2D Euclidean spaces and, moreover, the logics are not finitely axiomatisable.

PDF Details

IJCAI Conference 2018 Conference Paper

Automated Reasoning for City Infrastructure Maintenance Decision Support

Lijun Wei
Derek R. Magee
Vania Dimitrova
Barry Clarke
Heshan Du
Quratul-Ain Mahesar
Kareem Al Ammari
Anthony G. Cohn

We present an interactive decision support system for assisting city infrastructure inter-asset management. It combines real-time site specific data retrieval, a knowledge base co-created with domain experts and an inference engine capable of predicting potential consequences and risks resulting from the available data and knowledge. The system can give explanations of each consequence, cope with incomplete and uncertain data by making assumptions about what might be the worst case scenario, and making suggestions for further investigation. This demo presents multiple real-world scenarios, and demonstrates how modifying assumptions (parameter values) can lead to different consequences.

PDF Details

JAIR Journal 2016 Journal Article

Qualitative Spatial Logics for Buffered Geometries

Heshan Du
Natasha Alechina

This paper describes a series of new qualitative spatial logics for checking consistency of sameAs and partOf matches between spatial objects from different geospatial datasets, especially from crowd-sourced datasets. Since geometries in crowd-sourced data are usually not very accurate or precise, we buffer geometries by a margin of error or a level of tolerance, and define spatial relations for buffered geometries. The spatial logics formalize the notions of `buffered equal' (intuitively corresponding to `possibly sameAs'), `buffered part of' (`possibly partOf'), `near' (`possibly connected') and `far' (`definitely disconnected'). A sound and complete axiomatisation of each logic is provided with respect to models based on metric spaces. For each of the logics, the satisfiability problem is shown to be NP-complete. Finally, we briefly describe how the logics are used in a system for generating and debugging matches between spatial objects, and report positive experimental evaluation results for the system.

PDF Details DOI

ECAI Conference 2014 Conference Paper

A Logic of Part and Whole for Buffered Geometries

Heshan Du
Natasha Alechina

We propose a new qualitative spatial logic for reasoning about part-whole relations between geometries (sets of points) represented in different geospatial datasets, in particular crowd-sourced datasets. Since geometries in crowd-sourced data can be less inaccurate or precise, we buffer geometries by a margin of error or level of tolerance σ , and define part-whole relation for buffered geometries. The relations between geometries considered in the logic are: buffered part of (BPT), Near and Far. We provide a sound and complete axiomatisation of the logic with respect to metric models, and show that its satisfiability problem is NP-complete.

Details