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

Kaitain,

I've thought some more about your second set of requirements and I think
it can still be done. It's like a classic AI planning problem, ensuring
that the current state doesn't get 'clobbered' later. Insofar as your
expanded reqirements can be met at all (you have asked for two b's and
two c's in the first five elements, then you also want two a's, which
there isn't room for), it is still possible to meet them by working
forward one element at a time.  Probability is taken care of, if the
program first generates a random solution but will generate all possible
solutions if backtracking is forced. All possible solutions are then
equally likely. Try this:

/* Simply add elements one at a time. The next element will
   be chosen in such a way that the list is always legal */

legal_list(Nwanted,[]) :- Nwanted=<0, !.

legal_list(Nwanted,ResultingList) :-
	N1 is Nwanted-1,
	legal_list(N1,L1),
	next_element(L1,E),
	append(L1,[E],ResultingList). 

/* The next element might be the promotion or destruction of 
   an existing event or the creation of a new event. A priori
   they are equally likely but if one fails (because it is
   disallowed by the rules), backtrack and try another. */

next_element(ExistingList,PossibleElement) :-
	any_of([create,promote,destroy],Event),
	next_element(Event,ExistingList,PossibleElement).

next_element(promote,ExistingList,[UID,Type,promoted]) :-
	bagof(T,allowed_type(ExistingList,promote,T),AllowedTypes),
	any_of(ExistingList,[UID,Type,created]),
	\+memberchk([UID,Type,destroyed],ExistingList),
	memberchk(Type,AllowedTypes).

next_element(destroy,ExistingList,[UID,Type,destroyed]) :-
	bagof(T,allowed_type(ExistingList,destroy,T),AllowedTypes),
	any_of(ExistingList,[UID,Type,created]),
	\+memberchk([UID,Type,destroyed],ExistingList),
	memberchk(Type,AllowedTypes).

next_element(create,ExistingList,[UID,Type,created]) :-
	bagof(T,allowed_type(ExistingList,create,T),AllowedTypes),
	gensym('Event-',UID),
	any_of(AllowedTypes,Type).

any_of(List,X) :-
	random_permutation(List,ScrambledList),
	member(X,ScrambledList).

/* This is where the rules get applied */

% There must be at least two 'a's created in the first five elements
% At least one of the 'a's created in the first five elements must be destroyed somwhere in elements 6..10
% An 'e' cannot occur until there has been at least one 'c'
% A 'd' cannot occur until both 'a' and 'b' have occurred
% After both 'c' and 'e' have occurred, 'd' can no longer occur at all
% A 'd' cannot occur in elements 5..7

allowed_type(L,Type,a) :-
	length(L,3),
	\+memberchk([_,a,created],L),
	!,
	Type=create.

allowed_type(L,Type,a) :-
	length(L,4),
	member([UID1,a,created],L),
	\+((member([UID2,a,created],L),UID2\=UID1)),
	!,
	Type=create.

allowed_type(L,Type,a) :-
	length(L,9),
	\+((
		nth1(Nd,L,[U,a,destroyed]),
		between(6,9,Nd),
		nth1(Nc,L,[U,created,Nc]),
		between(1,5,Nc)
	 )),
	!,
	Type=destroy.

allowed_type(L,destroy,a) :-
	length(L,Length),
	(Length=<4 -> \+memberchk([_,a,destroyed],L) ; true).

allowed_type(_,create,a).
allowed_type(_,promote,a).

allowed_type(_,_,b).
allowed_type(_,_,c).

allowed_type(L,_,d) :-
	memberchk([_,a,_],L),
	memberchk([_,b,_],L),
	\+((memberchk([_,c,_],L),memberchk([_,e,_],L))),
	length(L,N),
	\+between(4,6,N).

allowed_type(L,_,e) :-
	memberchk([_,c,_],L).




On 14/03/2014 08:30, Kaitain Jones wrote:
> I've been working on something in the last week for which I assumed Prolog
> would be a good tool, but I'm slightly on the fence about its suitability
> now.
>
> Essentially I am trying to use Prolog to generate a single, semi-random
> sequence of entries that needs to meet some loose criteria only. For the
> sake of simplicity, let's assume I want to create a list of atoms. For each
> atom considered as a candidate to be added to the end of a list under
> construction, there are some constraints on which ones are legal. Let's say
> (arbitrarily) that
> 1. I can add an a,b or c as a new entry at any time.
> 2. I can add a new entry d if a and b are already in the list (at least one
> of each).
> 3. I can add an e if there is already at least one c.
> 4. If there is both an entry c and an entry e in the list then I can no
> longer add d.
> These sorts of things (waves hand). Details are not important.
>
> Using these kinds of addition rules, I want to ask the system to generate
> me a (semi-) random sequence of a given length whose only requirements are
> that each entry added must obey all given rules at the time of its addition
> to the sequence. I don't require an enumeration of all legal sequences; I
> just want one each time I execute the program. So
> [a,b,a,b,a,b,c]
> ...is legal (assuming I asked for a list of length 7), as is
> [a,b,c,d,e,a,b]
> ....but
> [a,b,c,d,e,b,d]
> ...is not (the final d violates rule 4).
>
> I might then add some further constraints: I'd like the system to create
> such a sequence, but with some additional macro-level requirements:
>
> * There must be 2 bs in the first five entries. (This would rule out the
> second list above, but the first would be accepted.)
> * There cannot be any ds between entries five and seven inclusive.
> etc.
>
> I have built such a program, but it feels a little inelegant and slightly
> arbitrary, and although Prolog helps make the writing of the
> rules/constraints easy, I feel a bit uncertain that my program is
> particularly idiomatic. I can't enumerate all solution lists and then pick
> one at random, because the state space is too large. Also, I can't see how
> it's easy to build a list with a mixture of bound and unbound members and
> use that to help guide the search efficiently, because I don't always know
> precisely which members should be bound, and the possible combinations of
> such semi-bound lists can themselves be very large in number.
>
> What I'm doing right now is creating the list a few entries at a time (e.g.
> five at a time). For each added member, I consider the list of all new
> entry candidates that would be legal using the universal rules, and pick
> one of these at random to add to the end of the list. When five have been
> added, I apply my extra constraint checks to see if these all pass. If they
> do, I move on to adding the next batch of five. If not, I try again. (Why
> five? That's the arbitrary part. Perhaps I'd be better off applying those
> constraints for every single entry added. But the macro constraints don't
> always apply to individual entries, but rather to the list as a whole, or
> subsequences of it.)
>
> This current approach does work, certainly for small-ish sequences (20-30)
> and a set of perhaps a dozen general rules and some mild macro-level list
> constraints. But I'm not sure that this is the best or most efficient way
> to approach the problem. It is really a hybrid imperative-declarative
> design (the control of the batched search in chunks of five is controlled
> by a C algorithm that calls into Prolog to execute the search itself). I
> would prefer a more idiomatic Prolog approach, but perhaps the language
> simply isn't especially well-suited to this task? (It is first and foremost
> designed to provide a total enumeration of solution state space.)
>
> I would welcome any thoughts/suggestions.
>
> KJ
> -------------- next part --------------
> HTML attachment scrubbed and removed
> _______________________________________________
> SWI-Prolog mailing list
> [email protected]
> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>