Spatial-reasoning for Agents in Multiple Dimensions

Debasis Mitra (Department of Computer Sciences, Florida Institute of Technology, USA)

Gérard Ligozat (LIMSI/CNRS, Université de Paris-Sud ORSAY Cedex, France)

Abstract: Suppose a group of mobile agents situated in some Euclidean space does not have any idea on where they are exactly located within that space. However, they do have some notion about their relative positions with respect to each other. This problem may be formulated as a multi-dimensional point-based qualitative reasoning problem with disjunctive constraints. In this article we have developed a set of incremental algorithms for finding feasible positions of a new agent relative to the other existing agents (located in 1D, 2D and the generalized d-D dimensional space for d_=1), given some qualitative spatial constraints between the new one and the other agents. Our approach is a domain-theoretic one, similar to that used in the traditional constraint-based reasoning works (CSP). This approach differs from the algebraic approach - that is traditionally deployed in the spatio-temporal reasoning areas. We have also obtained some tractability results here for the full binary constraint satisfaction problem (rather than the incremental problem, which is polynomial) based on a notion of strong pre-convexity. The article also hints toward many future directions for this work.

Keywords: multi-agent reasoning, multi-dimensional spatial reasoning, qualitative reasoning, reasoning with disjunction

Categories: I.2.4