Sufficient search space for spatial expert systems

This paper seeks the sufficient search space for the expert systems locating rectangular and arbitrary-shaped objects placed without rotation within a two-dimensional rectangular space. We found that for the layout of rectangular objects, the convex vertex set of feasible allocation space is a sufficient space to determine a feasible layout. We also found that for the layout of arbitrary-shaped objects, the boundary point set of the feasible allocation space is a sufficient space to determine a feasible layout. These two theorems are proved by developing two respective parallel translation algorithms. These theorems show that the search space can be significantly reduced in finding a feasible layout. Since these theorems were discovered while we were developing a spatial scheduling expert system, we have empirically tested the performance of the reduced search space with real world examples. According to the empirical test for the convex polygonal objects, the vertex set of feasible allocation space is satisfactory enough as a search space although the vertex set is not a sufficient space. (C) 2000 Elsevier Science Ltd. All rights reserved.