Source Code: Teacher's Timetable
TEACHERS.KSL Listing
/*
Timetable Example - Phil Vasey and Alan Westwood february 1999
==============================================================
Updated for WebFlex - May 2002 Clive Spenser and Alan Westwood
This example shows both forward and backward-chaining methods for
creating a timetable, though only forwards is made available over the web.
Description
-----------
Timetabling is a classical AI problem which involves both search and
strategy components. It has similar charactersistics to resource
allocation, scheduling and planning in general.
Running The Example
-------------------
The timetable example is presented as a choice between two contrasting
forward and backward chaining solutions. To run the example enter the
following goal at the command line:
?- run.
In this example we have some data that represents a number of
teachers, classes, subjects and periods. The teachers can teach
certain subjects and classes and have periods of freetime where they
are unavailable to teach.
Given this data, the basic requirement is to schedule a daily teaching
rota such that:
i. A teacher can only teach one class during a given period.
ii. A class is taught a subject once only per day.
You are encouraged to add a teacher or two to try and complete the rota.
This example compares two contrasting methods for implementing a
timetable given the above constraints. Both methods attempt to fill
the timetable as much as possible by suggesting teachers that can
teach a subject to a given class during a given period. This often
leads to a situation where there is a partially filled timetable,
where no more teachers and subjects can be given for the remaining
classes and periods without conflicts arising.
The two methods differ in how they deal with this deadlock.
Forward-chaining
----------------
This is the most efficient method, though there is no guarantee that
a potentially existing solution will always be found.
In this approach conflicts are resolved by either swapping previously
assigned teachers or previously assigned subjects. In this way
conflicts are resolved directly when they arise.
Backward-chaining
-----------------
This is less efficient than forward-chaining but if a solution exists
then this approach will eventually get there.
This methis is not made available over the web, but the code is here.
In this approach conflicts are resolved by blindly undoing the last
teacher and subject allocated, replacing them with some alternative,
and then attempting to fill out the rest of the timetable.
If this new allocation does not lead to a solution then this process
is repeated until all teacher - subject combinations have been
exhausted.
One problem with this method is that the very first teacher, class,
subject and period allocated may prevent a solution from being found,
yet this method will try all the possible solutions based on this
first allocation before rejecting it and trying an alternative.
Flex Technical Points
---------------------
The following flex technical points are demonstrated in this example:
1. The use of remember and forget to store values. It is important to
note that remembered facts are automatically forgotten on
backtracking.
2. The use of backward chaining relations in the forward chaining
process.
*/
% The first template outlines the following types of phrase:
% e.g. class alpha is taught maths by john during period 1
% class gamma is not taught french by mary during period 2
template taught
class ^ is taught ^ by ^ during period ^ ;
class ^ is not taught ^ by ^ during period ^ .
template not_yet_timetabled
class ^ needs timetabling for period ^ .
template potential_teacher
^ can potentially teach ^ to class ^ during period ^ .
template definite_teacher
^ can definitely teach ^ to class ^ during period ^ .
template bad_teacher
^ already teaches class ^ during ^ so cannot teach class ^ ;
^ does not teach any ^ during ^ so is available to teach class ^ .
template bad_subject
^ is already taught to ^ during ^ which conflicts with period ^ ;
^ is not taught to ^ at any other ^ so is available for period ^ .
action run ;
do restart
and new_teachers
and forward_chaining_timetable .
action show_teachers
do write( '<p>These are the teachers I know about: <//p>' )
and write( '<table border="1", cellpadding="8">' )
and write( '<th>Teacher<//th>' )
and write( '<th>Freetime<//th>' )
and write( '<th>Subjects<//th>' )
and write( '<th>Classes<//th>' )
and for every T is some instance of teacher
do write( '<tr>' )
and write_out( {{T},T`s freetime, T`s subjects, T`s classes } )
and write( '<//tr>' )
end for
and write( '<//table>' )
and write( '<//p>' ) .
action write_out( Set )
do for every member( X, Set )
do write_set( X )
end for .
action write_set( Set )
do write( '<td>' )
and for every member( Item, Set )
do write( Item ) and tab(1)
end for
and write( '<//td>' ) .
relation new_teachers
if show_teachers
and ask teacher_questions
and new_teacher_q is a new teacher whose subjects is subjects_q
and whose freetime is { freetime_q }
and whose classes is classes_q
and continue_q is yes
and !
and new_teachers .
relation new_teachers .
group teacher_questions
new_teacher_q, classes_q, subjects_q, freetime_q, continue_q .
frame teacher_questions_style
default caption is 'New Teacher' and
default columns is 2 and
default tablestyle is { bgcolor-'#ffffcc', cellpadding-4 } .
% First we set up the data for the timetable
% the following groups define the classes and periods
group class
class1, class2, class3, class4 .
group period
'1', '2', '3', '4', '5' .
group subjects
maths, physics, chemistry, english, geography, history .
% the following frame hierarchy defines the teachers, their subjects
% which classes they may teach and their freetime
frame teacher ;
default freetime is nothing and
default classes are every class .
instance john is a teacher ;
subjects are { maths and physics } and
freetime is { 3 } and
classes are { class1 and class2 }.
instance mary is a teacher ;
subjects are { french and maths } and
freetime is { 4 } and
classes are { class1 and class3 } .
instance matthew is a teacher ;
subjects are { history and geography } and
freetime is { 1 } and
classes are { class2 and class3 }.
instance helen is a teacher ;
subjects are { chemistry and physics } and
freetime is { 5 } and
classes are { class2 and class4 }.
instance henry is a teacher ;
subjects are { english and french } and
freetime is { 2 } and
classes are { class2 and class4 }.
question continue_q
Any more teachers to enter? ;
choose one of yes, no
because if there are no more new teachers I can go off and generate a timetable .
question new_teacher_q
Please enter the name of the new teacher;
input name
because I need to know the name of the new teacher .
question subjects_q
Please enter the subject for the new teacher;
choose some of subjects
because I need to know what subjects they can teach .
question freetime_q
Which period is free? ;
choose one of period
because I need to know which period they have free .
question classes_q
Which classes can be taught? ;
choose some of class
because I need to know which classes they can teach .
frame listbox ;
default rows is 6 .
frame subjects_q_style is a listbox .
frame freetime_q_style is a listbox .
frame classes_q_style is a listbox .
% the following templates enhance the readability of the rules and
% relations.
% the following relations are used by both the timetable methods
% generate a class and a period which are not already allocated
relation class C needs timetabling for period P
if C is some class
and P is some period
and class C is not taught anything by anybody during period P .
% generate any teacher and subject for a given class and period
% according to the intitial data specifications
relation T can potentially teach S to class C during period P
if T is an instance of teacher
whose freetime does not include P and
whose subjects include S and
whose classes include C .
% generate a teacher and subject for a given class and period
% and test that they do not conflict with any previous allocations
relation T can definitely teach S to class C during period P
if T can potentially teach S to class C during period P
and T does not teach any C1 during P so is available to teach class C
and S is not taught to C at any other P1 so is available for period P .
% identify potential teacher conflicts due to teachers already being
% allocated to some class for a given period
relation T already teaches class C1 during P so cannot teach class C
if class C1 is taught something by T during period P
and C1 is different from C .
% identify potential subject conflicts due to subjects already being
% taught to a given class during some period
relation S is already taught to C during P1 which conflicts with period P
if class C is taught S by somebody during period P1
and P1 is different from P .
% forward chaining method
% the following ruleset first continually fires the extend_timetable rule
% until it can no longer be fired. This rule is then removed from the
% timetable and forward chaining continues with the two conflict
% resolving rules only
ruleset forward_chaining_timetable
contains extend_timetable,
resolve_teacher_conflict,
resolve_subject_conflict ;
select rule using first come first served ;
update ruleset by removing any unsatisfied rules .
% this rule generates a valid class, period, teacher and subject
% and then allocates this to the current timetable
rule extend_timetable
if class C needs timetabling for period P
and T can definitely teach S to class C during period P
then remember that class C is taught S by T during period P .
% this rule resolves potential teacher conflicts
rule resolve_teacher_conflict
if class C needs timetabling for period P
and T can potentially teach S to class C during period P
and S is not taught to C at any other P1 so is available for period P
and T already teaches class C1 during P so cannot teach class C
and T1 can definitely teach S1 to class C1 during period P
and T1 is different from T
then forget that class C1 is taught something by T during period P
and remember that class C1 is taught S1 by T1 during period P
and remember that class C is taught S by T during period P .
% this rule resolves potential subject conflicts
rule resolve_subject_conflict
if class C needs timetabling for period P
and T can potentially teach S to class C during period P
and T does not teach any OldC during P so is available to teach class C
and S is already taught to C during P1 which conflicts with period P
and T1 can definitely teach S1 to class C during period P1
and S1 is different from S
then forget that class C is taught S by somebody during period P1
and remember that class C is taught S1 by T1 during period P1
and remember that class C is taught S by T during period P .
% backward chaining method
% in the following relation the remembering of the class, subject,
% teacher and period is undone when no more teachers can be proposed
% for the remaining classes and periods
relation backward_chain_timetable
if class C needs timetabling for period P
and !
and T can definitely teach S to class C during period P
and remember that class C is taught S by T during period P
and backward_chain_timetable .
relation backward_chain_timetable .
% this action initiates the backward chaining solution.
action backward_chaining_timetable ;
do backward_chain_timetable
and write( 'computed using backward-chaining ...' ) and nl
and print_table .
% this action initiates the forward chaining solution.
action forward_chaining_timetable ;
do invoke ruleset forward_chaining_timetable
and print_timetable .
question timetable_method
Which method ? ;
choose one of 'forward chaining solution',
'backward chaining solution' .
% these actions print several views of the final timetable solution
action print_timetable ;
do show_teachers
and write( '<table border="0">' )
and write( '<caption><h3>Timetable</h3><//caption>' )
and write( '<tr><td valign="TOP" width="33%">' )
and print_classes
and write( '<//td><td valign="TOP" width="33%">' )
and print_teachers
and write( '<//td><td valign="TOP" width="33%">' )
and print_subjects
and write( '<//td><//tr><//table><br><br>' ) .
action print_classes ;
do write( '<table cellpadding=10><caption>Timetable Displayed by Class<//caption>' )
and write( '<tr><th>Period<//th><th>Subject<//th><th>Teacher<//th><//tr>' )
and
for every C is some class
do write( '<tr><td colspan=3 align="center" bgcolor="#ffffcc">' ) and write( C ) and write( '<//td><//tr>' )
and for every P is some period
and class C is taught S by T during period P
do write( '<tr><td>' )
and write( P )
and write( '<//td><td>' )
and write( S )
and write( '<//td><td>' )
and write( T )
and write( '<//td><//tr>' )
end for
end for
and write( '<//table>' ) .
action print_teachers ;
do write( '<table cellpadding=10><caption>Timetable Displayed by Teacher<//caption>' )
and write( '<tr><th>Period<//th><th>Subject<//th><th>Class<//th><//tr>' )
and
for every T is some teacher
do write( '<tr><td colspan=3 align="center" bgcolor="#ffffcc">' ) and write( T ) and write( '<//td><//tr>' )
and for every P is some period
and class C is taught S by T during period P
do write( '<tr><td>' )
and write( P )
and write( '<//td><td>' )
and write( S )
and write( '<//td><td>' )
and write( C )
and write( '<//td><//tr>' )
end for
end for
and write( '<//table>' ) .
action print_subjects ;
do write( '<table cellpadding=10><caption>Timetable Displayed by Subject<//caption>' )
and write( '<tr><th>Period<//th><th>Class<//th><th>Teacher<//th><//tr>' )
and
for every S is some subjects
do write( '<tr><td colspan=3 align="center" bgcolor="#ffffcc">' ) and write( S ) and write( '<//td><//tr>' )
and for every P is some period
and class C is taught S by T during period P
do write( '<tr><td>' )
and write( P )
and write( '<//td><td>' )
and write( C )
and write( '<//td><td>' )
and write( T )
and write( '<//td><//tr>' )
end for
end for
and write( '<//td><//tr><//table>' ) .
