JUCS - Journal of Universal Computer Science 8(8): 774-791, doi: 10.3217/jucs-008-08-0774
Spatial-reasoning for Agents in Multiple Dimensions
expand article infoDebasis Mitra, Gérard Ligozat§
‡ Department of Computer Sciences, Florida Institute of Technology, Melbourne, Florida, United States of America§ LIMSI, Universite Paris XI, Paris, France
Open Access
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-dimensional spatial reasoning, reasoning with disjunction, qualitative reasoning, multi-agent reasoning