### Re: constraint satisfaction problem: creating a duty schedule

Thomas Russ <tar <at> ISI.EDU>

2007-04-20 17:59:11 GMT

On Apr 19, 2007, at 4:54 AM, Kambiz Darabi wrote:
> Hello,
>
> I have a problem which I would like to solve with PL.
>
> A group of crossing guards have to secure 3 different locations near a
> school. They have to do this 5 days a week in the morning and at noon.
>
> Some of them can only work on specific days and some would 'prefer'
> some days, but would be able to work also on 'non-preferred' days.
> Some can only work in the morning, others only at noon. Some will work
> only on one, others on two or three different (but not specific) days.
>
> I only got this far to define the location, day, and time concepts.
>
> ;; ----------------------------
>
> (in-module "CROSSING-GUARD-SCHEDULE")
> (clear-module "CROSSING-GUARD-SCHEDULE")
>
> (reset-features)
>
> (in-dialect :KIF)
>
> (propagate-constraints)
>
> (defconcept day (?d)
> :<=> (member-of ?d (setof monday
> tuesday
> wednesday
> thursday
> friday)))
> (defconcept location (?l)
> :<=> (member-of ?l (setof crossing1
> crossing2
> crossing3)))
>
> (defconcept time (?t)
> :<=> (member-of ?t (setof morning
> noon)))
>
> ;; ----------------------------
>
> As every combination of day, location, and time defines one 'duty' for
> which a guard can be scheduled, I tried to somehow combine them. I
> have tried numerous variations of relations playing with forall (and
> exists) like:
>
> (defrelation duty ((?l location) (?d day) (?t time))
> :<<= (forall ?l ?d ?t (location ?l)
> (day ?d)
> (time ?t)))
Note: The FORALL clause above is syntactically mal-formed. But the
solution I will suggest lies in a slightly different direction.
>
> but to no avail.
>
> 1) is the problem solvable at all?
Your general problem should be solvable, but not entirely within
PowerLoom. PowerLoom can do propagation of logical constraints, but
it doesn't have a particular constraint solver built in to it. So,
you will have to write some additional code to solve the problem with
PowerLoom.
>
> 2) how can I create the combination of the instances of the three
> concepts?
You were started on the right track, and need only a little bit more
development to get there. If I understand correctly, what you want
to have is a set of objects of type "Duty" that are defined by the
combinations of location, day, time.
One modeling solution to this is to use logic functions rather than
relations. With relations, you have tuples, but they are not that
convenient for manipulations. With functions, we can associate the
components with another object, which will be a "skolem" that is then
an instance about which you can make assertions.
For example:
(defconcept Duty) ;; Our concept of a duty shift.
(deffunction duty-fn ((?l location) (?d day) (?t time)) :-> (?d
Duty))
Now, you can create Duty instances as the value of a function of
location x day x time:
(retrieve all (duty-fn crossing1 tuesday morning ?d))
will return a result with a single skolem object. You can make
various assertions
about this object, using functional notation to refer to it. Let's
assume there is
also something like:
(defrelation assign ((?g guard) (?d duty)))
(assert (assign guard-1 (duty-fn crossing1 tuesday morning)))
(assert (assign guard-1 (duty-fn crossing1 friday morning)))
(assert (assign guard-2 (duty-fn crossing1 friday noon)))
If you want to look for unassigned times, you can write queries using
the fail operator
(retrieve all (and (location ?l) (day ?d) (time ?t)
(fail (exists (?g) (assign ?g (duty-fn ?l ?d ?
t)))))
>
> 3) do you have any hint on which direction to take for solving the
> problem?
The above can get you started with some of the infrastructure. The
process of trying out various approaches will need some additional code.
If you want to create (in advance) skolems for all combinations of
location, day and time, you might find the ASSERT-FROM-QUERY function
to be useful.
If you want to be able to explore potential alternate scheduling
attempts, then using the MODULE/CONTEXT mechanism can be handy. You
can establish separate reasoning contexts sharing the same common
parent module and make the assignments in each one.
I would have to think a little bit more carefully about the
constraints and preferences issue, but if you can encode the
constraints as logic rules, then you may be able to detect
conflicts. (Unfortunately, getting information about the causes of
such constraint violations is something we haven't had time to
develop more fully).
>
>
> Many many thanks
>
>
> Kambiz
> _______________________________________________
> powerloom-forum mailing list
> powerloom-forum <at> isi.edu
> http://mailman.isi.edu/mailman/listinfo/powerloom-forum