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>' ) .
Web design by Solanum
Copyright © 2014 Logic Programming Associates Ltd
All rights reserved