WebKB and the Sisyphus-I problem

Philippe A. MARTIN

(e-mail: pm .@. phmartin dot info)


Griffith University, School of Information Technology

Work supported by the Defence Science And Technology Organisation (DSTO)



Copyright © Philippe A. Martin · Last update: 26 March 1999 · e-mail: pm .@. phmartin dot info   Next










Overview













Textual Interface














Ontology



 Something > (Organization  Person  Location  Process);

   Organization > Project  Research_group;

   Person > Employee (Smoker Non_smoker);
     Employee > (Manager  Secretary  Researcher);
       Researcher > (Group_head  Large_project_head  Simple_researcher);

   Location > Office;
     Office > Central_office (Small_office  Large_office);
       Central_office > (Small_central_office  Large_central_office);
       Small_office > (Small_central_office  Small_and_not_central_office); 
       Large_office > (Large_central_office  Large_and_not_central_office); 

   Process > (Hack Smoke);

   Agent (Process, Person);
   Project (Person, Project);
   In (Person, Office);
   Near (Location, Location);












Kinds of representations/searches


spec [Researcher:?]->(Smoker)->[Boolean:yes];
spec [Researcher:?]->(isSmoker);
spec Hacker_smoker: ?;
spec Not_hacker_not_smoker: ?;


spec [Researcher:?]<-(Agent)<-[Smoke] | set smokers;
spec [Researcher:?]<-(Agent)<-[Hack]  | set hackers;
spec [Researcher:?]- { (Agent)<-[Hack];
                       (Agent)<-[Smoke]; } | set hackers_smokers;
subtract "$smokers" "$hackers_smokers" | set smokers_non_hackers;
subtract "$hackers" "$hackers_smokers" | set hackers_non_smokers;   
    












Data Set



 Large_central_office: C5-117 C5-119;
 Large_and_not_central_office: C5-120 C5-121 C5-122 C5-123;
 Small_and_not_central_office: C5-113 C5-114 C5-115 C5-116;

 [Office:C5-113]->(Near)->[Office:C5-114]->(Near)->[Office:C5-115]->(Near)->
    [Office:C5-116]->(Near)->[Office:C5-117]->(Near)->[Office:C5-119]->(Near)->
    [Office:C5-120]->(Near)->[Office:C5-121]->(Near)->[Office:C5-122]->(Near)->
    [Office:C5-123];
 [Office:C5-113]<-(Near)<-[Office:C5-114]<-(Near)<-[Office:C5-115]<-(Near)<-
    [Office:C5-116]<-(Near)<-[Office:C5-117]<-(Near)<-[Office:C5-119]<-(Near)<-
    [Office:C5-120]<-(Near)<-[Office:C5-121]<-(Near)<-[Office:C5-122]<-(Near)<-
    [Office:C5-123];


 Project: Autonomous_Systems ASERTI BABYLON EULISP KRITON MLT RESPECT TUTOR2000;
 Group_head: Thomas_D;
 Secretary:  Monika_X  Ulrike_U;
 Manager:  Eva_I;
 Large_project_head: Hans_W  Joachim_I  Katharina_N;
 Simple_researcher:  Andy_L  Angi_W  Harry_C  Jurgen_L Marc_M Michael_T
                     Uwe_T  Werner_L;


 [Simple_researcher: Andy_L]-   { (Project)->[Project:TUTOR2000]; (Agent)<-[Smoke]; }; 
 [Simple_researcher: Angi_W]-   { (Project)->[Project:RESPECT];                     };
 [Simple_researcher: Harry_C]-  { (Project)->[Project:EULISP];    (Agent)<-[Hack];  };
 [Simple_researcher: Jurgen_L]- { (Project)->[Project:EULISP];    (Agent)<-[Hack];  };
 [Simple_researcher: Marc_M]-   { (Project)->[Project:KRITON];    (Agent)<-[Hack];  };
 [Simple_researcher: Michael_T]-{ (Project)->[Project:BABYLON];   (Agent)<-[Hack];  };
 [Simple_researcher: Uwe_T]-    { (Project)->[Project:Autonomous_Systems];
                                             (Agent)<-[Smoke];    (Agent)<-[Hack];  };
 [Simple_researcher: Werner_L]- { (Project)->[Project:RESPECT];   (Agent)<-[Hack];  };


 [Employee:Michael_T]->(In)->[Office:C5-122];
 [Employee:Monika_X]->(In)->[Office:C5-117];












Problem-Solving Functions



 void function main ()
 {
   check_if_already_placed_employees();
   if (possible_to_place_the_group_head())
   { if (possible_to_place_the_secretaries())
     { if (possible_to_place_the_managers())
       { if (possible_to_place_the_heads_of_large_projects())
         { print; print "----- Placing simple researchers";
           try_to_place_simple_researchers_by_pairs();
           try_to_place_remaining_employees_alone();
         }
       }
     }
   }
 }



 boolean function possible_to_place_the_secretaries()
 {
   print "----- Placing the secretaries";
   spec Secretary : ?  | set The_secretaries;
   for s in $The_secretaries
   { spec "[Employee:$s]->(In)->[Office]" | set office_of_this_employee;
     if ($office_of_this_employee == "")  
     { if (! possible_to_place_with_another_secretary($s))
       { if (! possible_to_place_nearest_group_head($s,Large_office))
         { if (! possible_to_place_nearest_group_head($s,Small_office))
           { print "The secretary $s cannot be placed close to
                 $Office_of_group_head, the office of head of group $The_group_head"; 
             return false;
           }
         }
       }
     }
   }
   return true;
 }


    

 boolean function possible_to_place_nearest_group_head (employee,kind_of_office)
 {
   set near_chain "->(Near)->";  //first, try very close offices
   while (true)                  //the loop progressively increases $near_chain
   { spec "[Office:?]$near_chain[Office:$Office_of_group_head]"
         | set offices_near_group_head;
     if ($offices_near_group_head == "") { break; } //no more office at such distance 
     for o in $offices_near_group_head
     { ? $kind_of_office : $o  | set office_is_suitable;
       if ($office_is_suitable)
       { spec "[Employee]->(In)->[Office:$o]" | set occupied_office;
         if ("$occupied_office" == "") //$o is empty
         { place_employee_in($employee,$o); return true; }
       }
     }
     set near_chain "$near_chain[Office]->(Near)->";
   }
   return false;
 }



 void function place_employee_in (employee, office)
 {
   name "#$employee$office" "[Employee: $employee]->(In)->[Office: $office]";
   print "$employee is placed in $office";
   subtractFrom Employees_to_place $employee;
 }












Strengths and Weaknesses


WWW-based + CG + shell-scripting language

  • WWW-based command interface -> easy testing/querying/updating

  • Procedural -> explicit and complete;   tedious;   long?

  • CG -> an object-oriented language would have been as good

  • Document linking/embedding facilities -> not exploited










ICCS'99 slides