COMP9414: Artificial Intelligence
Assignment 1: Week Planner
Due Date: Week 6, Wednesday, July 6, 11:59 p.m.
Value: 15%
This assignment is motivated by the problem of scheduling all your personal activities in the
context of a busy week involving university studies, work, meals, travel, etc. There are both
constraints and preferences on the days and times of the activities. The constraints are “hard”
constraints (cannot be violated in any solution), while the preferences are “soft” constraints (can
be satisfied to more or less degree). Each soft constraint has a cost per hour giving the “penalty”
for failing to schedule the activity at the preferred time (we will not consider preferences for days).
The aim is to schedule all the activities so that the sum of all the costs is minimized, and all the
constraints are satisfied.
To be more precise, let us assume activities are to be scheduled on one of the days Sunday to
Saturday, starting at one of the times 7am to 7pm. Each activity will be given a fixed duration
(in hours) and occur only on one day (note that it is possible for an activity to finish after 7pm).
A constraint can refer to the start and end time of an activity or to the day of the activity, or can
be a relation between activities (such as ‘lecture’ must be before ‘tutorial’). A preference is that
an activity should start around a given time (ignoring the day). The full list of constraints and
preferences is defined below.
As an example, we might schedule a ‘dinner’ activity on Monday starting at 7pm for 1 hour – the
activity will therefore finish at 8pm. There is no need for your code to check whether the activity
finishes on the same day as it starts: you can assume this.
More technically, this assignment is an example of a constraint optimization problem, a problem
that has constraints like a standard Constraint Satisfaction Problem (CSP), but also a cost associated
with each solution. For this assignment, you will implement a greedy algorithm to find
optimal solutions to these scheduling problems that are specified in a file. However, unlike the
greedy search algorithm described in the lectures on search, this greedy algorithm has the property
that it is guaranteed to find an optimal solution for any such problem (if a solution exists).
You must use the AIPython code for constraint satisfaction and search to develop a greedy search
method that uses costs to guide the search, as in heuristic search (heuristic search is the same as
A∗
search where the path costs are all zero). The search will use a priority queue ordered by the
values of the heuristic function that gives a cost for each node in the search. The heuristic function
for use in this assignment is defined below. The nodes in this search are CSPs, i.e. each state is
a CSP with variables, domains and the same constraints (and a cost estimate). The transitions
in the state space implement domain splitting subject to arc consistency (the AIPython code
implements this). A goal state is an assignment of values to all variables that satisfies all the
constraints. The cost of a solution is the sum of the costs for the activities in the schedule.
A CSP for this assignment is a set of variables representing activities, binary constraints on pairs of
activities, and unary constraints (hard or soft) on activities. The domains are all the combinations
of days ‘sun’, ‘mon’, ‘tue’, ‘wed’, ‘thu’, ‘fri’ and ‘sat’, and times ‘7am’, ‘8am’, ‘9am’, ‘10am’, ‘11am’,
‘12pm’, ‘1pm’, ‘2pm’, ‘3pm’, ‘4pm’, ‘5pm’, ‘6pm’ and ‘7pm’. So the possible values are day time
pairs such as ‘mon 9am’. Each activity name is a string of letters or numbers (with no spaces).
The possible input (activities and constraints) are as follows:
# activities with name and duration
activity hnamei hdurationi
# binary constraints
constraint hA1i before hA2i # A1 ends when or before A2 starts
constraint hA1i after hA2i # A1 starts after or when A2 ends
constraint hA1i starts hA2i # A1 and A2 start at the same day and time
constraint hA1i ends hA2i # A1 and A2 end at the same day and time
constraint hA1i overlaps hA2i # A2 starts after A1 starts and not after A1 ends,
# and ends after A1 ends
constraint hA1i during hA2i # A1 starts after A2 starts and ends before A2 ends
constraint hA1i equals hA2i # A1 and A2 start and end at the same day and time
constraint hA1i same-day hA2i # A1 and A2 start and end on the same day
# hard domain constraints
domain hAi on hdi # A starts (and ends) on day d
domain hAi before hdi # A starts (and ends) before day d
domain hAi after hdi # A starts (and ends) after day d
domain hAi starts-before hti # A starts at or before time t on any day
domain hAi starts-after hti # A starts at or after time t on any day
domain hAi ends-before hti # A ends at or before time t on any day
domain hAi ends-after hti # A ends on or after time t on any day
# soft domain constraints
domain hAi around hti hcosti # cost per hour of not meeting time preference t
To define the cost of a solution (that may only partially satisfy the soft constraints), sum the
costs associated with violating the soft constraints over all activities. Let V be the set of variables
(representing activities) and C be the set of all soft constraints. Suppose such a constraint c with
time preference tc and cost costc applies to variable v, and let (dv, tv) be the start day and time
of v in a solution S. For example, costc might be 10 and (dv, tv) might be (mon, 5pm), while the
preferred time tc is 3pm; the cost of this variable assignment is 20 (2 hours difference × cost 10).
The time difference between t1 and t2 (converted to integer hours) is simply the absolute value of
t1 − t2, denoted |t1 − t2|. Then, where cv is the soft constraint applying to variable v:
cost(S) = P
cv∈C
costcv
∗ |tv − tcv
|
Heuristic
In this assignment, you will implement greedy search using a priority queue to order nodes based
on a heuristic function h. This function must take an arbitrary CSP and return an estimate of the
distance from any state S to a solution. So, in contrast to a solution, each variable v is associated
with a set of possible values (the current domain).
The heuristic estimates the cost of the best possible solution reachable from a given state S by
assuming each variable can be assigned the value that minimizes the cost of the soft constraint
applying to that variable. The heuristic function sums these minimal costs over the set of all
variables, similar to calculating the cost of a solution cost(S). Let S be a CSP with variables V
and let the domain of v, written dom(v), be a set of times for v (ignoring the day assigned to v).
Then, where the summation is over all soft constraints cv as above:
h(S) = P
cv∈C mintv∈dom(v) costcv ∗ |tv − tcv
|
Implementation
Put all your code in one Python file called weekPlanner.py. You may (in one or two cases) copy
code from AIPython to weekPlanner.py and modify that code, but do not copy large amounts of
AIPython code to your file. Instead, in preference, write classes in weekPlanner.py that extend
the AIPython classes (classes in green in the appendix below).
Use the Python code for generic search algorithms in searchGeneric.py. This code includes a
class Searcher with a method search() that implements depth-first search using a list (treated
as a stack) to solve any search problem (as defined in searchProblem.py). For this assignment,
extend the AStarSearcher class that extends Searcher and makes use of a priority queue to store
the frontier of the search. Order the nodes in the priority queue based on the cost of the nodes
calculated using the heuristic function, but making sure the path cost is always 0. Use this code
by passing the CSP problem created from the input into a searchProblem (sub)class to make a
search problem, then passing this search problem into a Searcher (sub)class that runs the search
when the search() method is called on this search problem.
Use the Python code in cspProblem.py, which defines a CSP with variables, domains and constraints.
Add costs to CSPs by extending this class to include a cost and a heuristic function h to
calculate the cost. Also use the code in cspConsistency.py. This code implements the transitions
in the state space necessary to solve the CSP. The code includes a class Search with AC from CSP
that calls a method for domain splitting. Every time a CSP problem is split, the resulting CSPs are
made arc consistent (if possible). Rather than extending this class, you may prefer to write a new
class Search with AC from Cost CSP that has the same methods but works with over constraint
optimization problems. This involves just adding costs into the relevant methods, and modifying
the constructor to calculate the cost by calculating h whenever a new CSP is created.
You should submit weekPlanner.py and all other files from AIPython needed to run your program.
The code in weekPlanner.py will be run in the same directory as the AIPython files that
you submit. Your program should read input from standard input (i.e. not hard-coded from
input1.txt) and print output to standard output (i.e. not hard-coded to output1.txt).
Sample Input
All input will be a sequence of lines defining the activities, binary constraints and domain constraints,
in that order. Comment lines (starting with a ‘#’ character) may also appear in the file,
and your program should be able to process and discard such lines. All input files can be assumed
to be of the correct format – there is no need for any error checking of the input file.
Below is an example of the input form and meaning. Note that you will have to submit at least
three input test files with your assignment. These test files should include one or more comments
to specify what scenario is being tested.
# two activities on the same day where time preference cannot be met
activity lecture 3
activity tutorial 1
# two binary constraints
constraint lecture before tutorial
constraint lecture same-day tutorial
# domain constraints
domain lecture on mon
domain lecture starts-before 1pm
domain lecture starts-after 1pm
domain tutorial around 3pm 10
Sample Output
Print the output using Python’s standard print function as a series of lines, giving the start day
and time for each activity (in the order the activities were defined) and the cost of the optimal
solution. If the problem has no solution, print ‘No solution’ (with capital ‘N’). When there are
multiple optimal solutions, your program should produce any one of them. Important: For
auto-marking, make sure there are no extra spaces at the ends of lines, and no extra empty lines
after the cost is printed (i.e. no additional newline characters after the one on the last line of the
solution showing the cost). This is the standard behaviour of the Python print function. Set all
display options in the AIPython code to 0.
The output corresponding to the above input is as follows:
lecture:mon 1pm
tutorial:mon 4pm
cost:10
Submission
• Submit all your files using the following command (this includes relevant AIPython code):
give cs9414 ass1 weekPlanner.py search*.py csp*.py display.py *.txt
• Your submission should include:
– Your .py source file(s) including any AIPython files needed to run your code
– At least three input files used to test your system (including comments to indicate the
scenarios tested), and the corresponding output files (call these input1.txt, output1.txt,
input2.txt, output2.txt, etc.); submit only correctly formatted input files
• When your files are submitted, a test will be done to ensure that your Python files run on
the CSE machine in the 9414 environment; take note of any error messages
• Check that your submission has been received using the command:
9414 classrun -check ass1
Assessment
Marks for this assignment are allocated as follows:
• Correctness (auto-marked): 10 marks
• Programming style: 5 marks
Late penalty: Your mark is reduced by 0.75 marks per day or part-day late for up to
5 calendar days after the due date, after which a mark of 0 is given.
Assessment Criteria
• Correctness: Assessed on valid input tests as follows, where input is read from a file redirected
to standard input, and output is redirected to standard output (not hard-coded file names):
python3 weekPlanner.py < input1.txt > output1.txt
• Programming style: Understandable class and variable names, easy to understand code,
good reuse of AIPython code, adequate comments, suitable test files
Plagiarism
Remember that ALL work submitted for this assignment must be your own work and no code
sharing or copying is allowed. You may use code from the Internet only with suitable attribution of
the source in your program. Do not use public code repositories on sites such as github –
make sure your code repository, if you use one, is private. All submitted assignments will
be run through plagiarism detection software to detect similarities to other submissions, including
from past years. Do not share your code with anyone both during and after the course has
finished. You should carefully read the UNSW policy on academic integrity and plagiarism
(linked from the course web page), noting, in particular, that collusion (working together on an
assignment, or sharing parts of assignment solutions) is a form of plagiarism.
DO NOT USE ANY CODE FROM CONTRACT CHEATING “ACADEMIES” OR
“TUTORING” SERVICES. THIS IS SERIOUS MISCONDUCT WITH A HEAVY
PENALTY UP TO AUTOMATIC FAILURE OF THE COURSE WITH 0 MARKS.
Appendix: AIPython Classes