Transcript Slide 1

Introduction to Artificial
Intelligence
Filename: eie426-intro-0809.ppt
2015/7/22
EIE426-AICV
1
Contents

A typical definition of Artificial Intelligence (AI)

The Turing test

AI applications

Topics Covered by AI

Basic knowledge representation schemes

Basic problem solving paradigms

Brief history of AI

The State of the Art
2015/7/22
EIE426-AICV
2
What is AI?

The development of theories and techniques
required to provide a computational engine the
abilities to perceive, think and act, in an intelligent
matter, in a complex environment.
Systems that think like humans
Systems that think rationally
Systems that act like humans
Systems that act rationally
2015/7/22
EIE426-AICV
3
What is AI? (cont.)
Artificial Computer
psychology intelligence science and
engineering


2015/7/22
Engineering Goal: to solve real-world problems using AI
ideas about representing knowledge, using knowledge, and
assembling systems.
Scientific Goal: to determine which ideas about representing
knowledge, using knowledge, and assembling systems
explains various sorts of intelligence.
EIE426-AICV
4
The Turing Test



Computing machinery and intelligence, Turing 1950
“Can machines think?”  “Can machines behave
intelligently?”
Operational test for intelligent behavior: the Imitation Game
2015/7/22
EIE426-AICV
5
The Turing Test (cont.)
The Turing test measures the performance of an allegedly
intelligent machine against that of a human being.
Three important features of the test:
1. An objective notion of intelligence
2. Preventing us from being sidetracked by confusing and
currently unanswerable questions
3. Eliminating any bias in favor of living organisms
The problem: Turing test is not reproducible, constructive,
or amenable to mathematical analysis.
2015/7/22
EIE426-AICV
6
Some Turing Test Questions















“What is the meaning of life?”
“Why is the sky blue?”
“How are you?”
“Is OJ guilty?”
“Which came first, the chicken or the egg?”
“What word rhymes with Orange?”
“What is love?” and “How does love feel?”
“Boxers or briefs?”
“Who is your best friend?”
“Do you prefer open minds or only open preferred minds?”
“Please respond only when I say 'Simon Says'.”
“Do you think that I should undergo an operation to remove my brain and
install a computer in my head?”
“Tell me about your childhood.”
“How are you feeling today?”
“When were you born?”
2015/7/22
EIE426-AICV
7
AI Applications
Mundane Tasks




2015/7/22
Perception
 Vision
 Speech
Natural language
 Understanding
 Generation
 Translation
