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)
Lecture I: Origins and History of Artificial Intelligence
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.
Exercise 1
Attempt to draw a state space for the famous Missionaries and Cannibals problem
On one bank of a river are three missionaries and three cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.
How can the boat be used to safely carry all the missionaries and cannibals across the river?
State Space
The Development of Expert Systems
• Stanford Professor, Terry Winograd developed the Shrdlu expert system which was able to understand a subset of English an manipulate wooden blocks.
• Soon after came numerous other systems targeting a diversity of domains.
• Researchers became aware that the representation of knowledge was central to achieving a truly intelligent system.
• Thereafter numerous formalisms were proposed.
The History of AI Research
• In 1973 a report by Sir James Lighthill concluded that AI work within the UK was unproductive. There ensued a removal of government funding. Referred to as the AI Winter.
• Consequently the US and Japan dominated AI research for a period gaining predominance .
• In later years expert systems emerged which offer a high level of performance in complex domains.
Examples include XCON & MECHO.
• R1/XCON delivered the first commercial return on AI by 1986 delivering circa $40 Million per annum.
The History of AI Research
• In 1987 Deep Blue defeats Gary Kasparov world chess champion.
• IBM shares soar in value. Regarded as a coming of age for AI.
• In 2011 IBM’s Watson* challenged humans on a Quiz show entitled Jeopardy. But not any contestants the two best all time performers on the show.
• IBM Watson, has consumed “600,000 pieces of medical evidence, more than two million pages from medical journals and the further ability to search through up to 1.5 million patient records”
AI Timeline
Can Computers Think?
•Throughout the evolution of artificial intelligence there have been many opponents to the whole concept of machines generating anything original.
•Turing identified many of these objections:
•Mathematical objection: based on Godel’s theorem claims limitations to the power of artificial systems.
•Lady Lovelace’s objection: claims that a computer can only do what it is told and thus it cannot have pretentions to originate
•Theological objection: suggests only the possession of a soul permits thought, hence machine nor animals can think anything (derived intentionality).
Can Computers Think?
Other Objections:
•Arithmetic Machine objection: a computer is little more than a fast arithmetic machine. Of course a computer can achieve more than merely arithmetic operations: SHIFT, READ, COMPARE, LOAD etc.
•Informality of Behaviour objection: impossible to detail set of rules which indicate how a person should act in all possible situations.
•Sensory Perception objection: humans have senses not available to machines sight, touch, smell, ESP.
•Head in the Sand objection: too horrendous even to contemplate that computers could think.
Contradicting the Objections
Numerous examples, however, may be cited to contradict this. ❑ Samuels checker program, primitive learning capacity
❑ Lenat’s Automated Mathematician, which identified new maximally divisible numbers not considered by most mathematicians.
❑ Prospector , which was claimed to be in error in certain circumstances, but was eventually proven to be right.
Thought, origin of new knowledge.
Consider a computer is given the following pieces of knowledge:
Elephants are large and grey… Clyde is an elephant.
Conceptually we can think of this knowledge as a graph. If in addition we armed the computer with the technique:
properties may be inherited following the directed arcs.
Hence it could conclude a new item of knowledge
Clyde is Large and Grey
Is this equivalent to thought? The computer only used techniques we equipped it with,
but after all we only use skills we acquire from our environment.
Can a computer exhibit emotions or indeed have morals?
Isaac Asimov: The Three Laws of Robotics
The Trolley Problem
Self Driving cars
Things to Do!
• Watch Marvin Minsky Interview:
INFINITE HISTORY PROJECT MIT
Marvin Minsky Interviewed by John Hockenberry
• Read Franklin, S., & Graesser, A. (1996, August). Is it an Agent, or just a Program?: A Taxonomy for Autonomous Agents. In International Workshop on Agent Theories, Architectures, and Languages (pp. 21-35). Springer, Berlin, Heidelberg.
Things to Do!
•Johnson-Laird, P.N. (1983).
Mental Models: Towards a Cognitive Science of Language, Inference, and Consciousness. Cambridge: Cambridge University Press.4
•Johnson-Laird, P.N. (2006) How We Reason. Oxford University Press.
•Watch The Social Dilemma Of Driverless Cars https://youtu.be/nhCh1pBsS80
Lecture I Learning Objectives (recap)
❑ 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;
Additional Resources
• SHRDLU
• https://hci.stanford.edu/winograd/shrdlu/
• https://www.youtube.com/watch?v=bo4R vYJYOzI
• History of AI
• http://sitn.hms.harvard.edu/flash/2017/hi
story-artificial-intelligence/
• https://www.bbc.com/timelines/zq376fr
• Joseph Weizenbaum’s ELIZA
• https://www.masswerk.at/elizabot/
• https://www.youtube.com/watch?v=RMK 9AphfLco
• AIVA (Artificial Intelligence Virtual Artist)
• https://www.youtube.com/watch?v=gzGk
C_o9hXI
• IBM Watson for Oncology
• https://www.ibm.com/us- en/marketplace/clinical-decision-support- oncology
• Timeline of AI Art
• https://aiartists.org/ai-timeline-art
• Self-driving cars and the trolley problem
• https://www.youtube.com/watch?v=9nV3
kQRP5eg
• A.L.I.C.E. (Artificial Linguistic Internet• Ex-Machina (2014) Computer Entity)
• https://www.pandorabots.com/pandora/ta lk?botid=b8d616e35e36e881