Dynamics of Beliefs and Strategy of Perception.
- 格式:pdf
- 大小:95.26 KB
- 文档页数:5
Dynamics of Beliefs and Strategy of Perception.Patrick J.Fabiani1Abstract.An autonomous agent equipped with sensors is expectedto efficiently perform a given mission within a dynamic and changingworld of which it has an uncertain representation.In order to keepthis representation well-grounded,the agent has to organize the ac-quisition of information autonomously.A key issue is to choose aframework for the representation of beliefs which is adapted to dealboth with time and uncertainty.A perception strategy,designed forthe purpose of collecting the right information at the right time,shouldbe based on a dynamic evaluation of the relevance of the beliefs ofthe system.A review of works concerning the problems of beliefrevision and temporal representation of uncertainty is presented.Thedifferences between the variety of existing formalisms are discussedand the framework of a well-adapted approach is recalled.The issueof a robust perception strategy is addressed within this framework;afirst solution,together with the corresponding results of simulationsof an autonomous surveillance system,are presented.1IntroductionThe issue which is dealt with refers to an autonomous system hav-ing an uncertain representation of the changing environment withinwhich it has to fulfil a given mission.The paperaddressesthe problemof how the system is taking time into account within its representa-tion of beliefs about the world.An overview of some approachesin thisfield of research isfirst presented in order to shed a newlight on the proposed approach,which extends earlier works on therepresentation of uncertainty.The emphasis is laid on the temporalerosion of the beliefs and on the design of a perception strategy foran autonomous surveillance system in a changing environment.Theproposed approachwas tested with simulations of a Markovian modelof the evolution of the environment:the results seem very promisingfor further developments.2Dynamics of Beliefs2.1Prediction and Perception“Dealing with uncertainty”means some capacity to cope with infor-mation that may result in a number of mutually exclusive hypotheses,ordered from the most likely to the most improbable.The system issupposed to suspend its judgement and consider them as a whole set,until some decisive information is obtained,in so far as any arbitrarychoice would result in a senseless loss of information.Most of thetime,in a dynamic environment it is computationally untractable tomaintain this set because of a“branching problem”:the number ofpossible casesincreases exponentially when considering,at each timepoint,all the possible evolutions from all the possible current statesBut if is very small then is said to be“highly improbable”in both initial assessments,and despite this,the combination invariably leads to the result that is certain.Eventually,if source1corresponds to the current beliefs of the system and source2reports from new sensory observations,any hypothesis that is initially considered as impossible by1cannot possibly become more plausible in the process of belief revision.This makes the use of Dempster-Shafer’s rule questionable in a changing environment,and particularly prob-lematic for the representation of the beliefs of an autonomous system equipped with noisy sensors,unless the value0is never assigned toa degree of belief that is expected to change.2.4Modal and credal ignoranceIn I.Levi’s Epistemic Utility Theory[14]a strong distinction is made between two kinds of ignorance:a modal ignorance and a credal ignorance.According to a given body of knowledge,consisting of all the propositions which are considered as certainly true,the system is able to determine a set of mutually exclusive hypotheses that are possibly true:at a given time point at most one of these hypotheses is true but the system does not know which one.This is called modal ignorance.Then among these hypotheses,the system can make an evaluation with respect to risk assessments or expectations:it may result in a unique probability distribution or in a set of several such distributions which are all permissible according to the system.This is called credal ignorance.The importance of taking modal ignorance and certainty degrees into account in the process of information combination appears in[6],but in their approach the degrees of certainty are handled as opinions,or likelihood values,whereas they actually estimate an amount of information[7].In[10]and[11]the author proposes a set of rules for Bayesian evidential updating with interval-valued probabilities as an improve-ment of strict Bayesianism and an alternative to Dempster-Shafer’s theory.In fact,it is shown in[9]that Dempster-Shafer’s updating is a special case of Bayesian updating with interval-valued probabili-ties.As far as belief revision is concerned,this approach is closely related to I.Levi’s proposal:both the credal state and the set of possi-ble hypotheses are subject to revision,thefirst one through classical Bayesian inference and the second one through a decision process based on epistemic utility maximization([15]).This leads to ma-nipulate convex sets of probability distributions while retaining the Bayesian inference scheme.It has been applied to estimation prob-lems([19],[17])and decision problems([18]).In[12],it is proposeda generalization to a non-convex set-based Bayesianism.2.5Back to the Increasing IgnoranceOn the one hand,approaches such as Interval-valued Probabilities, Shafer’s Theory of Evidence,or Set-Based Bayesianism avoid the drawback of being committed to a(supposedly accurate)single prob-ability distribution and they make it possible to represent ignorance. But on the other hand,they suffer from the fact that ignorance is expressed in such a way that any distribution of beliefs is permissi-ble and consequently the implementation of something equivalent to the principle of increasing ignorance would lead to the same dead-lock as in the Possibility Theory(2.2):as time goes by,the credal state of the system drifts towards a confusing undifferentiated state of belief where any credal probability distribution over the possible hypotheses is permissible:for example an upper probability equal to 1and a lower probability equal to0for every hypothesis.Anyway,no cautious formulation of this problem seems to have been studied within these frameworks so far.2.6Likelihood and ConfidenceDespite I.Levi clearly identifies two independent kinds of uncertainty, both the possibilistic and the classical probabilistic approaches are quite single-sided.It seems preferable to distinguish the problemat-ics and to introduce an explicit evaluation of the ignorance.On the one hand the likelihood value assigned to an hypothesis somewhat corresponds to the believed chances that this hypothesis is the right one,and on the other hand the degree of confidence stands for the amount of valid information that justifies the likelihood value.This approach is presented at greater length in[7]:each hypothesis is always considered as part of a set of mutually exclusive hypotheses in so far as when a piece of information about one of these hypotheses is obtained,it also concerns all the others.But for each hypothesis,the set in which it is considered may vary as its rival hypotheses may be either grouped or subdivided.If in the process of belief revision a likelihood value is assigned to each hypothesis,it is proposed to attach a degree of confidence to this distribution.The likelihood assessment can be modelled by a probability dis-tribution.The degree of confidence is not related to a probability but rather to a certainty degree:letΩbe a probability space:Ωis a space of possible worlds,is a sigma-field of subsets ofΩ,called possible hypotheses and:0;1is a probability distribution overΩat time.Then,is the likeli-hood distribution overΩat time and each hypothesiswith its likelihood value,is attached a degree of confidence.The following rules are recalled:0;10;(1)(2)min;(3)max;(4) A set of rules is also given in[7]for the combination of information coming from two independent sources1and2which respectively report the distributions of probabilities1and2over a set with the degrees of confidence1and2.An important point is that if the beliefs of the system about a set of rival hypotheses are obsolete,the acquisition of new information from a sensor increases the confidence in the believed distribution of probability over.2.7Erosion ofBelieft = 0Figure1.Alternate erosions and updatesIn this framework,it is proposed to model the evolution of a belief with time according to the principle of increasing ignorance(2.2). If no new information is available,the system’s degree of belief in is assumed to drift towards ignorance:this means that while its likelihood value remains unchanged if no general knowledge saysAbduction,Temporal and Causal Reasoning9P.J.Fabianiit should evolve,its associated degree of confidence is a decreasing function of time drifting towards0.The point is that each belief,if it is not updated by the arrival of new information,will turn into a default opinion as its justification becomes obsolete and possibly inaccurate. It is worth noticing that the erosion of belief may be characterized for each hypothesis with respect to the risk of occurence of an event causing a change in the truth value of:this means that for those propositions that belong to the system’s body of knowledge and are known to remain certain,there will be no erosion of belief,whereas for other hypotheses this erosion will be all the more rapid as the chances of an evolution during the current period of time are great. 3Strategy of Perception and Surveillance3.1Maximizing confidenceBasically,each possible world,as an atomic element of the set Ω,is fully determined by the instantiation of every state variable (,depending on time).Considering a set of possibledistinct values(with)for the state variable,then,each of the set of mutually exclusive hypotheses is a very natural element of.If and if a distribution of values of likelihood is assumed with a degree of confidence over every set,then,the value of likelihood of is given by and its degree of confidence is min min.In the proposed formalism,represents the global current opinion of the system about its environment and results in a likelihood value attached to each hypothesis.is the corresponding confidence distribution overΩ,that results in a degree of confidence attached to each possible world.The overall degree of confidence in the current credal state ismin minThen,a perception strategy designed with the long term purpose of collecting the right information at the right time can be founded on a decision criterion taking into account the proposed evaluation of the relevance of the system’s beliefs:that is both the reliability attached to each sensor and the elapsed time since the last update.As a consequence of the principle of increasing ignorance,the overall degree of confidence in the current credal state(3.1)is a decreasing function of time,corresponding to an increasing risk for the system due to a lack of information.The perception strategy has to be designed to maximize it as time goes by.Thus,it isfirst proposed that at a time(t)the system should use a one step forward decision process,and choose which action to perform next,so as to maximize the overall degree of confidence C(t).So,at each time step, the system will choose the action that increases the minimal degree of confidence in the distribution overΩ.3.2The Markovian environmentA simulation of a surveillance system following a confidence-based one step forward strategy of perception is now presented:a system is in charge of the surveillance of a limited changing scene divided into zones that are subdivided into atomic cells:let be the total number of cells.The size of the observation window allows the system to visit one and only one cell at each time step.As time goes by,the cells are independently and randomly switched on and off as if they were pieces of a landscape where brushfires could randomly break out.The scene is equivalent to a sequence of boolean variables1(01)that evolve according to a Markovian process(figure2).01(q)(p)(1 - p)(1 - q)Figure2.Markovian evolution process for a cellThe parameters and of the Markovian processes vary from a zone to another but are constant over the set of all the cells of a same given zone:is the conditional probability that1at time provided that0at time and the conditional probability that 0at time provided that1at time.If is the probability that1at time:1(5)lim7Nevertheless,the proposed approach is intended to be robust with regards to such a modelling of the sensors and rather uses a degree of confidence attached to the sensor itself.The degree of confidence attached to the simulated sensor was defined with a multiplicative coefficient and a decreasing function of time.The constant coeffi-cient stands for the unreliability of the sensor:as far as there is a unique sensor,the choice of an appropriate value for that constant was rather subjective(besides,it did not prove to be a crucial point in the design of the perception strategy).Furthermore,the experi-mental comparisons between simulations with“perfect”sensors and simulations with unreliable sensors mainly result in an equal loss of performance for all the strategies based on the beliefs of the system.3.3Perception strategiesAt each time,each cell is associated with a couple of mutually exclusive hypotheses:(1,0)over which the system can assess the likelihood distribution(,1)and attach a degree of confidence.Then,the cell is said to have the degree of confidence.According to the one step forward strategy of maximum confidence,at each time step,the observation window jumps from its position to the neighbouring cell that has the minimum degree of confidence.In that case,the rate of decay of the degree of confidence with regards to the erosion of belief is a crucial point.Abduction,Temporal and Causal Reasoning10P.J.FabianiFor each cell,the erosion should be all the more rapid as the chances of an evolution during the current period of time are great.So,at each time step,the rate of erosion of should depend on the beliefs of the system about :it should be a function of (respectively )if the system has a sufficiently great degree of confidence in the belief that0(respectively 1).Otherwise,the systemshould consider the worst case and the rate of erosion should be a function of max .In the following 1(fires are out most of the time)and therefore max .The idea is to use a probabilistic model of the scene in order to assess likelihood values that are relevant on an average and to erode theconfidence in the observations.A thresholdand a parameter were chosen and the following rule was implemented for each cell :05:(8)05:(9):(10)A very similar problem of surveillance,with cells representing elec-tric bulbs and having the same parameters of evolution,is studied in [2]within a Bayesian approach.The system computes for each and each the probability and controls the observation win-dow in order to minimize the expected error between the maximum likelihood estimate and the real state of the scene.As all expectations are calculated according to the ’s,the proposed strategies result in the minimization of criteria such as:1min 1or 11or Shannon’s entropy 1log (which is much more concerned with complexity than with informa-tion).They all turn out to be equivalent as their minima are ob-tained for the extreme values0or 1.According to the corresponding one step forward strategies the observation win-dow jumps at each time step to the cell that has the maximum min 1:the observation lowers this value.Such strategies tend to forget some cells that were not observed for some time [16]:if limStrategies ->random methodical Bayesian confidence Criterion 153%65%62%65%Criterion 253%65%63%65%Criterion 347.4%34.9%37.5%34.9%Criterion 428.9%25.0%25.6%25.0%the observation.The comparison between the different strategies is based on objective criteria of performance that are computed on an average over the whole simulation.Unfortunately,they are hard to optimize on line :Criterion 1:the percentage of detected fires among all those that have occurred on zone 1(an ideal score is 100%);Criterion 2:the percentage of detected fires among all those that have occurred on zone 2(an ideal score is 100%);Criterion 3:the global percentage of non detected fires on both zone 1and 2(an ideal score is 0%);Criterion 4:the average percentage of time,per cell and over the duration of the simulation,for which the beliefs of the system were erroneous as for the estimation of the real state of the cell (an ideal score is 0%).Due to the Markovian model of evolution,the average period of time during which a cell stays in the state 1(respectively0)lasts 1(respectively 1).If there are cells inthe scene,it takes at least a timeto visit all them once.As a consequence,the ratios and characterize the difficulty for the system to detect changes in the state of :if they are greater than one,it will be hard to detect all the changes.In the presented results,there are two zones of five cells in the scene and the Markovian parameters and were chosen so that :as a consequence,if is constant over both zones,is a key factor.It appears that the problem of surveillance is quite manageablewhen02and for that value the perception strategy based on degrees of confidence detects more than 93%of the fires in both zones (see table 4).On the other hand,saturation is reached when1all over the scene (table 1):in this case,the performance of the different strategies are almost equivalent.Table 2.Zone 1:(p=0.1,q=0.1)-Zone 2:(p=0.001,q=0.1)Table3.Zone1:(p=0.001,q=0.01)-Zone2:(p=0.001,q=0.1)Strategies->random methodical Bayesian confidenceCriterion180%88%0%68%Criterion284%91%95%94%Criterion315.9%8.9%7.1% 6.6%Criterion4 2.9% 1.7%0.9%0.8% As a conclusion,the proposed perception strategy shows a satisfac-tory behaviour throughout the comparisons.It is based on a dynamic model of the scene and is fully compatible with a probabilistic frame-work.A key point is that,unlike the Bayesian strategy,it leads to an exhaustive exploration of the scene,like the methodical strategy: therefore,it is a robust strategy and in most cases a better one than the methodical one(which is quite robust as well).In the future, the challenge could be to design rules of erosion for the degrees of confidence so that the associated strategy of perception should be appropriate for the optimization of a chosen criterion of performance.4ConclusionThe proposed approach seems to meet the needs of the design of a robust perception strategy for an autonomous surveillance system in an uncertain and changing environment.A set of rules is recalled that constitutes a definition of how the proposed degree of confidence and the likelihood value should be handled so as to produce a relevant mechanism for reasoning about time and uncertainty.The emphasis is laid on the dynamics of beliefs and more specifically on the erosion of the degrees of confidence.This approach was successfully applied to a problem of surveillance in a simulated Markovian environment. Further developments should lead to improve the performance of the proposed strategy.ACKNOWLEDGEMENTSThis research is partly supported by the Direction des Recherches et Etudes Techniques-DGA France-under“Perception”contract.REFERENCES[1]T.Dean and K.Kanazawa,‘Persistence and probabilistic projection’,IEEE Transactions on System,Man,and Cybernetics,19(3),574–585, (jun1989).[2]J.-L.Desnoyer,O.Dessoude,nusse,and X.Merlo,‘Robot per-ception systems:acoustics vision set-up control’,in Proceedings of the Symposium on Avanced Information Processing in Automatic Control, pp.229–233.IFAC,(1989).[3] D.Driankov and ng,‘Possibilistic decreasing persistence’,in9thInternational Workshop on Uncertainty in AI,Washington,(jul1993).[4] D.Dubois and H.Prade,‘Combination and propagation of uncertaintywith belief functions-a reexamination-’,in9th IJCAI-Los Angeles, pp.111–113.IJCAI,(1985).[5] D.Dubois and H.Prade,The´orie des possibilite´s:applications a`larepre´sentation des connaissance en informatique,E´ditions Masson, 1985.[6] D.Dubois,H.Prade,and ng,‘Dealing with multi-source informa-tion in possibislistic logic’,in10th ECAI,pp.38–42.John Wiley& Sons,(1992).[7]P.J.Fabiani,‘A new approach in temporal representation of belief forautonomous observation and surveillance systems.’,in11th ECAI-Amsterdam.,pp.391–395.John Wiley&Sons,(aug1994).[8]S.Hanks and D.McDermott,‘Modeling a dynamic and uncertain worldi:Symbolic and probabilistic reasoning about change.’,Artificial Intel-ligence,66(1),1–55,(mar1994).[9]H.E.Kyburg Jr.,‘Bayesian and non-bayesian evidential updating’,Ar-tificial Intelligence,31,271–293,(1987).[10]H.E.Kyburg Jr.,‘Evidential probability’,in12th International JointConference on Artificial Intelligence,pp.1196–1202.IJCAI,(1991).[11]H.E.Kyburg Jr.,‘Believing on the basis of the evidence’,TechnicalReport438,University of Rochester,Computer Science Dept.,(sep 1992).[12]H.E.Kyburg Jr.and M.Pittarelli,‘Set-based bayesianism’,TechnicalReport407,University of Rochester,Computer Science Dept.,(mar 1992).[13]J.F.Lemmer,‘Confidence factor,empiricism and the dempster-shafertheory of evidence’,in Uncertainty in Artificial Intelligence,volume4 of Machine Intelligence and Pattern Recognition,117–125,Elsevier Science,(1986).[14]I.Levi,Decisions and revisions,number3in Philosophical essays onknowledge and value.,Cambridge University Press,1984.[15]I.Levi,‘Information and ignorance’,Information Processing and Man-agement.,20(3),355–362,(1984).[16]X.Merlo,Techniques probabilistes d’inte´gration et de controˆle de laperception en vue de son exploitation par le syste`me de de´cision d’un robot,The`se de Doctorat,Institut Polytechnique de Lorraine,1988. [17] D.R.Morrel,‘Epistemic utility estimation’,IEEE Transactions on sys-tems,man and cybernetics,23(1),129–140,(jan1993).[18] D.R.Morrel and W.C.Stirling,‘Convex bayes decision theory’,IEEETransactions on systems,man and cybernetics,21(1),173–183,(jan 1991).[19] D.R.Morrel and W.C.Stirling,‘Set-valuedfiltering and smoothing’,IEEE Transactions on systems,man and cybernetics,21(1),184–193, (jan1991).[20] B.Nebel and C.Ba¨ckstro¨m,‘On the computational complexity of tem-poral projection and plan validation’,in10th National Conference on Ar-tificial Intelligence,pp.748–753,San Mateo,California,(1992).AAAI, Morgan-Kaufmann.[21] C.Perneel,H.V an De V elde,and M.Acheroy,‘A heuristic searchalgorithm based on belief functions’,in14th International Avignon Conference,pp.99–107.AFIA-AI’94,EC2,(1994).[22]G.Shafer,A Mathematical Theory of Evidence,Princeton UniversityPress,Princeton,New Jersey,1976.[23] F.V oorbraak,‘On the justification of dempster’s rule of combination’,Artificial Intelligence,48,171–197,(1991).Abduction,Temporal and Causal Reasoning12P.J.Fabiani。