Re: Is Prolog a good language for generating semi-random, constrained solutions?

On 03/14/2014 11:59 PM, Kaitain Jones wrote:
> Hi Bob,
>
> Thanks for your thoughtful reply. I did like the elegance of the approach
> that insists that as opportunities are running out to fulfill a quota
> requirement, the list must be kept on its quota target with the very next
> member added. However, there are some potential problems with this:
>
> 1. This approach is likely to deliver statistically skewed results. For
> instance, given my arbitrary ruleset, one would expect to see
>
> [b,b,a,a,a...]
>
> as frequently as
>
> [a,a,a,b,b...]
>
> However, with your suggested rules, I think I'm right in expecting to see
> the latter more frequently: there will be a disproportionate number of
> solutions that have the constraint satisfied with the b entries occupying
> precisely the final two spots.
>
> 2. Clashes of rules. Imagine I add another constraint that says that the
> first five members must ALSO contain two c entries (on top of the two b
> requirement). I think (?) it would be difficult to employ the same approach
> as for the b quota rules, because the system cannot do both things with the
> 4th and 5th members.
>
> 3. This is more a problem with extending the constraints in the manner I'm
> anticipating rather than a problem with the specific constraints I listed.
> What I am anticipating is that certain rules will need to refer to earlier
> entries when referencing later ones, and that the approach of confining
> constraints to individual, encapsulated rules would not facilitate this.
>
> Example:
>
> Let's say that every entry added is not merely an atom, but a tuple
> containing a unique ID, an atom representing the type, and a third field
> representing an event type. Each entry in the list can therefore be
> regarded as a piece of event data pertaining to that unique ID. The first
> time a UID is encountered, the event must be "created", but thereafter it
> will be something else.
>
> Example:
>
> [[0,a,created],[1,a,created],[2,c,created],[3,b,created],[4,d,created],[1,a,destroyed],[0,a,promoted],[3,b,destroyed]......]
>
> So five entities are created, one of those existing entities is promoted,
> and two of those existing entities are destroyed.
>
> Imagine that I want to impose the following constraint:
>
> "At least two entities of type a must be created in the first five list
> entries. During the second five list entries, at least one of this pair of
> type a entities must be destroyed."
>
> It doesn't seem possible to impose these kinds of linked constraints using
> the approach you suggested, because one cannot share bound variables
> between individual rules. Which is a shame, as your suggestion would surely
> have facilitated a more efficient construction (i.e. there would never have
> been a fourth entry which helped build an invalid list.) I am trying to
> think of a way to achieve that kind of tight, on-the-fly constraint rather
> than building a speculative list in chunks and then testing it
> retrospectively, but perhaps this simply can't be done given what my
> requirements are.

My initial thought was to express the problem as a list of variables
with (clp(fd)) constraints and perform random labelling. I think that is
a bit too optimistic, mostly because it the translation from your rules
to clp(fd) will be non-trivial. Still, it might make sense to keep that
model in mind.

What is this model? The idea would be to pick a random remaining
variable, inspect its domain and assign it a random member of its
domain. Next, constraint propagation will reduce the domains of the
remaining variables and we resume the labeling process until the list is
ground.  Not sure that will produce statistically the correct result and,
if this is not the case, whether this is a real problem.

Of course, instead of using clp(fd), we can define our own domain
representation and our own propagation.  That might allow to maintain
the rules in their natural format.

We can continue along these lines by using a clever labeling order.
Notable, if we see `there must be N X-events in the range S-E', we
probably need to do these first.  So, for the 2 bs in the first 5,
first take two bs.  If you need two create events, first place these.
The allocate the corresponding destroy events, etc.

This is not going to be an easy task.  Still, I think that Prolog has
some advantages here.  It should allow you to define a DSL for your
rules relatively easily and its natural backtracking will resolve
conflicts in the allocation easily.

Hope this helps.

	Cheers --- Jan