Transcript Introduction to AI & agent-based framework (to be revised soon)

DCP 1172
Introduction to Artificial Intelligence
Ch.1 & Ch.2 [AIMA]
Chang-Sheng Chen
AI Study/Research Map
•
•
•
•
•
•
•
•
Turing Test
Search-base System
Knowledge-base System
Logical Reasoning System
Neural Network
Fuzzy Network
Machine Learning
Genetic Programming
DCP 1172, Lecture 2
Applied Areas of AI
•
•
•
•
•
•
Game playing
Speech and language processing
Expert reasoning
Planning and scheduling
Vision
Robotics
…
DCP 1172, Lecture 2
The Architectural
Components of AI Systems
•
•
•
•
•
State-space search
Knowledge representation
Logical reasoning
Reasoning under uncertainty
Learning
DCP 1172, Lecture 2
The History of AI
• The “Dark Ages”, or the birth of artificial intelligence (19431956)
• The rise of artificial intelligence, or the era of great
expectation (1956-late 1960s)
• Unfulfilled promises, or the impact of reality ( late 1960s –
early 1970s)
• The technology of expert system, or the key to success ( early
1970 – mid-1980)
• How to make machine learn, or the rebirth of neural networks
( mid-1980 – present)
• Evolutionary Computation, or learn by doing ( early 1970present)
DCP 1172, Lecture 2
Acting Humanly: The Turing Test
• Alan Turing's 1950 article Computing Machinery and
Intelligence discussed conditions for considering a
machine to be intelligent“Can machines think?”  “Can
machines behave intelligently?”
• The Turing test (The Imitation Game): Operational
definition of intelligence.
DCP 1172, Lecture 2
Acting Humanly: The Turing Test
• Computer needs to possess: Natural language processing,
Knowledge representation, Automated reasoning, and Machine
learning
• Are there any problems/limitations to the Turing Test?
DCP 1172, Lecture 2
Some Examples
•
•
•
•
Playing chess
Driving on the highway
Translating languages
Diagnosing diseases
• Recognizing pattern
(e.g., speech, characters,
etc.)
• Mowing the lawn
• Internet-based
applications (e.g., spam
filtering, intrusion
detection/prevention,
etc.)
DCP 1172, Lecture 2
Playing Chess
• Environment?
• Board
• Actions?
• Legal moves
• Doing the right thing?
• Moves that lead to wins
DCP 1172, Lecture 2
Recognizing Speech
• Environment
• Audio signal
• Knowledge of user
• Actions
• Choosing word sequences
• Doing the right thing
• Recovering the users words
DCP 1172, Lecture 2
Translation
• Environment
• Source text to be translated
• Actions
• Word sequences in target language
• Doing the right thing?
• Words that achieve the same effect
• Words that are faithful to the source
DCP 1172, Lecture 2
Recognizing Pattern
• Environment
• Visual Characters (e.g., OCR)
• Optical Character Recognition
• Knowledge of user
• Actions
• reading text from paper
• translating the images into a form that the computer can
manipulate (for example, into ASCII codes).
• Doing the right thing
• Recovering the users writing and/or printing words
DCP 1172, Lecture 2
Diagnosing Diseases
• Environment
• Patient information
• Results of tests
• Actions
• Choosing diseases
• Choosing treatments
• Doing the right thing
• Eliminating disease
DCP 1172, Lecture 2
Driving
• Environment
• Restricted access highway
• Actions
• Accelerate, brake, turn, navigate, other controls
• Doing the right thing
• Stay safe, get where you want to go, get there quickly,
don’t get a ticket
DCP 1172, Lecture 2
Cloth Washing
• Environment
• Washing machine in a washroom
• Actions
• Washing (e.g., twisting, circulation, etc.)
• Refueling clean water
• Dumping dirty water
• Doing the right thing
• Make clothes look clean in a timely manner
DCP 1172, Lecture 2
Internet-based Application
• Pattern recognition
• Anti-virus, Intrusion detection system (IDS)
• Content filtering
• Anti-SPAM Mail filtering
• Network Security
• Intrusion detection/prevention system
DCP 1172, Lecture 2
Acting Humanly: The Full Turing Test
•
Alan Turing's 1950 article Computing Machinery and Intelligence discussed conditions for
considering a machine to be intelligent
•
•
“Can machines think?”  “Can machines behave intelligently?”
The Turing test (The Imitation Game): Operational definition of intelligence.
•
Computer needs to posses:Natural language processing, Knowledge
•
Problem: 1) Turing test is not reproducible, constructive, and amenable to
•
Total Turing Test: Requires physical interaction and needs perception and
representation, Automated reasoning, and Machine learning
mathematic analysis. 2) What about physical interaction with interrogator and
environment?
actuation.
DCP 1172, Lecture 2
Acting Humanly: The Full Turing Test
• Problem:
1) Turing test is not reproducible, constructive, and
amenable to mathematic analysis.
2) What about physical interaction with interrogator and
environment?
DCP 1172, Lecture 2
Acting Humanly: The Full Turing Test
Problem:
1) Turing test is not reproducible,
constructive, and amenable to
mathematic analysis.
2) What about physical interaction
with interrogator and environment?
Trap door
DCP 1172, Lecture 2
What would a computer need to pass the Turing test?
• Natural language processing: to communicate with examiner.
• Knowledge representation: to store and retrieve information
provided before or during interrogation.
• Automated reasoning: to use the stored information to answer
questions and to draw new conclusions.
• Machine learning: to adapt to new circumstances and to detect
and extrapolate patterns.
DCP 1172, Lecture 2
What would a computer need to pass the Turing test?
• Vision (for Total Turing test): to recognize the examiner’s
actions and various objects presented by the examiner.
• Motor control (total test): to act upon objects as requested.
• Other senses (total test): such as audition, smell, touch, etc.
DCP 1172, Lecture 2
Thinking Humanly: Cognitive Science
•
1960 “Cognitive Revolution”: information-processing psychology replaced behaviorism
•
Cognitive science brings together theories and experimental evidence to model internal activities
of the brain
•
•
What level of abstraction? “Knowledge” or “Circuits”?
How to validate models?
•
•
•
Predicting and testing behavior of human subjects (top-down)
Direct identification from neurological data (bottom-up)
Building computer/machine simulated models and reproduce results (simulation)
DCP 1172, Lecture 2
Thinking Rationally: Laws of Thought
• Aristotle (~ 450 B.C.) attempted to codify “right thinking”
What are correct arguments/thought processes?
• E.g., “Socrates is a man, all men are mortal; therefore
Socrates is mortal”
• Several Greek schools developed various forms of logic:
notation plus rules of derivation for thoughts.
DCP 1172, Lecture 2
Thinking Rationally: Laws of Thought
• Problems:
1) Uncertainty: Not all facts are certain (e.g., the flight might
be delayed).
2) Resource limitations:
- Not enough time to compute/process
- Insufficient memory/disk/etc
- Etc.
DCP 1172, Lecture 2
Acting Rationally: The Rational Agent
• Rational behavior: Doing the right thing!
• The right thing: That which is expected to maximize the
expected return
• Provides the most general view of AI because it includes:
•
•
•
•
Correct inference (“Laws of thought”)
Uncertainty handling
Resource limitation considerations (e.g., reflex vs. deliberation)
Cognitive skills (NLP, AR, knowledge representation, ML, etc.)
• Advantages:
1) More general
2) Its goal of rationality is well defined
DCP 1172, Lecture 2
How to achieve AI?
• How is AI research done?
• AI research has both theoretical and experimental sides. The
experimental side has both basic and applied aspects.
• There are two main lines of research:
• One is biological, based on the idea that since humans are intelligent, AI
should study humans and imitate their psychology or physiology.
• The other is phenomenal, based on studying and formalizing common
sense facts about the world and the problems that the world presents to
the achievement of goals.
• The two approaches interact to some extent, and both should
eventually succeed. It is a race, but both racers seem to be
walking. [John McCarthy]
DCP 1172, Lecture 2
Ontology
DCP 1172, Lecture 2
Khan & McLeod, 2000
The task-relevance map
Scalar topographic map, with higher values at more relevant locations
DCP 1172, Lecture 2
More formally: how do we do it? (1)
-
Use ontology to describe categories, objects and relationships:
Either with unary predicates, e.g., Human(John),
Or with reified categories, e.g., John  Humans,
And with rules that express relationships or properties,
e.g., x Human(x)  SinglePiece(x)  Mobile(x)  Deformable(x)
DCP 1172, Lecture 2
More formally: how do we do it? (2)
-
Use ontology to expand concepts to related concepts:
E.g., parsing question yields “LookFor(catching)”
Assume a category HandActions and a taxonomy defined by
catching  HandActions, grasping  HandActions, etc.
We can expand “LookFor(catching)” to looking for other actions in the category
where catching belongs through a simple expansion rule:
a,b,c a  c  b  c  LookFor(a)  LookFor(b)
DCP 1172, Lecture 2
Last Time: Acting Humanly: The Full Turing Test
• Alan Turing's 1950 article Computing Machinery and Intelligence
discussed conditions for considering a machine to be intelligent
• “Can machines think?”  “Can machines behave intelligently?”
• The Turing test (The Imitation Game): Operational definition of intelligence.
• Computer needs to possess: Natural language processing, Knowledge
representation, Automated reasoning, and Machine learning
• Problem: 1) Turing test is not reproducible, constructive, and amenable to
mathematic analysis. 2) What about physical interaction with interrogator
and environment?
• Total Turing Test: Requires physical interaction and needs perception and
actuation.
DCP 1172, Lecture 2
Last time: The Turing Test
http://aimovie.warnerbros.com
http://www.ai.mit.edu/projects/infolab/
DCP 1172, Lecture 2
Last time: The Turing Test
http://aimovie.warnerbros.com
http://www.ai.mit.edu/projects/infolab/
DCP 1172, Lecture 2
Last time: The Turing Test
http://aimovie.warnerbros.com
http://www.ai.mit.edu/projects/infolab/
DCP 1172, Lecture 2
Last time: The Turing Test
http://aimovie.warnerbros.com
http://www.ai.mit.edu/projects/infolab/
DCP 1172, Lecture 2
Last time: The Turing Test
http://aimovie.warnerbros.com
http://www.ai.mit.edu/projects/infolab/
DCP 1172, Lecture 2
This time: Outline
•
•
•
•
•
Intelligent Agents (IA)
Environment types
IA Behavior
IA Structure
IA Types
DCP 1172, Lecture 2
What is an (Intelligent) Agent?
• An over-used, over-loaded, and misused term.
• Anything that can be viewed as perceiving its
environment through sensors and acting upon that
environment through its actuators to maximize
progress towards its goals.
DCP 1172, Lecture 2
What is an (Intelligent) Agent?
• PAGE (Percepts, Actions, Goals, Environment)
• Task-specific & specialized: well-defined goals and
environment
• The notion of an agent is meant to be a tool for
analyzing systems,
• It is not a different hardware or new
programming languages
DCP 1172, Lecture 2
Intelligent Agents and Artificial Intelligence
• Example: Human mind as network of thousands or millions of
agents working in parallel. To produce real artificial intelligence,
this school holds, we should build computer systems that also
contain many agents and systems for arbitrating among the
agents' competing results.
• Distributed decision-making
and control
actuators
DCP 1172, Lecture 2
sensors
• Challenges:
• Action selection: What next
action to choose
• Conflict resolution
Agency
Agent Types
We can split agent research into two main strands:
• Distributed Artificial Intelligence (DAI) –
Multi-Agent Systems (MAS)
(1980 – 1990)
• Much broader notion of "agent"
(1990’s – present)
• interface, reactive, mobile, information
DCP 1172, Lecture 2
Rational Agents
How to design this?
Sensors
percepts
?
Agent
Environment
actions
Actuators
DCP 1172, Lecture 2
Remember: the Beobot example
DCP 1172, Lecture 2
A Windshield Wiper Agent
How do we design a agent that can wipe the windshields
when needed?
•
•
•
•
•
•
Goals?
Percepts?
Sensors?
Effectors?
Actions?
Environment?
DCP 1172, Lecture 2
A Windshield Wiper Agent (Cont’d)
•
•
•
•
•
•
Goals:
Keep windshields clean & maintain visibility
Percepts:
Raining, Dirty
Sensors:
Camera (moist sensor)
Effectors:
Wipers (left, right, back)
Actions:
Off, Slow, Medium, Fast
Environment: Inner city, freeways, highways, weather …
DCP 1172, Lecture 2
Towards Autonomous Vehicles
http://iLab.usc.edu
DCP 1172, Lecture 2
http://beobots.org
Interacting Agents
Collision Avoidance Agent (CAA)
• Goals:
Avoid running into obstacles
• Percepts ?
• Sensors?
• Effectors ?
• Actions ?
• Environment: Freeway
Lane Keeping Agent (LKA)
• Goals:
Stay in current lane
• Percepts ?
• Sensors?
• Effectors ?
• Actions ?
• Environment: Freeway
DCP 1172, Lecture 2
Interacting Agents
Collision Avoidance Agent (CAA)
• Goals:
Avoid running into obstacles
• Percepts:
Obstacle distance, velocity, trajectory
• Sensors:
Vision, proximity sensing
• Actuators:
Steering Wheel, Accelerator, Brakes, Horn, Headlights
• Actions:
Steer, speed up, brake, blow horn, signal (headlights)
• Environment: Freeway
Lane Keeping Agent (LKA)
• Goals:
Stay in current lane
• Percepts:
Lane center, lane boundaries
• Sensors:
Vision
• Actuators:
Steering Wheel, Accelerator, Brakes
• Actions:
Steer, speed up, brake
• Environment: Freeway
DCP 1172, Lecture 2
Conflict Resolution by Action Selection Agents
• Override:
CAA overrides LKA
• Arbitrate:
if Obstacle is Close then CAA
else LKA
• Compromise:
Choose action that satisfies both
agents
• Any combination of the above
• Challenges:
Doing the right thing
DCP 1172, Lecture 2
The Right Thing = The Rational Action
• Rational Action: The action that maximizes the expected
value of the performance measure given the percept sequence
to date
•
•
•
•
•
Rational = Best ?
Rational = Optimal ?
Rational = Omniscience ?
( 無所不知, …)
Rational = Clairvoyant ? (預知未來, 和死者溝通, ..)
Rational = Successful ?
DCP 1172, Lecture 2
The Right Thing = The Rational Action
• Rational Action: The action that maximizes the expected
value of the performance measure given the percept sequence
to date
•
•
•
•
•
Rational = Best
Rational = Optimal
Rational  Omniscience
Rational  Clairvoyant
Rational  Successful
Yes, to the best of its knowledge
Yes, to the best of its abilities (incl.
its constraints)
DCP 1172, Lecture 2
Behavior and performance of IAs
• Perception (sequence) to Action Mapping: f : P*  A
• Ideal mapping: specifies which actions an agent ought to take at any
point in time
• Description: Look-Up-Table, Closed Form, etc.
• Performance measure: a subjective measure to characterize
how successful an agent is (e.g., speed, power usage, accuracy,
money, etc.)
• (degree of) Autonomy: to what extent is the agent able to make
decisions and take actions on its own?
DCP 1172, Lecture 2
Look up table
Distance
10
Action
obstacle
No action
sensor
5
Turn left 30
degrees
2
Stop
DCP 1172, Lecture 2
agent
Closed form
• Output (degree of rotation) = F(distance)
• E.g., F(d) = 10/d
(distance cannot be less than 1/18)
DCP 1172, Lecture 2
How is an Agent different from other software?
• Agents are autonomous, that is, they act on behalf of the user
• Agents contain some level of intelligence, from fixed rules to
learning engines that allow them to adapt to changes in the
environment
• Agents don‘t only act reactively (被動地因應改變), but
sometimes also proactively ( 主動地改變)
DCP 1172, Lecture 2
How is an Agent different from other software?
• Agents have social ability, that is, they communicate with the
user, the system, and other agents as required
• Agents may also cooperate with other agents to carry out
more complex tasks than they themselves can handle
• Agents may migrate from one system to another to access
remote resources or even to meet other agents
• Example: E-mail Systems
• Mail Transfer Agent ( MTA, e.g., Sendmail, Postfix, etc.)
• Mail User Agent ( MUA, e.g., Outlook express, Netscape
communicator, etc.)
DCP 1172, Lecture 2
Environment Types
• Characteristics
• Fully observable vs. partially observable
• Deterministic vs. Stochastic (nondeterministic)
• Episodic vs. Sequential (nonepisodic)
• Episodic(獨立事件, 或前後沒有明顯關聯性)
• Hostile vs. friendly
• Static vs. dynamic
• Discrete vs. continuous
• Example: anti-SPAM filtering
• Filtering by regular expression (e.g., fixed pattern)
• Filtering by Bayesian Learning Network
• …
DCP 1172, Lecture 2
Environment Types
• Characteristics
• Fully observable vs. partially observable
• Sensors give access to complete state of the environment.
• Deterministic vs. Stochastic (nondeterministic)
• The next state can be determined based on the current state and
the action.
• Episodic vs. Sequential (nonepisodic)
• Episode: each perceive and action pairs
• The quality of action does not depend on the previous episode.
DCP 1172, Lecture 2
Environment Types
• Characteristics
• Hostile vs. friendly
• Static vs. dynamic
• Dynamic if the environment changes during deliberation
• Discrete vs. continuous
• Chess vs. driving
DCP 1172, Lecture 2
Structure of Intelligent Agents
• Agent = architecture + program
• Agent program: the implementation of f : P*  A, the
agent’s perception-action mapping
function Skeleton-Agent(Percept) returns Action
memory  UpdateMemory(memory, Percept)
Action  ChooseBestAction(memory)
memory  UpdateMemory(memory, Action)
return Action
• Architecture: a device that can execute the agent program
(e.g., general-purpose computer, specialized device, beobot,
etc.)
DCP 1172, Lecture 2
Using a look-up-table to encode f : P*  A
• Example: Collision Avoidance
• Sensors: 3 proximity sensors
• Effectors: Steering Wheel, Brakes
• How to generate?
• How large?
• How to select action?
obstacle
sensors
agent
DCP 1172, Lecture 2
Using a look-up-table to encode f : P*  A
• Example: Collision Avoidance
• Sensors: 3 proximity sensors
• Effectors: Steering Wheel, Brakes
sensors
• How to generate: for each p  Pl  Pm  Pr
generate an appropriate action, a  S  B
obstacle
agent
• How large: size of table = #possible percepts times # possible
actions = |Pl | |Pm| |Pr| |S| |B|
E.g., P = {close, medium, far}3
A = {left, straight, right}  {on, off}
then size of table = 27*3*2 = 162
• How to select action? Search.
DCP 1172, Lecture 2
Agent types
•
•
•
•
Simple reflex agents
Model-base reflex agents (with internal states)
Goal-based agents
Utility-based agents
DCP 1172, Lecture 2
Agent types
• Simple reflex agents
• Reactive: No memory
• Model-based reflex agents (with internal states)
• A model of the world = knowledge about “how the world
works”
• W/o previous state, may not be able to make decision
• E.g. brake lights at night.
• Goal-based agents
• Goal information needed to make decision
DCP 1172, Lecture 2
Agent types
• Utility-based agents
• How well can the goal be achieved (degree of happiness)
• What to do if there are conflicting goals?
• Speed and safety
• Which goal should be selected if several can be achieved?
DCP 1172, Lecture 2
Simple reflex agents
Actuators
DCP 1172, Lecture 2
Simple reflex (reactive) agents
• Reactive agents do not have internal symbolic models.
• Act by stimulus-response to the current state of the
environment.
• Each reactive agent is simple and interacts with others in a basic
way.
• Complex patterns of behavior emerge from their interaction.
• Benefits: robustness, fast response time
• Challenges: scalability, how intelligent?
and how do you debug them?
DCP 1172, Lecture 2
Model-based reflex agents w/ state
Actuators
DCP 1172, Lecture 2
Goal-based agents
Actuators
DCP 1172, Lecture 2
Utility-based agents
Actuators
DCP 1172, Lecture 2
Mobile agents
•
•
•
•
•
Programs that can migrate from one machine to another.
Execute in a platform-independent execution environment.
Require agent execution environment (places).
Mobility not necessary or sufficient condition for agenthood.
Practical but non-functional advantages:
• Reduced communication cost (eg, from PDA)
• Asynchronous computing (when you are not connected)
• Two types:
• One-hop mobile agents (migrate to one other place)
• Multi-hop mobile agents (roam the network from place to place)
• Applications:
• Distributed information retrieval.
• Telecommunication network routing.
DCP 1172, Lecture 2
Mobile agents
• Programs that can migrate from
one machine to another.
• Execute in a platformindependent execution
environment.
• Require agent execution
environment (places).
• Mobility not necessary or
sufficient condition for
agenthood.
A mail agent
DCP 1172, Lecture 2
Mobile agents
• Practical but non-functional advantages:
• Reduced communication cost (e.g. from PDA)
• Asynchronous computing (when you are not connected)
• Two types:
• One-hop mobile agents (migrate to one other place)
• Multi-hop mobile agents (roam the network from place to
place)
DCP 1172, Lecture 2
Mobile agents
• Applications:
• Distributed information retrieval.
• Telecommunication network routing.
DCP 1172, Lecture 2
Information agents
• Manage the explosive growth of information.
• Manipulate or collate information from many distributed sources.
• Information agents can be mobile or static.
• Examples:
• BargainFinder comparison shops among Internet stores for CDs
• FIDO the Shopping Doggie (out of service)
• Internet Softbot infers which internet facilities (finger, ftp, gopher) to use and
when from high-level search requests.
• Challenge: ontologies for annotating Web pages
• (e.g., SHOE=Simple HTML Ontology extension).
DCP 1172, Lecture 2
Summary
• Intelligent Agents:
• Anything that can be viewed as perceiving its environment
through sensors and acting upon that environment through its
actuators to maximize progress towards its goals.
• PAGE (Percepts, Actions, Goals, Environment)
• Described as a Perception (sequence) to Action Mapping: f : P*
 A
• Using look-up-table, closed form, etc.
• Agent Types: Simple reflex, model-based, goal-based, utility-based
• Rational Action: The action that maximizes the expected value of
the performance measure given the percept sequence to date
DCP 1172, Lecture 2