Information Technology Reference
In-Depth Information
Fig. 1.9
Partial scenes provided by the user and completed scenes produced by solving the induced
constraint satisfaction problem
and Frühwirth (
2003
)) and then the CSP is solved to give one or more instances of
the scene which differ from the one defined by the user, while still satisfying all
the required constraints. Full details of the implementation and our experimentation
with it are given in Colton (
2008c
).
In summary, the user is able to visually express constraints involving: (a) the
ranges of properties of rectangles, such as their co-ordinates, colours, dimensions,
etc., (b) co-linearity of points on rectangles, (c) propositional notions describing
pairs of rectangles, such as the constraint that if the width of rectangle 1 is greater
than that of rectangle 2, then its height should also be greater, (d) correlations be-
tween the properties of a rectangle, and (e) constraints specifying overlap or dis-
jointness of pairs of rectangles. The software then induces the constraints and asks
the user to check whether each one is there by design, or has risen co-incidentally, in
which case it can be deleted. At this stage, the user can also describe which aspects
of the scene are to be generated randomly, for instance they can specify that the X
co-ordinate of the rectangles should be chosen randomly from within a range. The
constraints are then interpreted as a CSP for the Sicstus CLPFD solver (Carlsson
et al.
1997
). The variables of the CSP are the co-ordinates, dimensions and colour
values of a set of rectangles, with the set size also specified by the user. Hence a so-
lution to the CSP represents a scene of rectangles, and if a random element has been
introduced, each scene will be different. To test the constraint solving approach,
we worked with an inspiring example of trees in a forest, which ultimately led to
the “PresidENTS gallery” as described below. The guiding scene and an example
generated scene are provided in Fig.
1.9
for two constructions.
Unfortunately, for scenes of ten or more elements, we found that the constraint
solver could take a prohibitively long time to find a perfect solution, and hence we
re-integrated the evolutionary approach so that the fitness function could be defined
as the number of singletons or pairs of scene elements adhering to the constraints.
This means that the visual specification of the scene constraints can be used with a
