MET CS 664

Artificial Intelligence
Module1 – Introduction to AI
Introduction to Artificial Intelligence

Outline

I. What is AI?

II. A brief history

III. The state of the art

I. What Is Intelligence?
A wish-list of general characteristics of intelligence

• Perception: manipulation & interpretation of data provided by sensors

• Action: control and use of effectors to accomplish a variety of tasks

• Reasoning: deductive (logical) inference, inductive inference

• Learning: adapting behavior to better cope with changing environments,

discovery of patterns, learning to reason, plan, and act.

• Communication: with other intelligent agents including humans using

signals, signs, icons, …

• Planning: formulation of plans -- sequences or agenda of actions to

accomplish externally or internally determined goals
What is AI?

Thinking Humanly Thinking Rationally

“The exciting new effort to make computers “The study of mental faculties through the use of
think … machines with minds, in the full computational models.” (Charniak and McDermott, 1985)
and literal sense.” (Haugeland, 1985)

“[The automation of] activities that we “The study of computations that make it possible to
associate with human thinking, activities perceive, reason, and act.” (Winston, 1992)
such as decision-making, problem solving,
learning ....” (Bellman, 1978)

Acting Humanly Acting Rationally

“The art of creating machines that perform “Computational Intelligence is the study of the design
functions that require intelligence when of intelligent agents.” (Poole et al, 1998)
performed by people.” (Kurzweil, 1990)

“The study of how to make computers do “AI … is concerned with intelligent behavior in artifacts.”
things at which, at the moment, people are (Nilsson, 1998)
better.” (Rich and Knight, 1991)
 Acting Humanly: Turing Test
Alan Turing (1950) : operational definition of intelligence

• A human interrogator poses some

written questions to another human
and a computer (or “robot”).

• The computer passes the test if

the interrogator cannot tell whether
the written responses come from
the human responder or the
computer.

Human respondent Human interrogator Robot

Annual Loebner prize competition (since 1990): the first prize of $100,000 to be awarded to
the first program that passes the "unrestricted" Turing test.

* Illustration art from [Link]

Six Disciplines of AI
To pass the Turing test, the following capabilities are required:

¨Natural language processing to communicate in a human language;

¨Knowledge representation to store what it knows;

¨Automated reasoning to answer questions and draw new conclusions;

¨Machine learning to adapt to new circumstances and to detect patterns.

Total Turing test requires interaction with the real world.

¨Computer vision & speech recognition to perceive the world;

¨Robotics to move around in the world and to manipulate objects.

Thinking Humanly: Cognitive Modeling

To say a program thinks like a human, we must know humans think first.

Learn about human thought in three ways:

• introspection – catching thoughts as they go by;

• psychological experiments – observing a person in action;

• brain imaging – observing brain activities.

General problem solver (GPS) by Newell & Simon (1961)

Also compares reasoning steps to those in the human solution.

Cognitive science constructs theories of the human mind by combining

¨ computer models from AI
¨ experimental techniques from psychology
Thinking Rationally: “Laws of Thought”

Represent problems using logic and build programs to create intelligent

systems.

Drawbacks:

§ Not easy to state informal (and often uncertain) knowledge in the

formal logical notation.

§ Big difference between solving a problem “in principle” and solving

it in practices.
Acting Rationally: Rational Agent
This course is about designing rational agents.

Rational behavior: doing the right thing

expected to maximize goal achievement,

given the available information

• An agent is an entity that perceives and acts.

• A rational agent is one that acts to achieve the best outcome.

II. Brief History of AI

• 1943 McCulloh & Pitts: model of artificial neurons

• 1950 Turing’s “Computing Machinery and Intelligence”

• 1956 McCarthy, Minsky, Newell, Simon, Shannon, Nash et al.

Dartmouth workshop: birth of “Artificial Intelligence”

• 1952-69 Early enthusiasm, great expectations, optimism fueled by

early success on some problems thought to be hard

• 1966-73 Collapse in AI research: Progress was slower than expected.

Unrealistic predictions, Herbert Simon (1957)
AI discovers computational complexity.
Brief History of AI (cont’d)

• 1969-86 Expert systems

• 1980- AI becomes an industry: expert systems booms, then

busts (1988-93): AI Winter”

• 1986- Neural networks regain popularity

• 1987- Probabilistic reasoning and machine learning

Brief History of AI (cont’d)

• 1995- Emergence of intelligent agents

§ AI technologies continue to find applications in
¨ information retrieval
¨ data mining and knowledge discovery
¨ customizable software systems
¨ smart devices (e.g., home, automobiles)
¨ agile manufacturing systems

