Transcript LOGIC PROGRAMMING - University College Dublin

University College Dublin
SCHOOL OF COMPUTER SCIENCE & INFORMATICS
Multi-Agent Systems(MAS) &
Distributed Artificial Intelligence(DAI)
G.M.P. O’Hare
Lectures 5 & 6
© G.M.P O'Hare
School of Computer Science & Informatics
Distributed Artificial Intelligence
Distributed Artificial Intelligence(DAI) :-Endeavours to achieve
Intelligent Systems not by constructing a large KnowledgeBased System, but rather by partitioning the knowledge domain
and developing 'Intelligent Agents',each exhibiting expertise in
a particular domain fragment.
This group of agents will thereafter collectively work towards
the solution of global problems.
© G.M.P O'Hare
School of Computer Science & Informatics
The Co-operating Experts Metaphor
This solution of problems by a group of agents, providing
mutual assistance as and when necessary is often referred to
as the.....
"Community of Co-operating Experts Metaphor"
Smith and Davis, Lenat, Hewitt
Proponents of this philosophy believe that reciprocal cooperation is the cornerstone of society.
© G.M.P O'Hare
School of Computer Science & Informatics
Social Agents
Domain Specific
Knowledge Base
Q?
M?
L 5
S 4
R AND P -> Q
M 2.4
3
P?
R 4
P 6
6
2
L OR S -> M
M -> P
S?
L?
R?
Aquuaintance
Model
4
5
© G.M.P O'Hare
School of Computer Science & Informatics
Why Distributed Artificial Intelligence?
 Mirrors Human Cognition
 Potential Performance Enhancements
 Elegantly Reflects Society
 Incremental Development
 Increased Robustness
 Reflects Trends in Computer Science in General
 Strong Analogies to Decompositional Techniques employed
in Software Engineering
© G.M.P O'Hare
School of Computer Science & Informatics
Coordination Paradigms
Numerous Different Paradigms have been proposed....
 The Blackboard Model (Reddy et al)
 The Actor Model (Hewitt)
The Contract Net Approach (Smith and Davis)
 The 'BEING' Concept (Lenat)
 Hybrid Approaches
