Abstract
Agents need to be able to change their beliefs; in particular, they should be able to contract or remove a certain belief in order to restore consistency to their set of beliefs, and revise their beliefs by incorporating a new belief which may be inconsistent with their previous beliefs. An influential theory of belief change proposed by Alchourron, Gärdenfors and Makinson (AGM) [1] describes postulates which rational belief revision and contraction operations should satisfy. The AGM postulates are usually taken as characterising idealised rational reasoners, and the corresponding belief change operations are considered unsuitable for implementable agents due to their high computational cost [2]. The main result of this paper is to show that an efficient (linear time) belief contraction operation nevertheless satisfies all but one of the AGM postulates for contraction. This contraction operation is defined for an implementable rule-based agent which can be seen as a reasoner in a very weak logic; although the agent’s beliefs are deductively closed with respect to this logic, checking consistency and tracing dependencies between beliefs is not computationally expensive. Finally, we give a non-standard definition of belief revision in terms of contraction for our agent.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alchourrón, C.E., Gärdenfors, P., Makinson, D.: On the logic of theory change: Partial meet functions for contraction and revision. Journal of Symbolic Logic 50, 510–530 (1985)
Doyle, J.: Reason maintenance and belief revision. Foundations vs coherence theories. In Gärdenfors, P., ed.: Belief Revision. Cambridge Tracts in Theoretical Computer Science, vol. 29, pp. 29–51. Cambridge University Press, Cambridge (1992)
Doyle, J.: Truth maintenance systems for problem solving. In: Proceedings of the Fifth International Joint Conference on Artificial Intelligence, IJCAI 1977, p. 247 (1977)
McAllester, D.A.: Truth maintenance. In: Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI 1990), pp. 1109–1116. AAAI Press, Menlo Park (1990)
Gärdenfors, P.: Conditionals and changes of belief. In: Niiniluoto, I., Tuomela, R. (eds.) The Logic and Epistemology of Scientific Change, pp. 381–404. North-Holland, Amsterdam (1978)
Gärdenfors, P.: Knowledge in Flux: Modelling the Dynamics of Epistemic States. The MIT Press, Cambridge (1988)
Rao, A.S.: AgentSpeak(L): BDI agents speak out in a logical computable language. In: Perram, J., Van de Velde, W. (eds.) MAAMAW 1996. LNCS, vol. 1038, pp. 42–55. Springer, Heidelberg (1996)
Laird, J.E., Newell, A., Rosenbloom, P.S.: SOAR: An architecture for general intelligence. Artificial Intelligence 33, 1–64 (1987)
Software Technology Branch, Lyndon B. Johnson Space Center Houston: CLIPS Reference Manual: Version 6.21 (2003)
Makinson, D.: On the status of the postulate of recovery in the logic of theory change. Journal of Philosophical Logic 16, 383–394 (1987)
Williams, M.A.: Iterated theory base change: A computational model. In: Proceedings of Fourteenth International Joint Conference on Artificial Intelligence (IJCAI 1995), pp. 1541–1549. Morgan Kaufmann, San Francisco (1995)
Galliers, J.R.: Autonomous belief revision and communication. In: Gärdenfors, P. (ed.) Belief Revision. Cambridge Tracts in Theoretical Computer Science, vol. 29, pp. 220–246. Cambridge University Press, Cambridge (1992)
Bezzazi, H., Janot, S., Konieczny, S., Pérez, R.P.: Analysing rational properties of change operators based on forward chaining. In: Kifer, M., Voronkov, A., Freitag, B., Decker, H. (eds.) Dagstuhl Seminar 1997, DYNAMICS 1997, and ILPS-WS 1997. LNCS, vol. 1472, pp. 317–339. Springer, Heidelberg (1998)
Makinson, D.: How to give it up: A survey of some formal aspects of the logic of theory change. Synthese 62, 347–363 (1985)
Nebel, B.: A knowledge level analysis of belief revision. In: Brachman, R., Levesque, H.J., Reiter, R. (eds.) Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, pp. 301–311. Morgan Kaufmann, San Francisco (1989)
Williams, M.A.: Two operators for theory base change. In: Proceedings of the Fifth Australian Joint Conference on Artificial Intelligence, pp. 259–265. World Scientific, Singapore (1992)
Rott, H.: Just Because Taking belief bases seriously. In: Buss, S.R., Hájaek, P., Pudlák, P. (eds.) Logic Colloquium 1998—Proceedings of the 1998 ASL European Summer Meeting. Lecture Notes in Logic, Association for Symbolic Logic, vol. 13, pp. 387–408 (1998)
Nebel, B.: Base revision operations and schemes: Representation, semantics and complexity. In: Cohn, A.G. (ed.) Proceedings of the Eleventh European Conference on Artificial Intelligence (ECAI 1994), pp. 341–345. John Wiley and Sons, Chichester (1994)
Nebel, B.: Syntax-based approaches to belief revision. In: Gärdenfors, P. (ed.) Belief Revision. Cambridge Tracts in Theoretical Computer Science, vol. 29, pp. 52–88. Cambridge University Press, Cambridge (1992)
Dixon, S.: A finite base belief revision system. In: Proceedings of Sixteenth Australian Computer Science Conference (ACSC-16): Australian Computer Science Communications, Brisbane, Australia, vol. 15, pp. 445–451. Queensland University of Technology, Australia (1993)
Dixon, S., Wobcke, W.: The implementation of a first-order logic AGM belief revision system. In: Proceedings of 5th IEEE International Conference on Tools with AI, Boston, MA, pp. 40–47. IEEE Computer Society Press, Los Alamitos (1993)
Wasserman, R.: Resource-Bounded Belief Revision. PhD thesis, ILLC, University of Amsterdam (2001)
Chopra, S., Parikh, R., Wassermann, R.: Approximate belief revision. Logic Journal of the IGPL 9, 755–768 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alechina, N., Jago, M., Logan, B. (2006). Resource-Bounded Belief Revision and Contraction. In: Baldoni, M., Endriss, U., Omicini, A., Torroni, P. (eds) Declarative Agent Languages and Technologies III. DALT 2005. Lecture Notes in Computer Science(), vol 3904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11691792_9
Download citation
DOI: https://doi.org/10.1007/11691792_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33106-3
Online ISBN: 978-3-540-33107-0
eBook Packages: Computer ScienceComputer Science (R0)