Automatic spatial layout planning system using a second-generation constraint logic programming language

摘要

Spatial layout planning generates two-dimensional layouts consisting of a configuration of rectangles. Our new method represents the rectangles as inconsistent sets of linear constraints. We then select the consistent sets from them by using a second-generation Constraint Logic Programming (CLP) language that employs a new search mechanism to handle disjunction efficiently. Because this is an NP-Complete class problem we introduce (1) domain knowledge to obtain feasible results, (2) some global constraints such as qualitative relation and capacity, and (3) a new mechanism that handles multiple disjunctions at the same time. Our approach is now being effectively applied to the layout of homes. In this paper, we use this example to explain our approach and describe our floor planning system, TG-FP/ 2, which can assist the customer by providing feasible plans. We also point out the advantages of our approach using a second-generation CLP language such as a declarative paradigm for easy description and efficiency for avoiding combinatorial explosion.