Description
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 fuzzy scheduling problems that are specified and read in from 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 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. The search will use a priority queue ordered by the values of the heuristic function that give a cost for each node in the search. The heuristic function for use in this assignment is defined below. The nodes in the 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. A goal state is an assignment of values to all variables that satisfies all the constraints.
The possible input (tasks and constraints) are as follows:
# binary constraints
constraint, ht1i before ht2i # t1 ends when or before t2 starts
constraint, ht1i after ht2i # t1 starts after or when t2 ends
constraint, ht1i same-day ht2i # t1 and t2 are scheduled on the same day
constraint, ht1i starts-at ht2i # t1 starts exactly when t2 ends
# hard domain constraints
domain, hti hdayi # t starts on given day at any time domain, hti htimei # t starts at given time on any day
domain, hti starts-before hdayi htimei # at or before given time domain, hti starts-after hdayi htimei # at or after given time domain, hti ends-before hdayi htimei # at or before given time domain, hti ends-after hdayi htimei # at or after given time domain, hti starts-in hdayi htimei-hdayi htimei # day-time range domain, hti ends-in hdayi htimei-hdayi htimei # day-time range domain, hti starts-before htimei # at or after time on any day domain, hti ends-before htimei # at or before time on any day domain, hti starts-after htimei # at or after time on any day domain, hti ends-after htimei # at or after time on any day
# tasks with name and duration task, hnamei hdurationi
cost(S) = Pcv∈C costcv ∗ δ((dv,tv),(dcv,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).
h(S) = Pcv∈C min(dv,tv)∈dom(v) costcv ∗ δ((dv,tv),(dcv,tcv))
Implementation
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, modify 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.
You should submit your fuzzyScheduler.py and any other files from AIPython needed to run your program (see below). The code in fuzzyScheduler.py will be run in the same directory as the AIPython files that you submit. Your program should read input from a file passed as an argument and print output to standard output.
Sample Input
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 tasks with two binary constraints and soft deadlines task, t1 3 task, t2 4
# two binary constraints constraint, t1 before t2 constraint, t1 same-day t2 # domain constraint domain, t2 mon # soft deadlines domain, t1 ends-by mon 3pm 10 domain, t2 ends-by mon 3pm 10
Sample Output
Print the output to standard output as a series of lines, giving the start day and time for each task (in the order the tasks were defined). If the problem has no solution, print ‘No solution’. When there are multiple optimal solutions, your program should produce one of them. Important: For auto-marking, make sure there are no extra spaces at the ends of lines, and no extra line at the end of the output. Set all display options in the AIPython code to 0.
The output corresponding to the above input is as follows:
t1:mon 9am t2:mon 12pm cost:10
Submission
• Submit all your files using the following command (this includes relevant AIPython code):
give cs9414 ass1 fuzzyScheduler.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
– A series of .txt files (at least three) that you have used as input files to test your system (each including comments to indicate the scenarios tested), and the corresponding .txt output files (call these input1.txt, output1.txt, input2.txt, output2.txt, etc.); submit only valid input test files
• When your files are submitted, a test will be done to ensure that your Python files run on the CSE machine (take note of any error messages printed out)
• 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
Assessment Criteria
• Correctness: Assessed on valid input tests as follows (where the input file can have any name, not just input1.txt, so read the file name from sys.argv[1]):
python3 fuzzyScheduler.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
