cdsm@doc.ic.ac.uk (Chris Moss) (06/04/86)
>From: VERACSD@USC-ISI.ARPA >Subject: Benchmarking KBES-Toools > >I have come across some recent benchmarks from NASA (U.S. >Gov't MEMORANDUM from the FM7/AI Section, April 3, 1986) >which compared various KBES tools' (ART, OP, KEE & CLIPS) >times for solving the MONKEY-AND-BANANA problem. (This >toy problem is explained in detail along with OPS source >in Brownston et. al.'s "Programming Expert Systems in OPS5".) > >Although the benchmarks include backward-chaining solutions >to the problem in both KEE and ART (along with forward >chaining counterparts), there is no PROLOG implementation >in the comparison. I am very interested in a PROLOG >comparison, and am in the process of implementing one. Here is a Prolog solution. It uses much the same logic as the Brownston book (i.e. forward chaining), though I've only used "working memory" (the State variables) for states not goals - this makes it much easier to incorporate subgoals, which is the reason there are basically 6 rules (equivalent to 14 Horn Clauses) rather than 26 in the OPS5 version (though there are also 21 subsidiary clauses). I've also removed the "state independent assertions" (light & heavy) from state, though they could be there. The Prolog solution takes 92 lines compared with 201 (non-comment) lines for OPS5. This includes the code for "modify" etc. which is not included in the OPS5 total. There are various packages on the market which are implemented in Prolog but provide the same kind of facilities. > (By the way, the time to beat is 1.2 secs. for a >forward-chaining implementation using ART on a 3640 with >4MB main-memory.) That's pretty easy. The code below runs in about 0.32 secs on a VAX 750 using the CProlog interpreter. With a compiler on the DEC 20 you should be able to do an order of magnitude faster (most of the time is probably spent in i/o anyway). I've included the timing routines at the end. You may have to alter the "cputime" routine to fit your local Prolog system. Chris Moss Imperial College, London. cdsm@doc.ic.ac.uk or cdsm@icdoc.uucp /* monkey & bananas problem from Brownston & al: Programming Expert Systems in OPS5 (Addison-Wesley 1985) */ test(X) :- problem(X, Goal, State), (goal(Goal,State,NewS) -> writeline(['Congratulations, the goals are satisfied']) ; writeline(['Impossible, the goal',Goal,'cannot be achieved']),fail). problem(general, hold(bananas), [monkey([7,7],couch,blanket), obj(bananas,[9,9],ceiling), obj(couch,[7,7],floor), obj(ladder,[4,3],floor), obj(blanket,[7,7],_)]). light(bananas). light(ladder). light(blanket). heavy(couch). /* goal(X,State,New) :- writeline([goal,X,in,State]), fail. */ goal(hold(Object), State,NewS) :- hold(Object, State) -> NewS=State ; light(Object) -> approach(Object, State, State2), goal(hold(nil), State2,State3), modify(hold(Object),State3,State4), modify(on(Object,monkey),State4,NewS), writeline([monkey,grabs,Object]) ; Object=nil, hold(Obj,State), modify(hold(nil),State,State2), modify(on(Obj,floor),State2,NewS), writeline([monkey,drops,Obj]). goal(at(Loc), State, NewS) :- at(Loc,State) -> NewS=State ; goal(on(floor), State, State2), goal(hold(nil), State2, State3), modify(at(Loc),State3,NewS), writeline([monkey,walks,to,Loc]). goal(at(Object,Loc), State,NewS) :- at(Object,Loc,State) -> NewS=State ; goal(hold(Object),State,State2), goal(on(floor),State2,State3), modify(at(Loc),State3,State4), modify(at(Object,Loc),State4,NewS), writeline([monkey,carries,Object,to,Loc]). goal(on(Object), State, NewS) :- ison(Object, State) -> NewS=State ; Object=floor -> modify(on(floor),State,NewS), writeline([monkey,jumps,to,floor]) ; object(Object), goal(hold(nil),State,State2), at(Object, Loc, State2), goal(at(Loc),State2,State3), modify(on(Obj),State3,NewS), writeline([monkey,climbs,on,Object]). /* goal(X,State,New) :- writeline(['** fail goal',X,in,State]), fail. */ approach(Object, State, NewS) :- ison(Object,ceiling,State) -> at(Object,Loc,State), goal(at(ladder,Loc),State,State2), goal(on(ladder), State2, NewS) ; at(Object,Loc,State), goal(at(Loc),State,NewS)./* window : support routines */ at(Loc,State) :- inn(monkey(Loc,_,_),State). at(Object,Loc,State) :- inn(obj(Object,Loc,_),State). hold(Object,State) :- inn(monkey(_,_,Object),State). ison(On,State) :- inn(monkey(_,On,_),State). ison(Object,On,State) :- inn(obj(Object,_,On),State). modify(at(Loc),State,NewS) :- change(monkey(_,On,Holds),monkey(Loc,On,Holds), State,NewS). modify(at(Object,Loc), State,NewS) :- change(obj(Object,_,On),obj(Object,Loc,On), State,NewS). modify(hold(Object),State,NewS) :- change(monkey(At,On,_), monkey(At,On,Object), State, NewS). modify(on(Object), State,NewS) :- change(monkey(At,_,Holds), monkey(At,Object,Holds), State, NewS). modify(on(Object,On), State, NewS) :- change(obj(Object,At,_), obj(Object,At,On), State, NewS). object(X) :- heavy(X) ; light(X). inn(X, [X|_]). inn(X, [_|Y]) :- inn(X,Y). change(Old,New,[Old|List], [New|List]). change(Old,New, [Other|List], [Other|Newlist]) :- change(Old,New, List, Newlist). writeline([]) :- nl. writeline([A|B]) :- write(A), write(' '), writeline(B). /* timing code */ testit(X) :- cputime(S1), test, cputime(S2), test2, cputime(S3), X is (S2-S1-S3+S2)/10. /* this works for Cprolog but maybe not for others */ cputime(X) :- X is cputime. for(X,X,Y). for(X,Y,Z) :- Y < Z, Y1 is Y+1, for(X,Y1,Z). test :- for(X,1,10), test1, fail. test. test1 :- test(general), !. test2 :- for(X,1,10), dummy, fail. test2. dummy.