The International Association for Automation and Robotics in Construction
Publications / 1987 Proceedings of the 4th ISARC, Haifa, Israel
Layout Planning as a Consistent Labelling Optimization Problem
Over the past decade the consistent labelling problem has received considerable interest in Artificial Intelligence. In particular, machine vision, cryptography and theorem proving. Many algorithms have been developed for solving consistent labelling problems. A majority of these algorithms are based on heuristic search. Techniques such as constraint propagation and forward checking have been used to reduce search effort. Typically, the consistent labelling problem is formulated thus: there is a set of discrete variables, each with a finite set of values from which one is to be chosen. The task is to find labelling for all the variables such that a given set of constraints are simultaneously satisfied. The consistent labelling problem places few requirements on the nature of the variables or the constraints: the constraints can be either symbolic or numeric, monotonic or non-monotonic, continuous or discontinuous, linear or non-linear. In this paper we propose a heuristic search technique for handling consistent labelling problems with the added requirement of generating a consistent labelling that optimizes a set of objectives. This new type of formulation is applicable to a wide variety of engineering problems. In this paper we have chosen layout planning as our example domain. The layout problem is formulated thus: there is a set of objects that have to be placed in a designated area where, each object has a finite set of locations (within the designated area) that it can be assigned to. The task is to find unique locations for all the objects such that the given set of constraints and objectives are simultaneously satisfied.