Adaptive Exploration of Locally Satisfiable Proposals for Design Layout

We present a new approach for rule-based design layout problems, examples of which include automated graphic design, furniture arrangement and synthesizing virtual worlds. We formulate this as a weighted constraint-satisfaction problem which is high-dimensional and requires non-convex optimization. We use a hyper-graph to represent a set of objects and the design rules applied to them. Although inference in graphs with higher order edges is computationally expensive, we present a hybrid solution-space exploration algorithm that adaptively represents higher order relations compactly. We exploit the fact that for many types of rules, satisfiable assignments can be found efficiently. In other words, these rules are locally satisfiable. Therefore we can sample from the known partial probability distribution function for each rule. Experimental results demonstrate that this sampling technique reduces the number of samples required by other algorithms by orders of magnitude. We demonstrate usage via different layout examples such as superimposing textual and visual elements on photographs. Our adaptive search algorithm is applicable to other optimization problems and generalizes many previously proposed local search based algorithms like graph cuts and iterated conditional modes.