Transcript LOGIC PROGRAMMING - University College Dublin

University College Dublin
DEPARTMENT OF COMPUTER SCIENCE
Robotics Part I & II
Multi-Agent Systems(MAS)
G.M.P. O'Hare
© G.M.P O'Hare
Department of Computer Science
The Turing Test
Allan Turing [5] in his classic paper ‘Computing Machinery and
Intelligence’, circumvented the problem of defining artificial
intelligence. Such a test took for form of a game.
The game he describes has three participants, an interrogator, a
human and a machine. The interrogator is physically removed from
the other two participants. He can communicate with each of them
by way of a teletype, he does not however, know which participant
is machine and which is human.
His task is to establish which one is the machine and which is the
human. This became renowned as the ‘Turing Test’.
A computer could be thought to display intelligence
if the interrogator could not distinguish between man and computer.
© G.M.P O'Hare
Department of Computer Science
The Turing Test II
Turing’s work did not, however, win universal acceptance.
More recently opponents like Millar [6] while recognising the
merits of his work highlights the fact that it does not yield any
insight into the various skills which constitute intelligence.
He believed this to be of great significance if any realistic
attempt is to be made at constructing a truly intelligent
machine.
If I may paraphrase Leonardo de Vinci (1452-1519), he in a
similar vein suggested that.........
“when man understands thenatural flight of the bird,
man will be able to build a flying machine.”
© G.M.P O'Hare
Department of Computer Science
A Working Definition
So with artificial intelligence, the definition we shall employ
is that volunteered by Marvin Minsky [7]
“Artificial intelligence is the science of making machines do
things that would require intelligence if done by man.”
© G.M.P O'Hare
Department of Computer Science
A Simple Example
E
4
F
7
"If there is a vowel on one side of a card then
there will be an even number on the other"
How many cards must you turn over in order
to test the validity of this statement?
© G.M.P O'Hare
Department of Computer Science
Another Simple Example
1
8
2
6
7
4
5
9
3
Players alternatively choose a card
until they select three cards in total
The Object of the Game is to obtain a total of 15 and ensuring
your opponent does not acquire a total of 15.
What strategy would you adopt?
© G.M.P O'Hare
Department of Computer Science
The History of AI 1
The term Artificial Intelligence is normally attributed
to John McCarthy.
In 1956 he organised a conference which was to enable
researchers in the field to share expertise.
As a consequence of his actions the discipline of AI
was founded.
Some attendees namely, Allan Newell, Herbert Simon
and Marvin Minsky himself, are now without question
the leading researchers in the field.
© G.M.P O'Hare
Department of Computer Science
The History of AI 2
At the conference Newell & Simon detailed work on the
theorem prover Logic Theorist which had been performed at
Carnegie.
This is commonly regarded as the first AI program as such.
The Logic Theorist was written in IPL (Information Processing
Language) the first language which permitted computers to
process concepts as opposed to numerical quantities.
© G.M.P O'Hare
Department of Computer Science
The History of AI 3
Minsky & McCarthy founded the MIT AI Laboratory.
McCarthy is renowned as the inventor of LISP while Minsky
proposed the Frame concept for Knowledge Representation.
In this early stage efforts tended to concentrate on:
Game Playing: equipping a computer to play a
particular game.
Theorem Proving: equipping a computer to show that
some statement follows logically from a set of
known truths called axioms.
© G.M.P O'Hare
Department of Computer Science
The History of AI 4
Early efforts employed a technique known as State Space Search
involving essentially several components ...
(a) an initial stage
(b) a final state
(c) an ability to detect final state
(d) a set of legal operations that can be applied to each state.
Such an approach can often be understood better by conceptually
regarding states as nodes and operations as arcs.
© G.M.P O'Hare
Department of Computer Science
The History of AI 5
By way of example in a chess game:
(a) initial state: initial state of chess board.
(b) final state: checkmate.
(c) ability to detect final state: ability to detect checkmate.
(d) set of legal operations: legal moves of chess.
© G.M.P O'Hare
Department of Computer Science
Generate & Test 1
The simplest form of state space search is that of Generate & Test.
Such an approach involves typically three stages, those of ...
(a) Generating a possible solution in the form of a new state.
(b) Ascertaining whether the new state is indeed the final state.
(c) If new state is the final state terminate, otherwise
repeat steps a, b and c.
© G.M.P O'Hare
Department of Computer Science
Generate & Test 2
Two forms of generate and test exist: Depth-first Search &
Breadth-first Search.
Both fall foul of the ‘combinatorial explosion’, caused by the
exponential growth of the nodes irrespective of the order of
generation.
Consequently exhaustive search is only feasible when the search
space is very small.
For larger spaces the search needs to be guided.
Guided searches are normally referred to as Heuristic Searches.
Searches of this nature utilise domain specific knowledge
called heuristics.
© G.M.P O'Hare
Department of Computer Science
Guided Searches
Guided searches are normally referred to as:
Heuristic Searches.
Searches of this nature utilise:
domain specific knowledge called heuristics.
© G.M.P O'Hare
Department of Computer Science
Exercise 1
Attempt to draw a state space for the famous
missionaries and cannibals problem
© G.M.P O'Hare
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
Hybrid Approaches
Hybrid Approaches
- Lesser and Corkill 1981
- Huhns et al 1983
© G.M.P O'Hare
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
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
Department of Computer Science
Agents & The Notion of Agency
The term agent is somewhat nebulous and means different things
to disparate research communities within Computer Science.
I use this terminology in the manner associated with the
Distributed Artificial Intelligence (DAI) community, namely
that agents are characterised by the attributes of autonomy;
social ability; reactivity and pro-activity.
In addition a stronger notion of agency is often applied which
demands that agents are ascribed mentalistic attitudes typically
knowledge; belief; intention and obligation.
Wooldridge & Jennings (1995) distinguish between two usages
of the term 'agent': the first is 'weak'; the second is
stronger and potentially more contentious.
© G.M.P O'Hare
Department of Computer Science
The Weak Notion of Agency
The Weak notion of agency refers to the general way in which
the term agent is used to denote software (usually) or harwarebased computer systems that has the following properties:
autonomy: agents operate without direct intervention with
control over their actions and internal state;
social ability: agents interact with other agents and possibly
humans via an agent-communication language;
reactivity: agents perceive their environment and respond
to changes that occur within it in a timely fashion;
pro-activeness: agents do not simply respond to their
environment, they are able to exhibit goal-directed
behaviour (initiative).
© G.M.P O'Hare
Department of Computer Science
The Stronger Notion of Agency
Within AI research, agency generally implies that in
addition to the properties already outlined an agent is
either conceptualised or implemented using concepts
more usually applied to humans.
These properties include:
mentalistic notions of belief, knowledge, intention
and obligation.
© G.M.P O'Hare
Department of Computer Science
Other Attributes of Agency
Other attributes discussed in the context of agency include:
mobility: the ability to move around an electronic network;
veracity: the assumption that an agent will not knowingly
communicate false information;
benevolence: is the assumption that agents do not have
conflicting goals and that every agent will try and do what
is asked of it.
rationality: in a crude sense the assumption an agent will act
in order to achieve its goals, and will not act in such a way as to
prevent its goals being achieved.
© G.M.P O'Hare
Department of Computer Science
Definition of an Agent
Agents are often physically and logically distinct and are
typically capable of reasoning, planning, communicating
and cooperating (Hern 1988).
They may be robotic, be defined in terms of sensory input,
motor control and time pressures, they may perform cognitive
functions, react to stimuli, contain symbolic plans, or possess
natural language capabilities.
Shoham (1993):“An agent is an entity whose state is viewed as
consisting of mental components such as beliefs, capabilities,
choices, and commitments.”
© G.M.P O'Hare
Department of Computer Science
Belief Desire Intention
Architectures
One particular Architecture that has been employed in the
development of Reflective Systems is that of the Belief
Desire Intention (BDI) Architecture.
The term BDI is attributed to Rao and Georgeff (1992).
The architecture models the reflective process in terms of the
interplay between these three mental attitudes.
© G.M.P O'Hare
Department of Computer Science
Beliefs, Desires and Intentions
Let us consider these three mental attitudes:Belief : represents the information state of the agent,
those things it believes to be true at a given
instance;
Desire: represents the evaluative state of the agent
that is those things that the agent at a
given instance desires to bring about;
Intentions: represents those activities which the agent has
decided at some previous time are crucial
in achieving its goals in an adequate
or optimum manner;
© G.M.P O'Hare
Department of Computer Science
Early DAI Environments
 ABE (Erman et al 1988)
 ARCHON (Wittig 1989)
 CooperA (Sommaruga et al 1989)
 MACE (Gasser et al 1987)
 MADE (Wooldridge & O'Hare 1990)
 Agent Factory (O'Hare 1992)
 MCS (Doran et al 1991)
 GBB (Hayes-Roth et al 1988)
© G.M.P O'Hare
Department of Computer Science
Classes of Commitment
Elsewhere in the literature [RG92] it is recognised that varying
degrees of commitment may be exhibited by agents.
Rao and Georgeff [RG91], [RG92] identify three discrete points
on this commitment continuum, namely:
 Blind Commitment,
 Single-Minded Commitment and
 Open-Minded Commitment.
© G.M.P O'Hare
Department of Computer Science
Blind Commitment
Blind commitment is defined as the adherence
to a commitment until such time as the agent believes
it has achieved the commitment.
© G.M.P O'Hare
Department of Computer Science
Single-Minded Commitment
Single-minded commitment represents a relaxation of
blind commitment in that the agent will not drop its
commitments unless it believes that they are no longer
achievable.
The computational overhead of assertaining whether a
given goal is achievable can be considerable.
Rao and Georgeff suggest that this can be achieved by
permitting belief revision but not goal revision.
© G.M.P O'Hare
Department of Computer Science
Open-Minded Commitment
Open-minded commitment offers a further relaxation
in that an agent is willing to revise its goals and beliefs,
retaining commitments that are still compatable with its goals.
© G.M.P O'Hare
Department of Computer Science
Communication within DAI
Communication is central to the development of any
satisfactory Multi-Agent System. Effective communication
is a prerequisite for achieving system coordination and
system coherence.
Werner [Wer89] has identified several discrete classes of
communication that occurs within Multi-Agent Systems.
These are:1. Complete abscence of communication;
2. Inter-Agent Signalling;
3. Message Passing;
4. Plan Passing;
5. Speech Acts;
© G.M.P O'Hare
Department of Computer Science
Coordination
Coordination represents the problem or activity of
reconciling the actions of the individual agent with
those of the group or indeed organisation.
Since agents actions are derived from their goals and since
agents are frequently benevolant their will inevitably be
conflict.
Such interference can only be reconciled through
communication.
© G.M.P O'Hare
Department of Computer Science
Coherence
System coherence involves ensuring that the overall
system performance is satisfactory
© G.M.P O'Hare
Department of Computer Science
Absence of Communication
Sometimes communities of agents can achieve coherent
behaviour without explicit communication.
Geneserth Ginsberg & Rosenchein [GGR84] considered
this very issue in a seminal paper entitled Cooperation
without Communication.
Agents might have a prearranged regime for achieving their
goals and this is established a priori thus avoiding any need
for dynamic communication.
Alternatively they may infer each others plans based on
observations to date. This results in a prediction of agents'
behaviour [Ros85].
© G.M.P O'Hare
Department of Computer Science
Agent Signalling
Inter-Agent activity can be sychronised through the
use of semaphore based technologies.
Semaphores offer a relatively simplistic communication
technique.
They utilise the standard, primitives of wait and signal and
are directly analogous to those techniques used within the
design of real-time languages and systems
© G.M.P O'Hare
Department of Computer Science
Message Passing
Another very common means of inter-agent communication
is that of message passing.
Early work by Hewitt & Agha formulated a computational
paradigm based upon actor-based computation. Central to
this was the notion of message passing.
Message passing generally manifests itsself in many DAI
systems.
© G.M.P O'Hare
Department of Computer Science
Plan Passing
This approach involves agents exchanging plans to one another.
By so doing agents can anticipate the future directed actions of
other agents.
One particular approach involves the exchange of Partial Plans.
This approach called Partial Global Planning (PGP)
was expounded by Durfee and Lesser. Within PGP agents build
partial and incomplete plans which they subsequently share to
colleagues in order to identify potential improvements.
This approach unlike for example multi-agent planning allows
agents to interleave planning and actions. Thus based upon
future plans received agents can revise their plans and
subsequently perform actions based upon this. PGP
was employed with great effect in the DVMT system.
© G.M.P O'Hare
Department of Computer Science
Essence of Speech Acts
The origins of Speech Act Theory can be traced to the
work of Austin [Aus62].
Two central characteristics associated with the basic
theory of Speech Acts are:1. That human utterances are viewed as actions in a
manner similar to physical operations that result in
the movement of a book for example. They too result in a
change in the state of the world.
2. That communication can be homogenised into a finite set
of Speech Verbs that can be used to as an effective medium
within which to communicate.
© G.M.P O'Hare
Department of Computer Science
Speech Acts and State Change
It is not immediately obvious how Speech Acts result in a
change to the environment.
All utterances are viewed as being situated within a particular
context and each results in a revision to that very context.
The context is often viewed as the aggredation of the mental
states of the participants namely the speaker and the hearer.
Such a mental state includes their Beliefs, Desires and Intentions.
© G.M.P O'Hare
Department of Computer Science
A Pragmmatic Theory of Speech
We can thus view a pragmatic theory of speech as a function
which takes a set of all utterances of a given language lets say L
and an associated set of Contexts within which these can be
expressed lets say C and derives the new context.
Thus
Speech_Function : L x C -> C
© G.M.P O'Hare
Department of Computer Science
Speech Act Actions
Austin also identified three discrete classes of action associated
with any given utterance:-
• Locutionary Acts :- which is performed by simply uttering a
syntactically correct phrase;
• Illocutionary Acts :- which is performed via a performative
verb examples include tell, inform, ask,
instruct, demand. Each verb has an
associated illocutionary force. Austin
identified some 1,000 such verbs in
English;
• Perlocutionary Acts:- is the bringing about of an effect on the
hearer of the utterance;
Speech acts generally refer to the illocutionary act.
© G.M.P O'Hare
Department of Computer Science
Speech Acts and Austin
Austin noted that certain utterances involved not merely the
assertain of facts but rather the performance of associated
action(s). These utterances are termed performatives and he
noted that these like physical actions are prone to failure.
The conditions that must exist for sucessful completion were
called felicity conditions. Three key conditions are:1. There must be an accepted procedure for the performative
and the circumstances and individuals must be specified for
this procedure.
2. This procedure must be executed correctly and completely.
3. The act must be performed in a sincere manner and any
associated or implied behaviour honoured.
© G.M.P O'Hare
Department of Computer Science
A DAI Textbook
Foundations of Distributed Artificial Intelligence,
O'Hare, G.M.P., and Jennings, N.R., (Eds.),
Wiley Interscience, 1996, ISBN 0-471-00675-0.
597 pages
Available Now
© G.M.P O'Hare
Department of Computer Science