© G.M.P O'Hare
School of Computer Science & Informatics
The Blackboard Model
DAI first presented itself in the form of a blackboard
model in the HEARSAY I,II and III (Carnegie Mellon Univ)
speech understanding systems
The Blackboard model involves agents communicating by way
of a shared global data structure called the 'Blackboard'
Agents could not communicate directly with each other but
only via the contents of the blackboard.
© G.M.P O'Hare
School of Computer Science & Informatics
Poll-Hypothesis-Test
The Model generally involves a poll-hypothesis-test cycle. In the case of the
HEARSAY systems this consisted of....
Initially a hypothesis is installed on the Blackboard regarding the meaning
of a particular utterance
poll
:- each ks is polled in order to ascertain if it can refine the.
hypothesis Those which can indicate their ability to do so
with an associated confidence factor
hypothesis :- The ks boasting the highest cf is invoked making the
appropriate refinement to the hypothesis on the blackboard.
test
:- The other kss evaluate the amendment and based on the
collected response the amendment is either adopted or
ignored
The hypothesis is successively refined repeating this cycle until
the utterance is identified with a sufficient degree of confidence
© G.M.P O'Hare
School of Computer Science & Informatics
Blackboard Problems
DAI approaches seem to have followed a course similar to those
developments which have taken place in the design of real-time languages
The blackboard exhibits obvious similarities to Hoare's Monitor concept
and in general the Mail-box concept
It also suffers from the same limitations :• Congestion Problems
• Reliability Problems
Thus there was a realisation as in real-time language design that....
"To divorce data transmission and process synchronisation
was totally unnatural"
Young, Real-Time Languages
© G.M.P O'Hare
School of Computer Science & Informatics
The Actor Model
Hewitt's Actor Model was one such example of later synchronised
approaches
The society of co-operating experts were to be modelled by a basic
building block called an Actor
Actors could communicate with other Actors via messages
The behaviour of an actor was to be defined dependent upon which
message it received and these potential actions are contained in a Script
Actors could communicate with those actors with whom they were
acquainted as indicated by way of their acquaintance list
This model therefore offered point to point communication
© G.M.P O'Hare
School of Computer Science & Informatics
The Contract Net Protocol I
The Contract Net Approach regarded the distribution of tasks amongst
agents, or the connection problem as a process of negotiation.
Contract Net Protocol:-
A node(the manager) advertises a problem via a broadcast to all other
nodes(potential contractors). Potential contractors compare this and other
problems and upon identification of the tasks for which they are most
suited they submit bids. The manager evaluates bids and awards contract
accordingly
© G.M.P O'Hare
School of Computer Science & Informatics
Contract Net II
The communication protocol is vastly superior in that both manager
and potential contractor participate in the decision regarding a suitable
contract
It is also worth noting that here three addressing modes are offered:
general broadcast, limited broadcast and point to point.
This approach adopts an inter agent language which while simple
is capable of supporting the relevant communication.
© G.M.P O'Hare
School of Computer Science & Informatics
Beings
Lenat commissioned a very different approach when trying to overcome
problems of inter agent understanding.
In his PUP6 system an agent was represented by a 'Being' which had to
comply with a predefined structure.
It consisted of a fixed number of 'parts', each part representing a question
that the ks may be equipped to answer.
If a part contained a value then the being is sufficiently knowledgeable
with the value representing a procedural attachment which would yield
the appropriate answer.
When a being asks a question it must therefore stipulate the relevant part.
This approach made question answering relatively trivial - essentially
pattern matching. It avoided the need for an inter node language,
however in so doing it enforced a very stylised form on each agent
Furthermore there was no provision for gaining expertise.
© G.M.P O'Hare
School of Computer Science & Informatics
Hybrid Approaches
Hybrid Approaches
- Lesser and Corkill 1981
- Huhns et al 1983
© G.M.P O'Hare
School of Computer Science & Informatics
Benevolence & Competition
Within all of these approaches there is this underlying presumption
that the intelligent agents necessarily want to co-operate.
"The Benevolent Agent Assumption"
More recently a school of thought believes that this is not necessarily the
case and agents may have conflicting goals
This has resulted in ....
"The Conflicting Agents Assumption"
Geneserth and Rosenchien Stanford HPP Project
© G.M.P O'Hare
School of Computer Science & Informatics
Problems with DAI
• Identification of appropriate task decomposition
and task distribution strategies
• Optimisation of problem solution
(Cammarata et al 1982,1983)
• Difference of opinion between experts where the mapping between
expertise and experts is not 1: 1 but 1: n - need conflict resolution
strategies
• Problems with understanding
• Handling uncertainty becomes even more problematic
• Need deadlock avoidance strategies
• Problems with heterogenous nodes
• Interoperability
© G.M.P O'Hare
School of Computer Science & Informatics
Reactive v Classical Systems
Essentially Multi-Agent systems occupy a point on a continuum
between two extreme classes of system. These two extremes are...
• The classical system
• The reactive or situated action system
We propose a compromise that of the
'Deliberate Social Agent'
© G.M.P O'Hare
School of Computer Science & Informatics
Classical System
Contemplative
Reasoning
X
Deliberate Social System
X
Complexity
Reactive
Reactive
Situated Action System
X
Internal Model
Percieve the world
© G.M.P O'Hare
Represent the world
School of Computer Science & Informatics
Reactive or Situated Systems
Agents react to varying situations and consequently do not have
an explicit representation of the world within which they exist.
Reasoning takes place within each agent at a very low level, essentially
each agent has little more than an ability to perform pattern matching.
A given situation is characterised and matched against a collection of rules
specifying appropriate behaviour associated with each of these situations
ie situation -action or situated action.
Typically the actions associated with a given situation are often very
simple and consequently the agents themselves are very simple
computational entities.
Even though each of the individual agents are very simple
the global complexity and global structures can be achieved as a result of
the emergent property of the interacting behaviours of the community of
agents.
© G.M.P O'Hare
School of Computer Science & Informatics
Reactive Systems Assessment
Advantages
* simplicity.
* avoidance of necessity for a sophiciated representation of the world
and more significantly the problems of maintaining this model.
* generally the structure of agent interaction is well defined and
domain independent.
Disadvantages
* New sets of rules need to be designed for each application.
* Each situation needs to be specified and identified so as to have
an associated rule.
* Difficulty in solving inherently recursive problems.
* Lack of a precise theory upon which the combining
behaviours of agents can be based and explained.
© G.M.P O'Hare
School of Computer Science & Informatics
Reflective Systems
Generally the agents within a reflective system are more complex
computational entities.
They do not merely react to a given situation in a specific way. In fact they
may often react in different ways dependent on their own ‘beliefs’ or
‘intentions’.
Such systems necessitate an internal representation of the world. They often
base their reasoning on the actions of the other agents within the community.
They normally possess some model of intentionality which represents their
goals, desires, prejudices, beliefs etc. about themselves and the remainder
of the community.
Certain classes of problem seem to necessitate this ability to reason using
intentionality. The ‘wisest man’ puzzle seems to typify these.
© G.M.P O'Hare
School of Computer Science & Informatics
Reflective Systems II
Reasoning intentionally normally demands use of
higher order logics.
Particularly Modal logics.
- epistemic logics
- doxastic logics
There are two general approaches
 Sentential logics (Konolidge)
 Possible World Logics (Kripke)
© G.M.P O'Hare
School of Computer Science & Informatics
Deliberative Systems Assessment
Advantages
 A clear theoretical reasoning model that underpins
the approach;
A mental state that is verifiable and traceable;
Amenable to modeling using higher order logics;
Disadvantages
Theoretical Model is complex and unwieldy;
Approach is more computationally demanding;
Less appropriate for time critical reasoning scenarios;
Necessitates the maintenance of a model of the environment;
© G.M.P O'Hare
School of Computer Science & Informatics
The Cognitive Chasm
Exotic, Formal
Complex
Computationally
Intractable Logics
of Intention
Pragmatic, Shallow,
Simpistlic M ulti-agent
Implementation testbeds
with little conformance to
complex theoretical models
The 'cognitive chasm'
that this thesis is
seeking to bridge
© G.M.P O'Hare
School of Computer Science & Informatics