Navigation within a structured search space in layout problems

HeGeL-2 is a heuristic-based layout generator equipped with a nonserial dynamic programming algorithm. HeGeL-2 finds optimal solutions to plan-layout design (PLD) problems which are defined as problems that involve the allocation of a nontrivial number (ten or more) of design units in one application. The search strategy HeGeL-2 uses is similar in some respects and dissimilar in others to human search behavior, which has been simulated in an earlier version of HeGeL-2. These similarities include constraint relaxing strategies common to both versions. Dissimilarities concern claims of optimality and 'goodness' of solutions measured by an objective function based on <I>soft </I>constraints. In this paper, the general problem of navigation in a search space for layout problems is discussed in the context of a general-purpose formalism. Through this formalism several layout generators, including LOOS, WRIGHT, and HeGeL-2, are described.