Multi-Agent Systems Lecture I
• Dr. Nestor Velasco Bermeo,
• Researcher CONSUS (Crop OptimisatioN through
Sensing, Understanding & viSualisation), • School of Computer Science
• University College Dublin (UCD)
Agenda
1. Introduction
2. Learning Outcomes
3. Student Effort Hours
4. Bibliography.
5. Origins and History of Artificial Intelligence.
Introduction to the course
• Module Coordinator: Professor Gregory O’Hare.
• Lecturer: Dr. Nestor Velasco Bermeo.
• Mode of Delivery: Blended.
• Course Notes: Brightspace [available as pdfs after each session]. • Examination: Final Exam Paper [2hrs End of Trimester]
• Sessions: Every Tuesday 14:00 – 15:50 hrs.
• Sessions will begin at 14:05, when joining and during the session it is recommended to mute your audio (unless an activity/question requires your participation).
*Sessions will not be recorded in order to promote attendance and participation.*
Learning Outcomes of the Module
1.Understand the key concepts that are associated with multi-agent systems, and its associated technologies and techniques.
2. Have an appreciation as to how to implement a simple agent system in an appropriate framework.
3 understand how the approach covered in the course relates to other approaches to implementing agent-oriented applications.
4 Understand the Belief Desire Intention (BDI) model for systems;
5.understand how agent technologies have been applied in various application domains.
Student Effort Hours
Student Effort Type Hours
Lectures 24 Autonomous Student Learning 100 Total 124
Recommended Bibliography
• M. Woolridge „An Introduction to Multi-Agent-Systems“, Wiley, 2001 •S. Russell, P. Norvig, „Artificial Intelligence: A Modern Approach“,
Prentice-Hall, 1995
•O’Hare, G. M., Jennings, N. R., & Jennings, N. (Eds.). (1996). Foundations of distributed artificial intelligence (Vol. 9). John Wiley & Sons.
* Additional Research articles and complimentary resources.
Topics to be covered
• Introduction
• History of A.I. and early efforts. • Agents and objects
• Agents and Expert Systems
• MultiAgent Systems
• What is Coordination or Cooperation?
• How cooperation occurs – The Prisoner’s Dilemma.
• Interactions between benevolent agents: cooperative distributed problem solving.
• Task and Result Sharing.
• Auctions and voting systems; negotiation.
• Commitments.
• Agent Management.
• Applications of Agent Systems.
• Intelligent Agents
• The design of intelligent
reasoning agents
agents
–
• Distributed Artificial Intelligence
•Theories of Agency (Weak vs Strong Agency)
• Reactive vs Intentional Systems • BDI
Lecture I: Origins and History of Artificial Intelligence
Lecture I Learning Objectives
❑ To understand the linage of AI:
❑ To understand where MAS sits within this
journey;
❑ To understand the principles around AI;
❑ To understand how MAS differentiates itself from traditional AI;
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 the form of a game….theTuring Test.
Born: June 23, 1912, Died: June 7, 1954, Wilmslow, United Kingdom
The Turing Test
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.
Can a computer pass for a human?
The Turing Test II
Turing’s work did not, however, win universal acceptance.
More recently opponents like Millar 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.
The Turing Test
“The isolated man does not develop any intellectual power. It is necessary for him to be immersed in an environment of other men, whose techniques he absorbs during the first twenty years of his life. He may then perhaps do a little research of his own and make a very few discoveries which are passed on to other men.”
― Alan Turing
Searle’s Chinese Room (1980)
• Strong AI Advocates believe:
• The appropriately programmed computer with the right inputs and outputs would thereby have a mind in exactly the same sense human beings have minds.
• Postulated by John Searle in his paper, “Minds, Brains, and Programs”, published in Behavioural and Brain Sciences in 1980. It was a thought experiment.
• A human enters a locked room but knows no Chinese (written or spoken).
• He is given a set of rules (in English) that define a mapping between sets of symbols (Chinese characters).
• These rules allow him to respond to inputs (written in Chinese) with outputs (also written in Chinese)…
• Does the machine literally “understand” Chinese? Or is it merely simulating the ability to understand Chinese?] Searle calls the first position
“strong AI” and the latter “weak AI”
The Turing Test (cont.)
If I may paraphrase Leonardo da Vinci (1452-1519), he in a similar vein suggested that………
“when man understands the natural flight of the bird,
man will be able to build a flying machine.”
A Working Definition
So with artificial intelligence, the definition we shall employ is that volunteered by Marvin Minsky
“Artificial intelligence is the science of making machines do things that would require intelligence if done by man.”
Learn, reason, -self-correct
Marvin Minsky
Born August 9, 1927, New York City, Died: January 24, 2016, Boston, Massachusetts
Useless Machine?
How it was Invented
Useless Machine operating
A Simple Example
AK27
“If there is a vowel on one side of a card then there will be an even number on the other side”
Which card(s) must be turned over in order
to determine whether or not the rule has been followed
Wason’s four-card problem
46%
33% Johnson-Laird & Wason, 1970
7%
4% *Other 10%
Which Cards should be turned? (If-then)
45 BE
89 RU
Inductive Reasoning vs Deductive Reasoning
Each card represents a person…
Drinks on one side Tea
Age on the other side 35
Let’s try Again…
Beer Water 25 16
“If a person is drinking alcohol, they must be 18 years or older”
Which card(s) must be turned over in order
to determine whether or not the rule has been followed
Knowledge Representation
*Wason’s four-card problem
A Short History of AI
• 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.
A Short History of AI
The History of AI 2
At the conference Newell & Simon detailed work on the theorem prover 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.
Inaugural AI Conference in 1956
Alan Newell & Herb Simon: Logic Theorist
•Proved 38 out of 52 theorems from Chapter 2 (The Theory of Logical Types) of Principia Mathematica.
• Based on logic
• Reasoning as Search (search spaces)
• Use of Heuristics
• Information Processing Language (IPL) – precursor to Lisp • Widely accepted as the first AI program…
You can find the paper in the following link (with the complete program included
The Logic Theory Machine. A Complex Information Processing System
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.
Expert Systems: SHRDLU 1968-70
•A program that understands a subset of English and can manipulate some wooden blocks.
•Implemented using Micro Planner (Carl Hewitt, 1969) & Lisp (McCarthy, 1958)
•Micro Planner (precursor to Prolog) provided a logical reasoning engine based on Resolution (Robinson, 1965)
•Lisp provided support for procedural code.
•Users interact with Shrdlu via a command line.
•Shrdlu parses the user input and responds appropriately.
•This can involve manipulating the blocks or responding to some user query…
Expert Systems: Shrdlu 1968-70
• Person: Pick up a big red block.
• Computer: OK.
• Person: Grasp the pyramid.
• Computer: I don’t understand which pyramid you mean.
• Person (changing their mind): Find a block which is taller than the one you are holding and put it into the box.
• Computer: By “it”, I assume you mean the block which is taller than the one I am holding.
• Computer: OK.
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.
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.
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.
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.