¨ autonomous vehicles

¨ bioinformatics

¨ internet tools: search engines, recommender systems

¨…

§ Steady progress on fundamental AI research problems continues.

Brief History of AI (cont’d)

• 2001- Big data

e.g., ImageNet

• 2011- Deep learning

§ Successful large-scale real-world applications in

¨ image recognition
¨ natural language processing
¨ speech recognition
¨ machine translation

¨…

§ Convolutional neural networks (CNNs)

2021's Top Stories About AI - IEEE Spectrum

“2021 was the year in which the wonders of artificial intelligence stopped being a story.”
Turing Award Winners in AI
1969 Marvin Minsky (MIT)

1971 John McCarthy (Stanford)

National Medal of Science (1990)

1975 Allen Newell (Carnegie Mellon) Founders of AI

National Medal of Science (1992)

Herbert Simon (Carnegie Mellon)

Nobel Prize in Economics (1978)
National Medal of Science (1986)

1994 Edward Feigenbaum (Stanford)

Raj Reddy (Carnegie Mellon)
2011 Judea Pearl (UCLA)
2018 Yoshua Bengio (U Montreal)
Geoffrey Hinton (U Toronto)
Yann Lecun (NYU & Facebook)
 Solomon Lefschetz

Academic Genealogy Albert Tucker

Herbert Simon John McCarthy Marvin Minsky

Allen Newell Edward Feigenbaum Raj Reddy

* All the photos are from [Link]

III. The State of the Art
• Game playing

¨ Chinook defeated human checkers champions (1994).

¨ Deep Blue (IBM) defeated the reigning world chess champion Garry
Kasparov (1997).

¨ Supercomputer Watson (IBM) beat human champions on “Jeopardy” (2011).

¨ AlphaGo (Google) beat the world’s No.1 ranking player Ke Jie in Go (2017).

¨ Libratus (Carnegie Mellon) defeated the world’s best Texas Hold ‘em poker
players head-to-head (2017), six-player (2019).

¨ “AlphaStar” AI (Google) defeated human pros at StarCraft II (2019)

(cont’d)
• Robotic vehicles
¨ Stanley (Stanford) won the DARPA Grand Challenge (2005)
¨ Boss (Carnegie Mellon) won the DARPA’s Urban Challenge (2007)

¨ Self-driving cars by Tesla, Google, etc.

Stanley Boss Google car Tesla car crash

Florida, 2016
• Legged robots (Boston Dynamics)

SpotMini Atlas Handle

(cont’d)
• Autonomous planning

¨ NASA’s Remote Agent program controlled the scheduling of operations for

a space craft (2000).

¨ Uber and Google Maps plan optimal routes for hundreds of millions of users.

• Speech recognition

¨ Flight booking via conversation with an automated system

¨ Real-time speech-to-speech translation

• Image understanding

¨ ImageNet object recognition

Extensive use of convolutional
neural networks (CNNs)
¨ Image captioning
Intelligent Agents

Outline

I. Agents and rational behavior

II. The nature of environments

III. The structure of agents

 I. Agents

• Perception (sensors)

• Reasoning / cognition

• Action (actuators)

Percept: perceptual inputs at any given instant.

Percept sequence: complete history of everything the agent has ever perceived.

Agent function (behavior):

reasoning
a percept sequence ↦ an action
* Illustration from [Link]
Construction of the Agent Function

Tabulation?

ª Very large, if not infinite table!

¨ Instead, implement the function internally by an agent program.

¨ The program runs on the agent’s architecture to produce the function.

Agent = architecture + program

¨ Abstract description vs concrete implementation!

The Vacuum-Cleaner World

• Environment: squares $ & %

• Percepts: [$, Dirty]

square the vacuum state of

cleaner is in the square

• Actions: left, right, suck, nothing

Agent Function

• Many ways to fill in the right column

• What is the right way?

Good/bad, intelligent/stupid?
Rational Behavior?

if status == Dirty then return Suck

else if location == A then return Right
else if location == B then return Left

Is this agent rational?

No, needless oscillation once all the dirt is cleaned up!

improve

Do nothing when all the squares are clean.

Rationality
What is rational depends on four things:

¨ performance measure defining the criterion of success

¨ prior knowledge of the environment

¨ performable actions by the agent

¨ perceptual sequence to date

A rational agent should select an action expected to maximize its

performance measure.
Performance Measure
• Awards one point for each clean square at each time step.
Meanwhile, assume
• known environment
• unknown dirt distribution and agent’s initial location
• only available actions: Left, Right, and Suck
• Left and Right having no effect if they would take the agent outside
• perfect sensing of location and dirt existence there

