Assignment 4

Write a Prolog scheduling program to assign people to tasks based on what types of tasks each person is capable of performing and how many hours that person can devote to tasks. It assumes that only one person performs each task and does not worry about the order of tasks (it assumes all tasks can be done independently of each other). Note that because of the ability in Prolog to ask Prolog to backtrack and find a different solution, your program will automatically find all possible solutions even though you didn't program a loop to do that or any of the backtracking code as you would have to do in most other languages.

The schedule program takes three arguments, a list of people, a list of tasks, and the resulting list of task assignments consisting of pairs of a person and his/her assigned task. For example, schedule([p1,p2,p3,p4], [t1,t2,t3,t4,t5,t6], RESULT). would return RESULT = [[p1, t1], [p2, t2], [p4, t3], [p4, t4], [p1, t5], [p3, t6]] given the database shown below. The program depends on Prolog having in its database two sets of functors: person and task. A person functor describes what types of tasks a person can do and how many hours they have free. For example, person(p1, [a,c,d], 12) says that person p1 is capable of performing tasks of types a, c, and d (but not b or any other task type) and has 12 hours to do tasks. A task functor describes the type of a task and how many hours it takes to perform that task. For example task(t1, a, 5) says that task t1 is of type a and takes 5 hours to perform.

Here is an example of a database of person and task functors (copy and paste this into a .prolog file to load into Prolog):

%%
%% person(ID, TASK_CAPABILITIES, AVAILABLE_HOURS)
%%
%%   How many hours each person has available and what classes of tasks they
%%   are capable of performing.
%%
person(p1, [c,a], 20).
person(p2, [b], 10).
person(p3, [a,b], 15).
person(p4, [c], 30).
%%
%% task(ID, TASK_CLASS, REQUIRED_HOURS)
%%
%%   How long each task requires and what class it falls under.
%%
task(t1, a, 5).
task(t2, b, 10).
task(t3, c, 15).
task(t4, c, 10).
task(t5, a, 15).
task(t6, b, 10).

Hints

Start by ignoring time constraints and just make sure that all tasks are only assigned to people who can perform them. You can recurse down the list of tasks to assign each task. Your first definition should be the stopping condition for schedule (what is the RESULT when the task list is an empty list?). Next worry about assigning a person to a single task. A person P can be assigned to a task T if P is a member of the People argument and there is a person functor in the database that describes P with his/her list of capabilities and there is a task functor in the database that describes T with its task type and that task type is a member of P's list of capabilities.

Only after you get the above code to work, then worry about keeping track of how much time each person has left for performing tasks (you are not allowed to change the database to do this). Instead, you will need a new variable to keep that information. I suggest making a helper functor that has the same arguments as schedule, but with one extra argument to keep a list of pairs of people IDs and how many hours that person has left in the current schedule. You can even name the helper functor with the same name, schedule, since the two functors will take a different number of arguments (4 vs. 3).

I found it helpful to use the select/4 functor from the lists library (add the line use_module(library(lists)). to your file). The select/4 functor takes an element and a list along with a replacement element and returns a new list with the replacement element substituted in place of the old element. For example, select(b, [a,b,c,d], e, R). would return R = [a, e, c, d]. This select/4 functor can be used to replace the old time left that a person has available for performing tasks with the new smaller time left after assigning that person to perform an additional task. For example, select([p1, _], [[p1, 15], [p2, 0]], [p1, 0], R). would return R = [[p1, 0], [p2, 0]].

Be sure to write full Design-by-Contract documentation for each unique functor (only one contract needed per functor even if a functor has multiple clauses).

My solution takes 27 lines of code, not including comments or the database of person and task functors. If your solution starts to require considerably more code, please come see me or our TA as you are likely doing too much or have the wrong approach.

Put your code into a file named schedule.prolog. Put the sample database above into a file named taskdb1.prolog. Create you own example of a task database similar to taskdb1 and put it in taskdb2.prolog. Create an ASCII text file named transcript1.txt that contains a transcript of your code running on taskdb1 and another text file named transcript2.txt showing your code running on taskdb2 (just copy and past from your SWI Prolog window into a text editor window). Finally zip together schedule.prolog, taskdb1.prolog, taskdb2.prolog, transcript1.prolog, and transcript2.prolog into a file named a1.zip. Submit your solution by uploading a4.zip to Laulima under the Assignments tab.