Commonsense reasoning
Robot control (http://www.cs.rochester.edu/u/jag/demos/demos.html)
EIE426-AICV
demo
8
AI Applications (cont.)
Formal Tasks


Games
 Chess
 Backgammon
 Checkers
 Go
Mathematics
 Geometry
 Logic
 Integral calculus
 Proving properties of programs
2015/7/22
EIE426-AICV
9
AI Applications (cont.)
Expert Tasks




2015/7/22
Engineering
 Design
 Fault finding
 Manufacturing planning
Scientific analysis
Medical diagnosis
Financial analysis
EIE426-AICV
10
Example: Airport Resource Information System
Arrange gates for flights considering the seat capacity, time to take
off, connected flights, weather condition, emergent factors, etc.
2015/7/22
EIE426-AICV
11
Topics Covered by AI











search and game-playing (√)
logical systems
knowledge (expert) systems (√)
planning systems (√)
uncertainty - probability and decision theory
machine learning (√)
computational intelligence
- artificial neural networks (ANN’s)
- fuzzy systems (FS’s), and
- evolutionary algorithms (EA’s) (√)
natural language processing (NLP) (√)
perception (√)
robotics (√)
philosophical issues (√)
√: to be taught
2015/7/22
EIE426-AICV
12
Relationships among various topics
Knowledge
Representation
Logic
Search
Machine
Learning
NLP
2015/7/22
Vision
Planning
Robotics
EIE426-AICV
Expert
Systems
13
Knowledge Representation
A representation is a set of conventions about how to
describe a class of things. A description makes use of the
conventions of a representation to describe some particular
thing.
Representation Techniques:



2015/7/22
Semantics nets (a subset: frames) √
Predicate logic
Production rules √
EIE426-AICV
14
Example: The Farmer, Fox, Goose, and Grain
A farmer wants to move himself, a silver fox, a fat goose, and
some tasty grain across a river. Unfortunately, his boat is so
tiny he can take only one of his possessions across on any
trip. Worse yet, an unattended fox will eat a goose, and an
unattended goose will eat grain, so the farmer must not leave
the fox alone with the goose or the goose alone with the grain.
How can he do?
2015/7/22
EIE426-AICV
15
Example: The Farmer, Fox, Goose, and Grain (cont.)
2015/7/22
EIE426-AICV
16
Powerful Idea:
Once a problem is described using an appropriate
representation, the problem is almost solved.
A Representation has Four Fundamental Parts:




2015/7/22
A lexical part - vocabulary
A structural part - constraints
A procedural part - access procedures
A semantic part - meaning
EIE426-AICV
17
Semantic Nets
A semantic net is a representation
In which

Lexically, there are nodes, links, and application-specific link labels.

Structurally, each link connects a tail node to a head node.

Semantically, the nodes and links denote application-specific entities.
With constructors that

Construct a node

Construct a link, given a link label and two nodes to be connected
With readers that

Produce a list of all links departing from a given node

Produce a list of all links arriving at a given node

Produce a tail node, given a link

Produce a head node, given a link

Produce a link label, given a link
2015/7/22
EIE426-AICV
18
Semantic Nets – Different Froms
To be taught
2015/7/22
EIE426-AICV
19
Problem Solving Paradigms

Describe and match √

Generate and test √

Means-ends analysis √

Problem-reduction √

Search √


Rule-based systems √
Predicate calculus
2015/7/22
EIE426-AICV
20
The Describe-And-Match Method
To identify an object using describe and match,

Describe the object using a suitable representation.

Match the object description against library descriptions until there
is a satisfactory match or there are no more library descriptions.

If you find a satisfactory match, announce it; otherwise, announce
failure.
2015/7/22
EIE426-AICV
21
Feature-Based Object Identification
2015/7/22
EIE426-AICV
22
Generate-And-Test
2015/7/22
EIE426-AICV
23
Generate-And-Test (cont.)
2015/7/22
EIE426-AICV
24
The Generate-And-Test Method
To perform generate and test,
 Until a satisfactory solution is found or no more candidate
solutions can be generated,
 Generate a candidate solution.
 Test the candidate solution.
 If an acceptable solution is found, announce it; otherwise,
announce failure.
Three properties for a good generator: complete,
nonredundant, informed.
2015/7/22
EIE426-AICV
25
The Means-Ends Analysis Method
A state space is a representation
That is a semantic net
in which
 The nodes denote states.
 The links denote transitions between states.
2015/7/22
EIE426-AICV
26
Current
state
2015/7/22
EIE426-AICV
27
Algorithm: Means-Ends Analysis
(Simple version)
To perform means-ends analysis,
 Until the goal is reached or no more procedures are available,
 Describe the current state, the goal state, and the difference
between the two.
 Use the difference between the current state and goal state,
possibly with the description of the current state or goal state, to
select a promising procedure.
 Use the promising procedure and update the current state.
 If the goal is reached, announce success; otherwise, announce failure.
Key idea is to reduce difference between the current state
and the goal state.
2015/7/22
EIE426-AICV
28
The Task:
A robot moves a desk with two things on it from one
room to another.
2015/7/22
EIE426-AICV
29
A Robot’s Operators
Operator
Preconditions
Results
PUSH(obj, loc)
at(robot,obj)^
large(obj)^
clear(obj)^
armempty
at(robot,obj) ^
at(obj, loc)^
at(robot, loc)
CARRY(obj, loc)
small(obj)
at(obj, loc)^
at(robot, loc)
WALK(loc)
PICKUP(obj)
none
at(robot, obj)
at(robot, loc)
holding(obj)
PUTDOWN(obj)
holding(obj)
 holding(obj)
PLACE(obj1, obj2)
at(robot, obj2)^
holding(obj1)
2015/7/22
EIE426-AICV
on(obj1, obj2)
30
A Difference Table
Operators
differences
2015/7/22
EIE426-AICV
31
The Progress of the Means-Ends Analysis Method
2015/7/22
EIE426-AICV
32
Algorithm: Means-Ends Analysis
(Advanced Version)
1
2
2015/7/22
Compare CURRENT to GOAL. If there are no differences between
them then return.
Otherwise, select the most important difference and reduce it by
doing the following until success or failure is signaled:
(a) Select an as yet untried operator O that is applicable to the
current difference. If there are no such operators, then signal
failure.
(b)Attempt to apply O to CURRENT. Generate descriptions of two
states: O-START, a state which O’s preconditions are satisfied
and O-RESULT, the state that would result if O were applied in
O-START.
(c)If
(FIRST-PART
MEA(CURRENT, O-START)) and
(LAST-PART
MEA(O-RESULT, GOAL))
are successful, then signal success and return the result of
concatenating
FIRST-PART, O, and LAST-PART.
EIE426-AICV
33
The Problem-Reduction (Goal Reduction) Method
2015/7/22
EIE426-AICV
34
A Decomposable Problem
2015/7/22
EIE426-AICV
35
Problem-Solving Methods Often Work
Together
PolyU
Bejing U
PolyU
HK Airport
HK Airport
Bejing Airport
Walk Taxi
Bejing Airport
Train
Means-ends analysis
Bejing U
Problem reduction
2015/7/22
EIE426-AICV
36
AI Prehistory
Philosophy
logic, methods of reasoning, mind as
physical system, foundations of learning,
language, rationality
Mathematics
formal representation and proof algorithms,
computation, (un)decidability, (in)tractability,
probability
Psychology
adaptation, phenomena of perception and
motor control, experimental techniques
Linguistics
knowledge representation, grammar
Neuroscience
physical substrate for mental activity
Control theory stability, simple optimal agent designs
2015/7/22
EIE426-AICV
37
History of AI
Timeline of major AI events
2015/7/22
EIE426-AICV
38
The State of the Art







2015/7/22
Autonomous planning and scheduling: NASA’s Remote Agent
Game playing: IBM’s Deep Blue
Autonomous control: the ALVINN computer vision system, to
steer a car to keep it following a lane (2850 miles, 98% of the time)
Medical diagnosis
Logistics planning: DRAT (Dynamic Analysis and Replanning
Tool)
Robotics: HipNav (a system that uses computer vision techniques
to create a 3-D model of a patient’s internal anatomy and then uses
robotic control to guide the insertion of a hip replacement
prosthesis.
Language understanding and problem solving: PROVERB (a
computer program that solves crossword puzzles better than most
humans)
EIE426-AICV
39