This agent is rational.

Omniscience vs Rationality

• An omniscient agent knows the actual outcome of its

actions.

Impossible in reality!

• Rationality maximizes the expected performance.

¨ Learn as much as it perceives.

¨ Does not require omniscience.

• Perfection maximizes actual performance.

Rationality ≠ omniscience ≠ perfection

II. Task Environment

To design a rational agent, we must specify its task environment:

• performance measure

• environment of the agent PEAS

• agent’s actuators and sensors

Automated Taxi Driver
Its task environment in the PEAS description:
PEAS for Other Agents

Universal Robots
ActiNav autonomous
bin picking kit
Environment Properties
• Categorize task environments according to properties.

appropriate families of techniques

for agent implementation
Environment Property 1
• Fully observable if the sensors can detect all aspects that are relevant to the choice of action.
vs. partially observable
Environment Property 2
• Single-agent
vs. multiagent

competitive

cooperative
Environment Property 3
if the next state of the environment is completely determined by the current
• Deterministic state and the action executed by the agent.
vs. stochastic otherwise.

unable to keep track of all the

cards in opponents’ hands; must be
treated as nondeterministic
Environment Property 4
if the agent’s experience is divided into atomic episodes, among which one
• Episodic does not depend on the actions taken in previous ones.
vs. sequential if the current decision could affect all future decisions.

instantaneous actions
can have long-term
consequences.
 Environment Property 5
• Dynamic if the environment can change while the agent is choosing an action.
vs. semi-dynamic if the environment does not change but the agent’s performance score does.
vs. static otherwise.
Environment Property 6
The distinction applies to
• Discrete
¨the environment’s state
vs. continuous ¨the way time is handled
¨the agent’s percepts and actions
III. The Structure of Agents

¨The job of AI is to design an agent program that implements

percepts ⟼ action

agent = architecture + program

Computing device, sensors & actuators

¨All agent programs have the same skeleton:

• input: current percept

• output: action

• program: manipulates inputs to produce output

Table Lookup Agent

It retains complete percept sequence in memory.

Doomed to failure due to

• daunting table size (e.g., easily over 10!"# entries for chess)
• no storage space
• no time for construction
• no way for the agent to learn all the entries
• no guidance on how to fill the table entries
Basic Agent Types
Four basic types embody the principles underlying almost all
intelligent systems:

¨Simple reflex agents 简单的反射型智能体

¨Model-based reflex agents 可以记住之前发⽣的事情

¨Goal-based agents 导航系统选择路径

¨Utility-based agents 最优⽅案

All of them can be converted into

¨Learning-based agents
 Simple Reflex Agent

• Select actions based on the

current percepts, and ignore
the percept history.

E.g., the vacuum agent

• Implemented through condition-

action rule.

if dirty then suck

if car-in-front-is-braking
Rectangles: agent’s current internal state then initiate-braking
Ovals: background information used in the process.
Vacuum-Cleaner World (Revisited)

if status == Dirty then return Suck

else if location == A then return Right
else if location == B then return Left
Simple Reflex Agent

§ Limited intelligence

It will work only if the correct decision can be made based on

only the current percept, i.e., only if the environment is fully
observable.
Model-based Reflex Agent

• Partially observable
environment.

• Need to maintain some

internal state.

• Update it using knowledge.

Model of the world

¨ How does the world change?

¨ How do actions affect the

world?
How This Agent Works

• It is rarely possible to describe the exact current state of the environment.

• The maintained “state” does not have to describe the world.

Goal-Based Agent

• Needs also some goal

information describing
desirable situations.

• Search and planning

when a long sequence of

actions is required to find
the goal.

• Difference in taking the

future into account.
Utility-Based Agent
• Different ways to achieve
a goal sometimes.

• Use a utility function that

maps a (sequence of
states) to a real number
(utility)

internal performance measure

• Maximize expected utility.

• Goal improvements:
¨ selection among conflicting goals

¨ selection based on likelihood of success

and goal importance
Learning-Based Agent
• Preferred method for creating
state-of-the-art AI systems:

¨ Allow operation in initially

unknown environments.
¨ Adapt to changes in the
environment --- robustness.

• Modifications of the four

components to bring them
in closer agreement with
the available feedback

Better overall performance

Learning-Based Agent
• Learning element introduces
improvements in performance
element.

• Critic provides feedback on the

agent’s performance based on
fixed performance standard.

• Performance element selects

actions based on the precepts.

• Problem generator suggests actions

that will lead to new and informative
experiences.