Formally Verifying Dynamic Properties of Knowledge Based Systems(7)

3AnytimeProblemSolvers:PSMswithboundedrun-TimeInthispaperwearestudyingthedynamicpropertiesofKBSs.InthissectionwewillstudyananytimePSM,sinceforsuchaPSMtheanalysisofitsdynamicpropertiesareofcentralimportance.Rememberthatananytimealgorithmgraduallyapproachestheperfectsolution,andcanbeinterruptedatanymomentwhennomorecomputationtimeisavailable,atwhichpointthecurrentlyavailablesolutionisreturned.

WewillbeinterestedindynamicpropertiesofthisPSM,suchasitsbehaviourwhenrun-timeincreases,andthegradualconvergenceoftheanytimebehaviourtotheoptimalsolution.

3.1OperationalisationofananytimePSM

Ouroriginalprogramfilter#returnedthesubsetofallcorrectelements(solutionclasses)ofagiveninputset(candidateclasses)andwassoundandcompletew.r.t.itscompetencedescription.Butthisisonlytrueundertheassumptionthatitcanhaveallthetimeitneedstocomputeitsoutput.Withthisinmindwecanadjustourprogramtoanotherprogram,whichwewillcall lter-bounded,whichgetsanintegerasadditionalparameter.Thisintegerwillbeaboundonthenumberofstepstheprogramcandoandcanbeinterpretedasaboundontheprogramrun-time.

ThisadditionalparameternmakesthisPSMintoananytimealgorithm:themethodreturnsasensibleapproximationofthe nalanswer,evenwhenallowedonlyalimitedamountofrun-time(i.e.whenthetime-boundissmallerthanthenumberofclassesthatmustbeconsidered).Theprogramterminateswhennreacheszeroandndecreasesbyoneineveryrecursivecall,andisshowninthe gurebelow.Wehaveindicatedthedifferenceswiththeoriginalcodeofthefilter#program.Thesedifferencesareonly:anadditionalparametern,whichisdecreasedineveryrecursivecall,plusanadditionaltestonn0toprematurelyendtherecursion.

filter-bounded#(cs,n;varoutput)

begin

//elseifcs=0n=0thenoutput:=0

varcandidate=select(cs)in

ifcorrect(candidate)then

begin

candidate,n-1;output);filter-bounded#(cs

output:=insert(candidate,output)

end

else

filter-bounded#(cscandidate,n-1;output)

end

Fig.2.Anytimeversionofthelinear lteringPSM