﻿A FRAMEWORK FOR
MULTI-AGENT BELIEF REVISION
By
Wei Liu (M.Eng)
SUBMITTED IN PARTIAL FULFILLMENT OF THE
REQUIREMENTS FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY
AT
THE UNIVERSITY OF NEWCASTLE
CALLAGHAN, NSW 2308, AUSTRALIA
AUGUST 2002
c○ Copyright by Wei Liu (M.Eng), 2002
I hereby certify that the work embodied in this thesis is
that the result of original research and has not been submitted
for a higher degree to any other University or Institution.
ii
Signature of Author
To Hongwei, Haolin and my parents.
iii
Contents
Abstract ix
Acknowledgements xi
1 Introduction 1
1.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Issues in Multi-Agent Belief Revision . . . . . . . . . . . . . . 5
1.2.2 A Framework for Multi-Agent Belief Revision . . . . . . . . . 7
1.3 Scope and Key Assumptions . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Intelligent Agents and Belief Revision 13
2.1 Intelligent Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 The Intelligence of an Agent . . . . . . . . . . . . . . . . . . . 14
2.1.2 Example: Academic Life . . . . . . . . . . . . . . . . . . . . . 18
2.2 An Informal Introduction to Belief Revision . . . . . . . . . . . . . . 20
2.2.1 Example: Umbrellas in the Rain . . . . . . . . . . . . . . . . . 20
2.2.2 Example: Air Kangaroo and Free Beer . . . . . . . . . . . . . 23
2.2.3 Three Issues of Belief Revision . . . . . . . . . . . . . . . . . . 23
2.3 Belief Revision as an Epistemological Theory . . . . . . . . . . . . . . 26
2.3.1 Four elements of an epistemological theory . . . . . . . . . . . 27
iv
2.3.2 Information Economy and Criteria of Rationality . . . . . . . 30
3 Belief Revision Techniques under the AGM Paradigm 32
3.1 The AGM Postulates and Belief Set Revision . . . . . . . . . . . . . . 32
3.1.1 Postulates for Expansion . . . . . . . . . . . . . . . . . . . . . 34
3.1.2 Postulates for Revision . . . . . . . . . . . . . . . . . . . . . . 35
3.1.3 Postulates for Contraction . . . . . . . . . . . . . . . . . . . . 37
3.2 Levi Identity and Harper Identity:
From Revision to Contraction and Vice Versa . . . . . . . . . . . . . 39
3.3 Determining the Sentences to be Retracted . . . . . . . . . . . . . . . 39
3.3.1 Epistemic Entrenchment Ordering . . . . . . . . . . . . . . . . 40
3.3.2 System of Spheres . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.3 Other Important Works . . . . . . . . . . . . . . . . . . . . . 43
3.4 Implementing Entrenchment Based Revision - Belief Base Revision . 44
3.4.1 Finite Partial Epistemic Rankings . . . . . . . . . . . . . . . . 45
3.4.2 Transmutations . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Belief Revision - The Probability and The Possibility Approach 51
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Belief Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 Possibility Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 Probability as Special Belief Functions . . . . . . . . . . . . . . . . . 63
4.6 Possibility as Special Belief Functions . . . . . . . . . . . . . . . . . . 65
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5 Belief Revision in a Multi-Agent Environment 69
5.1 Brief Introduction to Multi-Agent Systems . . . . . . . . . . . . . . . 69
5.2 Various Frameworks for Multi-Agent Belief Revision . . . . . . . . . . 75
5.2.1 Mutual Belief Revision of Van der Meyden . . . . . . . . . . . 75
5.2.2 MABR of Kfir-dahav and Tennenholtz . . . . . . . . . . . . . 77
v
5.2.3 MSBR of Dragoni et al. . . . . . . . . . . . . . . . . . . . . . 78
5.2.4 DBR of Dragoni et al. . . . . . . . . . . . . . . . . . . . . . . 79
5.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3 Belief Revision in Multi-Agent Systems - Concepts and Terminologies 81
5.4 Heterogeneities in Multi-Agent Systems . . . . . . . . . . . . . . . . . 84
6 Ontology - Tackling the Heterogeneity Issues 89
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.2 Classifying Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.3 Representing Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.4 Ontologies for Multi-Agent Belief Revision . . . . . . . . . . . . . . . 100
6.4.1 Tackling the Social Character Heterogeneity . . . . . . . . . . 100
6.4.2 Tackling the Semantic Heterogeneity - Translating among var-
ious ranking systems . . . . . . . . . . . . . . . . . . . . . . . 102
6.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7 Trust Evaluation 105
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.2 Essential Constituent Beliefs for Trusting Information Sources . . . . 108
7.3 Trustworthiness and Degree of Beliefs . . . . . . . . . . . . . . . . . . 111
7.3.1 Degree of Trustworthiness . . . . . . . . . . . . . . . . . . . . 112
7.3.2 Degree of Deception and Degree of Sincerity . . . . . . . . . . 113
7.3.3 The Evaluation of Competency and Sincerity . . . . . . . . . . 116
8 Information Pedigree 119
8.1 Evaluating Trust on Passing-On Information . . . . . . . . . . . . . . 120
8.1.1 Representing Information Pedigrees . . . . . . . . . . . . . . . 121
8.1.2 Information Pedigree Transformation using Trust Evaluation . 124
8.2 An Example in Resolving Conflicting Information . . . . . . . . . . . 126
8.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
vi
9 Shared Knowledge Structure and Knowledge Migration 132
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9.2 Shared Knowledge Structure . . . . . . . . . . . . . . . . . . . . . . . 134
9.3 Relationship with Other Knowledge Structures . . . . . . . . . . . . . 139
9.4 Inconsistency Principle . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.5 Knowledge Grade and Knowledge Migration . . . . . . . . . . . . . . 143
10 Multi-Agent Belief Revision – Architecture and Implementation 145
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
10.2 A Belief Revision Agent . . . . . . . . . . . . . . . . . . . . . . . . . 146
10.3 A FIPA Multi-Agent Platform Implemented in JADE 2.4 . . . . . . . 149
10.4 Design Using an Object-Oriented Approach . . . . . . . . . . . . . . 152
10.4.1 Domain Beliefs and Social Beliefs . . . . . . . . . . . . . . . . 153
10.4.2 Belief Revision Services - Use Case Study . . . . . . . . . . . . 157
10.4.3 Layered Belief Revision Engine . . . . . . . . . . . . . . . . . 162
10.5 Agent Communication Channel - JADE Agent Wrapper for Belief Re-
vision Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
11 Discussion, Conclusions and Implications 168
11.1 Discussion and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 168
11.2 Limitations and Implications for Future Research . . . . . . . . . . . 173
A Agent Environment Properties 175
B Logical Foundations 177
C JADE Implementation of Ontologies V2.4 180
D FIPA Agent Platform Components 182
E Publications 185
vii
Bibliography 186
viii
Abstract
Despite the fact that maintaining a consistent belief set is crucial for agents to exhibit
rational behaviour, most of the agent development toolkits or frameworks use simple
database insertion and deletion for the update of beliefs. One of our research aims is
to investigate concepts and techniques that facilitate a service-oriented belief revision
agent with social awareness.
Furthermore, research in the area of belief revision mainly focuses on a single
agent. Seldom are there studies into belief revision issues in a multi-agent environ-
ment. We investigated belief revision techniques for both individual agents as well as
multiple agents.
The research into individual agent belief revision exhibits a diverse range of revi-
sion schemes. However, they all can be described using some essential elements of an
epistemological theory. Furthermore, we also show that both probabilities and possi-
bilities are special cases of belief functions and can be represented by belief functions
when certain conditions are met.
With the research into multi-agent belief revision frameworks, an ontological clas-
sification of the various terminologies is presented, which provides the basis that aids
the investigation into the domain.
In order to address the inability of existing frameworks to deal with hetero-
geneities, we developed Ontologies for tackling social heterogeneities, semantic het-
erogeneities and syntactical heterogeneities.
We identified two constituents of evaluating an information source’s trustworthi-
ness and propose several ways of generating general or topic specific trustworthiness
ix
from the degree of sincerity and the degree of competency. This provides the crucial
input required by fusion and weighted knowledge base merging, which are often as-
sumed to be pre-computed. We also show that a pedigree of at least 3 levels of depth
will enable the agent to analyse and keep track of passing-on information, whose
credibility are often wrongly computed in some real application domains. Overall,
the research into trust issues not only provide a clear domain description but also
formulates the necessary components of agent beliefs, i.e. domain beliefs and social
beliefs.
After clarifying the trust issues, we proposed a shared knowledge structure that
is capable of representing both shared knowledge as well as private knowledge. This
leverage our research from a MSBR (Belief Revision using information from Multiple
Sources) level to a MABR (Multi-Agent Belief Revision) level.
The investigated concepts, such as revision schemes, trustworthiness, information
pedigree, shared beliefs and ontologies, eventually come together within a flexible and
general framework. The framework design herein uses JADE as the agent platform to
facilitate inter-agent communication and the belief revision system - SATEN for the
essential functionalities for a single belief revision agent. The so-designed framework
is capable of incorporating new belief revision schemes and a viable model for a het-
erogenous multi-agent environment. In particular, as a layering approach is adopted,
a belief revision agent designed under such framework is capable of providing ser-
vices at various levels. It provides a tangible architecture of a belief revision service
provider for a dynamic, heterogenous and autonomous open environment.
x
Acknowledgements
I would like to express my deep appreciation to Mary-Anne Williams, my supervisor,
for her introduction to the area, for her many suggestions, insightful guidance, broad
interest and constant support during this research. I am very grateful to have her as
both my supervisor and a personal friend. Thanks to her kind and cheerful nature,
she has shown great understanding and support to my study as well as my family.
I had the pleasure of meeting with Salem Benferhat and Daniel Le Berre. They are
very insightful researchers and willing to share their profound knowledge in mathematics
and software engineering with me. I learned a lot from them, no only technically,
but also a systematic way of thinking.
I also had the pleasure of meeting with Jérôme Lang, who has kindly shared
his knowledge in probability theory, possibility theory, belief functions and decision
making theories.
I also owe a great “thank you” to the Australian Government for sponsoring me
with the International Postgraduate Research Scholarship during this research, my
research in this area will not be possible without this. The University of Newcastle
Research Scholarship, which was awarded to me in 1999, was crucial to the successful
completion of this project. The staff in the Research Higher Degree of Newcastle University
are extremely supportive. They are wonderful people and especially, thanks to
Mr. John Sanderson the scholarship manager for his explanation of the rules during
the special period of my off-campus study.
I should also thank the support from RMIT university for financing me for travelling
back to work with my supervisor and to prestigious international conferences etc.
Special thanks to Dr. Phil Vines, Sheila Howell, A. Prof. Lin Padgham, A. Prof. Vic
Ciesielski, Margaret Pagonis, Dr. Faye Liu, Dr. Hugh Williams, Dr. James Harland,
Dr. Isaac Balbin, Feng Lu and many others for their mentoring and kind support. It
is my great pleasure to be working with you.
xi
I should also mention all my girl friends in the School of Management, Christine
Bruff, Kim Cowley, Merrilyn Stone, Dot Etheridge, Janice Carroll, Christine Toms,
Susan Robinson, Tong Hong Miew, Kath Bill and April May Kerr. You are my
dearest friends, the most beautiful and caring people I have ever seen. You can not
imagine how your kind nature, your caring about me and my family has made my
first couple of years in Australia such a wonderful life-long memory. All I can say is
I am lucky to meet you girls.
I am very grateful, of course, to my parents for sacrificing their time and energy
to look after us, and their endless love for Hongwei, Haolin and me. My appreciation
to mum, dad and my only brother is beyond words. Without them this work would
never have come into existence (literally). Thanks to my husband, the best cook in
my view, without you squeezing time from your busy schedule to cover up my duty
in the house, this work will not be possible. Finally, to my little boy, Haolin, thanks
to helping me completely relax my mind when you are around. You are our endless
pleasure.
Wei Liu
August, 2002
xii
Chapter 1
Introduction
“Be prepared, they are coming...
Computer scientists and technology professionals are preparing a brave
new world of software-based, intelligent agents that will act as virtual
support staff for any human beings willing to trust them. The main
difference: they will work 24/7, won’t take a lunch break and never utter
a gripe.”
— Mark Harrington from Newsday.com 1 Jan 15, 2002
1.1 Background and Motivation
The past two decades have seen a global information surge facilitated by the widely
accessible Internet technology for both industry and individuals. The world is con-
nected via this vast open network, with new nodes connecting to it and disconnecting
from it every second anywhere in the world. The vision of the world has changed
irreversibly forever, terms such as “global village” are not longer science fiction, ev-
erything becomes as close as at your finger-tips.
1 In online news article: Plugged In/Cyber Emissaries To Serve Online
1
The Internet and the World Wide Web have fundamentally changed the way
people access information. In both the computer science domain and everyday-life,
more and more, collecting information from several information sources has become
an exceedingly common and often critical activity to achieve our goals. Actually, the
World Wide Web is an unprecedented and enormous information repository, browsing
through it to locate relevant pieces of information becomes a tedious job for human
beings even with the help of the state of the art search engines.
Web services and web applications are important research topics in the artifi-
cial intelligence community, so too agent technologies. As agent technologies gain
maturity, it becomes widely accepted that agent-oriented approaches represent the
mainstream software engineering, particularly for tackling issues presented in large
complex systems[63]. Agent-oriented software engineering has gained tremendous at-
tention in recent times. Its practical and theoretical elements are proving to be helpful
in understanding and modelling complex systems, and as a result they have lead to
new and innovative solutions. The multi-agent designs are especially applicable to
Web applications which are highly heterogenous and autonomous in the sense that
no single system has global control or holds all the global data.
The first generation of web agents were shopbots[67] that compare prices (e.g.
Bargain Finder from Anderson Consulting[71]) and provide recommendations etc.
It is also predicated that with the help of research in agent research communities,
in three or four years time, the web will be populated by autonomous agents that
have more intelligence, that act on human’s behalf for information gathering, and
participate in on-line transactions, such as buying, selling and bidding.
To realise the agent-oriented vision, agents need to be intelligent so that they
2
can achieve an effective balance between proactive and reactive behaviours which
allow them to survive in a dynamic non-deterministic environment such as the Web.
In addition to this, agents need to have social-awareness which will enable them to
communicate, cooperate and/or negotiate under certain interaction protocols.
Belief revision is a ubiquitous process underlying many forms of intelligent behaviour[110].
Most importantly, it is an essential skill for an autonomous agent. It provides the
agent an ability to revise its beliefs in a coherent and rational fashion when it decides
to accept some new information. Most belief revision research, however, has been
produced with a single agent in mind, ie, only one problem solver using the belief
revision service.
SATEN[97, 107] 2 - a web based belief revision system which incorporates several
revision strategies is a good example of a single belief revision agent. Although it is
able to clone its current state, the clones and their ancestors can not communicate.
In other words, they act independently as single agents without awareness of other
agents’ existence.
Multi-Agent Systems (MAS) are distributed computing systems composed of a
number of interacting computational entities (possibly from various vendors). One
important characteristic distinguishing MAS from traditional distributed systems is
that both MAS and its components (agents) are intelligent[99]. As MAS become
increasingly attractive for solving larger and more complex problems, the need for
adequate belief revision technology in the MAS paradigm arises. As we have stated
before, it is becoming increasingly common that agents acquire information from
more than one information source. Further complicating the situation, quite often,
2 http://infosystems.newcastle.edu.au/webworld/saten
3
during tasks such as organising a business trip, retrieving information from multi-
ple databases, managing a large supply chain network, investigating witnesses at a
crime scene can not be completed without information sharing and exchange across
platforms and companies.
Therefore, we are increasingly confronted by issues such as, what an agent should
do in cases when it receives:
• Contradictory information from the same information source;
• Contradictory information from different information sources;
In shared information scenarios or cooperative information systems, what should
an agent do or how should agents cooperate to update/revise the shared/common
knowledge in an heterogenous open system?
• Buyers and sellers are only willing to expose a certain subset of their beliefs but
not their entire belief bases, what should be shared/common knowledge, how
should shared/common knowledge be elaborated?
• The agents involved may use different belief revision techniques, some may just
delete and/or insert facts to belief base, some may use sophisticated transmu-
tation algorithms[108] to decide the new degree of beliefs.
• Which agent should go about changing the shared/common beliefs, what are
the implications for other agents involved?
The research herein is an attempt to answer the above questions in theoretical
and computational ways. The aim is to design a framework which will facilitate the
transformation of a single belief revision agent like SATEN into a multi-agent belief
4
revision system. Meanwhile, the so-designed framework should be general enough
to accommodate existing legacy systems and flexible enough to assemble existing
revision techniques into a new multi-agent belief revision system.
As far as applications are concerned, the framework proposed herein will enhance
the current development and deployment of robust coherent multi-agent systems,
which could be widely applied to e-commerce, e-business, electronic markets, informa-
tion gathering and collective ratings (e.g. articles, books etc) on the web, bandwidth
allocation and the like (resource allocations), vehicle routing among independent dis-
patch centers, multi-enterprise agile manufacturing and scheduling, large supply-chain
networks, and multi-robot domain etc.
1.2 Objectives
Belief revision is regarded as an important research area that bridges the often sep-
arate research activities[24], such as philosophy, logic, probability (statistics), possi-
bility and theory of evidence etc. Similarly, studying belief revision in a multi-agent
environment links areas such as logic, social science, game theory, group decision
making, cooperative information systems etc.
1.2.1 Issues in Multi-Agent Belief Revision
One of the distinguishing features of multi-agent systems as compared to other
types of distributed problem solving systems is the autonomy of their constituent
entities, namely, the intelligent agents. Autonomy in general is understood to be
the property that agents can achieve designed and delegated goals without human
5
intervention[113]. A further interpretation is that agents may be developed by differ-
ent vendors [27][92] under different standards, using different platforms, technologies
and toolkits, bearing different assumptions. A good example that illustrates the di-
versity of agent technologies, Agenticities 3 - a large European project, is presented
on the Agentcities network 4 . It gives an intuitive flavour of the true meaning of the
phrase “large heterogenous open networks”. Among all the networks on the web it
is the largest. Some other heterogenous networks in real life are supply chain net-
works for large enterprises, where hundreds of individual companies cooperate to meet
the requirement of delivering the right amount of goods to the right location at the
right time (on the right devices). It is not surprising to see that one of the major
issues in managing large supply chains is the fact that each supplier has their own
unique product identifier for a product which may not be exactly the same as another
suppliers.
There are two ways of looking at the various heterogeneities presented in multi-
agents systems. On one hand, it is a result of the fact that no single authority has
the global control of the system. This is one of the key incentives that attracts
the participation of individual entities - enjoying the benefit of joining the network
without sacrificing their individual uniqueness and preferences. On the other hand,
the existence of heterogeneities is a major obstacle to system inter-operation and inter-
communication. Open environments are highly desirable in e-business domains and
exist in real life at a human level. Therefore, in facing the challenge of heterogeneities
and understanding the types and their forms of manifestations, it is important to work
with an multi-agent domain. The same is true in the field of belief revision.
3 http://www.agentcities.org
4 http://www.agentcities.net
6
Although a few belief revision frameworks claim to be suited for MAS applica-
tions, they each in turn adopt different terminologies. For example, “mutual belief
revision”[85], “arbitration”[74], “distributed belief revision”[20], “multi-agent belief
revision”[68] and “belief revision using information from different sources”[19] etc.
To understand the differences and similarities in our proposed research, we first need
to clarify and classify these terminologies. This is our first attempt at addressing the
heterogeneity issues.
A close look at these systems also reveals a common shortcoming, the lack of ade-
quate and efficient methodologies in tackling heterogeneity issues during information
exchange, such as trust of heterogenous information sources, heterogenous represen-
tation on shared/common knowledge, and the heterogeneity that exists in various
families of revision techniques etc.
Our research goal is not to replace existing systems but rather to digest and treat
them as legacy systems so that we can have a framework that is general and flexi-
ble enough to integrate them but also leaves room for accommodating new revision
techniques.
1.2.2 A Framework for Multi-Agent Belief Revision
Ontologies are becoming widely accepted as a powerful tool for bridging the gap
between legacy systems and enabling communication and inter-operability in a het-
erogeneous environment[50]. Therefore, an ideal belief revision system for multi-agent
environments should provide the necessary ontologies that enable the inter-operation
between revision agents that are deployed under various assumptions and that use
various revision techniques. Some of the ontologies used by a multi-agent belief revi-
sion system are implicit and embedded in the designed framework, some are explicit
7
and allow interaction with end-users.
Grounded by our research in classifying the types of belief revision in multi-agent
systems and taking into account the necessity of evaluating information sources’ trust-
worthiness, we propose a layered architecture for designing a single belief revision
agent.
Layer-1: Domain Belief Revision
Layer-2: Social Belief Revision
Layer-3: Shared/Common Belief Generation based on Interaction Protocols
Each layer is connected to the external environment via a communication channel.
Typically, in the proposed system, an agent needs to maintain two separate knowl-
edge bases, i.e., a domain knowledge base and a social knowledge base. There also
needs to be a mechanism which will dynamically generate a set of shared/common
domain knowledge with other agents according the data stored in its social knowledge
base.
As we will see in the thesis, the proposed system provides the essential build-
ing blocks for modelling belief revision agents at different levels using a 3-layered
architecture:
• Combining the bottom Layer-1 and the communication channel, we will have
the simplest agent, that is able to carry out single belief revision tasks or pro-
vide single belief revision services. This would be an agent with SATEN-like
functionalities and communication capabilities.
8
• Combining the two bottom layers, i.e. Layer-1 and Layer-2, and the commu-
nication channel, we will have a more sophisticated agent, capable of revising
beliefs received from multiple sources. For example, using Dempster-Shafer’s
Rule of Combination[98] or some fusion techniques[4]. Meanwhile, the agent can
also dynamically update and revise its social knowledge base, e.g. its record of
another agent’s trustworthiness value.
• Combing all three layers and a communication channel, we have an agent who is
not only capable of revising its own knowledge base, but also able to participate
in revising shared/common knowledge.
Moreover, in order to address the heterogeneity issues, firstly, we propose a mes-
sage structure for information exchange that allows agents to evaluate the information
sources’ trustworthiness. Secondly, we propose a shared knowledge structure in order
to capture the different interpretation of shared/common knowledge in the existing
systems. Lastly, we use a FIPA[33] compliant agent platform - JADE[61] - to facil-
itate agent communication, where domain ontologies can be added by the end-user
if needed. The design is described using UML (Unified Modelling Language)[90] and
various existing design patterns[39] are applied.
1.3 Scope and Key Assumptions
Firstly, we adopt the essential assumption of belief revision, i.e., we assume during
the revision process, the world is static. In other words, we do not investigate cases
when the new information to be added to the belief base is a result of change in the
world. Belief update[66] is required to model agents belief change in a dynamic world.
9
Secondly, we will assume an open decentralised loosely coupled environment. By
decentralised we mean that both control and data are logically and often geograph-
ically distributed. There is neither global control nor global data. Loosely coupled
means that individual agents spend most of their time in computation rather than
communication. Open means that the platform is free for agents to join and leave,
there is no obligation enforced.
Thirdly, we assume that each agent has special expertise in specific areas. The
expertise may overlap, but is not identical. Each agent has local memory and local
access to certain data. Often agents need to cooperate to achieve designed goals.
Cooperation here is in the usual sense that none have sufficient information to solve
the entire problem: information must be shared to allow the group as a whole to
produce a solution.
Finally, we assume agents are interconnected so that every agent can communicate
with every other agent by sending messages. The communication between agents is
facilitated by the agent platforms 5 and is always successful. In other words, we assume
the message sent from the sender arrives at the receiver without distortion.
In addition, the term information, knowledge and belief are used interchangeably
throughout the thesis. Except we sometimes distinguish knowledge from belief by
emphasising that finite flat knowledge takes the format of a sentence or a formula
only, while belief is a piece of graded knowledge and consists of flat knowledge and a
degree of belief.
5 See Appendix D for description of FIPA agent platform components.
10
1.4 Outline
In Chapter 2, the research starts with an intuitive example which attempts to motivate
the importance of the role of belief revision for an agent to be intelligent. Then in
the same chapter we review the various techniques and issues researchers have used
to address belief revision.
In Chapter 3, by presenting a widely accepted belief revision standard - the AGM
paradigm and works related to it, we then will have described the main research
methodologies in the field.
In Chapter 4, we conduct a comparative study, which gives a clear picture of how
the different approaches relate to each other. These include the traditional Bayesian
probabilities, the theory of evidence and the possibility theories. As a result, we
conclude our description of the major research efforts in belief revision for single agent
in a single agent environment. This sets the foundation for realising an individual
revision service agent, which may adopt various revision strategies.
In Chapter 5, we begin our investigation of belief revision in a multi-agent do-
main by looking at some existing systems. We suggest an ontological belief revision
hierarchy which clarifies the terminologies adopted in the current research. By inves-
tigating the characteristics of multi-agent systems, we identify three major types of
heterogeneities that need to be addressed when one models multi-agent belief revision.
In Chapter 6, ontologies are introduced as a powerful approach to tackle the
heterogeneity issues. We discuss suitable representations of ontologies and identify
the types of ontologies needed for the three kinds of heterogeneities identified in
Chapter 5.
11
In Chapter 7, we address the social heterogeneities by looking at the trustwor-
thiness of information sources. An agent’s ability to evaluate the trustworthiness of
other agents becomes crucial for it to survive, and indeed thrive, in an open het-
erogenous information sharing environment. In this chapter, we identify two essential
dimensions of beliefs for evaluating sources’ trustworthiness, namely, competency and
sincerity. Moreover, a couple of evaluation procedures are proposed and investigated.
In Chapter 8, we investigate a number of complicated cases of passing-on informa-
tion, where the same information may reach a receiver agent via different routes. In
order to keep information about the source agent we propose the use of an information
pedigree as the means of maintaining the history of communicated information. The
evaluation of overall trustworthiness prepares social knowledge to drive data fusion,
weighted knowledge base merging, and multiple source conflict resolution.
In Chapter 9, we address semantic heterogeneities, namely, various definitions of
social/shared knowledge. To facilitate the sharing of knowledge between agents and
dynamically maintain their private knowledge, a shared knowledge structure is pro-
posed and investigated. In the same chapter, we also investigate possible revision
mechanisms for such a structure - the knowledge migration. Based on the inconsis-
tency principle, and the knowledge grade defined by the shared knowledge structure,
the process of multi-agent belief revision becomes the process of knowledge migration.
In Chapter 10, the design of a flexible framework for multi-agent belief revision is
presented using software engineering approach.
The research concludes in Chapter 11 with discussions of the results and implica-
tions for future research.
12
Chapter 2
Intelligent Agents and Belief
Revision
“Every time we contemplate the leftovers in the refrigerator, trying to
figure out what else needs to be fetched from the grocery store before
fixing a dinner, we are exercising an aspect of intelligence not seen in even
the smartest ape.”
2.1 Intelligent Agents
— William H. Calvin in How Brains Think[10], 1996
This section will briefly answer the following three key questions:
• What are agents and intelligent agents?
• What is belief revision?
• Why belief revision is an ubiquitous process underlying intelligent behaviours?
Formally, an agent is a computer system that is situated in some environment,
and is capable of autonomous action in order to achieve its design objectives[112].
13
Although this is not the ultimate universally accepted definition of agent, it is
flexible and generic enough to include almost all the automatic control systems and
software daemons into the agent family, it is also restrictive enough to exclude those
software tools (such as a word processor) which do not have autonomy but rely on
human interventions to accomplish their tasks.
The key presupposition of an agent system is the ability to interact with (perceive
and act upon) the environment. The uncertain, non-deterministic, partially accessible
nature of the environment[96] makes autonomous actions not only desirable but also
necessary. This is due to the fact that such complexity and unpredictability of the
environment results in the inability of human designers and developers to hard-code
all possible situations that an agent is likely to meet.
Autonomy is the feature that differentiates an agent system from other computer
systems. Informally, autonomous action involves carrying out action without human
intervention. This implies that an agent system is expected to have more robust
behaviour such as recovery from failure and more reliable behaviour such as coping
with an uncertain and changing environment.
2.1.1 The Intelligence of an Agent
What is an intelligent agent then? It is easy to say that an intelligent agent is an agent
endowed with intelligence. The precondition is that we know the precise definition of
intelligence. But unfortunately, we do not.
Often, we describe ourselves as intelligent human beings. Rarely do we stop and
question ourselves: what exactly is intelligence? Are we intelligent by nature? Such
questions have not been of much interest to the research community until people
started to investigate the nature of intelligence by building intelligent machines[103],
14
e.g. intelligent agents. The following quotation states a neuro-physiologist’s view of
human intelligence[10]:
Piaget used to say that intelligence is what you use when you do not
know what to do. If you are good at finding the one right answer to
life’s multiple-choice questions, you are smart. But there is more to being
intelligent - a creative aspect, whereby you invent something new “on the
fly”. Indeed, various answers occur to your brain, some better than others.
Every time we contemplate the leftovers in the refrigerator, trying to
figure out what else needs to be fetched from the grocery store before
fixing dinner, we are exercising an aspect of intelligence not seen in even
the smartest ape. The best chefs surprise us with interesting combinations
of ingredients, things we would ordinarily never think “went together”.
Poets are particularly good at arranging words in ways that overwhelm
us with intense meaning. Yet we are all constructing brand-new utterances
hundreds of times every day, recombining words and gestures to get across
a novel message. Whenever you set out to speak a sentence that you’ve
never spoken before, you have the same creativity problem as the chefs
and poets. Furthermore, you do all your trial-and-error inside your brain,
in the last second before speaking aloud.
What we can obtain from the excerpt above is an intuitive explanation of the cre-
ative aspect of the reasoning process. More precisely, intelligence implies the human
behaviour that attempts to determine consequences by thinking rather than acting,
i.e., by reasoning about the world rather than taking action in it. Most intelligent
agents try to model or replicate some part of a human being’s reasoning process, so we
15
might expect that, an intelligent agent should exhibit creative behaviour (although
not necessarily as sophisticated as human creativity).
Within the agent research community, Wooldridge and Jennings’ definition[113]
of intelligent agent is widely accepted: an intelligent agent is one that is capable of
flexible autonomous action in order to meet its design objectives, where flexibility
means three things:
• reactivity: the ability to perceive their environment, and respond in a timely
fashion to changes that occur in it in order to satisfy their design objectives.
The subsumption architecture developed by Rodney Brooks is the best-known
reactive agent architecture. One of the important characteristics of such a sys-
tem is that the agent behaviours are implemented simply by mapping perceptual
input directly to actions without symbolic reasoning at all.
• pro-activeness: the ability to exhibit goal-directed behaviour by taking the
initiative in order to satisfy their design objectives; e.g. a procedure in PASCAL,
a function in C, or a method in JAVA is the basic building block for a system
that exhibits goal directed behaviour.
• social ability: the ability to interact with other agents (possibly humans) in
order to satisfy their design objectives. The social ability means things beyond
exchanging binary code, but more related to the human world, in terms of
sharing resource and goals, and thus agent can negotiate and cooperate with
others.
Purely reactive behaviour(event-driven) is ideal for agents that can operate in a
time-constrained (constantly changing) environment. Since agents must constantly
16
check the environment and reconsider the validity of their goals. However, such an
agent may waste time and computational resources unnecessarily in a comparably
static environment, so proactive (goal-driven) behaviour is more appropriate for a
static, unchanging environment whereas the assumption (pre-condition) of executing
the procedure remains true while the procedure is executing. Through a number of
experiments, Kinny and Georgeff [69] show that the key parameter that affects an
agent’s decision about being more proactive or more reactive is the the rate of world
change, γ.
Further to the above definition and to my understanding, being either proactive
or reactive only is not intelligent. Whereas being both proactive and reactive is. That
is, the ability to achieve an effective balance between being proactive and reactive
is the key feature that differentiates intelligent agents from other computing enti-
ties. The thinking/reasoning process that attempts to achieve the balance is the key
that underpins an agents intelligent behaviour. Therefore, the Wooldridge&Jenning’s
definition on intelligent agent can be put in a stronger form:
Definition 2.1.1. Intelligent software agents are the software systems that are not
only both proactive and reactive, but also capable of deciding the effective balance
between pro-activeness and reactiveness in a given situation, and at the same time
capable of social interaction with others.
In the following section, an example is used to describe the balance between pro-
activeness and reactiveness. The analysis and investigation of that example sheds
light on the importance of belief revision for intelligent agents.
17
2.1.2 Example: Academic Life
An academic, John, has two intentions 1 : being a good researcher and a good lecturer.
For the time being, John has two tasks to carry out concurrently, preparing a paper for
an international conference and managing a postgraduate subject. The two intentions
are not mutually exclusive, but as they consume the same resource, a good balance
is needed to achieve both. Imagine that John sits in front of the computer writing
his paper while the phone rings and the email program alerts: “you have a mail”.
What should John do? Continue writing the paper or answer the phone calls and
emails? If John constantly answers the phone calls and replies to the emails, there
is little chance that he will finish the paper on time. But if John simply ignores the
phone calls and emails from his students, eventually, he will not be recognised as a
responsible and approachable lecturer.
Writing a paper is one of the proactive procedures he adopted to achieve his
good researcher intention, while answering phone calls and replying to emails are
the proactive procedures for achieving his other intention of being a good lecturer.
Instead of blindly carrying out the procedures for one intension and dropping the
other, naturally, John will prioritise his tasks. Suppose John’s philosophy of time
management is as follows:
• If the paper’s due date is still relatively far away, but the students’ assignment
due date is approaching, and he expects many urgent phone calls and emails,
then the teaching duty takes priority.
• If the paper’s due date is approaching but not the assignment due date, then
the paper writing takes priority.
1 Goals if you like, goals can be seen as committed intentions.
18
• If there is a conflict between the precondition, ie, both the paper and assignment
due dates are approaching, the two intentions become mutually exclusive at that
period of time, then a decision has to be made to drop one intention temporarily.
We can see from the above example, as a human being, an academic can achieve
an effective balance between proactive behaviours (writing a paper, answering phone
calls and emails) and reactive behaviours(reconsidering the priority according to due
dates).
The flexibility resides in the change (the evolution) of the environment (e.g. how
close the due date is) that triggers the rearrangement of the priority of the current
intentions. This is essentially the same intelligence underlying the ability of working
out different plans for dinner based on the different left-overs in the fridge everyday.
To implement this in an intelligent software system, we need knowledge repre-
sentation 2 . One necessity is the agent knowledge base, which contains the agent’s
knowledge of the world, be it the recipes for dinner or the “recipes” for achieving
research and teaching success. The other necessity is the agent belief base, which
reflects the current state of the world, e.g. the beliefs about what is left in the fridge,
the beliefs about how many days left before the paper due etc. The result of observ-
ing the left-overs in the fridge and checking the calendar for today’s date are the new
pieces of information respectively that trigger the changes of the belief base.
Belief revision thus comes into play. As can be seen, for any intelligent agents
that are proposed or designed to be both proactive and reactive, belief revision is a
crucial capability. This argument can be taken even further, that is, belief revision is
a ubiquitous process underlying many forms of intelligent behavior[110].
2 Knowledge representation can be viewed as “the surrogate - the substitute for the thing itself,
used to enable a computational entity to reason about the world”. from http://www.medg.lcs
19
Belief revision is an essential skill that an autonomous agent should possess in
order to revise its beliefs in a coherent and rational fashion when it receives new
information. The concept will be explained further in the following sections.
2.2 An Informal Introduction to Belief Revision
Belief revision concerns the process of modifying an agent’s existing belief base in a
rational way by the introduction of new information that the agent has decided to
accept.
Before discussing belief revision within the paradigm of epistemological theories,
two examples are presented informally to illustrate:
• four elements of an epistemological theory (i.e. epistemic state, epistemic atti-
tude, epistemic input and epistemic change);
• two different ways of changing belief systems (i.e. direct/immediate belief re-
vision for foundation theory and logic-constrained belief revision for coherence
theory);
• three essential issues that concern the belief revision theorists, see Section 2.2.3
for more detail.
2.2.1 Example: Umbrellas in the Rain
John is just about to go out. Given that he believes it is raining outside now, he
decided to take an umbrella with him. But someone who just came in from outside
tells him that it is not raining now.
20
Let r stand for the fact that “it is raining” and ¬r for the opposite that “it is not
raining”. Similarly, u for “to take an umbrella” and ¬u for “not to take an umbrella”.
Therefore, John’s current state of belief can be represented as in Table 2.1.
It is raining. r
If it is raining, I will take an umbrella. r → u
If it is not raining, I will not take an umbrella. ¬r → ¬u
I will take a umbrella. u
Table 2.1: Raining and Umbrella
It is not rational for John to believe that it is raining and it is not raining at the
same point of time. Therefore, in the light of the new information (i.e. epistemic
input), ¬r, John is left with at least three options for his new belief state (assuming
John is only capable of three types of epistemic attitude towards beliefs, accepted,
rejected and unknown):
1) to continue believing r (e.g. John believed that person was just joking)
2) to stop believing in r but to believe in ¬r (e.g. John trusted that person
completely)
3) to be ignorant about r (e.g. John was neither sure of that person nor himself)
In case 1), John can simply keep his old belief state and do nothing. While in both
case 2) and 3), so-called epistemic changes are involved. Simply deleting r from the
database then adding ¬r into the database is one way of doing the changes, which
is the approach taken in foundation theory[57]. The trivial deletion and addition
operation is often accompanied by a sophisticated and in general nonmonontonic
inference operation to deduce the new beliefs[42] (e.g. NMR approach[36] or TMS[70,
21
59] approach). This is called direct/immediate belief revision as compared to
the logic-constrained belief revision. In logic-constrained settings, changes to the
database are no longer trivial but governed by set of rationality postulates. Such
an approach is often taken by coherence theory[57]. In the above example, because
r ↔ u, using one of the AGM postulates in Section 3.1, u will be removed when r is
removed and ¬u will be added automatically when ¬r is accepted. In other words,
¬u is added as a result of the change function, but not as a result of any form of
logical deduction as normally found in direct belief revision. In this thesis, the focus
is on logic-constrained belief revision, which is most eminently exemplified by the
Alchourrón-Gärdenfors-Makinson (AGM) paradigm.
In Table 2.1, beliefs above the horizontal line (r, r → u and ¬r → ¬u in this
example) are normally explicitly represented and so called explicit beliefs. The belief
below the horizontal line (u) is derivable from the explicit beliefs, and is called an
implicit belief. For computational reasons, implicit beliefs are not normally stored
explicitly in a database because they are always infinite. They include all tautologies
which are infinite (e.g. p ∨ ¬p, p ∨ ¬p ∨ ¬p, p ∨ ¬p ∨ ¬p ∨ ¬p ...).
Further discussion of explicit beliefs v.s. implicit beliefs is given in Section 2.2.3
and also in [42] and[41].
One may also find that the above process of changing the beliefs only makes
sense when the world is static. That is, during the change of beliefs, it is assumed the
environment does not change from a state of “raining” to “not raining”. Belief revision
investigates the issues of changing beliefs when the environment is static, whereas
belief update concentrates on the issues raised when the environment is changing
while beliefs change as well. Belief update is beyond the scope of this thesis, for
22
interested readers, please refer to [66]. It is important to note however that update
can be defined in terms of revision[95].
2.2.2 Example: Air Kangaroo and Free Beer
The Raining and Umbrella example only illustrates a very simple case of revision.
Revision can be more complicated and involve many choices among the alternative
resultant states, which is shown by this example. Table 2.2 illustrates the knowledge
base (i.e. belief state or epistemic state).
Air Kangaroo is a start-up airline. a
Air Kangaroo is an Australian airline. b
All Australian start-up airlines serve free beer. a ∧ b → c
Air Kangaroo servers free beer. c
Table 2.2: Air Kangaroo and Free Beer
Suppose John took Air Kangaroo and discovered that Air Kangaroo does not
provide beer for free (¬c). The consistency of the above knowledge base is thus chal-
lenged. To keep this knowledge base consistent, John needs to revise it. For example,
simply retracting a will retain consistency when ¬c is added. Actually, removing any
belief that is above the horizontal line in Table 2.2 will recover a consistent knowledge
base. Questions are, shall we remove all beliefs or just some/one of them? If not all
beliefs, then which one should be given up and which should be kept?
2.2.3 Three Issues of Belief Revision
Although simple, the above two examples do illustrate important issues associated
with belief revision. Most commonly, a development of a new belief revision mecha-
nism needs to address the following three key issues.
23
1) How are the beliefs in the database represented?
In our examples, beliefs are represented in the simplest and most intuitive way,
by sentences. There are other options available, such as possible worlds (also
called interpretations); one may also use mathematical frameworks such as prob-
ability theory for a quantitative representation, or possibility theory or belief
functions for a comparatively qualitative representation. Different schemes of
representation will be introduced in the sections that follow.
Clearly, a belief revision mechanism is sensitive to the formalism chosen to rep-
resent the beliefs. Whatever belief representation models a revision system may
choose, it satisfies the following Principle of Categorical Matching (PCM)[42],
The representation of a belief state after a belief change has taken
place should be of the same format as the representation of the belief
state before the change.
In other words, belief change happens within the formalism of representing the
beliefs but shall not change it.
2) What is the relation between the elements explicitly represented in the database
and the beliefs that may be derived from these elements?
This issue occurs when choosing sentences as the representation formalism.
Which sentences should we assume to be explicitly stored in an agent’s knowl-
edge base? What do we do with the logical consequence of a set of sentences?
Basically, there are two school of thought, one school prefers to take both the set
of sentences and its logical consequences (so-called belief set) into consideration,
the other prefers to operate on the explicitly stored sentences only (so-called
24
belief base) and resorts to some external logic to further the deduction. There
are pros and cons for both option.
Belief set representation requires an agent to be logical omniscient, i.e., it not
only knows its explicit beliefs, but also all their logical consequences. This is
an ideal case and good for investigating theoretical issues. The most important
contribution to the belief revision field - the AGM framework (more in section
3.1 - is based on this representation.
Let L denote a countable language which is closed under a complete set of
Boolean Connectives. We will denote sentences in L by lower case Greek letters.
We assume L is governed by a logic that is identified with its consequence
relation ⊢, that is, a sentence α is logically valid iff it is a consequence of the
empty set. The relation ⊢ is assumed to satisfy the following conditions[41]:
(a) If α is a truth-functional tautology, then ⊢ α.
(b) Modus ponens. If α ⊢ β and ⊢ α, then ⊢ β.
(c) Not ⊢⊥. That is, ⊢ is consistent.
(d) Satisfies the deduction theorem. That is, ⊢ α → β iff α ⊢ β).
(e) Is compact. That is, if α is a consequence of some set X, then α is a
consequence of some finite subset of X.
It follows that ⊢ contains classical propositional logic.
The belief base approach has been criticised as syntax sensitive[12], which is
not desirable for rational changes. For example, consider a belief base B1 =
{α, β}. In order to retract α ∨ β, both α and β have to be retracted. But after
25
adding α ∨ β back again, we don’t get back α and β. But if we represent the
belief base as B2 = {α, β, α ∨ ¬β, ¬α ∨ β}, retract α ∨ β and add it back we will
obtain α and β by logical deductions. Note that B1 and B2 generate the same
belief set.
However, the representation of belief sets requires double-exponential (for propo-
sitional logic) or infinite (for first-order logic) space. Computationally, belief
bases are a more appealing representation as compared to belief sets. Section
3.4 focuses on rational base revision.
3) How are the choices concerning what beliefs to retract made?
Retraction always involves more than one sentence as shown in the Air Kanga-
roo example. The guiding criterion adopted by most researchers is the principle
of minimal change. By specifying an underlying preference relation defined on
either sentences or possible worlds, one can express that a sentence (world) is
more preferable than another in the face of change. The preference relation can
either be a purely subjective preference such as Epistemic Entrenchment Order-
ing advocated by Gärdenfors et al. [40], or it might possess some mathematical
meaning such as probability, possibility and belief function.
2.3 Belief Revision as an Epistemological Theory
The theoretical framework that provides a conceptual apparatus for investigating
problems about changes of knowledge and belief, is called an epistemological theory[41].
The following four epistemic factors are the essential characteristics that form the core
of epistemological theories:
26
2.3.1 Four elements of an epistemological theory
Belief State
The first and most fundamental characteristic is a class of models of epistemic states
or states of belief. An epistemic state is a representation of a person’s knowledge and
belief at a certain point of time, for example, John’s state of belief at the moment he
discovered that Air Kangaroo does not serve free beer. 3
Epistemic states are the central entities in epistemological theories. Different
models of epistemic states often determine the representation of the other three core
entities.
Here three popular approaches are briefly outlined to illustrate the different ways
of representing epistemic states, which paves the way for introducing different types
of belief revision techniques.
According to Gärdenfors[41], the best-known approaches are the Bayesian models
which are widely used in decision theory and game theory. It is assumed in Bayesian
theory that all information that is relevant for decision making is conveyed by a
probability measure, which is defined over some object language or over some space
of events.
In such approaches, a state of belief is represented by a probability measure. A
dominant rationality criterion governing this type of model is that of coherence.
A second kind of approach represents an epistemic state as a set of propositions,
3 The epistemic states here are not seen as psychological states. This means that a state in a
computer program may also be seen as a model of an epistemic state.
27
expressed by sentences from some given object language 4 . Such approaches are cer-
tainly simpler than Bayesian approaches but also less informative (see the epistemic
attitudes that are representable in the two kinds of models). An epistemic state
contains those propositions that the agent accepts at a certain point of time. The
essential rationality criterion for such models is consistency. Logical omniscience is
also often assumed in the sense that the set of propositions representing an epistemic
state is supposed to be closed under logical consequences.
A third way of representing epistemic states is by a set of possible worlds. The
interpretation of such a set is that the agent associated with the state knows that the
“actual world” is a member of a set of possible worlds, and that any world in the set
could be the actual one, i.e. they are all consistent with his beliefs.
In the approaches based on sets of propositions, the valuation is given by a mem-
bership relation; and in probabilistic models the valuation is given by a probability
measure.
Epistemic Attitude
A second characteristic of an epistemological theory is a classification of the epistemic
attitudes that describe the status of various elements of belief that are contained in
an epistemic state. For example, a person may accept or not accept a particular fact
as true or he may judge it to be certain, probable, or possible. These are different
attitudes toward the same fact.
In an epistemic state based on a set of sentences, one can distinguish three different
kinds of belief:
4 One may differentiate propositions from sentences if needed: propositions are the contents of the
sentences, ie, propositions concern the semantic of the sentences, while sentences are the syntactic
representation.
28
1. A proposition α may be accepted, which means that α belongs to the set repre-
senting the epistemic state;
2. α may be rejected, which is to say that the negation of α is accepted in the
state;
3. α may be kept in suspense or undetermined, which means that neither α nor its
negation is an element of the relevant set of sentences.
In a model of an epistemic state based on a probability measure P, a richer typology
of beliefs is possible: one may say that a sentence α is more probable than β, meaning
that P (α) > P (β); that α is likely, meaning that P (α) > 0.5, and so on. In this
type of model we can also say that α is accepted if P (α) = 1 and similarly that α is
rejected if P (α) = 0 and undetermined if 0 < P (α) < 1.
Epistemic Inputs
A third characteristic is an account of the epistemic inputs that may lead to changes
of epistemic states. These inputs can be thought of as the deliverance of experience
or as linguistic (or other symbolic) information provided by other individuals (or
machines). For example, when John discovered that Air Kangaroo doesn’t serve free
beer, this observation served as an epistemic input that lead to a revision of his state
of belief.
Epistemic Changes
A fourth characteristic involves a classification of epistemic changes or changes of
belief. Different kinds of epistemic input result in different types of change in the
29
epistemic states. The most important epistemic changes are expansions, revisions,
and contractions, which we will discuss further in Section 3.1.
2.3.2 Information Economy and Criteria of Rationality
In addition to the above four characteristics, on the meta-level, an epistemological
theory should also contain criteria of rationality, which are used for evaluating the
above four factors.
As we know, epistemic states are used for representing an actual or a possible
cognitive state of some individual at a given point of time. One can think of the
idealised epistemic states as being equilibrium states. For example, if a set of beliefs
is not consistent or if a probability assignment to a field of beliefs is not coherent,
then the individual should, if it is to fulfill the rationality criteria, adjust the state
of belief until it reaches an equilibrium that satisfies the criteria of consistency or
coherence. To achieve a consistent belief set or a coherent probability assignment is
the driving force of belief revision and also the fundamental rationality criteria.
On the other hand, information is in general not gratuitous, and unnecessary losses
of information are therefore to be avoided. When we change our beliefs, we want to
retain as much as possible of our old beliefs. This heuristic criterion is called the
criterion of informational economy, which guides the selection of change operators.
This criterion is used to evaluate the changes of belief in the AGM paradigm and is
called the principle of minimal change, that is, the change is required to be minimal
such that it accommodates the epistemic input which initiates the change. It can
been seen in Section 3.1 that the minimal change criterion is main driver behind the
AGM postulates.
30
Different interpretations of the minimal change principle appear in the litera-
tures, such as absolute minimal change due to Williams[108], relative minimal change
(conditionalization) due to Sphon[100]. Williams[111] furthers the understanding of
minimal change while bearing the preference relation in mind. According to her, the
principle of minimal change says that, as much information should be conserved as
is possible in accordance with an underlying preference relation. In this sense, the
number of sentences to be given up is not necessarily the rational measure of the
magnitude of the change. For example, rational agents might choose to throw out
several weakly believed sentences to achieve consistency rather than throw out one
that is very strongly believed. The question of explicitly defining a rational minimal
change is still open and is often related to the application domain in practice.
31
Chapter 3
Belief Revision Techniques under
the AGM Paradigm
“Beliefs
The bird caught in the trap is a swan
The bird caught in the trap comes from Sweden
Sweden is part of Europe
All European swans are white
Consequences
The bird caught in the trap is white
New Information
The bird caught in the trap is black
Which sentence(s) would you give up?”
— Peter Gärdenfors and Hans Rott (1995) in [42]
3.1 The AGM Postulates and Belief Set Revision
A major source of inspiration that has made belief revision theory one of the most
active research areas in philosophical logic is the development and investigation of two
sets of postulates in a 1985 paper[1] by Alchourrón, Gädenfors, and Makinson(AGM).
Named after their founders, the postulates (one set for revision, the other for con-
traction) 1 are often called the AGM postulates.
1 For the sake of completion, in Section 3.1.1 we listed the AGM postulates for expansion as well.
32
In the AGM paradigm, an agent’s epistemic states (or belief states) are represented
by a deductively closed set (K) of sentences, i.e. a belief set or a theory. The logic
governing the deduction is ⊢ as defined in Section 2.2.3. The changes to the epistemic
state are thus modelled as processes involving the addition and removal of sentences.
Please note, the AGM belief change and the other change operations discussed in
this thesis do not consider the possibility of explicitly modifying individual facts. For
example, weakening the following sentence:
into
All Australian startup airlines serve free beer.
All Australian startup airlines except Air Kangaroo serve free beer.
will not be considered. For recent work on weakening beliefs in belief bases, see [6].
In AGM’s 1988 paper [40], the three kinds of theory change that were introduced
informally in section 2.2 are described as follows:
1)Expansion: A new sentence together with its logical consequences is added
to a theory K regardless of the consequences of the larger set formed, i.e. the
resulted set is not necessarily consistent. The theory that results from expanding
K by a sentence α will be denoted K + α .
2)Revision: A new sentence, possibly inconsistent with the theory K is added,
but in order that the resulting theory be consistent some of the sentences in K
are removed. The result of revising K by a sentence α will be denoted K ∗ α
3)Contraction: Some sentence in K is retracted without adding any new facts.
In order that the resulting system satisfies (I) some other sentences from K must
be given up. The result of contracting K with respect to the sentence α will be
33
denoted K − α .
The above description illustrates the AGM’s fundamental view of the theory change
problem. That is, computationally, theory change can be handled by a function which
maps a belief set K and a sentence α to a new belief set K + α (or K ∗ α or K − α ). Re-
spectively, we have for such purposes, expansion functions, revision functions and
contraction functions. Therefore, the ultimate goal of belief change is to develop
algorithms for computing appropriate revision and contraction functions for an arbi-
trary theories. Sets of postulates presented were developed and first introduced in
[1], which serves as the standard that the candidate change functions should comply
with. In the following subsections, the postulates are listed and briefly discussed.
3.1.1 Postulates for Expansion
(K + 1) K + α is a belief set. (Closure)
Expansion functions should take one belief set to another when new information
α is introduced and in so doing abide by the principle of categorical matching.
(K + 2) α ∈ K + α (Success)
The epistemic input should be accepted. Note the resulting belief set could be
inconsistent.
(K + 3) K ⊆ K + α . (Informational Economy)
As information is valuable, all the old beliefs should be retained in the expansion
of K by α.
(K + 4) If α ∈ K, K + α = K is a belief set.
34
If α is already accepted in K, a requirement to accept α should have no effect
on the belief state.
(K + 5) If K ⊆ H, then K + α ⊆ H + α (Monotonicity 2 )
K + α should not contain any beliefs that are not also included in H + α .
(K + 6) For all belief sets K and all sentences α, K + α is the smallest belief set
that satisfies (K + 1)-(K + 5).
It turns out that the expansion function (+) satisfies (K + 1)-(K + 5) iff K + α =
Cn(K) ∪ α.
An important result from the above is that the expansion postulates (K + 1)-(K + 5)
uniquely determine the expansion of K by α as the set of all logical consequences of
K together with α. In other words, there is an unique expansion function Cn(K∪{α})
that satisfies the AGM expansion postulates.
But as will be shown in the following sections, using the postulates presented below
alone will not guarantee an unique function for revision (contraction). This brings
us to the fore the third issue we discussed in Section 2.2.3. Extra logical information
will be required to help single out one revision (contraction) function. Two standard
ways of doing that will be introduced in Section 3.3.
3.1.2 Postulates for Revision
(K ∗ 1) K ∗ α is a belief set. (Closure)
The revision operators take one belief set to another when new possibly con-
flicting information is incorporated.
2 An inference operation or logic Cn is monotonic iff H ⊆ H ′
it is nonmonotonic.
35
implies Cn(H) ⊆ Cn(H ′
). Otherwise
(K ∗ 2) α ∈ K ∗ α (Success)
It guarantees that the epistemic input α is accepted in K ∗ α.
(K ∗ 3) K ∗ α ⊆ K + α (Expansion 1)
(K ∗ 4) If ¬α �∈ K, then K + α ⊆ K ∗ α (Expansion 2)
(K ∗ 3) and (K ∗ 4) together say that in the consistent case, revision is equivalent
to expansion.
(K ∗ 5) K ∗ α = K⊥ only if ⊢ ¬α (Consistency preservation)
The purpose of revision is to produce a new consistent belief set. Thus K ∗ α
should be consistent, unless α is logically inconsistent itself.
(K ∗ 6) If ⊢ α ↔ β, then K ∗ α = K ∗ β (Extensionality)
Logically equivalent sentences should lead to identical revisions. Shown in the
Raining and Umbrella Example in Section 2.2.1. In other words revision is
syntax insensitive.
(K ∗ 7) K ∗ α∧β ⊆ (K ∗ α) + β
(Conjunction 1)
It is shown in [40] that (K ∗ 7) is equivalent to K ∗ α ∩ K ∗ β ⊆ K ∗ α∨β
(K ∗ 8) If ¬β �∈ K ∗ α, then (K ∗ α) + β ⊆ K∗ α∧β (Conjunction 2, Rational Monotony)
(K ∗ 2) is often called “Priority of the New Information” by some researchers (e.g.
Dragoni[19]). It is sometimes criticised as an unfavourable property in an open envi-
ronment where information may come from multiple sources with various reliability.
We argue that taking postulate (K ∗ 2) as giving priority to the new information is a
misconception. In an open environment, where information may need to be judged
36
according to the source reliability, belief revision should be treated as a two step
process. Firstly, the agent needs to make a decision about whether to accept the new
information or not, or accept with a certain degree of plausibility. Then, in the second
step, if the agent decides to accept the new information, postulate (K ∗ 2) becomes
applicable. This can be illustrated by the example in Section 2.2.1. Before John
changes his current beliefs, he normally will give it a second thought to see whether
the information source is trustworthy or not (maybe the source is only joking about
the matter). In other words, the raw information from the source will be filtered
prior to the revision of the epistemic state. If the source is trustworthy, John will
then apply existing belief revision techniques to revise his belief state.
However, Benferhat[4] has a valid argument when considering revision as a special
process of fusion. He supports the idea that a fusion process is symmetric as opposed
to a revision process where the new information is prioritised. As a result, in fusion,
the new information may not necessarily be accepted in the result belief set.
3.1.3 Postulates for Contraction
(K − 1) K − α is a belief set.(Closure)
Contraction functions take a belief set to another with the concerned informa-
tion to be retracted.
(K − 2) K − α ⊆ K (Inclusion)
The sentence to be retracted should not be in K − α .
(K − 3) If α �∈ K, then K − α = K (Vacuity)
If α is not in K, nothing should be retracted from K, and all the existing beliefs
37
should be left unchanged, according to minimal change criterion.
(K − 4) If not ⊢ α, then α �∈⊆ K − α (Success)
Contraction is successful when the sentence to be retracted is no longer a logical
consequence of the new belief state K − α unless α is a tautology, in which case it
can never be removed.
(K − 5) If α ∈ K, then K ⊆ (K − α ) + α (Recovery)
This requires that all beliefs in K are recovered after first contracting and then
expanding with respect to the same belief.
(K − 6) If ⊢ α ↔ β, then K − α = K − β (Extensionality)
Logically equivalent sentences should lead to identical contractions, same moti-
vation as in (K ∗ 6).
(K − 7) K − α ∩ K − β ⊆ K− α∧β
(Conjunction 1)
The beliefs that are in both K − α and K − β are also in K− α∧β .
(K − 8) If α �∈ K − α∧β , then (K− α∧β ) ⊆ K− α (Conjunction 2, Rational Monotony)
The minimal change necessary to give up α ∧ β is closely related to the minimal
change necessary to reject α itself.
Recovery (K − 5) is the most controversial postulate of all. Although it is a valid
principle in non-probabilistic contexts for belief set revisions. It is questionable in
probabilistic contexts, especially in the case of contracting a sentence that has causal
consequences. It is also questionable in the context of base revision as shown in
Section 2.2.3. For detail discussion on the recovery postulate in base revision, see
[55].
38
3.2 Levi Identity and Harper Identity:
From Revision to Contraction and Vice Versa
It is widely accepted that [1, 73, 38] contraction operators and revision operators are
inter-definable. A revision of a belief set can be seen as a composition of a contraction
and an expansion, this is known as the Levi Identity, formally written as:
K ∗ α = (K − α ) + α
On the other hand, a contraction operator can be defined using a revision operator,
this is known as the Harper Identity, below,
K − α = K ∩ K ∗ ¬α
3.3 Determining the Sentences to be Retracted
On seeing that the AGM expansion postulates uniquely define an expansion operator
K + α = Cn(K ∪ {α}), one may wonder whether a unique revision and contraction op-
erator will be circumscribed by the corresponding revision and contraction postulates
or not. Unfortunately, it turns out that both contraction and revision are nonunique
operations. This is due to the fact that they both involve the retraction of informa-
tion, which in general presents a nonunique choice when determining which sentence
is to be given up.
Pure logical and set theoretical information is not sufficient and extralogical infor-
mation is needed for singling out a unique revision or contraction function[40, 106].
A variety of mechanisms for selecting what to retract have been tried. Some of these
mechanisms select among all the maximal consistent subsets with respect to K and
39
α, others among the possible worlds or models - the semantic extension of the con-
cerned set of sentences[45]. Some select among the candidates for deletion, others
among candidates for being retained. Some select by means of a choice function,
others select by preference orderings (unit intervals [0,1] or ordinals). Among these,
two prevailing ordering mechanisms are AGM’s epistemic entrenchment orderings[40]
and Grove’s systems of spheres[45]. They are briefly described in this section.
3.3.1 Epistemic Entrenchment Ordering
An epistemic entrenchment ordering is intended to capture the importance of a sen-
tence in the face of change. Given a belief set K of L, an epistemic entrenchment
related to K is any binary relation ≤ on L satisfying (EE1)-(EE5) below:
(EE1) For any α, β, and γ, if α ≤ β and β ≤ γ, then α ≤ γ. (Transitivity)
(EE2) For any α and β, if α ⊢ β, then α ≤ β. (Dominance)
(EE3) For all α, β ∈ K, if α ⊢ β then α ≤ β. (Conjunctiveness)
(EE4) When K �= K⊥, α �∈ K iff α ≤ β for all β. (Minimality)
(EE5) If β ≤ α for all β, then ⊢ α. (Maximality)
The notation α ≤ β is a shorthand for ‘β is at least as epistemologically entrenched
as α’. (EE1) requires the ordering relation ≤ to be transitive. (EE2) says that if α
entails β and either α or β must be retracted from the belief set K, then it is a smaller
change to give up α and retain β rather than to give up β, because then α must also
be retracted if we want the revised theory to be closed under logical consequences.
(EE3) prescribes that retracting α ∧ β from the belief set K can be achieved only by
40
giving up either α or β, but not necessarily both. (EE4) states that sentences that
are not in belief set K are the least entrenched and thus minimal in the ordering ≤.
Similarly, (EE5) simply says that only tautologies can be maximal in the ordering ≤.
Gärdenfors and Makinson[40] have shown that for every contraction operator −
there exists an epistemic entrenchment ≤ related to K such that the condition E −
below, is true for every α ∈ L, and conversely.
(E − ) K − α =
3.3.2 System of Spheres
� {β ∈ K : α < α ∨ β} if �⊢ α
K otherwise
In contrast to an epistemic entrenchment ordering, where the ordering is defined on
sentences, Grove’s system of spheres[45] focuses on the set Ω of possible worlds that
can be described in a language L. Any belief set K can be represented by the subset
[K] of Ω that consists of all possible worlds that contain the sentences in K.
A system of spheres centered on [K] [45] is a collection S of subsets of Ω that
satisfies the following conditions:
(S1) S is totally ordered by ⊆; that is, if S and S ′ are in S, then S ⊆ S ′ or
S ′ ⊆ S.
(S2) K is the ⊆-minimum of S; that is, if [K] ∈S, and, if S ∈S, then K ⊆ S.
(S3) Ω is in S and so the largest element of S.
(S4) If α is a sentence and there is any sphere is S intersecting [α], then there
is a smallest sphere in [S] intersecting [α].
41
[K]
S α
C( α)
Figure 3.1: System of Spheres Centered on [K]
Condition (S4) ensures that for any sentence α, if [α] intersects any sphere at all
in S, there is some sphere Sα that intersects [α] and is smaller than any other sphere
with this property. If [α]=∅ and does not intersect any sphere, then Sα = Ω. The set
C(α) = [α] ∩ Sα is the set of “closest” element in Ω to [K] in which α is an element.
The set C(α) is marked as the hatched area in Figure 3.1, which is adapted from
Figure 4.2 on page 85 in [41].
Grove[45] proves that
Definition 3.3.1. Let S be any system of spheres in M centered on [K] for some
belief set K. If, for any α, K ∗ α is defined to be KC(α), where KC(α) is the belief set
represented by set C(α) of possible worlds, KC(α) = ∩C(α). The resulting revision
function satisfies (K ∗ 1) − (K ∗ 8). Conversely, let ∗ be any revision function satisfying
(K ∗ 1) − (K ∗ 8). Then for any (fixed) belief set K there is a system S of spheres that
is centered on K and that satisfies K ∗ α = KC(α).
The key idea Grove presents is that the revision K ∗ α can be represented by KC(α),
which is the belief set represented by the set C(α) of worlds. That is, the following
condition (S ∗ ) can be used to construct a revision function from a system of spheres.
S'
S
[S]
[ α]
42
(S ∗ ) K ∗ α =
3.3.3 Other Important Works
� ∩C(α) if α is consistent
⊥ otherwise
Due to its simplicity, the AGM framework has inspired a lot of significant work
in the area of belief change. Among others, there is Peppas’[94] contribution of
identifying the class of well-behaved revision operators based on a well-ordered system
of spheres. Furthermore, Peppas and Williams[95] identify another representation – a
nice preorder on models and importantly they prove that under condition (ES) below,
an epistemic entrenchment, a system of spheres and a nice pre-order represent the
same revision function:
(ES) For every consistent φ, ψ ∈ L such that �⊢ φ and �⊢ ψ, φ ≤ ψ if
and only if C(¬φ) ⊆ C(¬ψ)
where C(φ) represents the smallest sphere in S intersecting [φ].
In terms of implementing a revision system, epistemic entrenchment orderings
have better computational properties than pre-orders on models for large knowledge
bases since the number of possible worlds are exponential in the size of sentences.
Consequently it is considered as a practical way of representing preference of epis-
temic states in a computing system. However, such choice is particularly domain
and application dependent. An example of implementing a system of spheres using
database technology is described by Williams in [111].
In addition to the ordering techniques stemming from an epistemic entrenchment
ordering and a system of spheres, which we call qualitative rankings, there are quanti-
tative orderings for specifying orderings between epistemic states based on probability
43
theory, belief functions or possibility theory, which will be introduced in Chapter 4.
The AGM paradigm provides an elegant general framework for describing revision
and contraction operators. However, two major problems arise when using it as a
foundation theory for a computer-based implementation of belief revision[105].
• The epistemic entrenchment orderings operate on belief sets, which requires an
ideal agent who knows all the logical consequences of his current beliefs. The
epistemic state thus represented by belief sets may be infinite in size, while a
computer implementation needs a finite representation.
• As AGM operators map epistemic entrenchment orderings of a belief set to a
new belief set, there is no specification of an entrenchment ordering of the re-
sulting set. Although this contributes to the flexibility of the AGM framework,
it presents difficulties when iterated revision is desired in an implementation.
Therefore, a means of propagating an epistemic entrenchment ordering to an-
other is needed.
Extensions to the AGM framework that address these problems can be found in
works on iterated revision[72], works on belief base change [105] and some combination
of the two [108].
3.4 Implementing Entrenchment Based Revision -
Belief Base Revision
Just as a theory does not uniquely determine a theory change operator, so too a theory
base does not uniquely determine a theory base change operator. In the case of theory
change additional structure in the form of an epistemic entrenchment ordering is used
44
to construct unique operators, and for theory base change Williams proposed finite
partial entrenchment rankings [105, 111].
3.4.1 Finite Partial Epistemic Rankings
A finite partial entrenchment ranking maps a finite set of sentences to rational num-
bers in the interval [0,1]. The higher the value assigned to a sentence the more
entrenched it is. Not like an epistemic entrenchment ordering which ranks a possible
infinite belief set, formally defined below, it grades the content of a finite belief base
according to its epistemic importance.
Definition: A finite partial entrenchment ranking is a function B from
a finite subset of sentences into the interval [0,1] such that the following
conditions are satisfied for all φ ∈ L:
(PER1) {φ ∈ L : B(φ) < B(ψ)} �⊢ φ.
(PER2) If ⊢ ¬φ, then B(φ) = 0.
(PER3) B(φ) = 1 if and only if ⊢ φ.
(PER1) is actually a reformulation of (EE2), and says that one should not assign
a higher value to an arbitrary sentence ψ than that of φ if ψ ⊢ φ.
(PER2) and (PER3) simply say that inconsistent sentences are assigned zero while
tautologies are assigned 1.
As noted before, a finite partial entrenchment ranking is an ordering of explicit
beliefs that explicitly represent a knowledge base, denoted by Kexp. A belief set is
the logical consequences of the explicit belief, the set of implicit beliefs, which is
denoted by Kimp. The major contribution of Williams’ work is that she defines a way
45
of ranking implicit beliefs based on (PER1) such that a finite partial entrenchment
ranking can be used to represent a finitely representable epistemic entrenchment
ordering 3 . Intuitively, beliefs that are not in the implicit belief set take the lowest
degree of acceptance in face of change, 0 in this case. On the other hand, a sentence
φ in the implicit belief set should be accepted at a degree no lower than its most
accepted precedent (i.e. the belief that entails φ). The ranking on implicit beliefs can
be formally captured in the definition of the function degree(B, φ) below.
Definition 3.4.1. Let φ be a nontautological sentence. Let B be a finite partial
entrenchment ranking. The degree of acceptance of φ is defined to be:
degree(B, φ) =
� max(B(ψ)), ψ ∈ Kexp ∩ {ψ : ψ ⊢ φ} if φ ∈ Kimp
0 otherwise
Williams[105] proves that a minimal epistemic entrenchment ordering ≤B can be
generated from a finite partial entrenchment ranking B if following the definition
holds:
φ ≤B ψ iff ⊢ ψ, or degree(B, φ) ≤ degree(B, ψ)
It is minimal in the sense that sentences take their minimal value in the order-
ing and sentences that are not in the implicit belief base Kimp will take a minimal
entrenchment 0.
3.4.2 Transmutations
As we can see from the revision techniques we introduced before, an epistemic en-
trenchment ordering is an integral part of an agent’s epistemic state and it is the
crucial information for identifying a unique revision operator. Therefore, the term
3 For the condition on an epistemic entrenchment ordering to be finitely representable, see
Williams’ [105].
46
knowledge system is introduced to take into account the information presented by
an epistemic entrenchment ordering. A knowledge system differs from a belief set in
the sense that a knowledge system contains not only the sentences as beliefs but also
their epistemic entrenchment as extralogical information about relative importance
of beliefs in the face of change. To facilitate iterated revision, belief revision is viewed
as a transformation of a knowledge system to another knowledge system rather than
that of a belief set to another belief set.
Spohn[100] presents a knowledge system as an ordinal conditional function that
maps the set of all consistent and complete theories 4 into the class of ordinals such
that there is a possible world assigned the smallest ordinal 0, which is interpreted as
an accepted world. An ordinal conditional function represents a plausibility grading
of possible worlds or a grading of disbelief, the worlds that are assigned the smallest
ordinal are the most plausible. Belief change in such a system is realised through
transmutations on ordinal conditional functions. Through transmutations, the order-
ing on the possible worlds is propagated into the new epistemic state when new in-
formation is incorporated. Among the family of transmutation operators, Spohn[100]
claims that conditionalisation is a desirable transmutation because the worlds which
are consistent with the new information and those which are not are shifted in relation
to one another.
Close to the idea of ordinal conditional functions[100], where an ordinal is as-
signed to a possible world, Williams proposes the idea of transmutations on partial
entrenchment rankings[108]. Different transmutation strategies are developed and
proposed based on different interpretations of the “minimal change” criterion. Two
4 For definitions on consistent and complete theory, see Appendix A
47
of the major types of transmutation are, adjustment, maxi-adjustment, and disjunc-
tive maxi-adjustment[6].
Here we briefly introduce the process of adjustment to illustrate a basic idea of
how to transmute one partial entrenchment ranking into another.
Adjustments define change functions for belief bases rather than belief sets, which
makes it computationally attractive for real world applications. Intuitively, an (φ, i)-
adjustment of B involves minimal changes to B such that φ is accepted with degree
i. In particular, each sentence ψ ∈ Kexp is reassigned a number B ∗ (φ, i)(ψ) closest
to its original B(ψ). This is guided by the principle that if an accepted sentence φ is
reduced to a degree i, each sentence that would be retracted in φ’s contraction will
be reduced to i as well. Formally, the definition of adjustment is as follows,
Definition 3.4.2. Let φ ∈ L and 0 ≤ i < 1. The adjustment of a finite partial
entrenchment ranking B is defined to be a function ∗ such that
B ∗ (φ, i) =
where for all ψ ∈ Kexp,
�
(B − (φ, i)) if i ≤ degree(B, φ)
(B − (¬φ, 0)) + (φ, i) otherwise
B − �
i, if degree(B, φ) = degree(B, φ ∨ ψ) and B(ψ) > i
(φ, i)(ψ) =
B(ψ) otherwise
and for all ψ ∈ Kexp ∪ {φ},
B + ⎧
⎪⎨ B(ψ) if B(ψ) > i
(φ, i)(ψ) = i if φ ↔ ψ or B(ψ) ≤ i < degree(B, φ → ψ)
⎪⎩
degree(B, φ → ψ) otherwise
For example, if B(ψ → φ) = 0.7, B(φ → ψ) = 0.6 and B(ψ) = 0.5, using the
definition above, the degree of implicit information φ is 0.5.
If we want to accept φ at a lower degree i = 0.2, we will have the new partial
entrenchment ranking, where B(ψ → φ) = 0.7, B(φ → ψ) = 0.6, B(φ) = 0.2 and
B(ψ) = 0.2. ψ migrate down the ranking.
48
If we want to accept φ at a greater degree say i = 0.5, we will have B(ψ → φ) = 0.7,
B(φ → ψ) = 0.6, B(ψ) = 0.5 and B(φ) = 0.5.
If we want to accept φ at a greater degree say i = 0.7, we will have B(ψ → φ) = 0.7,
B(φ → ψ) = 0.6, B(ψ) = 0.7 and B(φ) = 0.7.
The guiding principle here is actually (EE2), no matter how the new entrench-
ment is generated, the logical consequence should be at least as entrenched as its
precedent. As we can see from the above example, to obtain a successful (φ, i)-
adjustment, one must explicitly specify the ranking for both ψ → φ and φ → ψ, that
is specify the degree of independence (φ ∨ ψ) between sentences, which is not as nat-
ural and easy as specifying dependence. To address this problem, Williams proposed
maxi-adjustment[111], where information independence is assumed by default unless
dependence is derivable from the explicitly specified information. This is based on
Spohnian reasons[100], where α is reason for β iff raising the epistemic rank of α
would raise the epistemic rank of β. A maxi-adjustment is done by specifying reasons
and during the contraction of α, β is retained if β can not be derived as a reason
for α. Readers are referred to [110, 111] for the definition of maxi-adjustment and
related algorithms.
It is worthwhile to point out that both adjustment and maxi-adjustment satisfy
the AGM postulates. If only a base is used then extra processing is needed to satisfy
recovery.
Promisingly, adjustment and maxi-adjustment, and other transmutation strategies
are implemented in an object-oriented web based belief revision system, SATEN. For
details, see [107]. Actually, the work presented in this thesis builds on SATEN as
a single belief revision agent which provides the platform to study the issues that
49
might be presented in an open heterogenous multi-agent environment, where agents
can interact and exchanging information with other agents. The result of our study is
a theoretical and practical framework for extending SATEN into a multi-agent belief
revision test-bed.
50
Chapter 4
Belief Revision - The Probability
and The Possibility Approach
“The actual science of logic is conversant at present only with things either
certain, impossible, or entirely doubtful, none of which (fortunately) we
have to reason on. Therefore the true logic for this world is the calculus
of probabilities, which takes account of the magnitude of the probability
which is, or ought to be, in a reasonable man’s mind.”
4.1 Introduction
— James Clerk Maxwell (1850)
Gärdenfors [41] points out rather convincingly that the change of an epistemic state
can be defined in the framework of logic as well as in traditional probability theory.
As recognised by Dubios and Prade [24], this creates an exciting interaction between
different fields, in particular, logic, probability theory, belief functions, possibility
theory and more recently plausibility theory[35]. When it comes to devising ratio-
nal change operators, these different theories fit into the epistemological framework
51
described in Section 2.3 rather nicely. The pure logic framework may limit the rep-
resentational power to accepted, rejected and indetermined, while the probability-like
theories are more expressive, for example, one can represent complete ignorance, one
can also express that α is more probable/possible/plausible than β, which is achieved
at the price of working out a quantitative rather than a qualitative representation of
an agent’s belief state.
A brief introduction to probability theory, possibility theory and belief functions
is given, and followed by our discussion on their inter-relationships. We show that
both probabilities and possibilities are special cases of belief functions. This will pave
the way to out ontological 1 view of the field.
4.2 Probability Theory
Subjective or personalistic probabilities are the best known models of epistemic states
and of how epistemic inputs affect an epistemic state[41], which is widely used in
decision making and game theory. The epistemic states in a probability theory can
be represented by either sentences or possible worlds. A probability function defined
over these sentences or possible worlds provides a measure of an individual’s degree of
belief in the sentence or propositions, which enriches the epistemic attitude that can
be represented in this model. As shown in Section 2.3, Gärdenfors takes a slightly
different view, he considers the probability measure itself to be a representation of
the belief state. In contrast, we would rather take the sentences or possible worlds as
the model of an individual’s epistemic state and the probability measures as a means
of expressing a richer epistemic attitude. Actually, from the previous discussion, we
1 Ontologies will be discussed in Chapter 6
52
agree that a successful unique change operator relies on some means of ranking, be
it an epistemic entrenchment ordering, or a systems of sphere, or some other ranking
mechanisms. This suggests the ranking among sentences (or possible worlds) is an
inseparable element of an epistemological theory as far as belief change is concerned.
In fact, we are inclined to treat the ranking which expresses the epistemic importance
with respect to the new information as an integral part of an individual’s epistemic
attitude.
A probability space (S, X , P r) consists of a set S (the sample space), a set X
of subset of S whose elements are called measurable sets and a probability measure
P r : X → [0, 1], satisfying the following properties (known as the Kolmogorov axioms
for probability):
P1. 0 ≤ P r(X) ≤ 1 for all X ∈ X
P2. P r(S) = 1
P3. P r(∪ ∞ i=1Xi) = � ∞ i=1 P r(Xi), if the Xis are pairwise disjoint members of X .
(Countable Additivity)
Definition 4.2.1. A subset Y of X is said to be a basis of X if the members of Y are
non-empty and disjoint, and if X consists precisely of countable unions of members
of Y.
The probability of every measurable set can be computed from the probability of
every set in its basis by using P3. It is not hard to see that if X is finite then it has
a unique basis, which consists precisely of the minimal elements of X .
The above definition is defined on sets, to extend probability theory for logical
sentences, Stalnaker(1970)[101] provides this language based definition on probability
functions:
53
Definition 4.2.2. A (language-based) probability function is a function P from sentences
in L into real numbers that meets the following six conditions for all sentences
α,β, and γ:
(I) 0 ≤ P r(α) ≤ 1
(II) P r(α) = P r(α ∧ α) (Reflexivity)
(III) P r(α ∧ β) = P r(β ∧ α) (Commutativity)
(IV) P r(α ∧ (β ∧ γ)) = P r((α ∧ β) ∧ γ) (Associativity)
(V) P r(α) + P r(¬α) = 1
(VI) P r(α) = P r(α ∧ β) + P r(α ∧ ¬β)
Using the language-based Definition 4.2.2, a logic for L can be defined by following
the two definitions below.
Definition 4.2.3. A sentence α is logically valid iff P r(α) = 1 for all probability
functions that satisfy conditions (i)-(vi).
Definition 4.2.4. Two sentences α and β are logically disjoint iff ¬(α∧β) is logically
valid.
From Definition 4.2.4, a theorem equivalent to P3 (Countable Additivity) can be
established for probabilities of sentences,
Theorem 4.2.1. If α and β are logically disjoint, then for any probability function
P r, P r(α ∨ β) = P r(α) + P r(β).
As we can see from above, a probability measure can be defined on not only a
set of worlds but also on a set of sentences. The probability measures thus defined
are capable of representing partial beliefs 2 . In other words, in probabilistic settings,
sentences can be believed with certain degrees of belief but not necessarily always as
certain.
2 Partial beliefs refer to the sentences that are believed at a certain degree within a unit interval
[0,1] but are not certain.
54
The rationality of belief change modelled by probability functions is governed by
the coherence restriction. Intuitively, coherence requires that the new assignment of
probabilities of the sentences in face of new information forms a standard probability
function.
Belief change in a probabilistic framework is captured by defining probability up-
date functions. A probability update function is defined as a partial function from
probability functions to probability functions, that is, if τ is a probability update
function and P r is a probability function, then τ(P r) is the probability function that
arises as a result of updating P r in the light of the new information encoded by τ.
Traditionally, the standard way to update a probability function P r is to use the
well-know Bayesian Conditioning using the conditional probability function P r(·|B),
where
P (A|B) =
P r(A ∩ B)
P r(B)
Moreover, a sequence of probability updates can be combined by composition.
The composition operator ◦ is associative, but is not in general commutative; the
order of updating matters. The result of updating by τ1, then τ2, and then τ3 can be
given by the update function τ1 ◦ τ2 ◦ τ3. The following proposition holds for Bayesian
Conditioning, cond, given that B, C ∈ X ,
condB ◦ condC = condB∩C = condC ◦ condB
For B ∈ X , condB is defined to be the probability update function such that
condB(P r) = P r(·|B) if P r is a probability function on X when P r(B) > 0, and
undefined otherwise 3 .
3 The partiality of the update function allows it to be undefined if the new information that it
55
4.3 Belief Functions
A belief function is a function that assigns to every subset of a given set S a number
between 0 and 1. The idea of a belief function was introduced by Dempster [16, 17]
and put forward as a framework for reasoning about uncertainty by Shafer [98]. It
has an attractive mathematical theory, many intuitively appealing properties, and is
widely used as a standard tool in expert system applications. For the purpose of the
work presented in this thesis, we are particularly interested in the so-called Dempster-
Shafer’s rule of combination, which is an important technique for combining and
merging knowledge bases. Here, we will briefly introduce the semantic underpinning
of belief functions and their close relationship with probability theory and possibility
theory.
Formally, a belief function can be defined as a function satisfying the axioms
below. These axioms can be viewed as a weakening of the Kolmogorov axioms that
characterise probability functions. A belief function Bel on Ω is a function Bel :
2 Ω → [0, 1] satisfying:
(B0) Bel(∅) = 0
(B1) Bel(A) ≥ 0
(B2) Bel(Ω) = 1
(B3) Bel(A1 ∪ . . . ∪ Ak) ≥ �
I⊆{1,...,k},I�=∅(−1) |I|+1 Bel(∩i∈IAi).
A more intuitive way of formulating belief functions is by defining so called mass
functions. A mass function is a function m : 2 s → [0, 1] such that
encodes is incompatible with the probability to be updated.
56
(M1) m(∅) = 0
(M2) �
A⊆Ω m(A) = 1
m(A) is interpreted as the weight of evidence for A that has not already been
assigned to some proper subset of A. Actually, a mass function and a belief function
are interdefinable.
Theorem 4.3.1 ([98]).
1. If m is a mass function on Ω,then the function Bel : 2 Ω → [0, 1] defined by
Bel(A) = �
B⊆A m(B) is a belief function.
2. If Bel is a belief function on 2 Ω and Ω is finite, then there is a unique mass
function m on 2 Ω such that Bel(A) = �
B⊆A m(B) for every subset A of Ω.
In order to combine two or more independent 4 pieces of evidence, Dempster-
Shafer’s rule of combination is widely used and shows many appealing features in
real world applications. With the restriction of confining ourselves to finite sets S,
the rule of combination can be described as follows.
If m1 and m2 are mass functions with the same domain 2 Ω , the combination of
m1 ⊕ m2 is the mass function m(A) below when there exists a pair B1, B2 such that
then
B1 ∩ B2 �= ∅ and m1(B1)m2(B2) > 0 (Combination Condition)
m(A) =
�
{B1,B2|B1∩B2=A} m1(B1)m2(B2)
�
{B1,B2|B1∩B2�=∅} m1(B1)m2(B2)
4 Independence here is taken to be an intuitive, primitive notion. The probabilistic definition
of independence - namely, that A and B are independent if P rA ∩ B = P r(A) × P r(B) - is a
consequence of the intuitive notion, but not considered as sufficient or complete definition over
it.[53]
57
If there is no such pair B1, B2 that meets the combination condition, then m1 ⊕m2
is left undefined, and the corresponding belief functions Bel1 and Bel2 are said to be
not combinable.
Using the rule of combination, Shafter shows that the update of a belief function in
the face of new information can be captured by combining the existing belief function
Bel with a single support function Learn B (A) which puts all the weights on the new
evidence B; i.e. m(B) = 1 and m(A) = 0 if A �= B. Then, we have,
Learn B (A) =
� 1 if A ⊇ B
0 otherwise
The new Bel ∗ after observing B is then Bel ⊕ Learn B . Actually the result of
the combination is equivalent to what Shafter defined as conditional belief (Bel(·||B)
which is analogous to Bayesian’s conditional probability (P r(·|B)).
Bel(A||B) = Bel(A ∪ ¯ B) − Bel( ¯ B)
1 − Bel( ¯ B)
Based on his two views of beliefs, when taking new information as a generalized
probability (c.f. an evidence). Halpern proposed another version of conditional belief
function. For those who are interested, please refer to Theorem 3.4 in his paper[53].
4.4 Possibility Theory
Possibility theory[23] is a new form of information theory which is related to, but
independent of, both fuzzy sets and probability theory. Technically, a possibility
distribution is a normal fuzzy set (at least one membership grade equals 1). For
example, all fuzzy numbers 5 are possibility distributions. However, possibility theory
5 Fuzzy sets are a further development of the mathematical concept of a set. Conventional sets
have an either-or criterion for membership, whereas fuzzy sets adopt a grade of membership[114].
58
can also be derived without reference to fuzzy sets.
The rules of possibility theory are similar to probability theory, but use either
MAX/MIN or MAX/TIMES calculus, rather than the PLUS/TIMES calculus of
probability theory.
In possibility theories, an epistemic state can be represented both semantically
and syntactically. Most appealingly, the semantic ordering on possible worlds can be
nicely translated into syntactic ordering on sentences.
The semantic representation is captured by a possibility distribution π, which
is a mapping from the set of possible worlds (Ω) to the unit interval [0, 1]. π(ω)
represents the degree of compatibility of the possible world ω with [K], the set of
possible worlds in which all sentences in K are simultaneously true. According to
Gärdenfors[41], “[K] is the largest set of possible worlds that is compatible with the
individual’s convictions.” In particular, π(ω) = 0 means that the interpretation ω is
impossible, and π(ω) = 1 means that nothing prevents ω from being the real world.
When π(ω) > π(ω ′ ), ω is a preferred candidate to ω ′ for being the real state of the
world. A possibility distribution is said to be normal if ∃ω ∈ Ω, such that π(ω) = 1
A possibility distribution π induces two different syntactical ways of ranking sen-
tences in a language, namely, the possibility measure and the necessity measure.
• A possibility measure evaluates the extent to which φ is consistent with the
available knowledge expressed by π [115]. It is defined by:
Π(φ) = max{π(ω) : ω |= φ}
Therefore, in fuzzy sets, the transition from membership to non-membership is gradual rather than
abrupt.
59
and it satisfies:
∀φ ∀ψ Π(φ ∨ ψ) = max(Π(φ), Π(ψ))
• A necessity measure evaluates to what extent φ is entailed by the available
knowledge expressed by π . It is defined by:
and it satisfies:
N(φ) = inf{1 − π(ω) : ω |= ¬φ} = 1 − Π(¬φ)
∀φ ∀ψ N(φ ∧ ψ) = min(N(φ), N(ψ))
The duality relation N(φ) = 1−Π(¬φ) is an extension of the entailment in classical
logic. Traditionally, a sentence is entailed from a set of classical sentences if and only
if its negation is not consistent with this set. Therefore, before being entailed by the
available beliefs, the sentence concerned should be consistent with them first, which
means N(φ) > 0 implies Π(φ) = 1.
It is interesting to note the similarity between probability theory and possibil-
ity theory in their views of belief changes. Similar to probability theory’s tradi-
tional treatment of new information using conditional probability, in possibilistic
settings, revision is defined by a conditional possibility measure Π(·|A). Back in 1978,
Hisdal[58] first introduced the set function Π(·|A) through the following equality
∀B ∈ Ω, B ∩ A �= ∅, Π(A ∩ B) = min(Π(B|A), Π(A))
60
note here A = [α] is the set of models for new information α.
However since the above equation may have more than one solution in terms of
Π(B|A), Dubois and Prade[24] proposed the least specific solution, that is, when
A ∩ B = ∅, Π(B|A) = 0. When A ∩ B �= ∅
Π(B|A) =
� 1 if Π(A ∩ B) = Π(A) > 0
Π(A ∩ B) otherwise
The conditional necessity function is defined by duality,
N(B|A) = 1 − Π( ¯ B|A)
The possibility distribution π underlying the conditional possibility measure Π(·|A)
is defined by π(·|A). If ω �∈ A, π(ω|A) = 0; if ω ∈ A
π(ω|A) =
� 1 if π(ω) = Π(A)
π(ω) if π(ω) < Π(A)
Benferhat has a more general view of belief revision in terms of fusion[4]. Ac-
cording to him, belief revision can be viewed as a fusion process where the new
information has priority over the existing accumulated information in a prioritised
knowledge base. Basically, fusion differs from revision as a symmetric operation since
it does not necessarily distinguish the new information from the established ones.
Benferhat’s belief revision is interpreted as building a new possiblistic knowledge
base B⊕ with a distribution π⊕ obtained by aggregating π{φ,δ} and πB. He analyses
and compares different fusion operators in paper [4], thus we can define different
revision operators based on them.
With the epistemic meaning defined above for both possibility measures and ne-
cessity measures, in the possiblistic framework, the syntactical representation of an
61
epistemic state can be augmented to (φ, δ). It is important to note that, the certainty
degree of the sentence is explicitly specified in a possbilistic knowledge base as com-
pared to a traditional knowledge base, where only the sentence is explicit. Formally,
a possiblistic knowledge base is made up of a finite set of weighted sentences,
B = {(φi, δi) : i = 1, n}
where δi is understood as a lower bound on the degree of necessity N(φi).
Moreover, the syntactic representation can be translated to a corresponding se-
mantic one by defining possibility distribution π out of δ guided by the intuition
below[2]:
• For a possibilistic knowledge base only consists of one sentence (φ, δ), then
each interpretation ω which satisfies (i.e. consistent with) φ, π(ω) = 1; for each
interpretation which falsifies φ will have a possibility degree π(ω) such that
the higher δ is, the lower π(ω) is, a simple selection is 1 − δ. Therefore, the
possibility distribution associated with B = {(φ, δ)} is:
∀ω ∈ Ω, π{φ,δ}(ω) =
� 1 if ω ∈ [φ]
1 − δ otherwise
• For a general possibilistic knowledge base B = {(φi, δi)}, the intuition is all the
interpretations satisfying all the beliefs in B will have a highest possibility, 1;
and the other interpretations will be ranked w.r.t. the highest belief that they
falsify[23],
∀ω ∈ Ω, πB(ω) =
� 1 if ∀(φi, δi) ∈ B, ω ∈ [φ]
1 − max{δi : (φi, δi) ∈ B and ω �∈ [φi]} otherwise
62
It is interesting to note that, the idea of a normalised possibilistic knowledge base
coincide with definition of a knowledge system used by Williams [108, 111] in trans-
mutations. It also turns out Williams’ Partial Entrenchment Rankings are equivalent
to the Necessity Orderings [24]. The connection can be furthered through Peppas
and Williams’ contribution [95] on a condition (ES) which governs the equivalence
of an epistemic entrenchment ordering, a system of sphere and a nice pre-order. The
condition (ES) is described in Section 3.3.3.
Furthermore, in Dubois and Prade’s [24], one can find thorough discussions on
how possibility theory in belief change can be related to the AGM paradigm and even
a broader spectrum of research in this area in the last two decades, such as Spohn’s
ordinal conditional functions [100] and potential surprise [109] etc.
4.5 Probability as Special Belief Functions
The major distinction between a probability function and a belief function is that a
probability function assigns a number between 0 and 1 to some but not necessarily
all of the subsets of a belief base, which are often called measurable sets in probability
theory. In contrast, a belief function assigns a number to every subset of a set. There
are two standard ways of extending a probability function P r so that it is defined
on all subsets. One is to define the inner measure P r∗ introduced by P r, which is
understood to be the best approximation to the probability P r from below. The other
one is to define the outer measure P r ∗ , which is considered as the best approximation
to P r from above. As it is often claimed pure statistical probabilities sometimes are
difficult or even impossible to obtain in real world applications, the interval [P r∗, P r ∗ ]
is often considered as that the best range that real probability P r may fall into. The
63
inner measure and outer measure induced by P r are defined for an arbitrary subset
A ⊆ S[52].
P r∗(A) = sup{P r(X) |X ⊆ A and X ∈ X }
P r ∗ (A) = inf{P r(X) |X ⊇ A and X ∈ X }
For a finite sample space or if the number of measurable sets in the sample space
is finite, the inner measure of A is just the measure of the largest measurable set
contained in A, while the outer measure of A is the measure of the smallest measurable
set containing A. For any set A, we have P r∗ ≤ P r ∗ and if A is measurable, then
P r∗(A) = P r(A) = P r ∗ (A). It is easy to show that P r∗ is a belief function in that it
satisfies the three axioms characterising belief functions and P r ∗ is the corresponding
plausibility function. The connection between probability, belief and inner measure
can be easily seen if using the mass functions in finite spaces. If P r is a probability
function defined on a set X of measurable subsets of a finite set S, and Y is a basis
of X , let m be the mass function such that
m(A) =
� P r(A) if A ∈ Y
0 otherwise
and let Bel be the belief function corresponding to m. Then according to the defini-
tion of P r∗, we can easily obtain Bel(A) = P r∗(A) for all A ⊆ S. In fact, for all the
measurable sets, Bel(A) = P r(A) and more generally, Bel(A) is equal to the inner
measure on arbitrary subsets. It is important to notice that the mass function m
has the property that its focal elements, i.e., those sets that have positive mass, are
disjoint. Moreover, if the focal elements are not only disjoint but are also singletons,
64
a belief function turns out to be a special type of probability function, in which every
element in the sample space is measurable. Therefore, we have,
Theorem 4.5.1 ([53]). A belief function is a discrete probability function if only if
its focal elements are disjoint singletons.
4.6 Possibility as Special Belief Functions
We can show via the following proof 6 that the necessity measure is actually a special
Dempster-Shafer’s belief function when the focal elements are nested singletons.
Given two sentences φ and ψ ordered by “qualitative necessity relation” (≥c)
defined by the necessity measures. Assume the certainty degree of φ and ψ are N(φ)
and N(ψ) respectively, with the help of the following proposition (proposition 2 in
[24] and it is also proved in [40]:
if φ ⊢ ψ then ψ ≥c φ
We know that φ ⊢ φ ∨ ψ and ψ ⊢ φ ∨ ψ so we obtain:
therefore,
φ ∨ ψ ≥c φ and φ ∨ ψ ≥c ψ
N(φ ∨ ψ) ≥ max(N(φ), N(ψ))
Recall the characteristic inequality of belief function, the degrees of belief on
possible worlds[φ], [ψ], for φ and ψ respectively follows the inequality below,
6 Thanks to Jérôme Lang for his valuable discussions on probability, possibility and belief functions
and the proof presented here is mostly attribute to him.
65
Let us assume
Bel([φ] ∪ [ψ]) ≥ Bel([φ]) + Bel([ψ]) − Bel([φ] ∩ [ψ])
1. The focal elements for defining BelN are nested singletons. Using the mass
distribution function m on two focal elements A1 and A2, the assumption is
easily seen as equivalent to:
BelN(A1) ≥ BelN(A2) iff A1 ⊇ A2
2. Either [φ] ⊇ [ψ] or [φ] ⊇ [ψ] i.e. [φ] and [ψ] are nested.
and we can get
BelN([φ] ∪ [ψ]) ≥ max(BelN([φ]), BelN([ψ]))
We can easily observe the match between N(φ) and BelN([φ]), i.e. N(φ) =
BelN([φ]). This can be formulated into the theorem below similar to that of be-
lief function and probability:
Theorem 4.6.1. A belief function is a necessity function if only if its focal elements
are nested singletons.
4.7 Summary
As shown in the beginning of Chapter 2, belief revision is an essential capability for
an agent to exhibit intelligence and to be both proactive and reactive. Therefore, in-
vestigating issues that arise in the field of belief revision with a focus on implementing
the proposed techniques for real world applications is of crucial importance.
66
In the last two decades, belief revision became an increasingly important research
area as it generated valuable discussions between disciplines that have traditionally
ignored each other, such as philosophy, logic, computer science and mathematics.
One of the major contributions to this field is the AGM paradigm introduced
in Chapter 3, famous for its sets of rationality postulates and the simplicity of the
framework. The AGM postulates circumscribe three types of belief change operators,
expansion, contraction and revision. Belief states are represented by deductively
closed sets of sentences, called belief sets. Operations of change take the form of
either adding or removing specified sentences. When we contract a deductively closed
set K of sentences by a nontautologous sentence α, the outcome K − α is a deductively
closed set of sentences that does not contain α.
There are two operations that incorporate new information, namely, expansion
K + α and revision K ∗ α. The outcome, K + α , which results from expanding K by α is
simply Cn(K ∪ {α}). Clearly, expansion is a monotonic operation, and if ¬α ∈ K,
then K + α is inconsistent. In contrast to an expansion, the outcome of revising K
by α is a deductively closed set that contains α, which is consistent if only if α is
consistent. Hence, in revision, but not expansion, old beliefs are sacrificed to achieve
consistency. Based on the AGM postulates, expansion is a unique monotonic oper-
ation, but not revision and contraction. Two major ordering techniques, epistemic
entrenchment and system of spheres are proposed as extra logical information devices
for constructing certain classes of revision and contraction operators.
Alongside or even before AGM’s syntactical qualitative approaches designed to de-
velop a deeper understanding of belief revision under the umbrella of epistemological
theories, there are quite a few quantitative and qualitative mathematical frameworks
67
proposed for tackling belief change issues as well. These include the famous Bayesian
probabilities, Dempster-Shafer’s belief function and Dubois-Prade’s possibility theo-
ries. Quite surprisingly, these all fit into the epistemological framework described by
Gärdenfors nicely. As shown by the brief presentation of these works in this chapter,
although they are different works carried out separately by different researchers, they
are very closely related. In [24], Dubios and Prade show that a qualitative neces-
sity ordering is almost exactly the same as AGM’s epistemic entrenchment orderings.
Furthermore, a necessity measure in possibility theory is actually a special case of a
belief function, and a belief function can be used to define a probability function if it
meets the disjoint singleton criteria presented in Section 4.5.
The comparative analysis in the thesis provides a solid theoretical foundation for
the development of a multi-agent belief revision system that might be operating in an
heterogenous environment where agents can adopt their own revision mechanisms.
In this thesis, we follow the literature in using the term ‘revision’ with three
different senses. In its wide meaning, belief revision refers to the general problem of
changing belief states; a narrower meaning refers to inserting an arbitrary piece of
information into a belief system; still narrower is the sense just introduced; i.e. where
the new piece of information is inconsistent with the original belief system.
68
Chapter 5
Belief Revision in a Multi-Agent
Environment
“... there are seven main components to a BDI agent:
1. a set of current beliefs,
2. a belief revision function (brf), which takes a perceptual input
and the agent’s current beliefs, and on the basis of these, determines
a new set of beliefs.
3. ...”
— Michael Wooldridge (1999) in [113]
5.1 Brief Introduction to Multi-Agent Systems
Agent technologies and multi-agent systems have been identified as the mainstream
software engineering[63] for large distributed domains, such as ecommerce/ebusiness,
distributed sensor networks, air traffic control[77], resource allocation for Internet
access[80] etc.
The major focus of a multi-agent system is to create a system that interconnects
separately developed agents such that the group of agents is able to function beyond
the capabilities of any singular agent by itself.
69
A classical real-world example is a system inside which a personal travel agent will
negotiate with other software agents who represent the interests of different share-
holders, such as hotel agents, airline agents, and etc. This is a truly multi-agent
problem which involves the inter-operation of separately developed and self-interest
agents which provide a service beyond the capability of any single agent. In the
process, most or all gain financially.
Although there is no clear boundary between them, a multi-agent system is
different from that of Parallel AI and Distributed Problem Solving. Nwana and
Ndumu[89] point out that in agent research and practice, very often, people tend
to confuse: agents and objects; distributed computing and agent-based computing;
object-oriented systems, expert systems and agent-based systems. Before we can start
discussing issues about belief revision in an multi-agent environment, we will have to
first clarify these easy-to-confuse concepts.
Woodridge[113] illustrates one of the major differences between objects and agents
with an interesting slogan: “Agents do it for money. Objects do it for free.”. One
other well-recognised difference is that agents have internal control on the running
threads and most importantly have the ability to refuse the request, while objects are
normally designed to be passive and methods are evoked by external events.
As to object-oriented computing, distributed computing etc, according to Nwana
and Ndumn[89], they do not in themselves offer solutions to multi-agent systems for
the following reasons:
• Distributed computing modules are designed to be passive/cooperative and
homogeneous[25].
70
• The communications between distributed computing modules are usually low-
level while multi-agent systems require high-level messages.
• Multi-agent system applications require a cooperative-knowledge level (i.e. on-
tology level) while object-oriented systems, expert systems etc typically operate
at the symbol and knowledge level[87] at most.
In fact, parallel AI and/or distributed problem solving techniques are more ap-
propriate in the following areas, where multi-agent systems are not really needed:
• Solutions are needed to enhance modularity (which reduces complexity), speed
(due to parallelism), reliability (due to redundancy), efficiency and flexibility.
• Problems are too large for a centralised single ‘agent’ to perform due to resource
limitations or the risk of having one centralised system.
• Solutions are used mainly to address problems requiring heterogeneous reason-
ing.
Areas that multi-agent solutions really excel at include:
• Problems requiring the interconnecting and inter-operation of multiple, au-
tonomous, ‘self-interested’ existing legacy systems, e.g. expert systems or de-
cision support systems. For example, when solutions need to be drawn from
distributed autonomous experts, e.g. in health care provisioning or electricity
distribution. 1
• Problems that are inherently distributed, e.g. geographically, as in distributed
sensor networks or air-traffic control.
1 Possible citation of Laurence’s paper on manager gathers information form individuals.
71
• Problems whose solution require the collation and fusion of information, knowl-
edge data from distributed, autonomous and ‘selfish’ information sources, e.g.
British Telecommunication’s personal travel assistance prototype application[86],
such systems also go under the name of cooperative information systems.
Clearly, multi-agent systems are considered as a solution to complex real-world
problems which in general involve multiple, autonomous, self-interested entities, re-
quire unsupervised interaction between the entities, especially require the collation
and fusion of information from the distributed entities.
Based on the above understanding of multi-agent systems, the term “multi-agent
belief revision” may carry a two-fold meaning.
Firstly, it implies a multi-agent solution for complex belief revision problems,
where multiple heterogenous belief bases are involved and the conclusion can not be
drawn without a consistent overview.
Secondly, it can also be seen as an emergent behaviour that occurs in a multi-agent
environment. Belief revision is essential for an agent to exhibit intelligent behaviour.
In a multi-agent system - a society populated with intelligent agents, the issue of
revising shared/common belief naturally arises which does not present in a single
agent situation. This not only requires communication, negotiation, and cooperation
among agents, but due to the autonomy of each individual (possibly selfish) agent, it
exhibits behaviours much more complex than that of group decision making, which
we will discuss under the title of “heterogeneity” in Section 5.4.
Bearing in mind the global picture of where multi-agent systems reside in the
family of distributed AI, let’s have a close look at the multi-agent environment and
describe some important assumptions that define the boundaries of the system scope
72
that we are to consider herein.
We consider a general decentralised environment, where both control and data
are logically and often geographically distributed. In addition, agents could come
from different designers or different vendors, whose protocols or mechanisms are not
foreseen. Each agent makes its own choices as to whether it will talk to another agent
and at what time. Each agent has local memory, no memory needs to be shared by
all agents. Each agent typically has several distinct knowledge bases, specifically, for
example, some for domain knowledge, some for social knowledge.
Furthermore, we assume that each agent has special expertise in specific areas.
The expertise overlaps, but is not identical. An agent’s expertise and services are the
only data open to other agents. Expertise is graded, e.g. by professional institutions.
Lastly, we assume the communication between agents is always successful. Every
agent can communicate with every other agent by sending and receiving messages.
Any information sent out by agent x will arrive at agent y precisely with no distor-
tion. For our special interest, those messages are in a formal form, we will discuss a
reasonable form in the following chapters. We also assume the existence of low-level
protocols (peer-peer, broadcast, multi-cast) to ensure effective and flexible communi-
cation. Agents could choose between connection oriented and connectionless to suit
their needs. In addition to answering another agent’s queries, an agent could also
offer information and services to other agents based on its own internal decision.
We also assume the use of FIPA 2 agent platform for information discovery. For
example, we assume the existence of a directory facilitator for yellow page services
and an agent name server for white page services.
2 http://www.fipa.org
73
Under the above assumptions, each agent has an incomplete, local view of the
environment. No agent is assumed to have sufficient information to solve all global
problems and agents do not typically have full access to others’ internal states. How-
ever, the agent expertise and services are available to other agents through service
descriptions and registrations with the directory facilitator.
Viewing multi-agent systems as societies of heterogenous autonomous agents that
satisfy the above assumptions, we formulate the following criteria for evaluating the
existing work on multi-agent belief revision.
Q1: Is there a super agent that has global access to all information?
Q2: Are the agents heterogenous? For example, do they use different revision
techniques, do they have different levels of expressing epistemic attitudes?
Q3: Are the agents cooperative and trustworthy?
Q4: Can agents choose what, who and when to communicate?
In this chapter, first we review some existing frameworks for multi-agent belief
revision by asking the above four questions. Then we present a picture of the field
by classifying them according to whether the revision techniques are developed for a
single agent environment or a multiple agent environment. Lastly, we identify differ-
ent types of heterogeneities in order to address the weakness of the reviewed frame-
works. Furthermore, the investigation for further understanding the heterogeneity
issues helps define our research issues.
74
5.2 Various Frameworks for Multi-Agent Belief Revision
5.2.1 Mutual Belief Revision of Van der Meyden
Mutual Belief Revision is a nested process during which an agent must revise not
only its own beliefs about the world, but also its beliefs about other agents’ beliefs
about the world and moreover about other agents’ beliefs about its own beliefs, and
so on. A multi-agent version of perfect introspection logic K45n is employed to model
the so-called mutual belief :
Definition 5.2.1. A set of agents mutually believe ϕ iff each of them believes ϕ, and
each of them believes that each of them believes ϕ, and so on, ad infinitum[31].
The theory of mutual belief revision ends up with a unique operator which satisfies
the following four assumptions:
(1) Agents have perfect introspection 3 , but maybe inconsistent.
(2) Agents revise their beliefs synchronously, in response to an event ɛ whose
occurrence is a common knowledge.
(3) The world is static;
(4) Each agent’s revision method is a common knowledge.
Assumption (3) simplifies the problem so that there is no need to consider the
change of the environment and confines the problem to revision, not update. As
noted earlier, it is this basic assumption that differentiates revision from update.
But the other three assumptions ((1),(2) and (4)) limit the proposed theory’s ca-
pability of handling heterogeneities in multi-agent environment. By assuming perfect
3 Perfect introspection assumes a considerable degree of self-knowledge, [37] has detail.
75
introspection, the system requires agents to know exactly what they believe and do
not believe. On one hand, this is a quite rigid requirement and in the real world,
agents only tend to know something after performing a search. On the other hand,
perfect introspection only applies to ideal agents. However, a real system may have in-
competent or stupid agents, who do not have perfect introspection, namely, they may
not know what they believe and what they don’t or they may have wrong introspec-
tion about what they believed. Assuming perfect introspection limits the capability
of dealing with heterogenous agents. Assumption (2) confines this theory to simple
communication, namely, broadcasting. Assumption (2) and (4) together mean that
not only the revision method is known to others but also the whole revision process
and the input event that will trigger everyone’s revision simultaneously.
Clearly mutual revision systems fail the test of being truly multi-agent solutions
because assumptions (1),(2) and (4). Furthermore, the infinite recursive definition of
mutual belief makes it almost impossible to implement.
The idea of mutual revision is further illustrated in [85] by the “scientists in
conference” example. In the example, all the agents work faithfully, broadcasting
what they know and what they do not know. Considering a distributed knowledge
base system, where each agent represents a local knowledge base. Based on the
above four assumptions, the agent should store its own knowledge about the world.
Meanwhile, it has full access to all other remote agents’ knowledge bases that belong
to other agents. Therefore, every agent knows what the others know and what they
do not know. On the receipt of new information, at first the agent revises its own
beliefs, then because the revision method is common knowledge, it could readily and
successfully predict what all the other agents will do with their beliefs.
76
In fact, mutual belief revision can be thought of as a set of single belief revision
processes carried out uniformly in a parallel but decentralised manner.
5.2.2 MABR of Kfir-dahav and Tennenholtz
In contrast to Van der Meyden, Kfir-dahav and Tennenholtz[68] approach MABR in
the context of heterogeneous systems. The Private Domains (P Di) and the Shared
Domain (SD) of the agent knowledge base are defined in order to capture a general
setting where each agent has private beliefs as well as beliefs shared with other agents.
Under such a knowledge structure, each agent may have its own perspective of the
world but needs to coordinate (ie agree on) its belief on shared elements. The shared
domain also defines the communication language for the agents.
One important question in this scenario is how do we manage and maintain the
knowledge in P Di and SD? By definition[68], SD is just the intersection of each
agent’s KB. Although it is not explicitly stated, the authors assume that agenti is
aware of (knows) its own knowledge in P Di and the existence of SD. Since an agent
does not know other agents’ P D, what happens if after several sequences of revision,
the intersection of the P Dis is not empty?
For example, consider the situation in which two agents(A1, A2) engage in revision,
Φi stands for the KB of Ai, i=1,2.
According to the definition,
Φ1 = {γ, φ, ψ}
Φ2 = {α, β, φ}
77
SD = {φ}; P D1 = {ψ, γ}; P D2 = {α, β}
If A2 receives a piece of new information, say, α→ψ, then by Modus Ponens, ψ
should be in P D2. Thus,
P D1 ∩ P D2 = {ψ} �= ∅
A2 will only expand P D2 but not SD providing that nobody says that ψ is also
believed by A1. The authors did not tell us what to do with this ψ. If ψ∈SD, it
seems to us, they implicitly assumed that the existence of a super agent who knows
all the agents’ private knowledge and the society’s shared knowledge, so that the
intersection of private knowledge can always be upgraded to the shared domain. If
ψ�∈SD, then the definition of SD is violated.
5.2.3 MSBR of Dragoni et al.
Recognising that agents may join a network with low degrees of competence or non-
cooperative intentions, Dragoni et al. [20] states that the reliability of the source
affects the credibility of the information and vice-versa. Neglecting the “priority to
the incoming information principle” is thus proposed and implemented by considering
the information pair 〈information, source〉 rather than just 〈information〉.
During an AGM revision, priority is given to the incoming information. For
instance, the new information will be accepted using an expansion if it is consistent
with the current belief sets. In the sense of transmutation[108], the new information
is allowed to come with a certain rank and to be accepted at this prescribed level. In
this case although you don’t necessarily totally accept the new information, you do
78
need to respect the incoming rank. There is no explicit rational step to change the
rank in these frameworks. While the non-priority of or in the extreme case, neglecting
incoming information is thus a two step procedure, first, revise the rank according
to the reliability of the informant and then incorporate the information with the
new rank. Therefore, by evaluating the source reliability, the receiver agent has the
flexibility of deciding whether to take the impinging information into account or not.
5.2.4 DBR of Dragoni et al.
In Distributed Truth Maintenance Systems[59], all the agents are both individually
and mutually consistent with all other agents with whom they have exchanged knowl-
edge. While in DBR[20][21], the Liberal Belief Revision Policy is adopted, that is,
to let all the agents stand by their own beliefs based on their own view of the evi-
dence. Therefore, the local consistency is considered as a prerequisite, but the global
consistency is only considered as an end point which is eventually reached through
some selection strategies. Every node (agent) in the DBR system is able to carry out
MSBR as well as communicate with each other.
As to the knowledge structure, local knowledge is distinguished from global knowl-
edge. By using certain voting functions[20], the local knowledge can be selected to
become global knowledge. Compared to Kfir-dahav and Tennenholtz’s terminology,
Dragoni et al.’s local and global knowledge could be seen as the counterparts of the
knowledge in P Di and SD, respectively. But a subtle improvement is made by Drag-
oni et al. in that certain voting functions are employed to generate global knowledge
rather than simply taking the intersection of P Dis. Actually, private or local knowl-
edge as defined here are not private in the real sense, because it is implicitly assumed
79
there is some super agent, at least a human developer, exists in the system to super-
vise the knowledge upgrade 4 . Private knowledge should be confidential, ie, invisible
to all the outsiders.
To classify agent knowledge in this way is still too simple to some extent. For
example, in an agent society populated with multiple agents, some agents may wish
to form small groups or teams to accomplish goals. Therefore, shared knowledge (or
team knowledge) rather than global knowledge is sometimes required.
5.2.5 Summary
To summarise, mutual belief revision is only capable of revising knowledge, but not
graded belief. Kfir-dahav and Tennenholtz’s MABR and Dragoni et al.’s DBR have
overcome this by discussing revision in the broad sense of knowledge system trans-
mutation. The social behavior that might affect the information credibility has been
discussed by Dragoni et al. in the context of MSBR. This is an advance over other
studies based on reliable, faithful and mutually trustworthy communication. The
knowledge structures proposed by Kfir-dahav and Tennenholtz, and Dragoni et al.
initiate an effort in classifying knowledge. However, they are not rich enough to elim-
inate some ambiguity or to offer some essential flexibility. It will be shown in Section
5.4 that finding a feasible way of classifying knowledge is an important step towards
modelling social heterogeneity occurred in knowledge bases.
None of the schemes discussed above address the issues that might arise from
4 Knowledge upgrade is one phase of knowledge migration, which also encompasses the dual phase
of upgrade, ie knowledge degrade. Upgrade refers to the process that local knowledge is selected to
become global knowledge, while degrade is the opposite process. Knowledge migration will be fully
discussed in Chapter 9.
80
multiple revision strategies, which would be highly desirable in a heterogenous revi-
sion system. Although MABR and DBR’s communication mode is not restricted to
broadcast as mutual belief revision does, the underlying heterogeneity issues which
might inhibit efficient and reliable communication has not been addressed in any
depth. Heterogeneities appear in various forms in multi-agent systems. For the
purpose of research with regard to belief revision in a multi-agent environment, the
heterogeneities pertain to the domain need to be discussed and dealt with.
5.3 Belief Revision in Multi-Agent Systems - Concepts
and Terminologies
As we can see from above, a variety of notations have been adopted by researchers
investigating belief revision of multi-agent systems. A good understanding of the
relationships between these approaches is essential before carrying out any further
research. To clarify the terminologies and associated concepts for belief revision of
multi-agent systems, let us revisit the definition of “agent”. Generally, an agent
implies a problem solving entity that both perceives and acts upon the environment
in which it is situated, applying its individual knowledge, skills and other resources to
accomplish high-level goals. By employing various algorithms and processes, agents
are capable of taking actions to achieve their individual goals or interacting with
other agents to achieve mutual goals. According to whether belief revision is involved
in individual goals or mutual goals, previous research efforts in belief revision of
multi-agent system can be classified into two categories, ie, Belief Revision using
information from Multiple Sources(MSBR) and Multi-Agent Belief Revision (MABR).
On one hand, belief revision could be considered as part of the agent’s skills to
81
maintain the consistency of its own epistemic state. In this case, an individual belief
revision process is carried out in a multi-agent environment, where the new infor-
mation may come from multiple sources and may be in conflict. Belief revision in
this sense is called MSBR by Dragoni et al.[18][22][19]. Cantwell[11] tries to resolve
conflicting information by ordering the information sources on the basis of their trust-
worthiness. This could be viewed as a rational way of generating the new information
credibility based on the source reliability using the terms of MSBR. Benferhat et al.[2]
investigate revision of information from multiple sources in the face of uncertainty
as data fusion, using possibilistic logic; Liberatore and Schaef[74] treat the MSBR
process as intelligent merging of knowledge bases, which they call Arbitration.
On the other hand, belief revision could also be used to achieve a society’s or
team’s mutual belief goals(e.g. reaching consensus before carrying out a plan). In
this setting, more than one agent takes part in the process. In order to pursue a
mutual goal, the agents involved need to communicate, cooperate, coordinate and
negotiate with one another.
A MABR system is a MAS whose mutual goal achievement involves belief revision.
As we stated before, it carries a two-fold meaning:
Firstly, it can be seen as a multi-agent solution for complex belief revision prob-
lems, where multiple heterogenous belief bases are involved and the conclusion can
not be drawn without a consistent overview or consensus among multiple agents.
Secondly, it can also be seen as a behaviour that emerged as a result of the
interaction among multiple belief revision agents.
Since a multi-agent system is actually an intelligent distributed system, an alter-
native name for MABR could be intelligent Distributed Belief Revision(DBR). MABR
82
is the terminology adopted by Kfir-dahav and Tennenholtz[68]. Dragoni et al. prefer
DBR[21] based on the comparison with Distributed Truth Maintenance(DTM). Van
der Meyden’s semantical theory of BR in synchronous MAS, namely, Mutual Belief
Revision, also falls into the MABR category.
MSBR studies individual agent revision behaviours, ie, when an agent receives
information from multiple agents towards whom it has social opinions. MABR in-
vestigates the overall BR behaviour of agent teams or a society. MSBR is one of the
essential components of MABR.
As shown in the previous chapter, the AGM paradigm[40] has been widely ac-
cepted as a standard framework for belief revision. But its major focus is in pre-
scribing revision behaviours of an ideal single agent. The belief revision process is
more complex in a multiple agent scenario. Besides the Principle of Minimal Change,
there exist other requisites due to the sophisticated agent interactions. Therefore, the
AGM framework is not rich enough to prescribe a satisfactory revision operator for
MABR. In the following chapters, we develop a general framework based on an on-
tology to capture the necessary heterogenous properties so as to accommodate the
sophisticated agent interactions.
As a result, belief revision can be thought of in a narrower sense, which encom-
passes all previous work in AGM. It can be considered in a wider sense, taking into
account MASs, from the viewpoint of a single agent or a society of agents. An agent
is capable of carrying out Individual Belief Revision(IBR), while an agent society or
team is capable of MABR, an agent is capable of participating in MABR is referred
to as an MABR agent. IBR in a single agent environment(Single Belief Revision,
SBR) could be achieved using classical belief revision techniques satisfying AGM
83
Belief Revision in
Single Agent Environment (SBR)
Individual Belief Revision (IBR)
Belief Revision
Multi-Agent Belief Revision (MABR)
(Intelligent Distributed Belief Revision)
Individual Belief Revision in MASs
Multiple-Source Belief Revision (MSBR)
Figure 5.1: Belief Revision Hierarchy
postulates. IBR in a multiple agent environment is MSBR, ie, a single agent will
have to process information coming from more than one source. After obtaining the
new credibility of the new information on evaluating the multiple sources using some
techniques(e.g.[11][19]), MSBR degenerates to SBR. We can classify the types of BR
using the hierarchy in Figure 5.1.
5.4 Heterogeneities in Multi-Agent Systems
Much of the conceptual power of the MAS paradigm arises from the flexibility and
sophistication of the agent interactions and organisations. As the basic skill for both
individual agents and agent societies to maintain consistency, the belief revision pro-
cesses and results will heavily depend on the way agents communicate, cooperate,
coordinate and negotiate with one another. Heterogeneity is one of the basic origins
of such flexibility but it also gives rise to complexity. Taking the opportunities as well
as solving the difficulties could lead to a more dynamic and versatile belief revision
perspective. Therefore, it is necessary to identify various types of heterogeneities and
study how they might affect belief revision behaviours in multi-agent systems.
Heterogeneities in a multi-agent system may take many forms, ranging from the
hardware and software platform that each agent is based on, to the organisation
schema that relates individual agents socially to others forming teams and societies,
84
to the basic knowledge representation structure and reasoning strategy that makes
the agent intelligent, to the problem domain that an agent specialises in. We focus
on the issues raised by heterogeneities in the knowledge systems, which includes the
last two cases. Following is a brief classification according to the source (i.e. level) of
these knowledge system heterogeneities.
• Social Character Heterogeneity(social-level): Within a multi-agent system, an
agent is socially situated in a particular environment with its existence known
to other agents. As a problem solving entity, an agent is also defined as a soft-
ware entity that acts on behalf of the user to accomplish certain tasks assigned
by the user. Therefore, just as a human could behave in a benevolent or mali-
cious way, there is no reason to forbid agents from possessing such characters.
In the context of modelling trust[65], “free will” has been defined to describe
the mental decision process of judging between benevolent and malicious be-
haviour. Agents possessing free will of this type are designated as passionate.
However, an agent, such as algorithms, protocols, software and hardware which
could hardly be characterised as having a free will are classified as rational.
On the other hand, due to technical or other possible reasons (e.g. hardware
quality), the agent could either be competent or incompetent. Combining these
characteristics, agents could be roughly classified into four categories: com-
petent rational, competent passionate, incompetent rational and incompetent
passionate agent.
• Semantic or Logical Heterogeneity(meta-level): Borrowing terms from cooper-
ative information systems(CIS)[60], semantic heterogeneity results when dif-
ferent conceptualisations and different database schemas are used to represent
85
the same or overlapping data which is replicated in two or more databases. A
simple real world example could be the various grading techniques in an ed-
ucational system such as percentage or letter grade[54]. A generalisation of
such heterogeneity also occurs in the agent knowledge bases. For example, the
knowledge could be represented using different logics, in favour of an agent’s
problem solving capability with respect to certain problem domain.
• Syntactic Heterogeneity(content-level): This is a domain specific heterogeneity
which arises from the fact that in many cases the same letters or words are used
to represent different concepts or objects by different agents and vice versa.
This happens during the process of building knowledge into autonomous agents
to enhance their intelligence. Natural language is commonly transformed into a
simple logical form. Developers have the freedom to name things as they wish.
For example, some agents may choose the letter “a” for describing an apple,
while some other agents might prefer the whole word “apple” or something else.
This is also a common phenomenon in all the emerging research areas, different
terminologies have been used to describe the same concept, or vice versa. While
a research area matures, general terms and frameworks will be proposed to serve
as a specification.
It can be seen from the previous study in MABR, researchers have progressively
put more accent on the heterogeneity that exists in agent knowledge bases. In the
early 1990’s, Fagin et al.[31] semantically defined mutual belief and common knowl-
edge. Van der Meyden extended this modal logic approach into MABR in 1994.
Malheiro[81] in the same year defined private and shared belief to model the belief
revision process in a distributed truth maintenance system. Similarly, Kfir-dahav and
86
Tennenholtz claimed in 1996 that their work[68] is more amenable to solve the het-
erogeneity problem than Van der Meyden’s by stating that agent knowledge could fall
into private and shared domains. Recently, other researchers[78][102], following Fagin
et al.’s approach, defined various concepts such as team knowledge and shared knowl-
edge. Dragoni et al. also distinguishes global knowledge from local knowledge[20].
Actually, defining shared, common and private knowledge paved the way for mod-
elling the social character heterogeneity. In other words, the diversity of different
kinds of knowledge is the reflection of social heterogeneity in agent knowledge bases.
Private knowledge is needed by passionate agents to keep confidential information.
Such privacy enables the possibility of malicious behaviour which is sometimes needed
for an agent to maximise its own or group utility in a competitive environment. On
the other hand, common or shared knowledge is essential to establish cooperation-
oriented communication and commitment. For example, incompetent agents could
carry out teamwork by sharing knowledge so as to achieve high-level goals which could
not be accomplished by any individual. Understanding the similarities and distinc-
tions among these conceptualisations of agent knowledge poses a serious challenge
when trying to integrate systems based on different knowledge structures.
Semantic and syntactic heterogeneity have not yet been studied in the context of
MABR.
The existence of a variety of belief revision strategies is an example of semantic
heterogeneity that exists in MABR. For belief revision within the AGM paradigm,
many revision schemes have emerged during the past decade as shown in the previous
chapter, such as numerical revision using probabilistic[93] or possibilistic logic[24],
sentence-based revision using various transmutation[108] and so on. Special needs for
87
communication and inter-operability arise, because a variety of ranking mechanisms 5
might be used when employing various revision strategies. How do agents commu-
nicate with each other in terms of the information credibility? In other words, how
does an agent incorporate new information from another ranking system?
Communication and inter-operability difficulties are associated with syntactic het-
erogeneity too. How could the information reliability be guaranteed during the in-
formation passing process in a system with such low-level heterogeneity that same
string means something different?
5 Ranging from ordinal natural numbers(ie {0, 1, 2, ..., ∞}) to unit interval (ie [0, 1]).
88
Chapter 6
Ontology - Tackling the
Heterogeneity Issues
“Ontologies are nothing but names with standard meanings. In a world of
data exchange names are incredibly important, because you and I cannot
exchange information about a thing unless we agree on the name for the
thing.”
6.1 Introduction
— R.V. Guha (Editor for W3C’s standard for RDF)
It is widely accepted that an ontology is an efficient approach that can be used to
tackle heterogenous issues involved in the generalisation of low-level heterogenous
data to relatively high-level concepts for the purposes of communication, system
inter-operation and software reuse. Recent years have seen a promising surge in both
research and practice of ontologies. Nowadays, ontology is no longer just a concept
of the Artificial Intelligence laboratories where researchers recognise its importance,
and hope other people - such as domain experts or knowledge engineers - will take
89
up the tedious work of creating ready-to-use ontologies. In fact, more and more real-
world implementations of ontologies, especially, ontologies for the World Wide Web
have proved successful and are now heavily relied upon by e-commerce and e-business
applications.
Ontologies on the Web range from large taxonomies (subclasses-superclasses) cat-
egorising web sites (such as Yahoo! and Google’s Web Directories) to categorisations
of products for sale and their features (such as on Amazon.com). These are the so-
called first generation ontologies, which ground today’s machine to human web. In
this machine to human web, the machine outputs search results, humans then have to
interpret and filter the often large retrieved repository for relevant information. The
next generation ontologies, will facilitate the revolution of the world wide web into
Berners-Lee’s vision of semantic web[7] 1 , which makes a huge amount of information
available in machine-readable format. This will not only free human-beings from the
information overflow but also enable the automatic online B2B trading. With the
machine-readable information, large numbers of intelligent agents will be employed
to do the knowledge gathering, reasoning, economic optimising or even bidding on
human’s behalf. At the time of research, there are several large, general ontologies
that are freely available, some examples are Cyc 2 , WordNet 3 and World Fact Book 4 .
1 The semantic web will enable machines to comprehend semantic documents and data, not human
speech and writing.
2 http://www.cyc.com/cyc-2-1/cover.html
3 http://www.cogsci.princeton.edu/ wn
4 http://www-ksl-svc.stanford.edu:5915/doc/wfb
90
6.2 Classifying Ontologies
Uschold [104] pointed out, ontologies may vary along three dimensions, namely, pur-
pose, formality and the subject matter.
In general, an ontology defines a common vocabulary for parties who need to
share information in a domain. The information sharing may occur among people
or among software agents and facilitating communication between people or between
organisations, and inter-operation between heterogenous systems. The ontology used
for such purposes serves as a translator between systems that “speak” different lan-
guages. For example, a human translator translating between English and Chinese
has to understand both languages, and has to know the mapping between the two
languages. Essentially, the two languages provide two different sets of vocabulary
that describe the same perception of the world, or the domain of discourse. This is
one of the dominant usages of ontology. Other possible usages [88, 104] are mainly for
system engineering purposes, such as analysing the domain knowledge, making the
domain assumptions explicit, separating the domain knowledge from the operational
knowledge and thus enabling the reuse of domain knowledge.
If categorised by its subject matter, a Domain ontology is for special subjects
such as medicine, finance and etc. Upper model or top-level ontology[51] is general
world knowledge, such as the WorldFact Book we mentioned in the Introduction Sec-
tion 6.1. A task, method or problem solving ontology is for the subject of problem
solving. For example, the AGM postulates prescribe a method ontology that spec-
ifies a set of revision functions. A representation ontology is for the subject of a
knowledge representation language. For example, ontology languages such as CycL,
KIF, DAML+OIL, XML, and RDF etc are themselves representation ontologies for
91
representing knowledge and capturing relations among the defined concepts.
Ontologies can also be classified according to their formality. An ontology is highly
informal if expressed loosely in natural language; structured informal if in a restricted
and structured form of natural language; Semi-formal if in an artificial formally de-
fined language such as Ontolingua and Knowledge Interchange Format(KIF)(links in
[47]) and etc; rigorously formal if in meticulously defined terms with formal semantics,
theorems and proofs of such properties as soundness and completeness.
Furthermore, the semi-formal and rigorously formal ontology languages can be
categorised based on the underpinning logical paradigm. For example, the syntax of
both CycL and KIF are derived from First-Order Predicate Logics. They both provide
an important extension which allows reification of formulas as terms used in other for-
mulas. Therefore, CycL and KIF allow meta-level statements. Ontolingua and Frame
Logic integrate frames concepts (i.e. classes) into predicate logic. Their central mod-
elling primitives are classes with certain properties (i.e. attributes), as compared to
KIF and CycL, whose central primitives are predicates. On the other hand, recently,
there is much interest in ontology languages based on Description Logics[9], such as
CLASSIC and DAML. A distinguishing feature of Description Logics is that classes
(usually called concepts) can be defined intentionally using descriptions. The descrip-
tions are used to specify the properties that objects must satisfy in order to belong
to the concept. Moreover, the language used to express the descriptions allows the
construction of composite descriptions. Such features makes description logic based
ontology languages good candidates for web service descriptions.
For our purposes, as will be shown in the later sections, a first-order logic based
ontology that is able to support identification of concepts, attributes and describing
92
relations between concepts would suffice.
In summary, ontologies are important for both human beings and software agents
who are involved in knowledge sharing. Actually we may not be aware of an important
fact that, we, human beings are using ontologies in every aspect of our life and
developing ontologies since the ancient civilisation began. Our everyday languages
can be seen as a form of informal ontology. It is a matter of fact that it is scientific
discovery that builds and continuously adds to our general world knowledge, i.e. our
informal top ontology.
It is often the case that ontologies that we use are not in formal languages. This
is due to the fact that as intelligent human beings, we understand natural languages
and are able to reasoning using them.
However, the existence of explicit machine interpretable ontologies is crucial to
facilitate communication between heterogenous agents, as well as a means of accessing
and referring to them (such as an access protocol or a naming space)[29]. In an
open environment, agents are developed by different programmers and organisations,
and designed around various ontologies, either explicit or implicit. Assuming agents
interact with an open system sharing intrinsically the same ontology is therefore not
realistic. This is also one of the main driving forces for current research activities in
the Semantic Web[7] and service description languages[84].
An ontology based communication envisaged by FIPA is illustrated in Figure
6.1[29].
In a more general and ambitious setting, FIPA’s ontology service specification
XC00086D[29], suggests that one or more Ontology Agents should be implemented in
an open environment to facilitate the following:
93
Ontology Query
Ontology
Ontology Query
ACL Communication =
Agent A Agent B
Ontology-Based Communication
Figure 6.1: Ontology-Based Communication Model
• querying the definition of terms
• selecting the shared ontology
• checking the equivalence of two ontologies
• locate a particular ontology
• translating a term
6.3 Representing Ontologies
Now that we have discussed what an ontology can do, along with the dimensions on
which it may differ, we can now have a closer look at ontologies themselves. What is
an ontology about? What should it look like and what should actually appear in the
representation of an ontology?
According to Guarino[49], philosophically, a piece of reality is often captured by a
set of informal rules that constrain its structure, which is referred to as a conceptuali-
sation. It involves the underlying model of the domain in terms of objects, attributes
and relations. A conceptualisation may be implicit, e.g. exist only in someone’s mind,
or embodied in a piece of software. An explicit account or representation of some part
94
of a conceptualisation[48] is usually called an ontology. In other words, ontologies are
explicit specifications of the terms in the domain and relations among them[46].
In addition to conceptualisation, there are two other important features of an
explicit ontology:
• Vocabulary: this involves assigning symbols or terms to refer to those objects,
attributes and relations.
• Axiomatisation: this involves encoding rules and constrains which capture
significant aspects of the domain model.
In Figure 6.2, we illustrate that two ontologies may be based on different concep-
tualisations (Person Ontology 1 v.s. 3), they may be based on the same conceptual-
isation but use different vocabularies (Person Ontology 1 v.s. 2), they may also be
differ in how much they attempt to axiomatise in the ontologies (Person Ontology 2
v.s. 4). In other words, ontolgies are not necessarily absolute but could be context
sensitive.
It is important to note that the trees in Figure 6.2 only describe one essential
relation between concepts, namely, the “IsA” relation. Other relations do not appear
in Figure 6.2, for example, FatherOf(man, children).
Essentially, an ontology consists of a vocabulary of non-logical symbols, definitions
of symbols (maybe empty for the primitive symbols) and use the logical formula-
tion for non-primitives. Axioms constraining the interpretation of primitive symbols
(which maybe empty or outside the logical formulation).
In Ontolingua and Frame Logic[32], for the purpose of creating an ontology[88],
the central frame-based modelling primitives needed are defined and realised. In On-
tolingua, an ontology is defined as a formal explicit description of concepts in a
95
Person
Male Female
Person
Man Woman
Father Mother Dad Mum
(1) Person Ontology 1 (2) Person Ontology 2
Person
Anglo-Saxon Asian Latino ...
Man
(3) Person Ontology 3
Person
Woman
Dad Grandpa Mum
Grandma
(4) Person Ontology 4
Figure 6.2: Person Ontology
96
domain of discourse (class(sometimes called concepts)), properties of each concept
describing various features and attributes of the concept (slots (sometimes called
roles or properties), and restrictions on slots (facets (sometimes called role re-
strictions)). An ontology together with a set of individual instances of classes
constitute a knowledge base.
Take a person ontology for example, described below:
• Concept PERSON has two attributes name and address. This implies the domains
of name and address are the elements of PERSON. The range of name and address
are concepts of NAME and ADDRESS.
• Concepts MAN and WOMAN are defined as subclasses of PERSON. This implies that
all attributes defined for PERSON are also applicable for MAN and WOMAN.
• Concept FATHER is a subclass of MAN that implements a FatherOf relation.
The domain of a FatherOf relation is Father, the range of the relation is the
elements of CHILDREN.
• Similarly, concept MOTHER is a subclass of WOMAN that implements a MotherOf
relation. The domain of a MotherOf relation is MOTHER, the range of the elements
of CHILDREN.
• Concept CHILDREN is a class that has attribute children. The range of children
a non-empty set of the elements of PERSON.
The above ontology can be represented using the syntax of Ontolingua as:
//Concepts
class PERSON(?NAME, ?ADDRESS)\\
97
class NAME(?class)\\
class ADDRESS(?class)\\
class MAN(?class)\\
class WOMAN(?class)\\
class FATHER(?class)\\
class MOTHER(?class)\\
class CHILDREN(?class)\\
//attributes are instances of corresponding concepts
relation instance-of(?name, ?NAME)\\
relation instance-of{?address, ?ADDRESS)\\
//MAN, WOMAN are subclasses of PERSON
relation subclass-of(?MAN, ?PERSON)\\
relation subclass-of(?WOMAN,?PERSON)\\
//FATHER, MOTHER are subclasses of MAN and WOMAN, respectively
relation subclass-of(?FATHER, ?MAN)\\
relation subclass-of(?MOTHER, ?WOMAN)\\
//Attributes are inherited
relation domain(?name, ?PERSON)\\
relation domain(?address, ?PERSON)\\
relation domain(?name, ?MAN)\\
relation domain(?address, ?MAN)\\
relation domain(?name, ?WOMAN)\\
relation domain(?address, ?WOMAN)\\
//FatherOf and MotherOf are one-to-many-realtions
relation one-to-many-relation(?FatherOf)\\
relation one-to-many-relation(?MotherOf)\\
relation FatherOf(?FATHER, ?CHILDREN)\\
relation MotherOf(?MOTHER, ?CHILDREN)\\
//The value of children instances in the FatherOf
//relation is of type PERSON
relation instance-of(?children ?PERSON)\\
relation value-type(?children, ?FatherOf, ?PERSON)\\
relation value-type(?children, ?MotherOf, ?PERSON)\\
//Possible Functions:
function value-cardinality(?children,?FatherOf):-> ?n\\
function value-cardinality(?children,?MotherOf):-> ?n\\
98
This person ontology can be further implemented in JAVA to achieve agent communication
at an ontological level. For the purpose of demonstrating how an ontology
is implemented in a programming language, part of the ontology code adapted from
JADE2.4 user guide[30] is shown below:
public class PeopleOntology extends FullOntology {
// The name of this ontology.
public static final String ONTOLOGY_NAME = "PEOPLE_ONTOLOGY";
// Concepts, i.e., objects of the world.
public static final String PERSON = "PERSON";\\
public static final String MAN = "MAN";\\
public static final String WOMAN = "WOMAN";\\
// Slots of concepts, i.e., attributes of objects.
public static final String NAME = "NAME";\\
public static final String ADDRESS = "ADDRESS";\\
// Predicates
public static final String FATHER_OF = "FATHER_OF"; \\
public static final String MOTHER_OF = "MOTHER_OF";\\
// Roles in predicates, i.e., names of arguments for predicates
public static final String FATHER = "FATHER";\\
public static final String MOTHER = "MOTHER";
public static final String CHILDREN = "CHILDREN";\\
private static PeopleOntology theInstance = new PeopleOntology();
public static PeopleOntology getInstance() { return theInstance; }
public PeopleOntology(Ontology base)
{
super(ONTOLOGY_NAME, ACLOntology.getInstance());
// Add definitions of schemata here.
......
}
}
99
6.4 Ontologies for Multi-Agent Belief Revision
Three levels of heterogeneities were identified in Section 5.4, namely, social charac-
ter heterogeneity at the social level, semantic heterogeneity at the meta level and
syntactical at the content level.
While most ontology languages serve at the content level, the syntactic heterogene-
ity is highly application dependent and requires knowledge acquisition in the domain
(e.g. Internet resource allocation, travel industry). The domain specific ontology can
be implemented using the syntax available in JADE ontology support. The JADE
ontology base class diagram is shown in Appendix C.
The following two sections will not discuss the syntactic heterogeneities as they
are domain dependent. However, we discuss the social heterogeneities and semantic
heterogeneities pertaining to belief revision frameworks for multiple agents.
6.4.1 Tackling the Social Character Heterogeneity
We define a heterogenous society as a multi-agent system that is populated with both
rational and passionate agents, who might be competent or incompetent in a certain
domain. To enable the inter-operability within and between heterogenous societies,
ontologies are needed for the purpose of supporting communication by translating
between different modelling methods and paradigms for instance.
The social heterogeneities presented in multi-agent belief revision frameworks are
typically reflected by the modelling method of shared belief and the modelling method
of trust.
As shown in the discussion in Chapter 5, existing frameworks have different models
to represent shared belief and private belief. To complicate the matter even further,
100
there is no consensus as to how private belief can be protected from shared belief. In
other words, the knowledge structures are heterogenous. Therefore, to have agents
built around different knowledge structures, an ontological description of a knowledge
structure is needed. The knowledge structure has to be general enough to represent
each structure considered and sophisticated enough to separate shared belief from
private belief.
According to the classification dimensions introduced in the previous sections, here
we need a computer-executable semi-formal ontology that addresses heterogeneities
in the domain of structuring knowledge.
Another type of heterogeneity involves the way of modelling trust. In a heteroge-
nous society, agents can range from trustworthy or untrustworthy. Due to the fact
that agents are built by different vendors and represent different users’ interest, we
can not assume agents are all competent and always sincere. Agents can be unfaithful
in order to maximise their utility. Agents may also be incompetent due to program-
ming defects. Therefore, it is crucial to understand how trust can be interpreted in a
multi-agent belief revision domain, how it affects the sharing of information and how
an agent can survive and build up their knowledge about others in an untrustworthy
environment. An ontological description of the trust issue on information sources (as
information passing and sharing are the main activities concerned in belief revision
involving multiple agents) are needed to describe the model of domain belief and the
necessary format of social belief. Such an ontology will enable the representation
of an agent’s insincere behaviour as an information source. For example, delivering
information that it does not believe in. The ontology also facilitates reasoning about
other agents’ competency and thus minimises the possibility of being defrauded by
101
untrustworthy agents.
6.4.2 Tackling the Semantic Heterogeneity - Translating among
various ranking systems
In general, there are two major ranking systems employed by the major belief revision
techniques discussed in chapters 3 and 4. Namely, the use of ordinals and the use of
the unit interval [0,1]. These two ranking systems are not equally expressive. In most
cases, the unit interval is considered richer than the ordinals. Therefore, information
may be lost when one translates ranks from a rich ranking system like [0,1] to an
ordinal one.
Benferhat et al.[5] shows that it is possible to translate between Spohn’s kuppa
function (ordinals) to the necessity ordering of possibility theory (unit interval),
namely,
µ = e −σ
102
(6.1)
where 0 < µ < 1 and σ is an ordinal. This equation works for translating between
infinite orderings.
In the case of translating between two finite orderings, one possible transformation
from [b1, b2] to [0,1] can be done by a conditioning function, which maps the highest
ordinal to 1 and the lowest ordinal to 0.
µ =
o − b1
b2 − b1
(6.2)
Numerically, it is realisable to translate between a unit interval to a ordinal.
However, it is not always feasible to translate between two ranking systems or even
within one ranking system that based on different revision scheme.
In fact, even if the same ranking mechanism is adopted, the ordering can take
on different meanings. For example, in AGM’s epistemic entrenchment settings, the
ordering describes the underlying importance of each sentence in face of change. In
other words, the relative importance may need to be altered when the epistemic input
is different. Furthermore, in Williams transmutations, the ordinal used for partial
entrenchment ranking can reflect the ordering of preference or the different level of
necessities or capturing the degree of suprise[109]. Similarly, the unit interval can take
on meanings such as the degree of belief(Theory of Evidence), statistical probabilities
(Bayesian Theory) and possibilities (Possibility Theory) in different mathematical
revision paradigms.
Determining the appropriate translation may require substantial communication
between agents to clarify the intended meaning of their ranking and the underlying
revision scheme.
According to the classification criteria above, on the semantic heterogeneity of
ranking systems, a problem solving ontology is needed to transform one ranking
system to another.
6.5 Discussion
Ontologies are not panacea, they can be both constructive and destructive. Informa-
tion distortion could occur during the generalisation process of ontology design. Many
criteria exist to prescribe a good ontology[46] and more are still under investigation.
Essentially, the key is to thoroughly understand the problem domain.
To design an ontological knowledge structure and model trust, both philosophical
and psychological investigations into the nature of shared/common, private knowledge
103
and trust issues are necessary.
Trust issues are investigated in chapters 7 and 8. Basic components of evaluating
trustworthiness of information sources are identified, together with the way of repre-
senting malicious and incompetent behaviour of information sources. This not only
provides the essential data needed for fusion and conflict resolution but also prepares
the ontological components of an agent’s social beliefs and domain beliefs as shown
in Section 10.4.1.
In Chapter 9, a general knowledge structure, which encompasses private, shared
and accessible knowledge, is proposed. In the knowledge migration phase, a proper
revision operator on a shared domain poses a great challenge due to the fact that
belief revision in this case is a mixed process composed of traditional belief revision,
communication and other interactions. Sophisticated decision making techniques are
required of such a belief revision operator, because the revision process could branch
according to communication mode and social intention. Therefore in certain circum-
stances, the revision result might not be easily determined.
104
Chapter 7
Trust Evaluation
“.... trust is a social good to be protected just as much as the air we
breathe or the water we drink. When it is damaged, the community as a
whole suffers; and when it is destroyed, societies falter and collapse.”
7.1 Introduction
— Sissela Bok (1978) in [8]
A dominant approach to trust evaluation in the agent literature stems from viewing
agents as software modelled on humans. In this approach agents are ascribed mental
states (beliefs, desires etc), have personalities (benevolent, malicious etc) and are
able to make decisions and act autonomously (i.e. without human intervention). The
most promising attribute of agents is that, in addition to the ability to stand alone,
make decisions and perform on their own as individual entities, they can interact
with each other, establish (cooperative or competitive) relationships, thus forming
so-called agent societies. Some researchers go even further by exploring the idea of
a digital city 1 , which hosts citizen agents under the governance of police agents and
1 Digital City: http://www.digitalcity.gr.jp/virtualcommunity/tourguide.html
105
military agents, and so forth. In such virtual agent societies, analogous to physical
human societies, it is necessary to consider the possibilities of fraud, being cheated,
and being deceived during information exchanges. This raises the issue and fuels the
growing interest in trust.
The interest in a formal theory of trust for the purpose of agent research can be
traced back to the early 90’s[62]. Furthermore, there has been a resurgence in recent
years inspired by The First International Workshop on Deception, Fraud and Trust
in Agent Societies in 1998.
Despite the broad use of the term “trust” in network security, cryptography and
e-commerce, it is rarely generally defined in the agent literature. One reason for
this is that the notion itself is highly context-sensitive and can be given a variety of
readings; one can define it for specific applications but not easily for the general case.
Elofson[26] attempted to give a composite definition of trust after studying several
perspectives on the meanings of trust:
Definition 7.1.1. Trust is the outcome of observations leading to the belief that the
actions of another may be relied upon, without explicit guarantee, to achieve a goal
in a risky situation.
From our vantage point, this definition is a good definition because it emphasises
the belief aspects of trust, the risk involved in trust and the close relationship between
trust and delegation. However, there is an important element missing, one that we
are particularly interested in, that is the “reliance” on the information an agent
conveyed 2 .
It is important to clarify the phrase trust of an information source. This is different
2 On the other hand, communication can be thought of as a special form of action performed by
the trustee agent, which is perceived by the trustor agent. One could argue Elofson definition covers
the special case of defining trust on information sources.
106
from trust of another agent’s capability and responsibility for carrying out certain
delegated tasks. It is about the credibility of the information delivered by the source
agent. For example, consider the following questions:
1. Shall I trust the informant, is it possible that he is lying to me?
2. Is he competent in the subject matter, how can I know that he is not telling me
something stupid?
Thus, an agent’s trustworthiness as an information source is evaluated using the
credibility of the information conveyed.
In this and the following chapter, we focus on how an agent can obtain and
evaluate the trustworthiness of an information source. Two essential constituents
belief are identified in Section 7.2, namely, competency and sincerity. In Section 7.3,
we propose the corresponding evaluation procedures. By evaluating sincerity and
competency separately, and in addition to the information’s pedigree, we are able
to analyse and model the process of passing-on information in Section 8.1. Using
an example, Section 8.2 demonstrates an application of evaluating trustworthiness
during the process of resolving conflicting information.
The work presented in these two chapters is incorporated into a social belief revi-
sion agent in Chapter 10 which is capable of revising both its social knowledge base
and its domain knowledge base (i.e. revising information from multiple sources). In
addition, the belief revision agent is capable of interacting with other agents to carry
out multi-agent belief revision.
107
7.2 Essential Constituent Beliefs for Trusting Information
Sources
Castelfranchi and Falcon[13] pointed out that the degree of trust is a function of the
subjective certainty of the pertinent beliefs, namely, the cognitive constituents that
are essential to establish trust with another agent. These include competence belief,
disposition belief, dependence belief, fulfillment belief, willingness belief, persistence
belief and self-confidence belief. The component beliefs are identified and evaluated
to help the decision making in delegating certain tasks to a trustee, not for the
purpose of determining the reliability of a trustee as an information source. However,
it does shed light on how to decompose the problem of evaluating trustworthiness
into tractable components. Taking a similar approach, in this section, we identify the
essential constituent beliefs for trusting an information source.
The communicative act considered here for exchanging information is most ap-
propriately described as an inform act, using performatives defined in FIPA ACL 3 .
Provided that the communication is successful, the result of the inform act is that
the receiver successfully receives the information the sender intended to send it to. In
other words, when an agent receives some information from another agent, the action
of informing has already been performed by the trustee (i.e. the sender). There-
fore, the evaluation on disposition, willingness, fulfillment and persistence belief is
no longer necessary, as these are beliefs regarding the extent to which the delegated
action (i.e. informing in this case) is to be carried out. This is the major difference
between trust on delegation and trust of information sources, when trust of informa-
tion sources is considered as a special case of trust on delegation. What remains is
3 FIPA: Foundation of Intelligent Physical Agent: http://www.fipa.org, ACL: Agent Communi-
cation Language.
108
the competence belief and the dependence belief, where dependence belief is closely
related to sincerity belief defined in the list below.
According to Demolombe[15], a sender agent’s trustworthiness on delivering cor-
rect information can be analysed on the basis of four elementary properties:
1. Sincerity: agent A is sincere with respect to agent B when he believes what he
says to B.
2. Credibility: agent A is credible when what he believes is true in the world.
3. Co-operativity: agent A is co-operative with respect to agent B if he tells B
what he believes.
4. Vigilance: agent A is vigilant with respect to p if, whenever p is true in the
world, then A believes p.
Not surprisingly, philosopher John Hardwig[56] pointed out that the reliability
of a receiver’s belief depends on the reliability of the sender’s character, both his
moral character and his epistemic character. The moral character is mainly the
agent’s truthfulness, while the epistemic character involves his level of competence,
conscientiousness and epistemic self-assessment.
It is not hard to see the two essential pertinent beliefs that both Demolombe
and Hardwig agree on here are: the sincerity and the competency. Furthermore, the
discussion earlier in this section using Castelfranchi and Falcon’s approach confirms
the same decomposition.
Observation: The sincerity and the competency beliefs are the necessary con-
109
stituents in the evaluation of a social cognitive agent’s trustworthiness as an
information source. Although these two are not the only ones required, they
are sufficient in the sense that most other possible constituents fall into these
two categories.
What about the cooperativity and vigilance proposed by Demolombe[15]? Should
they be in the set of the component beliefs for trusting an information source?
As a necessary condition for an agent to be credible, vigilance falls into the broader
category of competency.
Cooperation and trust have a strong reciprocal relationship with each other. That
is, a trusting climate encourages cooperation, and a positive cooperative outcome
in turn enhances the level of trust for all parties involved. Marsh[83] claims that
cooperation can be classified according to the incentive as cooperation towards mutual
rewards, cooperation based on communal relationships and cooperation that emerges
from coordination. No matter what incentive makes an agent cooperative or not, the
result of cooperativity in information exchange is a matter of whether the receiver
(trustor) obtained some information from the sender (trustee) or not. Generally,
agents who are not cooperative will either provide no information or wrong/misleading
information. Whereas, agents who are cooperative will provide information truthfully.
As a consequence cooperativity analysis for information exchange can be considered
as an important factor that may affect the degree of sincerity. It then becomes part
of the sincerity analysis but not necessarily an independent component belief in its
own right.
Assumption: By accepting the separation of trustworthiness into competence
and truthfulness beliefs, from now on, we can assume the trustworthiness of
information sources are scalable and comparable.
110
honest
ignoramus
trustworthy
agents
non-sense agents
dishonest
experts
Figure 7.1: Four Types of Agents in terms of Sincerity and Competency
Therefore, by interpreting trustworthiness in terms of agents’ competency and
sincerity, we are able to model the following types of agents, which are depicted in
Figure 7.1:
• G1: Trustworthy Agents (agents who are both truthful and credible)
• G2: Honest Ignoramus (agents who are honest but not credible)
• G3: Dishonest Expert (agents who are credible and not honest)
• G4: Nonsense Agents (agents who are neither truthful nor credible)
7.3 Trustworthiness and Degree of Beliefs
In the fields of data fusion[3], weighted knowledge base merging[76], multiple source
conflict resolution [19] and multi-agent belief revision[68], the value of trustworthiness
is always assumed to be given. In this section, based on the observation in Section
7.2 above, we present two ways of using trustworthiness. One is that the degree of
trustworthiness t is used as a single value, the other is the degree of sincerity (s) and
the degree of competency (c) used separately with the degree of beliefs δ.
111
7.3.1 Degree of Trustworthiness
Given the value of an information source’s competency and sincerity, the total trust
on an information source T can be computed using an evaluation function τ(s, c) :
S × C → T , which maps a degree of sincerity s ∈ S and a degree of competency
c ∈ C to the trustworthiness of an information source t ∈ T . s, c, t ∈ [0, 1], with 1
the most truthful, credible and trustworthy respectively, 0 the least. The greater the
value of t, the more trust an agent has in an information source.
⎧
1, if s = c = 1
⎪⎨
0, if s = c = 0
τ(s, c) = c,
s,
⎪⎩
s ⊕ c,
and ∀y∃z, tx(y) ≤ tx(z) or tx(z) ≥ tx(y)
if s = 1
if c = 1
otherwise.
Subscripts and variables (e.g. x, y, z...) are used to indicate agents, i.e., trustee
and trustor. For example, tx(y) is agent x’s faith in agent y as an information source.
Similarly, we can have sx(y) and cx(y) for agent x’s evaluation of agent y’s sincerity
and competency respectively.
Three simple operators that can be used for ⊕ are:
• τmulitply = s × c
• τmin = min(s, c)
• τssf = 1 − (1 − s)(1 − c)
= s + c(1 − s)
= c + s(1 − c)
112
The multiplication τmulitply and the minimum operator τmin are straightforward, and
need little explanation. The third function τssf is the so-called Bernoulli’s rule of
combination[98], which is a special case of Dempster-shafer’s rule of combination on
Simple Support Functions(SSF), where s and c are viewed as single support functions
on an agent’s sincerity and competency respectively[98]. It can be easily shown that:
τmultiply ≤ τmin ≤ τssf
In our model an agent can choose different operators for different situations, or an
agent can be designed with different characteristics in terms of how it evaluates others.
Multiplication τmultiply tends to be cautious but pessimistic, Bernoulli’s combination
shows optimistic behaviour, while minimum operator is mild and represents a com-
promise between the two.
7.3.2 Degree of Deception and Degree of Sincerity
Given two agents, x and y, sx(y) denotes x’s evaluation of y’s general 4 sincerity on
information that he delivered, and 0 ≤ sx(y) ≤ 1. The intended interpretation of this
value is to what extent y tells exactly what he believes in his own knowledge base. For
example, y believes p at a degree δ, but he may decide to tell x that he believes p at a
degree δ ′
. To allow agents to communicate both the content and the degree of beliefs,
we assume the message takes the form: (p, δyx), where p is the information, δyx is the
degree of belief delivered along with the information p, whilst the real degree held
by agent y is δy. To minimise the negative effect of being deceived, agent x’s task is
4 We use general here to indicate that the degree of sincerity sx(y) is not content sensitive. The
content sensitive value will be represented using sx(y, O) as show in Section 7.3.3.
113
to guess a value as close as possible to δy before making any changes that might be
triggered by the information from y.
Using this general message format, we are able to model different levels of an-
ticipated deception. The degree of belief discussed in this paper is considered as a
Bayesian’s probability measure, where δ(p) = 1 means that p is accepted, δ(p) = 0
means p is rejected or ¬p is accepted and undetermined if 0 < p < 1[40]. Particu-
larly, δ(p) = δ(¬p) = 1
2 is considered as the way of expressing complete ignorance5 .
Therefore, in the extreme case, an agent can tell the opposite of what he believes (i.e.
δy = 0 but δyx = 1 and vice versa) or tell something he is completely ignorant about
(δy(p) = δy(¬p) = 1
2 , but 0 < δyx < 1).
It is true in the real world, sometimes, truthful messages might be unbelievable,
and sending them could be irrational. On the other hand, some lies might be believ-
able, or at least could sway the receiver to reconsider or change its actions in favour
of the sender. As 0 ≤ δ ≤ 1, there are boundaries as to what extent an agent can lie,
and the degree of deception(γ) is thus defined:
γ =
|δyx − δy|
max(δy, 1 − δy)
The sender agent’s decision about the value of γ is affected by various factors,
but mainly (and intuitively) by two: the utility and the believability. In other words,
there is a optimal value for γ which can maximise his utility and also sound true but
not absurd. As this is not our major concern, we are not going to pursue this further
here. If interested, please refer to Gmytrasiewicz’s[44] study on why and when it is
5 Bayesian theory is often criticised for its inappropriate representation of ignorance, but our
definition on the degree of deception can be easily modified to fit into other definitions of degree of
beliefs such as the one used in Dempster-Shafer’s belief functions.
114
feasible for an agent to lie to others.
The receiver agent x, on receiving a information couple (p, δyx), will have to guess
the value of δy and use the obtained δ ′ y along with the competency belief (c) for his
further decision making. Assume agent x himself uses the above mechanism for γ
to defraud others, then he is likely to make the assumption that y is using similar
mechanisms for himself[25]. A reasonable guess can be achieved if we assume,
degree of deception ≡ 1 - degree of sincerity (i.e. γ ≡ 1 − s)
Substituting γ with 1−s in the above definition sentence for γ, which is the subjective
guess of γ, we have
OR
δ ′ y =
δyx
1 ± (1 − s) and δ′ y ≥ 1
2
δ ′ y = δyx ± (1 − s)
1 ± (1 − s) and δ′ y < 1
2
115
where s �= 0 (7.1)
where s �= 0 (7.2)
In the case where s = 1, δ ′ y = δy, which means x believes y is completely truthful in
the information that y delivered. In the case of s = 0, agent x can just ignore the
information and not make any changes to his knowledge base.
The “cleaned” degree of belief δ ′ y can then be used together with the degree of
competency c to obtain the degree of acceptance 6 δ y x. To obtain this value, the com-
bination operators proposed in Section 7.3.1 can be used. This will provide reliable
input to belief change and knowledge base integration etc, which is illustrated by an
example in Section 8.2.
6Degree of acceptance is the degree of belief at which an receiver agent will incorporate the
information into his own knowledge base.
7.3.3 The Evaluation of Competency and Sincerity
Sections 7.3.1 and 7.3.2 describe two ways of using degrees of competency (C) and
degrees of sincerity (S) provided an agent already has the values c and s. But how
and where does an agent get these values?
In the real world, we often have some general feelings about others’ trustworthi-
ness, such as x generally trusts y to a degree, which is denoted by tx(y) in Section
7.3.1. But quite often, trust on a certain action is specific to task(s). Similarly, an
information agent’s trustworthiness specifically depends on the domain area of the
incoming information. For example, we might trust our father’s opinion on how to
get our TV fixed if he is an an electronic engineer, but would not trust his opinion
on the direction of our AI research. Therefore, a general static trust value is not
sufficient and we need a context sensitive measure of trust. So we introduce a topic
specific trust evaluation towards others in both competency and sincerity. Thus, we
augment the notation with one more variable, the topic O. We denote cx(y, O) as x’s
evaluation of y’s competency with respect to topic O. Similarly we have sx(y, O).
According to whether there is any previous experience with a trustee, Marsh [83]
suggests three possible situations that an agent might encounter in assessing other’s
trustworthiness. They are adapted to suit our needs and listed below.
1. The agent is not known, in this or similar topics.
2. The agent is known, but not in this or similar topics.
3. The agent is known and trusted in this or similar topics.
Inspired by Jonker and Trenur’s trust dynamics[64], the above three situations
can be handled respectively as shown below:
116
1. In the first case, without previous trust influencing experiences but with a
given competency or sincerity threshold, cδ or sδ, the information source can
be treated as either initially competitive cx(y, O) ≥ cδ (faithful sx(y, O) ≥ sδ)
or initially uncompetitive cx(y, O) < cδ (unfaithful sx(y, O) < sδ). Practical
strategies can be added to enable agents to choose different initial values in
different situations.
2. If the agent is known in some other topics, the non-relevant previous experience
can be used as a coefficient (0 ≤ α ≤ 1) to adjust the initial competency
(sincerity) as assigned in the first case.
3. For the third case, the previous experiences can be used to calculate the cur-
rent competency (sincerity) using a competency (sincerity) evaluation or update
function. Such functions can be defined to suit various applications by following
the properties and constraints proposed by Jonker and Trenur[64]. Although
such functions are applicable for both competency and sincerity evaluation, one
may find that an agent’s competency value is unlikely to change as dramati-
cally as the sincerity value does. Therefore, it is reasonable to expect a slow
dynamic in competency evaluation/update functions as compared to the ones
for sincerity.
The above procedures are applicable for information that contains a single topic.
For information that contains more than one topic, we will have to obtain the com-
petency value and the sincerity value for each individual topic first and then combine
them using the same set of combination operators (i.e. τmultiply, τmin and τssf) pro-
posed for trustworthiness evaluation in Section 7.3.1.
117
Using formal methods to encode the incoming information, we can calculate the
topics for it[82]. Topics of a sentence p are defined as the minimum set of atoms
occurring in p. For example, given φ = a ∨ b, φ ′ = a ∧ b, ψ = (a → b), and
ψ ′ = (a → ¬b), using uppercase letters A and B to denote the topic for proposition
a and b respectively, we have
topic(φ) = topic(φ ′ ) = topic(ψ) = topic(ψ ′ ) = {A, B}
Consider the following example: Agent y told agent x that e-commerce does not
necessarily involve computer science (i.e. a → ¬b). There are two topics: e-commerce
(A) and computer science (B) involved in the information delivered by y. Given the
values of cx(y, a) and cx(y, b), to calculate the combined competency of agent y on
this information, we have
cx(y, {A, B}) = cx(y, A) ⊕ cx(y, B)
The above function can easily be extended to calculate the combined competency
(sincerity) for more than two topics.
118
Chapter 8
Information Pedigree
“The foundation theory holds that some of one’s beliefs ‘depend on’ oth-
ers for their current justification; these other beliefs may depend on still
others, until one gets to foundational beliefs that do not depend on any
further beliefs for their justification. ...
On the other hand, according to the coherence theory, it is not true that
one’s ongoing beliefs have or ought to have the sort of justificational struc-
ture required by the foundations theory. In this view ongoing beliefs do
not usually require any justification. Justification is taken to be required
only if one has a special reason to doubt a particular belief. Such a reason
may consist in a conflicting belief or in the observation that one’s beliefs
could be made more “coherent”, that is, more organised or simpler or less
ad hoc, if the given belief were abandoned (and perhaps if certain other
changes were made).”
119
— G. Harman (1986) in [57]
8.1 Evaluating Trust on Passing-On Information
It is known that a large majority of knowledge and beliefs come from indirect expe-
riences, namely, communication. In the real world, communication is not necessarily
restricted to conversation with other agents. It also includes emails, publications,
books, newspapers and TV channels and more recently the Web. We do not distin-
guish these special information channels from agents as information sources. Instead,
they are considered as special types of information sources and an agent must evaluate
their trustworthiness.
Furthermore, the communicated information itself could come from the sender’s
indirect experiences as well. In such cases, the sender serves as a mediator who passes
on information from a source agent to a receiver agent.
Literature related to the trust of information sources often only consider the recip-
rocal trust attitudes among agents. There are few studies on the trust of passing-on
information. Even in the real world, people tend to ignore the importance of passing-
on information, which may result in the receiver’s inability to diagnose the sources of
conflict. Consequently, this will affect the receiver’s evaluation of other agents, and
as a result the quality of their acquired information.
For example, in a Robot Soccer scenario 1 , the perception of a robot is limited,
the robot who is far away from the ball has to rely on communication to obtain the
estimated position of the ball. Suppose Robot-1 is close enough to perceive the ball
position, he sends information about the position of the ball to the closest robot, say
Robot-2, and Robot-2 passes this information onto Robot-3. Typically, Robot-3 will
consider the received information as Robot-2’s perception because the information
1 Thanks to James Brusey at RMIT University for the valuable discussion on Robot Soccer.
120
Robot-3
Robot-2
Robot-4
Robot-1
ball
Figure 8.1: Robot Soccer Scenario
source (Robot-1) is normally not mentioned. Suppose at the same time (the ball
hasn’t been moved yet), Robot-3 got a message stating a different position message
from Robot-4 who is also close enough, then Robot-3 has to judge which position is
more accurate before taking action.
In such situations where conflict occurs, it is crucial for an agent to identify the
original sources that are responsible for the conflicting information. The need for this
is intensified in highly risky situations.
8.1.1 Representing Information Pedigrees
One natural and sensible approach a proactive rational agent could take to further
clarify the conflicting information sources is to interrogate the sender agents. By con-
flicting information sources we mean those agents whose information when considered
together will spoil the consistency of the receiver agent’s knowledge base.
To facilitate such interrogation, idealistically agents would retain an infinite rea-
sonable depth of information pedigree, which records the origin of the information.
121
Figure 8.2: Information Pedigrees
However, this is not practical. We will show in this section, by allowing agent to de-
scribe passing-on information, a three level information pedigree would be sufficient
in terms of keeping information about the sources.
It is widely accepted that agents receive information from two major channels via
their perceptions directly from the environment and via communication with other
agents. Thus, on other agents’ query about the source of information an agent should
have one of the following answers:
1. The information in doubt is my own observation.
2. The information in doubt is from agent-1 (maybe also from agent-2, agent-3, ...
agent-n), the pedigree tree is thus enlarged.
We depict different scenarios of information gathering using information pedigree
diagrams in Figure 8.2, where agents are nodes and the directed arcs stands for
information route.
122
The trustworthiness assessment represented by Scenario 1 and 2 in the pedigree
diagram concerns pairs formed by individual senders with the receiver. Scenario
1 illustrates that agent-2 tells agent-1 some of his observed information, whereas
Scenario 2 represents the situation where agent-1 receives observational information
from multiple agents. With the degree of trustworthiness (or degree of sincerity and
degree of competency) prepared as in Section 7.3, Scenario 1 turns into a traditional
belief change problem - how to maintain a consistent knowledge/belief base in face
of new information. While Scenario 2 becomes a fusion (or knowledge base merging)
problem - how to incorporate new information from multiple sources.
Scenarios 3, 4 and 5 illustrate more complicated cases where senders pass on
information from the original sources to a receiver. The general information format
(p, δyx) used in Section 7.3.2 is only suitable for the pair-wise communication shown
in scenarios 1 and 2. Such representation is not sufficient for passing-on information,
as the receiver agent also expects the sender agent to tell him some information about
the original source. Therefore, we propose the following four tuple,
Iyx : (p, z, δyx, δzyx)
where, x, y, z are agent IDs, p is the information, z is the original source of information
p, δyx is agent y’s degree of belief of p that agent y told agent x, δzyx is agent z’s
degree of belief of p that agent y told agent x. When z = y, that is, the sender is the
original source, (p, z, δyx, δzyx) is then equivalent to (p, δyx).
Using the above information format, a sender can send a receiver not only his own
degree of belief on p but also pass on other agent’s degree of belief on p. Moreover,
Scenarios 3, 4 and 5 can then be represented using information matrix similar to the
example shown in Table 8.1 for Scenario 4,
123
Information Sender Source Sender’s DOB* Passing-on DOB*
p 2 3 δ21 δ321
... ... ... ... ...
p n 3 δn1 δ3n1
p n ... δn1 δ...n1
p n m δn1 δmn1
∗DOB - Degree Of Belief
Table 8.1: Agent-1’s Information Matrix for Scenario 4
8.1.2 Information Pedigree Transformation using Trust Evaluation
As we are talking about sincerity and competency, we have to consider the sender’s
trustworthiness on both the information itself and passing-on information about the
original source.
Taking Scenario 3 for instance, on receiving (p, 3, δ21, δ321), agent-1 faces the fol-
lowing uncertainties,
1) Agent-2 may or may not be faithful about his degree of belief on p, that is,
δ2? = δ21, where δ2 is agent-2’s true degree of belief on p and δ21 is what agent-2
told agent-1. For evaluation, degree of sincerity on topic P (i.e. s1(2, P )) could
be employed here.
2) Agent-2 may or may not be competent in evaluating p. For evaluation, degree
of competency on topic P (i.e. c1(2, P )) could be used here.
3) Agent-2 may or may not be faithful about what agent-3 told him, that is,
δ32? = δ321, where δ32 is the real value agent-2 received from agent-3 and δ321
124
is what agent-2 told agent-1 about δ32. Using a similar approach as equation
(7.1) and (7.2), we can estimate δ32. The estimated value δ ′ 32 is thus a function
of δ321 and degree of sincerity s1(2, 3) in the topic about agent-3.
4) Agent-2 may/may not be competent in passing information onto others, e.g.
not certain whether the information is distorted during the process or not. This
could be evaluated using the degree of competency c1(2, 3) in the topic about
agent-3.
Uncertainty of types 1) and 2) can be handled using the standard pair-wise trust-
worthiness evaluation proposed in Section 7.3. For uncertainty types 3) and 4), the
topic of the trustworthiness evaluation is no longer about p, but about another agent,
which is why we have the notation s1(2, 3) and c1(2, 3) in the above list.
The ultimate goal of sincerity analysis is to get a close estimation of the source
agent’s degree of belief in p. In the case when agent-3 tells agent-1 directly about p,
according to equation (7.1) and (7.2), we have,
125
δ ′ 3 = f(δ31, s1(3, P )) (8.1)
But in the case of Scenario 3 in Figure 8.2, agent-1 has to estimate the relationship
between agent-2 and agent-3 and thus figure out the possibility that agent-3 lies to
agent-2, which could be captured using the degree of sincerity s1(32, P ). Therefore,
using δ ′ 32 and s1(32, P ) to substitute δ31, s1(3, P ) in the above formula 8.1, agent-1 is
able to estimate δ ′ 3 shown as follows,
δ ′ 3 = f(δ ′ 32, s1(32, P ))
To generalize the above process, we can use the following transformation shown
in Figure 8.3.
Figure 8.3: Information Pedigree Transformation
Figure 8.3 shows us that a 3-level pedigree tree can be transformed into a 2-level
one. This will finally enable the use of belief change techniques, data fusion, merging
or integration techniques to help the receiver agent maintain a consistent knowledge
base.
As one may notice, the information pedigree diagrams in Figure 8.2 are no more
than 3 levels in depth. This is because as soon as the receiver is notified about another
agent by the sender, the receiver agent can directly contact the third involved agent for
further information requested. Adding in another level of pedigree will unnecessarily
increase the complexity of the trustworthiness evaluation process, which requires an
agent to estimate the relationship of too many other agents. Therefore, to keep no
more than one level of information source is sensible and sufficient for an agent to
maintain the origin of communicational information.
8.2 An Example in Resolving Conflicting Information
Consider the following example,
John is interested in acquiring a property. After inspecting a potential property,
he suspects that the dining room is a new extension and is not sure whether it is a
legal extension. Then he inquired about this with the real estate agent, asked his
126
Agent Information
Lawyer: 1 No building approval in the past 7 years. e → ¬l
Real Estate Agent: 2 No building extension within the last 10 years. ¬e
John’s observation: 3 Dinning area seems to be newly extended e
Friend A: 4 Statements about the purchaser’s inspection. s
Friend B: 5 Statements suggest a possible illegal extension. s → ¬l
Table 8.2: John’s House Inspection
Agent Information Degree Of Belief Sincerity Competency Trustworthiness(×)
δyx sx(y, P ) sx(y, P ) sx(y, P )
1 e → ¬l 1 1 1 1
2 ¬e 0.9 0.4 0.8 0.32
3 e 1 1 0.5 0.5
4 s 1 1 0.8 0.8
5 s → ¬l 0.9 1 0.6 0.6
Table 8.3: John’s Social Knowledge
lawyer to read legal documents on the property, and also listened to two friends’
opinions. Following is a summary of what he has gleaned from different sources:
In Table 8.2, we assume that John has the values for degree of sincerity (s) and
degree of competency (c) in his social knowledge base already. Then we can either
work out the degree of trustworthiness (t) based on the values of s and c, or use s
and c separately with δyx as shown in Section 7.3.
The trustworthiness values in Table 8.2 are obtained using operator τmultiply in-
troduced in Section 7.3.1. This prepares the essential values that are required by
Cantwell[11] in his process of resolving conflicting information.
127
Using the notation of relative support, Cantwell[11] obtains the order of sentences
based on the joint trustworthiness 2 of the sources that have rejected the states. Tak-
ing the example illustrated in Table 8.2 for instance, the conflict resolving process
suggested by Cantwell can be described using the following steps:
1. Construct all the possible worlds based on the information state:
t1 : e → ¬l; t2 : ¬e; t3 : e; t4 : s; t5 : s → ¬l
The possible worlds thus formed are
128
{(e, l, s), (e, l, ¬s), (e, ¬l, s), (e, ¬l, ¬s), (¬e, l, s), (¬e, l, ¬s), (¬e, ¬l, s), (¬e, ¬l, ¬s)}.
2. Given each agent(witness)’s individual trustworthiness, find out the joint trust-
worthiness of agents who reject the world, for example, for world (e, l, s), since
agent 1 and 2 reject e, agent 1 and 5 reject l, agent 5 reject s, the joint trustwor-
thiness of rejecting world (e, l, s) is then t1 +t2 +t1 +t5 +t5 = 3.52. Similarly, by
applying such procedure to each every possible world, we would thus associate
a joint trustworthiness value to each world.
3. The worlds which have the largest joint trustworthiness value are the candidates
to be rejected.
The above method does not guarantee a unique solution. Actually, in a special
case when all the witnesses have equivalent trustworthiness, it generates the maximal
consistent set of worlds, which is equivalent to the result of theory extraction[107].
Moreover, the worlds that are apt to be rejected are often the ones that do not satisfy
the proposition that no agent is against. This implies that things uttered by agents
take priority, if there is no objection, the receiver agent should accept it without
doubt.
2 In this case, the joint trustworthiness of a set of agents is just the simple addition of the individual
trustworthiness of each agent.
Alternatively, we can use equations (7.1) and (7.2) to work out the estimated
degree of belief (δ ′ y, y = 1, 2, 3, 4, 5) and combine δ ′ y with c to obtain the degree
of acceptance (δ y
john , y = 1, 2, 3, 4, 5) that the receiver agent (John) is willing to
consider. This will turn the above example into a standard belief revision problem,
which could be easily solved using the existing belief revision techniques, such as
Williams’ adjustment[108].
After calculating δ y
john , we have δ1 john > δ 4 john > δ 5 john > δ 3 john > δ 2 john, therefore,
δ 1 john(1) : e → ¬l
δ 4 john(0.8) : s
δ 5 john(0.54) : s → ¬l
δ 3 john(0.5) : e
δ 2 john(0.45) : ¬e
As the real estate agent’s claim has the lowest degree of acceptance, a rational
agent will give up ¬e and continue to accept that the extension is illegal to keep a
consistent knowledge base.
In addition, with the help of information pedigree, the receiver agent can figure
out the information that is in contradiction then ask the sender agents involved to
further track down the information source. For example, after inquiring, agent-2
(Real Estate Agent) told the receiver agent, my information is from the city council,
which is a definite trustworthy authority, the piece of information ¬e from agent-2
will then take a much higher priority in the above ordering. In this case John’s own
observation e can be discarded, i.e. he was wrong about the existence of an extension.
129
As shown by this example, the trust evaluation process proposed in here provides
valuable insights into areas such as belief revision, conflict resolution, fusion and etc.
In particular, the separation of sincerity and competency analysis offers a clarified
view of the analysis required for evaluating the trustworthiness of an information
source, which in turn enables the analysis of passing-on information and offers a
more flexible way of handling conflicting information. With information pedigrees,
we give agents another means of searching for more evidence so as to arrive at a unique
sensible solution. Furthermore, the trust evaluation based on experience makes the
framework applicable in iterative situations as well.
8.3 Discussion
Trust is often referred to as an adaption, a generalisation or as a means for the
reduction of complexity[83]. Adaption (via evolution) and generalization enables
agents to learn from experience in beneficial ways and provides agents with means
of reasoning about and to make general assumptions about other agents or their
environment for which they are ignorant. Therefore, trust evaluation is a valuable
and essential survival skill for agents as they interact in an uncertain social and
physical environment.
In this chapter and the previous chapter, we investigated a procedure for evaluat-
ing an agent’s trustworthiness as an information source. By separating this process
into competency analysis and sincerity analysis, we were able to deal with complicated
cases of passing-on information, where the same information may reach the receiver
agent through different routes. In order to keep information about the source agent,
130
we introduced information pedigrees as a means to maintain the history of communi-
cational information. Information sources’ trustworthiness analysis and computation
described herein can be used to prepare agents to perform fusion, weighted knowledge
base merging, and multiple source conflict resolution.
The results from these two chapters serves as the basis for an agent-oriented
implementation that supports the acquisition of information from multiple sources
with different degree of trustworthiness. Chapter 10 details the design of the system
which use the Java-based multi-agent programming paradigm JADE together with
Belief Revision and Theory Extraction engines[107] from SATEN.
131
Chapter 9
Shared Knowledge Structure and
Knowledge Migration
“For certain, consumers must be assured that agents will not compromise
private information and deviate beyond their constraints.”
9.1 Introduction
— Pattie Maes and Rober Guttman (MIT Media Labaoratory)
It is well-known that e-commerce is one of the major application areas of agent tech-
nologies. From a consumer buying behaviour (CBB) [79] perspective, agents can play
important roles in three primary CBB stages: product brokering, merchant broker-
ing, and negotiation as to what to buy, who to buy it from and how to determine the
terms of the transaction respectively. In particular, there already exists agent sys-
tems that can negotiate and make agreements in domains such consumer-to-consumer
(eBay’s Auction Web), business-to-business (FairMarket) and stock markets (E-Trade
and OptiMark Technologies). In order to trust and conduct trading using these sys-
tems, the agent owners must be assured that the agent will not compromise private
information and deviate beyond its design goals.
132
One of the major drawbacks of the frameworks we visited in Chapter 5 is that there
is no clear indication as to how the agent could explicitly separate owner’s sensitive
private information from the information that needs to be shared with other agents.
This is a context dependent decision. In the case when information is exchanged
mainly via communication, a simple solution could be to simply flag every piece of
information with an extra property - level of privacy. However, some problems may
still arise. First, hard-coding a privacy property could lead to maintenance problems
when the circumstance changes or the trading partner changes. Secondly, this also
poses problems when the involved parties can actually query each other’s databases.
Especially, considering that the two major goals of e-commerce is inter-operability
and automation, more and more information services provide direct database access.
Therefore, to have a dynamic knowledge structure is important for the purposes of
protecting private information from shared information and allowing different level
of sharing with regards to different agents in different circumstances.
In addition, the proposed sophisticated knowledge structure serves as a upper-level
ontology that addresses the social heterogeneities that may existed in an open system,
which is lacking in the current frameworks. In most of the frameworks presented in
Chapter 5, agents knowledge bases are considered to be accessible by all agents and
every agent provides faithful information. Therefore, with the informal ontology
proposed herein we are able to discuss shared knowledge and private knowledge in
different frameworks. As we will also show in Section 9.5, the process of multi-agent
belief revision under the shared knowledge structure becomes the process of knowledge
migration.
133
9.2 Shared Knowledge Structure
The accessible knowledge(KAcc) is defined as a subset of an agent’s knowledge base
(KB), which is open to anonymous viewers or certain viewers specified by the agent
itself. KAcc can exist in various circumstances, for example, a web site that provides
personalised information to personal assistance agents, or a buyer agent who can
dynamically change preferences according to the merchant it interacts with. Figure
9.1 illustrates three agents’ belief bases, with their subsets classified according to
dynamic accessibility.
R 11
Agent 1
K pri (1)
K 2-Acc (1,3)
R 13
K 3-Acc (1,23)
R 31
1
K 2-Acc (1,2)
K 3-Acc (3,12)
K 2-Acc (3,1)
R 12
K C
K pri (3)
R 33
1
R 21
K 2-Acc (3,2)
1
K 2-Acc (2,1)
R 32
Agent 3
K 2-Acc (2,3)
R 23
Agent 2
K pri (2)
K 3-Acc (2,13)
Figure 9.1: Accessibility to Knowledge Bases
From agenti’s point of view, the agent acquaintance base is populated by the
agents that it interacts with. Let us assume that there are n agents in the society
R 22
134
including agenti. We denote the KB of agenti to be K(i). It is composed of m-
accessible knowledge and m-semiprivate knowledge as defined below:
135
1. m-Accessible Knowledge: Accessible knowledge for agentj, denoted by KAcc(i, j),
represents the set of sentences that agenti determines to open to agentj. Since
agenti can fully access its own knowledge base, when i = j, KAcc(i, i) is actually
just K(i). To avoid any confusion that might arise, K(i) is adopted. Therefore,
in the following sections, KAcc(i, j) only stands for the cases when j �= i. As
the subset of KAcc(i, j) may also be accessible to agents other than i and j, it is
necessary to define strictly 2-accessible knowledge (K2−Acc(i, j)) and accessible
knowledge for multiple agents (KAcc(i, j · · · k)). Following is the definition:
K2−Acc(i, j) = KAcc(i, j) ∩ (∪(· · · , KAcc(i, k), · · ·))
where k �= i and k �= j. Let l be the cardinality of the set {KAcc(i, j), · · ·
, KAcc(i, k), · · ·}, the right hand side of the set operation results in a strictly
2-Accessible knowledge set iff l = C 2−1
coefficients, � �
s
= r
s! , n is the population of the society.
(s−r)!r!
KAcc(i, j · · · k) = ∩(KAcc(i, j), · · · , KAcc(i, k))
n−1 = n − 1, where C r s is the binomial
where m is the cardinality of the set {i, j, · · · , k}, 1 < m ≤ n. m is called the
degree of accessibility, KAcc(i, j · · · k) is the accessible knowledge for m agents.
Similar to the definition of K2−Acc(i, j), the m-accessible knowledge 1 Km−Acc(i, j · · · k)
could be defined based on KAcc(i, j · · · k)
1 m − accessible means strictly accessed by m agents. While the knowledge accessible by m agents
means this knowledge is accessible by any subset of the m agents.
K s (ij...n)
n-shared
knowledge
K s (ij)
2-shared knowledge
for agent i and j
KB
K n-Acc (i,j...n) K n-sp (i,j...n)
n-Accessible
Knowledge
K 2-Acc (i,j)
......
maximally n-1
2-Accessible Knowlege
n-semiprivate
knowledge
K 2-Acc (i,n)
K pri (i)
private
knowledge
Figure 9.2: Shared Knowledge Structure
Km−Acc(i, j · · · k) = KAcc(i, j · · · k) ∩ (∪(· · · , KAcc(i, p · · · q), · · ·))
KAcc(i, p · · · q) has the same degree of accessibility as KAcc(i, j · · · k), but set
{j, · · · , k} has no intersection with set {p, · · · , q}. Let l be the cardinality of
the set {KAcc(i, j · · · k), · · · , KAcc(i, p · · · q), · · ·}, the right hand side of the set
136
operation results in a strictly m-Accessible knowledge set iff l = C m−1
n−1 , n is the
population of the society.
The bottom up m-accessible knowledge classification results in a tree structure,
which is displayed in Figure 9.2, where m = 1, · · · , n.
2. m-Semiprivate/Private Knowledge: As the complement of Km−Acc(i, j · · · k),
the m-semiprivate knowledge Km−sp(i, j · · · k) is private towards agentj, · · · ,
agentk, which is accessible by agenti itself and agents other than j, · · · , k. The
following relation holds:
∪(· · · Km−Acc(i, j · · · k) · · · ) ∩ Km−sp(i, j · · · k) = K(m+1)−sp(i, j · · · k + 1)
� �� �
C m−1
n−1
When m = 1, the knowledge is only accessible by agent i itself and not by any
one else, it becomes the private knowledge of agent i, denoted by Kpri(i).
3. KB of agenti: K(i) is the knowledge base of agent i. Within this KB, the
agent can assign various level of accessibility to various agents in the society
and reserve the rest of the KB as its private knowledge Kpri(i).
K(i) = ∪(Kpri(i), K2−Acc(i, j), · · · , Km−Acc(i, j · · · k), · · · , Kn−Acc(i, j · · · n))
� �� �
1
� �� �
C 2−1
n−1
� �� �
C m−1
n−1
= ∪(Kpri(i), KAcc(i, j), · · · , KAcc(i, k) · · · , KAcc(i, n) )
� �� �
n−1
where j �= i and j = 1, · · · n for an n agent society.
Applying the definitions above to the other agent’s knowledge bases, K(i) can be
further classified:
1. Mutually Accessible Knowledge: It is the set of sentences that agents i, j, · · · , k
all believe but may not know whether everyone knows that everyone believes
those sentences and may not know to what degree. 2-mutually accessible knowl-
edge KAccMutual(ij) is a special case when both agents believe and know each
other knows that each of them believes, which is defined as:
KAccMutual(ij) = ∩(Kacc(i, j), Kacc(j, i))
The ideal m-mutually Accessible Knowledge defined in the similar way is not
realisable. Since the knowledge is classified from agenti’s viewpoint, it is im-
possible for i to know about the knowledge classification of other agents.
KAccMutualIdeal(ij · · · k) = ∩(KAcc(i, j · · · k), · · · , KAcc(j, i · · · k), KAcc(k, i · · · j)
� �� �
m!
C m−1 =m
m
137
where, m is the cardinality of set {i, j, · · · , k}.
Therefore, only super agents who can access every agent’s KB can do the above
evaluation. For agent i, it could only reason about the possible m-mutually
accessible knowledge at a coarse level:
KAccMutualP ossi(ij · · · k) = ∩(KAccMutual(ij), · · · , KAccMutual(ik))
but
⊇ KAccMutualIdeal(ij · · · k)
KAccMutual(ij) = KAccMutualP ossi(ij) = KAccMutualIdeal(ij)
2. m-Shared Belief: Ks(ij) represent the 2-shared knowledge of agent i, and j. It
describe a package of knowledge that agent i and j both believe and both of
them know that each other believes it to an agreed degree. Ks(ij) is defined as:
Ks(ij) = (∗)KAccMutual(ij)
where ∗ stands for the various kinds of operator that can generate shared knowl-
edge from the mutually accessible knowledge. One simple candidate is to simply
take the mutually accessible knowledge as shared knowledge and derive a unan-
imous ranking on it. Alternatively it could be used to initiate conversations
among the agents to select an agreed subset.
m-shared belief is defined as
Ks(ij · · · k) = (∗) ∩ (Ksij, · · · , Ksik)
where ∗ has the same meaning as defined above. The discussion for possible
138
m-mutually accessible knowledge suggests that ∗ in this case should enable
agenti to send out queries to other agents. This is to determine the accessibility
of KAccMutualP ossi(ij · · · k) from the other agents viewpoint. If all the agents
faithfully answer queries whenever required, KAccMutualIdeal(ij · · · k) would be
the final result of such queries.
3. Common Belief: Kc is the n-shared beliefs, which is a special case of shared
belief when the set of sentences is believed by the whole society with an agreed
degree(i.e. n-shared knowledge), and everyone in the society knows that every-
one believes it at a certain degree and · · · and everyone knows that · · · that
everyone believes it to a certain degree.
The mutually accessible knowledge is stored separately in each agent’s local knowl-
edge base, the rank of the same sentence in KAccMutual(ij · · · k) does not necessarily
have to be the same according to individual agent’s judgment. But when the agents
decide to share some knowledge, it is necessary for them to agree on the rank of
the shared knowledge. Thus the rest of each agent’s knowledge base needs to be
revised to accommodate the agreed degree. By the way, shared/common belief could
be extracted from each agent’s knowledge base and stored in a common location if
everyone agrees to do so. This would be beneficial in terms of saving space and it
would enhance the robustness of the dynamics of shared information.
9.3 Relationship with Other Knowledge Structures
Essentially, two types of knowledge structures for modelling common/shared knowl-
edge exist in the literature,
139
(I) The labelled tree of mutual belief by Van de Meyden[85] based on possible
worlds semantics of modelling knowledge and belief in MASs[31];
(II) The knowledge in a Shared Domain (SD) and a Private Domain (PD) by
Kfir-dahav and Tennenholtz [68].
In the case of mutual belief [85], the accessibility relations are defined on the possible
worlds according to the agents current beliefs. A labelled tree formally represents
this, which is a mixture of domain and social knowledge. Each agent is able to reason
uniformly because the whole tree structure is visible to everyone. It is inflexible to
some extent because it does not support private knowledge.
Tidhar et al.[102] define team knowledge as “the team knows only what is known
to every subteam”. Such team knowledge is actually the intersection of subteams’
knowledge base, which is similar as SD defined in [68]. It is shown in Chapter 5 such
a classification is not capable of modelling truely private knowledge. It implicitly
presumes a super agent who can access all the agents’ KBs, draw the conclusions from
the shared knowledge and impose that on each individual. Imposing team knowledge
top down from a team leader is only one way of achieving team knowledge. The other
way is to derive consensus (via. negotiation or argumentation etc.) from the team
members. The latter way is not supported by the structures in [68][102].
Intuitively, the agents knowing the same thing does not necessarily imply ei-
ther the awareness of, or the sharing of intentions. While agents sharing some
knowledge means the shared knowledge must be known to each agent involved, i.e.
Shared =⇒
�⇐= Known. Previous research reported in the literature fails to capture such
intuition. However our share knowledge structure is successful in achieving it by au-
thorising agents to organise their own knowledge bases. The accessibility as defined
in Section 9.2 is totally determined by an individual agent’s personal stance. It is
140
considered as an attribute of a certain subset of the agent KB regardless of how the
agent is going to reason on it. Since there is no need to reveal all of its KB, true pri-
vacy is maintained when cooperating. The operator (*) is suggested to derive shared
belief from a rational set of mutually accessible knowledge without the aid of super
agents. However, this knowledge structure does not preclude the possibility of the
existence of a super agent. This could be done by simply forcing all the other agents
to register their platform to give full accessibility to the super agent. The super agent,
on the other hand, would allow only limited or no accessibility to others.
The proposed shared knowledge structure is capable of simulating previous struc-
tures by rearranging the accessibility relations. For example, if every agent opens its
domain knowledge base to all the others, the n-possible mutually accessible knowledge
becomes n-ideal mutually accessible knowledge. The n-shared knowledge achieved is
just the knowledge in SD. The complement is left for P D. If every agent fully
opens both its social knowledge base and domain knowledge base, the accessibility
relation becomes transitive. Therefore, shared knowledge structure is able to capture
the semantics of mutual belief[85], and in this case, Kpri(i) is empty.
9.4 Inconsistency Principle
In this framework, the consistency of an individual’s knowledge base with the com-
mon/shared beliefs is our primary concern. This is achieved using standard single
agent belief revision techniques. So local consistency is still a prerequisite of each
agent, but the global consistency of the society is not required either during or after
the process of belief revision. Hence, inconsistency across the knowledge bases of the
society is permitted. This is called inconsistency principle. This is different from the
141
Liberal Belief Revision Policy[20] where the final distributed belief revision goal is to
achieve global consistency.
Observation: If sentence p is inconsistently believed in the agent society, then
neither p ∈ Kc nor ¬p ∈ Kc
This observation also holds for the shared belief bases. That is, among the agents
who share the belief, neither it or its negation are derivable from the shared belief
base. It becomes one of the key postulates that should be satisfied during the multi-
agent belief revision process. Therefore, as long as a sentence is not derivable from the
common belief base, it could be inconsistently believed across the society or across
several groups; similarly, as long as a sentence is not in a shared belief base of a
certain group, it could be held inconsistently at least across the agents in this group
or across several subgroups.
The major goal of belief revision based on our proposed shared knowledge struc-
ture and the inconsistency principle is to maintain the consistency of K(i) with Kc,
and with shared belief base Ks(ij · · · k).
Common/shared beliefs are distinct from mutually accessible knowledge by the
fact that the rank in Kc/Ks(ij · · · k) should be respected, while different ranks could
be assigned to the same mutually accessible knowledge by different agents. Therefore,
maintaining the consistency of K(i) with Kc means aligning the rank of common be-
liefs in every agents knowledge base when new information is accepted by the society.
That is, the revision process to revise K(i) by a set of sentences with fixed ranks (in
Kc/Ks(ij · · · k)) and also the new information, while the rank of new information and
sentences in K(i) are changeable, those in Kc are not.Revision regarding the shared
knowledge Ks(ij · · · k) uses a similar process but within a smaller groups of agents.
142
Communication and negotiation might be necessary to reach a consensus on ranking
of Kc/Ks(ij · · · k).
Consequently, belief dynamics considered here are more sophisticated than is re-
quired for single agent revision and could be extended to knowledge migration in
terms of knowledge grade, which is discussed in the next section.
9.5 Knowledge Grade and Knowledge Migration
Based on the shared knowledge structure, an agent’s knowledge base could be ordered
according to the degree to which beliefs are shared:
Common B (n, · · · , 2)-Shared B (n, · · · , 2)-AccNotShared B Pri B
HIGH <————————————————————————– LOW
where B stands for beliefs, n is the agent population. Common beliefs have the
highest grade of sharing and private beliefs have the lowest.
According to the inconsistency principle, inconsistency is permitted across the
agent society as long as the inconsistent knowledge is not in Kc. Therefore, if the new
information ¬φ contradicts the common belief, instead of giving up φ and expanding
Kc by ¬φ in the traditional way, the following procedure could be taken to incorporate
¬φ as well as letting some agents whose background knowledge supports φ still keep
it:
• The observer agent broadcasts the observation and waits for a response. If
all the agents agree to do nothing to Kc, then ignore ¬φ and keep everything
unchanged. If all agree to accept ¬φ, perform mirror revision on Kc with
respect to φ and derive consensus on the result Kc ˙+¬φ. Otherwise, perform
mirror contraction on Kc with respect to φ and deriving consensus on the result
Kc − φ and then go to the next procedure.
143
• There is a maximum of n − 1 groups of agents who share their own n − 1 shared
beliefs. Check within each group whether they wish to accept, say, ¬φ. If yes,
revise the corresponding shared belief base with ¬φ. If no, check whether to
accept φ. For the group who won’t take either one, the process repeats through
the smaller subgroups until they are broken down into the individual agent.
In this procedure, an important property is that the original believed common
belief φ has been migrated down either to some groups’ shared belief bases Ks(ij · · · k)
or to someone’s Kpri(i). In the sense of knowledge grade, φ has been degraded during
the revision.
On the other hand, information could also be upgraded from a lower grade to a
higher one. At first, the revision on accessible but not shared knowledge results in the
accessibility update. Then, when an agent updates its accessibility or receives other
agents’ accessibility update announcement, it will re-evaluate the knowledge in its
knowledge base and the accessible knowledge in others’ knowledge bases. Following
the procedure of defining shared/common belief in Section 9.2, m-shared belief can
be generated from the lower grade m-accessible knowledge. In fact, the process of
deriving shared/common knowledge is just the process of knowledge upgrade.
Knowledge upgrading and degrading in multi-agent belief revision is called knowl-
edge migration. Scenarios of knowledge migration vary according to the application.
In general, knowledge migration is the process of reshaping the knowledge structure
and is triggered by the new information.
144
Chapter 10
Multi-Agent Belief Revision –
Architecture and Implementation
“Designing object-oriented software is hard, and designing resuable object-
oriented software is even harder. You must find pertinent objects, factor
them into classes at the right granularity, define class interfaces and in-
heritance hierarchies and establish key relationships among them. Your
design should be specific to the problem at hand but also general enough
to address further problems and requirements.”
10.1 Introduction
— From the first page of Design Patterns[39]
Although it is widely accepted that belief revision should be one of the essential
capabilities for any intelligent agents, most of the current agent frameworks and
development environment (such as JACK 1 and JADE 2 ) do not have direct support
1 http://www.agent-software.com/
2 http://jade.ceslt.it/
145
Belief
Revision
Agent
Perception
From
Others
Knowledge
Kernel
Domain
Belief Base
Social
Belief Base
3-Layered
Belief Revision
Engine
Communication Wrapper
To
Others
Action
Figure 10.1: A Belief Revision Agent
for belief revisions. Therefore, we propose an infrastructure where one or more service-
oriented belief revision agents can provide belief revision services to other agents.
The belief revision service agent is an agent who can maintain the consistency of
its knowledge base(s) or the delegators’ knowledge bases in face of change.
10.2 A Belief Revision Agent
Figure 10.1 illustrates a belief revision agent that has social awareness. It consists of
a perception unit, an action unit and a knowledge kernel. It communicates with other
agents through a communication wrapper. The knowledge kernel consists of a social
belief base, a domain belief base, and a 3-layered belief revision engine.
146
The perception unit receives information from the communication wrapper, then
filters and dispatches it to each layer of the revision engine shown in Figure 10.2.
The action unit has two types of output, namely, the internal actions (depicted by
the dotted line in Figure 10.1) and the external communicative act (depicted by solid
line in Figure 10.1). The internal actions act on the domain belief base and the social
belief base. These actions together with the data flow provide three types of services:
Single Belief Revision (SBR), Belief Revision using information from Multiple Sources
(MSBR) and Multi-Agent Belief Revision (MABR). The external communicative act
is sent to other agents through the communication wrapper. It is mainly for delivering
revision results to other agents and for participating in group decision making when
revising shared or common knowledge.
The separation of cooperation knowledge (in our case, social beliefs) from domain
knowledge is a theme that can be found in the early Distributed Artificial Intelligence
work[14]. It leads to computational efficiencies and allows the agent’s functions to
be modularised into interactive layers. The possible contents of the social belief base
and the domain belief base will be further explained in Section 10.4.1.
The domain belief base provides the domain knowledge that agents use to reason,
and it is the domain belief base that the SBR processes act on. Therefore, for an
agent to perform revision actions, there must exist at least one domain knowledge
base either external (such as shared belief bases) or internal to the agent.
Compared to the stand-alone single agent, the existence of one or more social
belief bases is one of the distinctive features possessed by agents who socially interact
with others. We define an agent acquaintance base as a dynamic set of known agents
from an individual agent’s point of view. It is populated with all the agents that a
given agent interacts with, including itself. There are several ways for an agent to
147
MABR
MSBR
SBR
Action Unit
3-layered Belief Revision Engine
Layer 3
Negotiation, Cooperation
Decision Making
Layer 2
Social Belief Revision
Layer 1
Domain Belief Revision
Communication Wrapper
Perception Unit
Legend:
Figure 10.2: A 3-Layered Belief Revision Engine
make itself known to other agents. For example,
148
Data Flow in Layer3
Data Flow in Layer2
Data Flow in Layer1
1. Register to an agent platform yellow page service as described by FIPA (imple-
mented in JADE as Directory Facilitator),
2. Broadcast its existence, or
3. Directly register to a particular agent’s address book to become acquainted with
that agent. Basically, the agent acquaintance base is an agent’s personal record
of all the agents that it has experienced with.
The 3-layer belief revision engine based on a vertically layered two-pass flow archi-
tecture is the core of a belief revision agent. Vertical layering outperforms horizontal
layering in terms of the feasibility of achieving coherent agent behavior[113]. The data
control adopted allows feedback from higher levels to invoke the lower level functions,
which in turn allows modelling heterogeneous agents with different levels of belief
revision capability. Section 10.4.3 will discuss the revision engine in detail.
Using the social information together with the domain information, the following
functionalities should be achieved by the revision engine:
• The agent acquaintance base should be open to any agent who joins or leaves
at any time.
• The agent should be able to carry out not only simple belief revision tasks but
also complex tasks that involve more than one agent, such as revision using
information from multiple sources.
• The agent should be able to communicate with other agents, maintain the
candidate set of shared knowledge, i.e. the mutually accessible knowledge in
order to participate in a higher-level multi-agent belief revision, which involves
the changes of shared knowledge or common knowledge.
• The agent should also be able to handle polluted information, i.e. information
from malicious agents and incapable agents.
• The agent should also be able to update their social beliefs dynamically.
10.3 A FIPA Multi-Agent Platform Implemented
in JADE 2.4
The standard model of an agent platform, as defined by FIPA, is represented in Figure
10.3.
Details of the description of FIPA agent platform components are available in
Appendix D.
The Agent Management System (AMS) is the agent who exerts supervisory control
over access to and use of the Agent Platform. Only one AMS will exist in a single
149
Software
Agent
Agent Platform
Agent
Management
System
Message Transport System
Message Transport System
Agent Platform
Directory
Facilitator
Figure 10.3: FIPA Agent Reference Model from FIPA:XC00023H [34]
platform. The AMS provides white-page and life-cycle service, maintaining a directory
of agent identifiers (AID) and agent states[30]. Each agent must register with an AMS
in order to get a valid AID.
The Directory Facilitator (DF) is the agent who provides the default yellow page
service in the platform.
150
The Message Transport Service, also called Agent Communication Channel (ACC),
is the software component supports the transportation of messages between agents
on any given agent platforms and between agents on different agent platforms.
JADE (Java Agent Development Framework) is a software development frame-
work aimed at developing multi-agent systems and applications conforming to FIPA
standards for intelligent agents. It includes two main products: a FIPA-compliant
agent platform and a package to develop Java agents.
JADE implements this reference model and provides a FIPA compliant agent
platform. In particular, it has the following features:
• An AMS and a DF are automatically created and the ACC module is set to
allow message communication when a JADE platform is launched.
• The agent platform can be distributed on several hosts. Only one Java applica-
tion, and therefore only one Java Virtual Machine (JVM), is executed on each
host. Each JVM is a basic container of agents that provides a complete run
time environment for agent execution and allows several agents to concurrently
execute on the same host.
• The main-container, or front-end, is the agent container where the AMS and DF
lives and where the RMI registry, that is used internally by JADE, is created.
The other agent containers, instead, connect to the main container and provide
a complete run-time environment for the execution of any set of JADE agents.
For the lifecycle of a service-oriented belief revision agent:
• The JADE platform controls the birth of an agent. The agent constructor is
first executed.
• The JADE platform automatically registers the agent with the AMS and obtains
a unique AID from the AMS. The agent is then put into an AP_ACTIVE state.
• The agent modifies the data registered with AMS if necessary.
• The agent registers the description of itself and its services with one or more
DFs if necessary. Three essential service types of a belief revision agent are:
MABR, MSBR and SBR.
151
• The agent is then put into a AP_WAIT state waiting for request or query from
other agents (either from its manager agent or from some other agent).
• After receiving the request or query, the agent will follow the FIPA request
and query protocol for inter-agent communication and executing belief revision
behaviours.
152
• According to the specific application, the agent can also be put into a AP_SUSPEND
state. The agent is terminated if it is put in a AP_DELETED state.
JADE provides simplified APIs to interact with AMS and DF agents. Actually,
the functionalities provided by AMS and DF are common to most of the agents, which
include register, deregister, modify and search. The two classes
jade.domain.AMSService and jade.domain.DFService are provided for deployed
agents to use these services. It is important to note though, JADE calls the reg-
ister methods automatically with the default AMS just before the agent executing
domain specific actions, and calls the deregister method just after the agent is termi-
nated. Therefore, there is normally no need for a programmer to explicitly register
or deregister an agent with an AMS.
10.4 Design Using an Object-Oriented Approach
Structured programming was the dominant approach to software development in
1970s. Things changed quite rapidly as in 1980s, object-oriented language gain a
successful rise in popularity due to its renovating concepts such as encapsulation, in-
heritance, messaging and polymorphism[28]. The introducing of these programming
concepts greatly simplified the software development life cycle and made software
reuse possible and powerful.
In the process of reformulating the existing single SATEN agent into a belief
revision agent with social awareness, we use Unified Modelling Language (UML) to
aid the design, apply relevant design patterns[39] and use JADE agent platforms to
facilitate inter-agent communication. The design purpose is to provide a prototype
that is adaptable to further changes and is modularised and reusable under various
circumstances.
10.4.1 Domain Beliefs and Social Beliefs
An agent’s belief base consists of different sorts of knowledge. For the purpose of real-
ising the framework described in previous sections, it is important to separate domain
beliefs from social beliefs. Domain beliefs consist of facts and beliefs about the domain
of discourse. For example, travel and tourism industry, electronic commerce, finance
and etc. For our purpose, social beliefs are concerned with trustworthiness evaluation.
It consists of information about other agents’ degree of sincerity, degree of credibility
etc, depending on the level of trust evaluation power that agent programmers would
like to bestow to the agents.
The following example may give us a better idea of what domain beliefs and social
beliefs are:
• Domain Beliefs: Agent B told me that Air Kangaroo supplies beer for free.
• Social Beliefs: Agent B is a close friend, who has no reason to lie to me in favour
of Air Kangaroo in this matter(Sincerity). Agent B is also a frequent flyer with
many airlines(Competency).
153
Here, we take a top-down approach to define the data structure of a domain belief
and a social belief.
The essential element of a domain belief is a logical sentence. The sentence can be
implemented as a JAVA String with special characters that served as logical connec-
tors. We assume the programme parsing the strings exists externally and the parsed
strings are ready to be feed into the existing theorem prover (e.g. VADER 3 ). A logical
sentence (p) is thus the core of a domain belief.
The logical sentences then may come with a value (δ) that provides the necessary
extra-logical information for iterated belief revision. It may take on various meanings
such as degree of preference, degree of probability, degree of necessity, or degree of
belief, depending the underlying revision scheme. This can be implemented as a
Degree object which has a JAVA primitive double value.
In addition, agents obtain information not only through their own observation but
also from communication. As shown in Chapter 7, the source information (Source)
is critical in further assessing the credibility of the utterance. Therefore, the core
sentence may be associated with a source agent or a set of source agents.
Furthermore, if desired, the sentence may have explicit topics T opic associated
with it. The topics are currently implemented as a set of JAVA Strings.
Finally, in order to dynamically manage the privacy or accessibility of a piece of
belief, the sentence may also be associated with the accessibility information (Access),
similarly to the source field, the accessibility can be represented by a set or a vector
of agent names. The agents in JADE are identified by unique agent identifiers, im-
plemented using AID class. As JADE is used as the agent platform which provide
3 http://infosystems.newcastle.edu.au/webworld/vader/
154
the necessary communication channel, we use JADE AID class to maintain our agent
names.
The above facets are mainly for domain beliefs. There are some special fields
needed for representing social beliefs. We first need the agent name (AID) as provided
by JADE agent platform. The AID is the core of a piece of social belief. A social belief
base turns into an acquaintance base when only the core element AID is recorded.
In the case when no other fields specified for a social belief, the AIDs simply serve as
a record of all the agents that the agent is currently acquainted with.
155
Then we may need the subjective evaluation of trustworthiness (T rustworthiness)of
the identified agent. As shown in Chapter 7, the trustworthiness value could be simple
subjective estimation, which could be represented in the similar format of the degree
(δ) for the domain belief. Alternatively, the trustworthiness value could be calculated
from degree of sincerity (Sincerity) and degree of competency (Competency), each
of which could be represented using the same format as δ.
As pointed out in Chapter 7, the trustworthiness value may also vary according
to topics (T opic), therefore, we also need a field to store the topics. Trustworthiness,
sincerity and competency record with out a specified topic would be considered as
general trustworthiness, general sincerity and general competency respectively.
In summary, an ideal piece of domain belief representation for our purpose is
a 5-tuple < p, δ, Source, T opic, Access >. Compared to the core of a belief (sen-
tence, p), we call the rest elements for an ideal belief as the axillaries of a belief.
All combinations of a core sentence with any number of the axillary elements are
considered to be valid beliefs in the framework. For example, < p, δ >, < p, T opic >,
< p, Source, T opic > are considered as valid domain beliefs.
Similarly, an ideal piece of social belief is either a 3-tuple
< AID, T rustworthiness, T opic > or a 4-tuple < AID, Sincerity, Competency, T opic >
depending on whether the trustworthiness is a simple subjective estimation or a com-
posite value calculated from the component beliefs of trust. It is also true that
any combination of the core with any other axillaries (< AID, T rustworthiness >,
< AID, T opic > or < AID, Sincerity, Competency, T opic >) would make valid so-
cial beliefs.
Degree
-degree
+getValue()
Source
-source
+getValue()
DomainBelief
-sentence
+addComponent()
+removeComponet()
+getChildren()
-topic
Topic AccessibleBy
CompositeDomainBelief
+getValue()
-AccessibleBy
+getValue()
Figure 10.4: UML: Class Diagram of Domain Beliefs
Figure 10.4 shows that through inheritance and composition we are able represent
to various kind of domain beliefs as well as social beliefs.
When implementing the above fields for a domain belief base and social belief base,
we would like not only to fulfil the flexibility requirement for representing various
types of domain and social beliefs, but also to make sure further development does
not necessarily interfere with the current implementation. For example, the social
belief tuple < AID, Sincerity, Competency, T opic > may not be an exhaustive list
of all the possible information a social belief need to encapsulate. An agent may want
to keep a relationship field as well such as “friend, competitor, normal” and so on.
0..*
1
156
JADE Agent Platform
Sincerity
-sincerity
+getValue()
Trustworthiness
-trustworthiness
+getValue()
«uses»
-AID
+addComponent()
+removeComponent()
+getChildren()
Competency
-competency
+getValue()
AID
SocialBelief
0..*
0..*
-topic
Topic
+getValue()
CompositeTrustworthiness
1
CompositeSocialBelief
+getValue()
+addComponent()
+removeComponent()
Figure 10.5: UML: Class Diagram of Social Beliefs
Therefore, the composite pattern[39] is used to compose a composite belief from the
leaves (e.g. δ, T opic and ect) as shown by the UML diagram in both Figure 10.4 and
Figure 10.5.
10.4.2 Belief Revision Services - Use Case Study
Refering back to the ontological description of the Section 5.3 and the discussion in
previous sections, the belief revision agent herein described can provide three types of
belief revision services: SBR, MSBR and MABR. These services are described using
use case diagrams illustrating the functionalities that the 3-layered belief revision
engine consists of.
1
157
The use cases described here focus on the external behaviour of the system but
Actor
*
*
* *
*
*
Transmutation
Layer:SBR
DegreeOfBelief
TheoryExtraction
«uses»
«uses»
Fusion
Figure 10.6: UML Use Case: Single Belief Revision
not how things are actually performed inside the system, which will be described
instead using the class diagrams.
Single Belief Revision
There are four main use cases for a single belief revision, which are shown in the use
case diagram Figure 10.8. There are basically four types of use cases in the single
belief revision layer.
The DegreeOfBelief use case models a scenario where the agent answers queries
of the degree of believing in a sentence. The TheoryExtration performs the request
of extracting a consistent theory from the given belief base. The Transmutation and
Fusion use cases perform revising a belief base in face of new information and fusing
multiple belief bases respectively.
An example description of the DegreeOfBelief use case is shown below.
Objective: Query the degree of belief δ of a sentence p
*
158
Initiated: When an actor sends a query message in ACL with QUERY performative
Message Flow: Actor to send a QUERY message and the sentence. The communi-
cation between the actor and the use case should follow FIPA “request-like” 4
interaction protocols.
Value returned to actor: One of the following:
• Refuse(reason)
• Not-Understood
• Failure(reason)
• Inform(result)
If the request is successfully processed, the actor should receive a value that
indicates the degree of belief for the sentence.
Belief Revision using information from Multiple Sources
Figure 10.7 illustrates the use cases for the MSBR layer. Two use cases GeneralTrust
and TopicSpecificTrust are for query agents to inquire about the level of trustwor-
thiness of a particular acquaintance, either general or specific to a topic. Meanwhile,
there is a use case in this layer to allow dynamic update of social beliefs.
The core use case in this layer is the MSBR use case. It uses the agent trustwor-
thiness to compute a new degree of acceptance. The the degree of acceptance is used
as important input for fusion in the SBR layer.
4 The FIPA request like protocols include FIPA-Request, FIPA-query, FIPA-propose, FIPA-
Request-When, FIPA-recruiting, FIPA-brokering, FIPAsubscribe and etc.
159
SocialInfoQueryActor
MSBRActor
* *
*
1..*
GeneralTrust
DegreeOfTrust
«extends»
Layer:MSBR
«extends»
TopicSpecificTrust
«uses» «uses»
*
1
MSBR
Layer:SBR
«uses»
Fusion
SocialBeliefUpdate
*
*
160
UpdateActor
Figure 10.7: UML Use Case: Belief Revision using Information from Multiple Sources
Multi-Agent Belief Revision
The MABR layer will contain use cases such as updating the accessibility of the
domain beliefs, query about the shared beliefs, and core functionality of knowledge
migration. This is shown in Figure 10.8.
Imagine agent-x shares φ with agent-y, it also believes that φ → ψ, but this is
not shared with agent-y. Instead it shares the logical consequence ψ with agent-z.
Therefore, when agent-y send a request to remove φ, agent-x has to communicate
with agent-z as well to make a decision on whether to remove ψ or degrade that to a
private knowledge. A typical MABR process (i.e. the knowledge migration) involves:
1. Keep a copy of the original belief base K
PerceptionActor
MABRActor
*
1..*
1
*
Accessbility
«uses»
SharedBelief
KnowledgeMigration
Layer:MABR
«uses»
«uses»
Layer:MSBR
MSBR
Layer:SBR
Transmutation
Figure 10.8: UML Use Case: Multi-Agent Belief Revision
2. Carry out a SBR or a MSBR and obtain a resulting K ′
3. Compare K and K ′ , and work out all the affected partners.
4. Inform all the involved partners about the possible changes
5. Based on the decision making rules (e.g. compare agent-y and agent-z’s trust-
worthiness) and partners feedback to choose between upgrade or degrade the
belief and all the logical consequences
Therefore, the core use case knowledge migration will use the functionality pro-
vided in either the MSBR layer or the SBR layer or both.
161
10.4.3 Layered Belief Revision Engine
As we can see from the above use case study, each layer of the engine has a core
use case. Moreover, to accomplish the core functionality, the higher layer will need
functionalities provided by its lower layer(s). Therefore, we can treat the layer’s func-
tionality as sub-capability of the higher layer’s capability. This provide a modularised
design that meets the requirements of agent-oriented programming[43, 91]. It also
facilitates the possibility of plug-in compatible capabilities in order to incorporate
specific revision techniques.
In JADE, each functionality/service provided by an agent should be implemented
as one or more behaviours. A scheduler, internal to the base Agent class and hidden to
the programmer, automatically manages the scheduling of behaviours. User defined
behaviours should extend the base class behaviours and added to the agent class
using Agent.addBehaviour().
The functionalities of each layer is therefore wrapped into behaviours and then a
JADE belief revision agent can use it by simply calling Agent.addBehaviour().
The layered belief revision engine can be implemented using the composite pattern
as shown in Figure 10.9.
The UML class diagram is closely related to the use case diagrams for each layer,
with most of the use cases implemented in classes. Furthermore, the MABR process
is implemented as a composite of all the functionalities it can provide, with MSBR
process as a component function that supports the overall functionality. Similarly,
the MSBR process consists of functionalities such as updating social beliefs, querying
the degree of trust, and obtaining the acceptance level of new beliefs based on social
beliefs, then feeding the new degree of beliefs into the SBR layer to achieve MSBR.
162
1
«interface»
MSBR
0..*
«interface»
CompositeMABR
«interface»
CompositeMSBR
«interface»
SBR
«interface»
SharedBelief
«interface»
DegreeOfTrust
0..*
«interface»
KnowledgeMigration
«interface»
SocialBeliefUpdate
Figure 10.9: The Composite Pattern used for Belief Revision
«interface»
MABR
SBR is basically a reformulation of the existing SATEN functionalities, as shown
in the UML class diagram in Figure 10.10. It shows the hierarchy of a single belief
revision process and at the same time leave spaces for possible incorporation of other
revision schemes such as Probability, Possibility and Belief Functions.
10.5 Agent Communication Channel - JADE Agent
Wrapper for Belief Revision Services
As shown in Section 10.3 and Appendix D, a JADE agent platform automatically
registers an agent with the AMS when the agent is created and thus the agent will gain
access the Message Transport Services. It provides base classes such as DFService
for a JADE agent to use the service provided by the directory facilitator. Moreover,
it also extracts the common structure of FIPA communication protocol as shown in
Figure 10.11 below.
163
There are basically two roles that an agent can perform when involved in a
1
JADE Agent Platform
«interface»
SBR
«interface»
TheoryExtraction
«interface»
Probability
«interface»
Possibility
Adjustment Maxi-Adjustment DMA
«uses»
Transmutation-Adjust
Behaviour
«uses» «uses» «uses»
«uses»
Fusion-Adjust
Transmutation-MA
Fusion-MA
Figure 10.10: Single Belief Revision
Transmutation-DMA
«interface»
BeliefFunctions
«uses»
Fusion-DMA
communicative act, namely, an initiator and a responder. In order to make sure
the communication between two agents is meaningful and rational for both parties,
JADE introduces the concept of rational effects of communicative acts[30]. With the
achieve-rational-effect functionalities provided by two classes AchieveREInitiator
and AchieveREResponder, an agent can be involved in any FIPA request like conver-
sations. The initiator sends a message (i.e. performs a communicative act, as shown
in the white box). The responder can then reply by sending a not-understood, or
a refuse to achieve the rational effect of the communicative act, or also an agree
message to communicate the agreement to perform (possibly in the future) the com-
municative act, as shown in the first row of shaded boxes. The responder then
performs the action and, finally, must respond with an inform of the result of the
164
Not-Understood
Communicative
Act
Refuse
Reason
Failure
Agree
Inform
Done(Action)
Inform
(iota x (result action)x)
Figure 10.11: Homogenous Structure of Agent Communication Protocol[30]
action (eventually just that the action has been done) or with a failure if anything
went wrong. JADE has extended the protocol to make optional the transmission of
the agree message. If performing the action takes a short time, sending the agree
message will create an ineffective overhead. In such cases, the agree to perform the
communicative act is subsumed by the reception of the next message in the protocol.
Figure 10.12 shows how the JADE communication functionalities can be used
together with the belief revision behaviours by a BRInitiator agent.
The BRInitiator agent extends the JADE base class Agent and adds the
AchieveREInitiator behaviour into its behaviour base. It also adds the DFService
from the JADE library to its behaviour base to be able to register its service to a
directory facilitator. Finally, it adds to its behaviour base BRBehaviour as its major
service.
The BRBehaviour class in Figure 10.12 is a fictional class which is going to be
replaced by the actual class that extends JADE behaviour and implements one
of the interfaces SBR, MSBR and MABR which forms the hierarchy shown in Figure
165
10.9. Depends the services, the BRBehaviour class will interact with either the
DomainBeliefBase or SocialBeliefBase or both. The two types of belief bases
are aggregation of the DomainBeliefs and the SocialBeliefs illustrated in Figure
10.4 and Figure 10.5 respectively.
JADE Agent Platform
Communication Wrapper
Agent
BRInitiator
AchieveREInitiator
«uses»
«uses»
DFService
BRBehaviour
Behaviour
«interface»
CompositeMABR
«uses»
«uses»
SocialBeliefBase
-socialBeliefs
DomainBeliefBase
-domainBeliefs
Figure 10.12: Agent Communication Channel - JADE Agent Wrapper
10.6 Summary
We illustrated in this chapter using a software engineering approach of how to design
and implement the multi-agent belief revision framework and the concepts involved.
The investigated concepts in the former chapters, such as various revision schemes,
trust, information pedigree, shared beliefs and ontologies, eventually come together
within a flexible and general framework. The framework is adaptable for incorporating
new belief revision schemes and viable for a heterogenous multi-agent environment. In
particular, as the layering approach is adopted, a belief revision agent designed under
such a framework is capable of providing services at various levels. It can model single
166
belief revision behaviour, revision behaviour for information from multiple sources,
as well as cooperative revision in multi-agent situation where revision on shared or
common knowledge is desired. This provides a tangible architecture of a belief revision
service provider for an dynamic, heterogenous, autonomous open environment.
167
Chapter 11
Discussion, Conclusions and
Implications
“Mind maps are tools which help you think and learn ...”
— From http://www.maps.jcu.edu.au/netshare/learn/mindmap/index.html
has belief revision behaviours
is implemented in
JADE
BRAgent
extend JADE
Agent Class
forms
Intelligent
Agents
Multi-Agent
Systems
implemented
JADE
Agent
Framework
need
Muti-Agent
Belief Revision
has heterogenieties
need ontologies
JADE Basic
Ontologies
Belief
Revision
ontologies
Ontologies for
Belief Revisioin
trust
shared belief and
private belief
SBR v.s.
MSBR v.s
MABR
specifies
requires
implemented in
Domain Beliefs
and Social
Beliefs
shared
knoweldge
structure
Layered Belief
Revision
Engine
Figure 11.1: Mind Map of Multi-Agent Belief Revision
11.1 Discussion and Conclusion
Agent technology has gained tremendous attention from both the research community
and industry. The Internet and the World Wide Web provide a large-scale truly dis-
tributed, dynamic, open and heterogenous test-bed for agent and multi-agent theories
168
and techniques.
Agent technology is an innovative programming paradigm that is different to the
object-oriented approach. It is particularly powerful and useful in modelling and
tackling problems inherent in large distributed systems, such as air traffic control,
distributed manufacturing system, Health Care, e-commerce and e-business, and etc.
To meet the surging interest from the industry and to explore the agent tech-
nology, many agent programming languages, APIs, SDKs and frameworks have been
developed. Some treat agents as normal software entities that can perform normal
functions and processes with the common capability of communicating with others,
i.e. sending and receiving messages. Some focus on implementing intelligent agents
based on human beings’ practical reasoning, thus bestowing mental attributes to
agents, such as belief, intension, desire and goals. Agents built around this paradigm
are often referred to as BDI agents. The deliberation power of BDI agents makes
it particularly of interest to us, as these agents exhibit rational behaviour such as
persistence in achieving goals, social awareness and robustness in terms of recovering
from failure.
Often, belief revision is considered as one of the essential functions that a BDI
agent should possess so that it can maintain a consistent belief base. However, most of
the agent development toolkits or frameworks either do not support the representation
of agent internal states such as beliefs, or belief set structures but use simple database
insertion and deletion to represent the update of beliefs. In fact, maintaining a
consistent agent belief set is crucial for agents to exhibit rational behaviour.
The web based belief revision system - SATEN provides a nice tool for human
researchers to test out consistency of theories but the process is not automated,
169
meaning it can not communicate with other software programs or agents to further
its potential as a belief revision service or component. Therefore, there is the need
of re-programming SATEN into a belief revision agent, which provides belief revision
services to other types of agents. The design process carried out in Chapter 10
facilitates the wrapping of SATEN into a service oriented belief revision agent with
social awareness.
On the other hand, the research in the area of belief revision mainly focus on
maintaining beliefs kept with one single agent. Seldom are there studies into belief
revision issues that are presented in a multi-agent environment. We investigated belief
revision techniques for individual agents as well as the frameworks that address belief
revision issues in a multi-agent environment.
The research into individual belief revision shows us a diverse range of revision
schemes, some operate on theories, some on theory bases, some abide by the AGM
postulates, some fall into the traditional Bayesian probability paradigm, some follow
a more general way of representing beliefs, such as possibility theory and belief func-
tions. It is interesting to note that all these revision schemes are somewhat related,
basically they can all be described using the essential elements of an epistemologi-
cal theory, that is, epistemic state, epistemic input, epistemic attitude and epistemic
changes. The epistemic changes are all regulated by certain rationality criteria, such
as minimal change or coherence requirement. Furthermore, we showed that both
probabilities and possibilities are special cases of belief functions and can be repre-
sented by belief functions when certain conditions are met.
An important outcome of the research into the available multi-agent belief revision
frameworks is an ontological classification of the various terminologies adopted in
170
the literature, where there is no consensus as yet. We classified belief revision into
three major categories, namely, simple belief revision (SBR), belief revision using
information from multiple agents (MSBR) and multi-agent belief revision(MABR).
This provided a sound basis that aided our investigation into the domain.
Another outcome of the research is the identification of a major drawback of the
current frameworks. That is, they are not capable of dealing with heterogeneity issues.
It is not feasible therefore to use these frameworks in open systems, where agents
are designed by different vendors and representing interests of different uses. This
motivates our research into classifying various types of heterogeneities that might exist
and affect the belief revision process in a multi-agent environment. We identified three
common types of heterogeneities: social heterogeneity, semantic heterogeneity and
syntactical heterogeneity. Ontologies are an effective way of handling heterogeneities
and thus come into play. Basic promises as to what ontologies can do have been
investigated and it further evokes the necessary research into two areas: the trust
issues on information sources and the issues of representing shared beliefs without
compromising private beliefs.
We analysed the differences between trust in an action and trust in a piece of
information. Two constituents of evaluating an information source’s trustworthiness
were thus identified, namely, the belief of sincerity and the belief of competency.
We also proposed several ways of generating general or topic specific trustworthiness
from the degree of sincerity and degree of competency. The obtained trustworthiness
serves as crucial input, and is often required by fusion and weighted knowledge base
merging when considering revision on information received from multiple sources. Our
investigation into the feasibility of keeping information about the source shows that it
171
is advisable for an agent to keep a pedigree of at least 3 levels of depth. This enables
the agent to analyse and keep track of passing-on information, whose credibility can
be wrongly computed in some real application domains, such as robot soccer. Overall,
the research into trust issues not only provided a clear domain description but also
formulated the necessary components of agent beliefs, i.e. domain beliefs and social
beliefs. The implementation details are provided in Chapter 10.
After clarifying the trust issues, we proposed a shared knowledge structure that
is capable of representing both shared knowledge as well as private knowledge. This
allows us to leverage our research from a MSBR level to a MABR level. At the MABR
level supported by shared knowledge structure, agents can dynamically manage their
shared knowledge with other agents and participate in group decision making pro-
cesses in maintaining the consistency of the shared beliefs. We define a knowledge
grade for a belief according to the level of accessibility. MABR can therefore be
achieved through knowledge migration where a piece of information can be upgraded
and degraded.
The investigated concepts, such as various revision schemes, trust, information
pedigree, shared beliefs and ontologies, eventually come together within a flexible
and general framework. The framework is adaptable for incorporating new belief re-
vision schemes and viable for a heterogenous multi-agent environment. In particular,
as the layering approach is adopted, a belief revision agent designed under such a
framework is capable of providing services at various levels. It can model single belief
revision behaviour, revision behaviour for information from multiple sources, as well
as cooperative revision in multi-agent situation where revision on shared or common
knowledge is desired. This provides a tangible architecture of a belief revision service
172
provider for an dynamic, heterogenous, autonomous open environment.
11.2 Limitations and Implications for Future Research
The belief revision agent we described is service oriented, the agent instances may
operate on a request agent’s knowledge base. This may raise security concerns. Intel-
ligent agents are considered to be autonomous, thus able to making decisions without
human interventions. Therefore, if the infrastructure does not enforce the security
and privacy rules that it should abide by, a belief revision agent may not be stopped
from trading some of the trustor’s private beliefs to increase its own utilities. There-
fore, in some case, a subsumption structure would be better, where the belief revision
agent works as an internal process of a manager agent. The manager agent can ini-
tiate a belief revision agent and delegate revision tasks to it. The revision agent
could function as a passive process of the manager agent and have no external access
directly, meaning all inter-agent communication should be conducted through the
manager agent. Alternatively, such belief revision functionalities (SBR, MSBR and
MABR) can be implemented into capabilities, which can then be kept internal to the
agent itself. Further research into an infrastructure that addresses the security and
privacy concerns is certainly of interest and would have practical implications to real
applications.
Although JADE is used as the agent platform and the belief revision agent ex-
tends a JADE base agent, the framework does not preclude the possibility of using
other agent development environment and infrastructure to achieve more sophisti-
cated agent behaviour. For example, JACK - a BDI agent programming environment
173
- focuses more on the agent internal behaviour as compared to JADE agent, which
focuses more on the external behaviour such as communication and etc. JACK agents
exhibit goal-directed behaviour and are more suitable to be described as intelligent
agents. JACK provides a more robust environment for modelling agent internal states
such as belief sets, which simplify the implementation of social beliefs and domain
beliefs. However, JADE agents excel at ontology description, supporting FIPA com-
pliant features for agent management and communication. With the newly developed
FIPA-JACK 1 and further work into it, it is possible to combine the strength of two
agent development environments to have a better agent wrapper for belief revision
services.
On the MABR level, group decision making processes are often needed to achieve
the possible consensus on the shared beliefs. This coincides with the research into
knowledge merging, such as arbitration merging[74] and majority merging[75]. Fur-
ther research into the connection between knowledge migration and different merging
operators would be exceedingly useful. In particular, domains such as cooperative in-
formation systems, distributed databases, resolving conflicts among multiple agents,
would be appealing application areas for such research. It is also possible for our
multi-agent belief revision design to serve as a flexible test-bed for various merging
operators.
1 http://www.cs.rmit.edu.au/agents/protocols/
174
Appendix A
Agent Environment Properties
• Accessible vs inaccessible.
An accessible environment is one in which the agent can obtain complete, accu-
rate, up-to-date information about the environment’s state. Most moderately
complex environments(includeing, for example, the everyday physical world and
the Internet) are in accessbile. The more accessible an envirom=nment is, the
simpler it is to build agents to operate in it.
• Deterministic vs non-deterministic.
As we have already metnioned, a deterministic environment is one in which
any action has a single guaranteed effect - there is no uncertainty about the
state that will result from performing an action. The pysical world can to
all intents and purposes be regarded as non-deterministic. Non-deterministic
environments present greater problems for the agent designer.
• Episodic vs non-episodic.
In an episodic environment, the performance of an agent is dependent on a
number of discrete episodes, which no link between the performance of an agent
in different scenarios. An example of an episodic environment would be a mail
175
sorting system. Episodic environments are simpler from the agent developers’
perspective because the agent can decide what action to perform based only on
the current episode - it need not reason about the interactions between this and
furture episode.
• Static vs dynamic.
A static environment is one that can be assumed to remain unchanged except
by the performance of actions by the agent. A dynamic environment is one that
has other processes operating on it, and which hence changes in ways beyond
the agent’s control. The physical world is a highly dynamic environment.
• Discrete vs continuous.
An environment is discrete if there are a fixed, finite number of actions and
percepts in it. A chess game is an example of discrete environment, and taxi
drivinng is an example of a continous one.
As Russell and Norvig observe[96], if an environment is sufficiently complex, then
the fact that it is actually deterministic is not much help: to all intents and purposes,
it may as well be non-deterministic. The most complex general class of environ-
ments are those that are inaccessible, non-deterministic, non-episodic, dynamic, and
continuous.
176
Appendix B
Logical Foundations
In order to formalise the above examples and introduce belief revision theory formally,
this section will present the logical notations and terminologies that we are going to
use throughout the thesis.
Facts (e.g. It is raining) are expressed as sentences 1 in some formal language L
(e.g. propositional logic or first order logic). Assume the language L is closed under
the logical connectives (i.e. boolean operators): ¬ (negation), ∧ (conjunction), ∨
(disjunction), → (implication), and ↔ (if and only if).
Letters p, q, r .... are used for atomic sentence and letters A, B, C ... for arbitrary
sentences. They represent the sentences in L, thus the facts that an agent has in its
knowledge/belief set or base.
Each sentence has a meaning (semantics) - either t or f - relative to the meaning
of the propositional symbols it contains. For example, sentence A ∨ B’s meaning is
relative to the t and f of both A and B.
An interpretation, or truth assignment, for a set of sentences is a function from
its set of propositional symbols to {t, f}.
1 closed formulae.
177
An interpretation satisfies a sentence if the sentence evaluates to t under the in-
terpretation. In order words, a sentence is satisfiable if there exist a truth assignment
that can make the forumla true.
A set S of sentences entails A if every interpretation that satisfies all elements of
S, also satisfies A. This is denoted S ⊢ A. It is usual to write A ⊢ B instead of
{A} ⊢ B, where {A} is a one-element set with the only element A.
A set S of sentences is valid or tautology if every interpretation for S satisfies
every formula in S. In other words, no matter what truth values that are assigned to
S, every sentence in S evaluates to t. This is denoted ⊢ S. In propositional logic, a
valid sentence is also called a tautology, which is denoted similiarly ⊢ A.
A set S of sentences satisfiable (or consistent) if there is some interpretation for
S that satisfies every sentence in S.
A set S of sentences is unsatisfiable (or inconsistent) if it is not satisfiable, ie,
there is no interpretation for S that satisfies every sentence in S. An inconsistent
sentence A is denoted �⊢ A.
Formulae A and B are equivalent, A � B, provided that A ⊢ B and B ⊢ A. For
example:
A belief base is a set of sentences in L.
A → B � ¬A ∨ B
¬A � A → f
A belief set is a set of sentences in L which satisfies the integrity constraint:
(I) If K logically entails B, then B ∈ K. (Integrity Constraint)
178
In other words, a belief set includes both explicit beliefs(ie, sentences) plus all of
the implicit beliefs which can be derived from them.
179
Appendix C
JADE Implementation of
Ontologies V2.4
The package jade.onto.basic includes a set of classes that are commonly part of
every ontology, such as Action, TruePredicate, FalsePredicate, ResultPredicate, The
BasicOntology can be joined to any user-defined ontology as described in section 3.6.
Notice that the Action class should be used to represent actions. It has a couple
of methods to set/get the AID of the actor (i.e. the agent who should perform the
action) and the action itself (e.g. Register/Deregister/Modify).
180
ContentElement
GenericAction Proposition
CommunicationAct AgentAction Predicate ActionPredicate HigerOrderPredicate Concept
E.g.
Inform,
Request
E.g.
Buy,
Sell
E.g.
FatherOf,
SonOf
E.g.
Done
E.g.
Believe,
Intend
Figure C.1: Ontology Elements Represented as JADE Classes[30]
Term
E.g.
Person,
Address
181
Appendix D
FIPA Agent Platform Components
The agent management reference model consists of the following logical components,
each representing a capability set. These can be combined in physical implementa-
tions of Agent Platforms (AP):
• An Agent is the fundamental actor on an AP which combines one or more
service capabilities into a unified and integrated execution model that may
include access to external software, human users and communications facilities.
An agent must have at least one owner, for example, based on organisational
affiliation or human user ownership, and an agent may support several notions
of identity. An Agent Identifier (AID) labels an agent so that it may be distin-
guished unambiguously within the Agent Universe. An agent may be registered
at a number of transport addresses at which it can be contacted and it may
have certain resource brokering capabilities for accessing software.
• A Directory Facilitator (DF) is a mandatory component of an AP. The DF
provides yellow pages services to other agents. Agents may register their services
with the DF or query the DF to find out what services are offered by other
agents. Multiple DFs may exist within an AP and may be federated.
182
• An Agent Management System (AMS) is a mandatory component of an AP.
The AMS exerts supervisory control over access to and use of the agent platform.
Only one AMS will exist in a single agent platform. The AMS maintains a
directory of AIDs which contain transport addresses (amongst other things) for
agents registered with the AP. The AMS offers white pages services to other
agents. Each agent must register with an AMS in order to get a valid AID.
• An Message Transport Service (MTS) is the default communication method
between agents on different APs.
• An Agent Platform (AP) provides the physical infrastructure in which agents
can be deployed. The AP consists of the machine(s), operating system, agent
support software, FIPA agent management components (DF, AMS and MTS)
and agents.
The internal design of an AP is an issue for agent system developers and is not
a subject of standardisation within FIPA. APs and the agents which are native
to those APs, either by creation directly within or migration to the AP, may
use any proprietary method of inter-communication.
It should be noted that the concept of an AP does not mean that all agents
resident on an AP have to be co-located on the same host computer. FIPA
envisages a variety of different APs from single processes containing lightweight
agent threads, to fully distributed APs built around proprietary or open middle-
ware standards.
• Software describes all non-agent, executable collections of instructions acces-
183
sible through an agent. Agents may access software, for example, to add new
services, acquire new communications protocols, acquire new security proto-
cols/algorithms, acquire new negotiation protocols, access tools which support
migration, etc.
184
Appendix E
Publications
1. Wei Liu and Mary-Anne Williams, Trustworthiness of information sources and
information pedigrees, Intelligent Agents VIII (Agent Theories, Architectures
and Languages), John-Jules Ch. Meyer, Milind Tambe (Eds.), Springer (Hot
Topics in LNAI), 2002.
2. Wei Liu and Mary-Anne Williams, A framework for multi-agent belief revision,
Journal of Studia Logia, edited by David Makinson, 2001.
3. Wei Liu and Mary-Anne Williams, A framework for multi-agent belief revi-
sion(part ii : A layered model and shared knowledge structure), in the Proceed-
ings of the 8th International Workshop on Non-Monotonic Reasoning (NMR2000)
(Colorado, USA), 2000.
4. Wei Liu and Mary-Anne Williams, A framework for multi-agent belief revision
(part i: The role of ontology), in the Proceedings of 12th Australian Joint
Conference on Artificial Intelligence (Sydney, Australia) (Norman Foo, ed.),
Lecture Notes in Artificial Intelligence, Springer-Verlag, 1999.
185
Bibliography
[1] C. Alchourrón, P. Gärdenfors, and D. Makinson, On the logic of theory change:
Patial meet functions for contraction and revision, Journal of Symbolic Logic
50 (1985), 510–530.
[2] Salem Benferhat, Dider Dubois, and Henri Prade, From semantic to syntactic
approaches to informtion combination in possibilistic logic, Aggregation and
Fusion of Imperfect Information, Studies in Fuzziness and Soft Computing
(B. Bouchon-Meunier, ed.), Physica Verlag, 1997, pp. 141–161.
[3] Salem Benferhat, Didier Dubois, Henri Prade, and Henri Prade, A practical
approach to fusing prioritized knowledge bases, Progress in Artifical Intelligence,
LNAI 1695.
[4] Salem Benferhat, Didier Dubois, Henri Prade, and Mary-Anne Williams, A
practical approach to fusing prioritized knowledge bases, Progress in Artificial
Intelligence, LNAI 1695, Springer Verlag, 1999, pp. 222–236.
[5] , A practical approach to revising prioritized knowledge bases, The Pro-
ceeding of the Third International Conference on Knowledge Based Intelligent
Information Engineering Systems, IEEE Press, 1999, pp. 170–174.
[6] Salem Benferhat, Souhilla Kaci, Daniel Le Berre, and Mary-Anne Williams,
Weakening conflicting information for iterated revision and knowledge integra-
tion,, the Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence (IJCAI), 2001.
[7] Tim Berners-Lee, The semantic web, Online Journal of Science American
(May,2001).
186
[8] Sissela Bok, Lying: Moral choice in public and private life, Pantheon Books,
1978.
[9] R. Brachman and J. Schmolze, An overview of the kl-one knowledge represen-
tation system, Cognitive Science 9 (1985), no. 2, 171–216.
[10] William H. Calvin, How brains think: Evolving intelligence, then and now, Basic
Books (Science Masters), New York, 1996.
[11] John Cantwell, Resolving conflicting information, Journal of Logic, Language
and Information 7 (1998), 191–220.
[12] Christina Carrick, Belief revision: A survey.
[13] Cristiano Castelfranchi and Rino Falcone, Principles of trust for mas: Cog-
nitive anatomy, social importance, and quantification, the Third International
Conference on Multi-Agent Systems (Los Alamitos) (Y Demazeau, ed.), IEEE
Computer Society, 1998, pp. 72–79.
[14] R Davis and RG Smith, Negotiation as a metaphor for distributed problem
solving, Artificial Intelligence 20 (1983), 63–109.
[15] R. Demolombe, To trust information sources: a proposal for a modal logical
framework, the First International Workshop on Deception, Fraud and Trust in
Agent Societies (Minneapolis/St Paul, USA) (C. Castelfranchi and Y-H. Tan,
eds.), 1998.
[16] A. P. Dempster, Upper and lower probabilities induced by a multivalued mapping,
Annals of Mathematical Statistics 38 (1967), 325–339.
[17] , A generalization of bayesian inference, Journal of the Royal Statistical
Society, Series B 30 (1968), 205–247.
[18] A.F. Dragoni, Belief revision under uncertainty in a multi-agent environment,
Knowledge-Based Systems: Advanced Concepts, Techniques and Applications
(S.Tzafestas, ed.), World Scientific, 1997, pp. 191–215.
[19] A.F. Dragoni and Paolo Giorgini, Revising beliefs received form multiple sources,
Frontiers of Belief Revision (Mary Anne Williams and Hans Rott, eds.), 1999.
187
[20] A.F. Dragoni, Paolo Giorgini, and Marco Baffetti, Distributed belief revision vs.
belief revision in a multi-agent environment: First result of a simulation ex-
periment, Multi-Agent Rationality, Proc. of MAAMAW’97 (Ronneby, Sweden),
LNAI, Springer-Verlag, 1997, pp. 45–62.
[21] A.F. Dragoni, Paolo Giorgini, and Paolo Puliti, Distributed belief revision versus
distributed truth maintenance, Proc. of 6th IEEE conf. on Tools with A.I., IEEE
computer Press, 1994.
[22] A.F. Dragoni and P.F. Giorgini, Belief revision through the belief function for-
malism in a multi-agent environment, Third International Workshop on Agent
Theories, Architectures and Languages, Springer-Verlag, 1997.
[23] D. Dubois, J. Lang, and H. Prade, Possibilistic logic, Handbook of Logic in
Artificial Intelligence and Logic Programming, vol. 3, Oxford University Press,
Oxford, U.K., 1994, pp. 439–513.
[24] Dider Dubois and Henri Prade, Belief change and possibility theory, Belief Re-
vision (Peter Gärdenfors, ed.), Cambridge University Press, Cambridge, 1992,
pp. 142–182.
[25] Bruce Edmonds, Modelling socially intelligent agents, Applied Artificial Intelli-
gence 12 (1998), 677–699.
[26] G Elofson, Developing trust with intelligent agents: An exploratory study, the
First International Workshop on Deception, Fraud and Trust in Agent Soci-
eties (Minneapolis/St Paul, USA) (C. Castelfranchi and Y-H. Tan, eds.), 1998,
pp. 125–139.
[27] Eithan Ephrati and Jeffrey S. Rosenschein, Deriving consensus in multiagent
systems, Artificial Intelligence 87 (1996), 21–74.
[28] Hans-Erik Eriksson and Magnus Penker, Uml tookit, John Wiley and Sons, Inc.,
1998.
[29] fab@fipa.org, Fipa ontology service specification (xc00086d), FOUNDATION
FOR INTELLIGENT PHYSICAL AGENTS, Geneva, Switzerland, version d
ed., August 2001.
188
[30] Tiziana Trucco Giovanni Rimassa Fabio Bellifemine, Giovanni Caire, Jade pro-
grammers guide, CSELT S.p.A. and TILab S.p.A., 2001.
[31] Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, Reason-
ing about knowledge, 1 ed., The MIT Press, London, 1995.
[32] Dieter Fensel, Ontologies: A silver bullet for knowledge management and elec-
tronic commerce, Springer, Berlin, 2001, With Brief Introduction to almost all
ontoligies languages: KIF, Ontolingua, Frame Logic, Classic, except DAML.
[33] FIPA, http://www.fipa.org/.
[34] Foundation of Intelligent Physical Agent, Fipa agent management specification,
xc00023h ed.
[35] N. Friedman and J. Y. Halpern, Plausibility measures: A user’s mannual.
[36] D.M. Gabbay, C.J. Hogger, and J.A. Robinson, Nonmonotonic reasoning and
uncertain reasoning, Handbook of Logic in Artificial Intelligence and Logic Pro-
gramming, vol. 3, Oxford University Press, Oxford, U.K., 1994.
[37] Dov M. Gabbay, C.J. Hogger, and J. A. Robinson (eds.), Handbook of logic
in artificial intelligence and logic programming, vol. 1, Oxford University Press
Inc., New York, 1993.
[38] Peter Gädenfors, An epistemic approach to conditionals, American Philosophi-
cal Quatery 18 (1981), 203–211.
[39] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, Design pat-
terns, elements of reusable object-oriented software, Addison Wesley Longman,
Inc., 1995.
[40] P. Gärdenfors and D. Makinson, Revisions of knowledge systems using epistemic
entrenchment, Proceeding of the Second Conference on Theoretical Aspects of
Reasoning About Knowledge (M. Vardi, ed.), Morgan Kaufmann, 1988.
[41] Peter Gärdenfors, Knowledge in flux - modeling the dynamics of epistemic
states, The MIT Press, London, 1988.
189
[42] Peter Gärdenfors and Hans Rott, Belief revision, Handbook of Logic in Artifi-
cial Intelligence and Logic Programming - Volume 4: Epistemic and Temporal
Reasoning (Dov M. Gabbay, C. J. Hogger, and J. A. Robinson, eds.), Oxford
University Press, 1995.
[43] Fausto Giunchilglia, John Mylopoulos, and Anna Perini, The tropos software
development methodology: Process, models and diagrams, Agent-Oriented Soft-
ware Engineering Workshop in the First International Joint Conference on Au-
tonomous Agents and Multi-Agent Systems (AAMAS 2002) (Bologna, Italy),
2002.
[44] Piotr J. Gmytrasiewicz and Edmund H. Durfee, Toward a theory of honesty and
trust among communicating autonomous agents, Group Decision and Negotia-
tion 2 (1993), 237–258.
[45] A. Grove, Two modellings for theory change, Journal of Philosophical Logic 17
(1988), 157–170.
[46] Thomas R. Gruber, Toward principles for the design of ontologies used for
knowledge sharing, Technical Report KSL 93-04, Knowledge Systems Labora-
tory, Stanford University, 1993.
[47] Tom Gruber, Welcome to the srkb working group, SRKB mailing list,
http://www-ksl.stanford.edu/email-archives/srkb.messages/0.html (1994).
[48] N. Guarino and P. Giaretta, Ontologies and knowledge bases - towards a termi-
nological clarification, Towards Very Large Knowledge Bases- Knowledge Build-
ing and Knowledge Sharing (NJ Mars, ed.), IOS Press, 1995, pp. 25–32.
[49] Nicola Guarino, Understanding, building and using ontologies - a commen-
tary to ‘using explicit ontologies in kbs development’by van heijst, schreiber
and wielinga, International Journal of Computer Studies 46 (1997), no. 3/4,
293–310.
[50] Nicola Guarino, Formal ontology and information systems, 1st International
Conf. on Formal Ontology in Information Systems(FOIS’98) (Trento, Italy)
(Nicola Guarino, ed.), Amsterdam, IOS Press, 1998.
190
[51] , Some ontological principles for desinging upper level lexical resources,
In Proceedings of First International Conference on Language Resources and
Evaluation, ELRA-European Language Resources Association, Granada, Spain,
1998, pp. 527–534.
[52] P. Halmos, Measure theory, Van Nostrand, 1950.
[53] Joseph Y. Halpern, Two views of belief: Belief as generalized probability and
belief as evidence, Artificial Intelligence 54 (1992), 275–317.
[54] Jiawei Han, Raymond T. Ng, Yongjian Fu, and Son K. Dao, Dealing with se-
mantic heterogeneity by generalization-based data mining techniques, Coopera-
tive Information Systems - Trends and Directions (Gunter Schlageter Michael
P. Papazoglou, ed.), Academic Press, San Diego, 1998, pp. 207–232.
[55] S. O. Hansson, Belief contraction without recovery, Studia Logica 50 (1991),
251–260.
[56] John Hardwig, The role of trust in knowledge, Journal of Philosophy 88 (1991),
693–708.
[57] Gilbert Harman, Change in view, Bradford Books, MIT Press, Cambridge, MA,
1986.
[58] E. Hisdal, Conditional possibilities - independce and non-interactivity, Fuzzy
Sets and Systems 1 (1978), 283–297.
[59] M. N. Huhns and D. M. Bridgeland, Distributed truth maintenance, Cooperating
Knowledge Based Systems (S. M. Dean, ed.), Springer-verlag, 1990, pp. 133–
147.
[60] Richard Hull, Managing semantic heterogeneity in databases, Proceedings of
the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of
Database Systems (Invited tutorial) (Tucson, Arizona), ACM, 1997, pp. 51–61.
[61] JADE, http://jade.ceslt.it/.
191
[62] N. R. Jennings, On being responsible, Decentralized AI 3 — Proceedings of
the Third European Workshop on Modelling Autonomous Agents and Multi-
Agent Worlds (MAAMAW-91) (Amsterdam, The Netherlands) (E. Werner and
Y. Demazeau, eds.), Elsevier Science Publishers, 1992, pp. 93–102.
[63] N. R. Jennings, On agent-based software engineering, Artificial Intelligence 117
(2000), no. 2, 277–296.
[64] Catholijn M. Jonker and Jan Treur, Formal analysis of models for the dynamics
of trust based on experiences, the 9th European Workshop on Modelling Au-
tonomous Agents in a Multi-Agent World : Multi-Agent System Engineering
(MAAMAW-99) (Berlin) (Francisco J. Garijo and Magnus Boman, eds.), vol.
1647, Springer-Verlag: Heidelberg, Germany, 1999, pp. 221–231.
[65] Audum Jφsang, Prospectives for modeling trust in information security, Infor-
mation Security and Privacy, ACISP’97 (Sydney, Australia) (Vijay Varadhara-
jan, Josef Pieprzyk, and Yi Mu, eds.), LNCS, vol. 1270, Spinger-Verlag, 1997,
pp. 2–13.
[66] H. Katsuno and A. O. Mendelzon, Propositional knowledge base revision and
minimal change, Artificial Intelligence 52 (1991), 263–294.
[67] Jeffrey O. Kephart and Amy R. Greenwald, Shopbot economics, Proceedings of
the Third International Conference on Autonomous Agents (Agents’99) (Seat-
tle, WA, USA) (Oren Etzioni, Jörg P. Müller, and Jeffrey M. Bradshaw, eds.),
ACM Press, 1999, pp. 378–379.
[68] Noa E. Kfir-dahav and Moshe Tennenholtz, Muti-agent belief revision, 6th Conf.
on Theoretical Aspects to Rationality and Knowledge, 1996, pp. 175–194.
[69] David Kinny and Michael Georgeff, Commitment and effectiveness of sit-
uated agents, The Twelfth International Joint Conference on Artificial
Intelligence(IJCAI-91) (Sydney, Australia), 1991, pp. 82–88.
[70] J. De Kleer, An assumption based truth maintenance system, Artificial Intelli-
gence 28 (1986), 127–162.
[71] B. Krulwich, Bargain finder agent prototype, 1995.
192
[72] Daniel J. Lehmann, Belief revision, revised, International Joint Conference of
Artificial Intelligence, 1995, pp. 1534–1540.
[73] Isaac Levi, Subjunctives, dispositions and chances, Synthese 34 (1977), 423–455.
[74] Paolo Liberatore and Marco Schaerf, Arbitration (or how to merge knoweledge
bases), IEEE Trans. on Knowledge and Data Engineering 10 (1998), no. 1,
76–90.
[75] J. Lin, Integration of weighted knoweldge bases, Artifical Intelligence 82 (1996),
no. 2, 363–378.
[76] Jinxin Lin and Alberto O. Mendelzon, Merging databases under constraints,
International Journal of Cooperative Information Systems 7 (1998), no. 1, 55–
76.
[77] M. Ljungberg and A. Lucas, The oasis air traffic management system, Proceed-
ings of the Second Pacific Rim International Conference on Artificial Intelligence
(PRCAI’92), 1992.
[78] Alessio Lomuscio and Mark Ryan, Ideal agents sharing (some!) knowledge, 13th
European Conf. on AI, ECAI’98 (Henri Parade, ed.), John Wiley & Sons, Ltd,
1998, pp. 557–561.
[79] P. Maes, R. Guttman, and A. Moukas, The role of agents as mediators in elec-
tronic commerce, Special Issue of Knowledge Engineering Review on Practical
Applications of Agents, Edited by Barry Crabtree (Summer, 1998).
[80] T. Magedanz, K. Rothermel, and S. Krause, Intelligent agents: An emerging
technology for next generation telecommunications?, INFOCOM’96 (San Fran-
cisco, CA, USA), 1996.
[81] Benedita Malheiro, N. R. Jennings, and Eugénio Oliveira, Belief revision in
multi-agent systems, 11th European Conferece on Artificial Intelligence (Ams-
terdam, The Netherlands) (A. G. Cohn, ed.), John Wiley & sons, Ltd., 1994,
pp. 294–298.
193
[82] Pierre Marquis and Nadège Porquet, Decomposing propositional knowledge bases
through topics, Partial Knowledge And Uncertainty: Independence, Condition-
ing, Inference (Rome, Italy), 2000.
[83] Stephen Paul Marsh, Formalising trust as a computational concept, For the
degree of doctor of philosophy, University of Stirling, 1994.
[84] S. McIlraith, T.C. Son, and H. Zeng, Semantic web services, IEEE Intelligent
Systems. Special Issue on the Semantic Web 16 (2001), no. 2, 46–53.
[85] Ron van der Meyden, Mutual belief revision, the Fourth International Confer-
ence on Principles of Knowledge Representation and Reasoning (KR’94), 1994.
[86] D. Ndumu, J. Collis, and H. Nwana, Towards desktop personal travel agents,
1998.
[87] A. Newell, The knowledge level, Artificial Intelligence 18 (1982), 87–127.
[88] Natalya Fridman Noy and Deborah L. McGuinness, Ontology development 101:
A guide to creating your first ontology, Tech. report, Stanford Knowledge Sys-
tems Laboratory Technical Report KSL-01-05 and Stanford Medical Informatics
Technical Report SMI-2001-0880, March 2001.
[89] Hyacinth S. Nwana and Divine T. Ndumu, A perspective on software agents
research, The Knowledge Engineering Review 14 (1999), no. 2, 1–18.
[90] Object Management Group (OMG), http://www.omg.org/technology/documents/formal/u
Unified modeling language (uml) specification, version 1.4 ed., 2001.
[91] Lin Padgham and Michael Winikoff, Prometheus: A methodology for develop-
ing intelligent agents (poster), the proceedings of the First International Joint
Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2002)
(Bologna, Italy), 2002.
[92] Michael P. Papaxoglou and Gunter Schlageter (eds.), Cooperative information
systems, Academic Press Limited, San Diego, California, 1998.
[93] J. Pearl, Probabilistic reasoning for intelligent systems, Morgan Kaufmann Pub-
lishers, 1988.
194
[94] P. Peppas, Belief change and reasoning about action: An axiomatic approach to
modelling inert dynamic worlds and the connection to the logic of theory change,
Ph.D. thesis, University of Sydney, Australia, 1993.
[95] P. Peppas and M. A. Williams, Constructive modelings for theory change, Notre
Dame Journal of Formal Logic 36 (1995), no. 1, 120–133.
[96] S. Russell and P. Norvig, Artificial intelligence: A modern approach, Prentice-
Hall, 1995.
[97] SATEN, http://u2.newcastle.edu.au/webworld/saten/ (hint: use netscape 4.5
or above with java 1.1.1 plugin).
[98] Glenn Shafer (ed.), A mathematical theory of evidence, Prinston University
Press, New Jersey, 1976.
[99] Munindar P. Singh, Muti-agent systems - a theoretical framework for inten-
tions, know-how, and communications, LNAI, Springer-Verlag, Berlin Heidel-
berg, 1994.
[100] W. Spohn, Ordinal conditional functions: A dynamic theory of epistemic states,
Causation in Decision, Belief Change and Statistics: II (W. L. Harper and
B. Skyrms, eds.), Kluwer Academic, 1988, pp. 105–134.
[101] Stanlnaker, Probability and conditionals, Philosophy of Science 37 (1970), 64–
80.
[102] Gil Tidhar, Elizabeth A. Sonenberg, and Anand S. Rao, On team knowledge and
common knowledge, Third International Conference on Multi-Agent Systems
(Paris, France) (Yves Demazeau, ed.), IEEE Computer Society, 1998, pp. 301–
308.
[103] A. M. Turing, On computable numbers, with an application to the entscheidungs
problem, Proceedings of the London Mathematical Society, 2, vol. 42, 1936-7,
pp. 230–265.
[104] Mike Uschold, Knowledge level modeling: concepts and terminology, The Knowl-
edge Engineering Review 13 (1998), no. 1, 5–29.
195
[105] M. A. Williams, On the logic of theory base change, Logics in Artificial In-
telligence (C. MacNish, D. Pearce, and L. M. Pererira, eds.), LNCS, no. 835,
Springer Verlag, 1994, pp. 86–105.
[106] M. A. Williams and Maurice Pagnucco, Determining explanations using trans-
mutations, Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, Morgan Kaufmann, 1995, pp. 822–827.
[107] M. A. Williams and A Sims, Saten: An object-oriented web-based re-
vision and extraction engine, International Workshop on Nonmono-
tonic Reasoning (NMR’2000)., Online Computer Science Abstract:
http://arxiv.org/abs/cs.AI/0003059/, 2000.
[108] Mary Anne Williams, Transmutation of knowledge systems, 4th International
Conf. on Principles of Knowledge Representation and Reasoning (J. Doyle,
E. Sandewall, and P. Torasso, eds.), Morgan Kaufmann Publishers, 1994,
pp. 619 – 629.
[109] Mary Anne Williams, Aesthetics and the explication of surprise, Journal of
Languages of Design 3 (1996), 145–157.
[110] , Anytime belief revision, International Joint Conference on Artificial
Intelligence, Morgan Kaufmann Publishers, 1997, pp. 74 – 80.
[111] Mary-Anne Williams, Applications of belief revision, Transactions and Change
in Logic Databases (B. Freitag, ed.), vol. LNCS 1472, Springer Verlag, 1998,
pp. 15–47.
[112] M. Wooldridge and N. R. Jennings, Intelligent agents: Theroy and practice.,
The Knowledge Engineering Review 10 (1995), no. 2, 115–152.
[113] Michael Wooldridge, Intelligent agents, Multiagent Systems (Gerhard Weiss,
ed.), The MIT Press, 1999.
[114] L.A. Zadeh, Fuzzy sets, Information and Control 8 (1965), 338–353.
[115] , Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems
1 (1978), 3–28.
196
