Methodologies for Solving Conflicting Beliefs
1 Aims
Multi-Agent Systems (MAS) are a natural setting for conflicts where different
perspectives regarding shared information are generated by the different
agents. The multiple conflicting perspectives can be: (i) incompatible
beliefs regarding some shared concept, or (ii) reconcilable beliefs regarding
some shared concept. These types of conflicts are called, respectively,
negative and positive conflicts. The aim of this project was the development
of methodologies for solving conflicting beliefs. The type of MAS envisaged
are made of autonomous cooperating agents with belief revision capabilities.
In particular, the agents implemented are built upon individual Assumption
based Truth Maintenance Systems (ATMS) enhanced with the necessary abilities
to perform conflict resolution. Each agent has a self model, where the
agent's individual intelligent system is described (knowledge and beliefs
that the agent has or is expected to have), and an acquaintances model,
where the full listing of the capabilities of the other agents which are
relevant to the problem solving activity of the agent is provided (tasks
and results that the other agents are expected to provide or share with
the agent). It is based on the information listed on the acquaintances
model that the agents cooperate, performing task sharing and result sharing.
The investigation carried out was focussed on building conflict solving
methodologies for two specific kinds of negative conflicts:
-
Belief/Disbelief Conflicts - when some agents believe while some
other do not believe in the same proposition;
-
Disbelief Conflicts - when the agents detect incompatible sets of
beliefs and have, as a result, to drop previously held conclusions (reason
maintenance).
While in the case of Belief/Disbelief conflicts, the methodology for conflict
resolution has to decide which belief status should be adopted, in the
case of the Disbelief conflicts, it has to try to find alternatives to
support the previously believed conclusions.
The concept of conflict resolution addressed in this work is not a
one time conflict solving activity as in a typical MAS. A conflict in this
scenario is dynamic, may have multiple episodes during its existence, and
only ceases to exist when all of the involved agents believe in the proposition.
New conflict episodes occur whenever any change regarding the conflict
is detected, either because the number of agents involved or because the
perspectives themselves have changed. Every time a new episode of an existing
conflict is detected a re-evaluation of the conflict is performed and a
new outcome may be generated.
2 Methodologies for Solving Conflicting Beliefs
Specific methodologies were designed for the resolution of the identified
types of negative conflicts:
-
A methodology for solving Belief/Disbelief conflicts - a selection process
based on the assessment of the credibility values of the opposing belief
status, and
-
A methodology for solving Disbelief conflicts - a search process for an
unique consensual alternative based on a "next best candidate" strategy.
The methodologies hereby presented rely on the availability of belief revision
capabilities since dynamic conflict resolution requires the MAS to abandon
previous conclusions in order to adopt new ones.
2.1 Belief/Disbelief Conflicts
The Belief/Disbelief Conflicts result from the attribution of contradictory
belief status to the same concept/proposition by different agents. To solve
this type of conflicts, and since conflict solving is regarded as a dynamic
activity, the agents involved have to maintain two separate views: their
individual perspectives and the socially generated conflict solution. While
the responsibility for generating the individual perspectives rely solely
on the agent itself, the conflict outcome depends on the application
of Belief/Disbelief conflict solving methodologies. The methodology
conceived for solving the Belief/Disbelief conflicts encompasses two complementary
approaches:
-
the default domain dependent approach - where each domain has a
multiple perspectives processing criterion defined a priori by the
designer of the system, which can be changed, during execution, by the
user through the user interface, and
-
the dynamic data dependent approach - where each conflict episode
will be analysed beforehand to decide which multiple perspectives processing
criterion to apply.
2.1.1 The Default Domain Dependent Approach
The knowledge represented in the MAS is organized in domains with pre-defined
characteristics. These properties include, among others, (i) lists of candidates
for attributes of domain concepts ordered by preference - representing
alternative values for the listed concept attributes, and (ii) a list of
default multiple perspective processing criteria ordered by preference-
specifying the set of policies, organized by preference, that can be used
to accommodate the domain's conflicting perspectives. In order to process
the multiple agent perspectives regarding the belief status of a proposition
three basic processing criteria were implemented:
The CONsensus (CON) criterion - The shared proposition will
be (i) Believed, if all of the perspectives of the different
agents involved are believed, or (ii) Unbelieved, otherwise.
The MAJority (MAJ) criterion - The shared proposition will
be (i) Believed, as long as the majority of the perspectives
of the different agents involved is believed, and (ii) Unbelieved,
otherwise.
The At Least One (ALO) criterion - The shared proposition
will be (i) Believed as long as at least one of the perspectives
of the different agents involved is believed, and (ii) Unbelieved,
otherwise.
The default domain multiple perspective processing criterion is pre-defined
by the knowledge engineer according to the characteristics of the represented
domain knowledge:
The CON criterion is selected whenever the consensus of the involved agents
perspectives about a belief is mandatory (e.g., only when every agent confirms
that the power has been shut off will the system report that the power
has been shut off);
The MAJ criterion is selected whenever the belief in a shared proposition
depends on the majority of the involved agents (e.g., only after
receiving the confirmation of a warning message regarding some possible
malfunctioning device from the majority of the agents will the system act);
The ALO criterion is chosen whenever a single believed perspective is enough
for making the shared proposition believed (e.g., the occurrence of
single serious alarm message is enough for triggering some system action).
Although these criteria allow an automated domain dependent multiple perspective
processing mechanism they are not flexible in the sense that they do not
take into account the strengths and weaknesses of the perspectives that
contribute to each belief status (are not data dependent).
2.2.2 The Dynamic Data Dependent Approach
Data dependent features like the agents reliability and the "strength"
of their beliefs can be used to solve Belief/Desbelief conflicts. Although
the three basic multiple perspective processing criteria remain immutable
their application depends on a prior selection process. The dynamic selection
process is based on assessment of the credibility values associated with
each belief status. Different credibility assessment procedures were conceived:
The Foundations ORigin based Procedure (FOR)
The perspectives of the agents are based on their individual set of
foundations (ATMS based agents) that resulted from some process of observation,
assumption or communication. Since communicated perspectives also resulted
from some process of observation, assumption or communication, ultimately,
the foundations set of any perspective is solely made of observed and assumed
propositions.
Within this procedure, the credibility attached to observed foundations
and assumed foundations is, respectively, 1 and 1/2. The credibility of
any perspective is then a value between 0 and 1, where 1 means that perspective
is 100% credible (it depends solely on observed foundations), 1/2 means
that the perspective has 50 % of chances of being credible, and 0 means
that no credibility whatsoever is associated with the perspective. Moreover,
the credibility of the belief status of an agent perspective is affected
by the reliability of the agent. The FOR procedure calculates the credibility
values attached to the Believed and to the Unbelieved status
and chooses to apply the basic multiple perspective processing criterion
whose outcome is the most credible belief status. If the most credible
belief status is:
(i) Unbelieved then the CON criterion is applied to the episode
of the conflict;
(ii) Believed then, if the majority of the perspectives are in favour
of believing in the proposition the MAJ criterion is applied, else the
ALO criterion is applied to the episode of the conflict.
The reliability of the agents is dynamic: an episode winning agent increases
its reliability (the individual agent perspective coincides with the outcome
of the episode) while an episode loosing agent decreases its reliability
(the individual agent perspective is contradictory to the result of the
episode). Initially, the reliability of the agents is equal to 1, but as
the time evolves and conflict episodes are processed, the reliability range
of an agent may vary between 0 and 1, where 1 means that the information
communicated by the agent has been the most credible, and where a value
near 0 means that the information issued by the agent has been less than
credible.
-
The BElief Status based Procedure (BES)
Each perspective has a credibility value which is equal to the reliability
of the agent. The different perspectives in favour of each belief status
are counted and the BES procedure chooses to apply the basic multiple perspective
processing criterion whose outcome is the most credible belief status.
If the most credible belief status is:
-
(i) Unbelieved then the CON criterion is applied to the episode
of the conflict;
-
(ii) Believed then, if the majority of the perspectives are in favour
of believing in the proposition the MAJ criterion is applied, else the
ALO criterion is applied to the episode of the conflict.
The reliability of the agents is dynamic: an episode winning agent increases
its reliability (the individual agent perspective coincides with the outcome
of the episode) while an episode loosing agent decreases its reliability
(the individual agent perspective is contradictory to the result of the
episode). Initially, the reliability of the agents is equal to 1, but as
the time evolves and conflict episodes are processed, the reliability
range of an agent may vary between 0 and 1, where 1 means that the information
communicated by the agent has been the most reliable, and where a value
near 0 means that the information issued by the agent has been less than
reliable.
The Belief/Disbelief conflict solving methodology starts by applying
the FOR procedure. If the FOR procedure is able to determine the most credible
belief status, the selected processing criterion is applied and the episode
is solved. However, if the result of the application of the FOR procedure
is a draw between the conflicting perspectives, the Belief/Disbelief
conflict solving methodology proceeds with the application of the BES
procedure. If the BES procedure is able to establish the most credible
belief status, the selected processing criterion is applied and the episode
is solved. Finally, if none of the above procedures is able to solve the
conflict episode the Belief/Disbelief conflict solving methodology
tries a last resort:
-
The Global Domain Relaxation Procedure (GDR)
The application of a less demanding multiple perspective processing
criterion to the whole domain of the conflict may eventually solve the
conflict episode. This approach is very raw and depends on the characteristics
of the domain: some domains may allow such a relaxation while others don't.
The ranking of the multiple perspective processing criteria according to
their degree of demand is: first, the CON criterion, second, the MAJ criterion,
and last, the ALO criterion. If this procedure is allowed the
default domain criterion is relaxed according to the order provided.
The sequence of application of the described procedures is structured according
to the amount of information used by the procedure to decide which belief
status should be adopted: first, the FOR procedure - based on the credibility
of the foundations which includes the reliability of the agents; second,
the BES procedure - based on the reliability of the agents and on the counting
of the the perspectives in favour of each belief status; and last, the
GDR procedure - a last resource that is independent of the data involved
in the conflict episode. There is no guaranty that by the end of the application
of the GDR procedure the conflict is solved.
Dynamic conflict resolution relies on the availability of belief revision
methodologies within the system in order to abandon the previous conflict
episode outcome and to adopt the new conflict episode solution. Each
agent is able to maintain its individual perspective has long has it remains
well founded, while, simultaneously, the global view (the outcome of the
most recent conflict episode) may change as new conflict episodes are detected
(a new conflict episode is detected whenever any perspective or the number
of agents involved changes).
2.2 Disbelief Conflicts
-
In multi-agent systems with reason maintenance the detection of incompatible
(invalid sets of) beliefs within the system triggers the reason maintenance
procedure making previously believed conclusions unbelieved. Although this
activity is essential to the maintenance of well founded beliefs,
the system should make an effort to try to believe in its conclusions as
much as possible. To solve this type of conflicts the system needs to know
how to provide alternative support to the invalidated conclusions. This
search for "next best" solutions is a relaxation mechanism. The selection
process developed relies on:
-
The Preference Order Procedure (PRO)
The preference order procedure is based on the relaxation of the attributes
of the support foundations of the detected Disbelief conflict, according
to a pre-defined preference ranking. As it was already referred, each knowledge
domain has for some domain concepts lists of ordered attribute candidates.
Each list contains the set of possible instances ordered by preference
(the first element is the best candidate, the second element is the second
best, and so forth) for the attributes of the specified domain concept,
representing alternative values for the concept attributes. When a Disbelief
conflict occurs it means that the originally built support (made of
the best attribute candidates) became invalid, and a search for a new alternative
support based the "next best" strategy has to initiated. This is achieved
by looking for "next best" instances for the foundations of the invalidated
proposition, which, when found, will provide a new valid support for the
concept.
When there are alternative instances for the foundations of concepts,
the involved agents exchange their next best candidates together with the
preference order affected by agent's reliability. In the case of the foundations
maintained by a single agent this process is a simple next best selection
process. In the case of the foundations maintained by groups of agents
a consensus candidate has to be found: if the gathered proposals are (i)
identical - the new foundation has been found; (ii) different -
the agents that proposed higher preference order candidates generate new
next best proposals (propose the following lower preference order candidates),
until they run out of candidates. The alternative foundations found though
this procedure are assumed by the system. The credibility of the resulting
new foundations are a function of the lowest preference order candidate
used and of the involved agents reliability. The reliability of the agents
is not affected by the Disbelief conflicts resolution activity.
The Disbelief conflict solving methodology starts by applying the
PRO procedure. If the PRO procedure is able to determine new foundations
for the conflicting belief, the conflict episode was solved. However, if
the PRO procedure was unable to solve the conflict, the Disbelief conflict
solving methodology proceeds with the application of the GDR procedure
already presented.
The sequence of application of the described procedures is again structured
according to the amount of information used by the procedure to decide
which belief status should be adopted: first, the PRO procedure - based
on the availability of next best candidates for the foundations;
and last, the GDR procedure - a last resort that is independent of the
data involved in the conflict episode. There is no guaranty that by the
end of the application of the GDR procedure the conflict is solved.
3 Conclusion
The concept of dynamic conflict resolution addressed in this work classifies
a conflict as a multiple episode occurrence, which terminates only when
all of the involved agents believe in the shared information. New conflict
episodes occur whenever any change regarding the conflict is detected,
either because the number of agents involved or because the perspectives
themselves have changed. Every time a new episode of an existing conflict
is detected a re-evaluation of the conflict is performed, the previous
episode result is dropped and a the new episode outcome is generated.
Although the conflicts addressed may be considered specific of the
proposed framework, the methodologies developed are general and can be
applied to more general kinds of conflicts. On one hand, the Belief/Disbelief
conflicts represent the negative type of conflicts where a fundamented
choice between two opposite results has to be made, while on the other
hand, the Disbelief conflict is a negative type of conflict (resulted from
the detection of a set of invalid beliefs) where the solution lays on the
search for an alternative consensus. The search for a consensus is a well
suited methodology for the general type of negative conflicts, especially
when more than two irreconcilable perspectives are in conflict - the involved
agents try to find alternative support for believing in an unique perspective.
The implemented methodologies try to solve the detected conflicts but
cannot, beforehand, guaranty whether their effort will be successful or
not.
For further information please contact:
Benedita Malheiro E-mail:
[email protected]
Eugenio Oliveira
E-mail: [email protected]
Last Updated: 22/01/99