CS 561: Artificial Intelligence
1
CS 561: Artificial Intelligence
Instructors: Prof. Laurent Itti (itti@usc.edu)
TAs:
Lectures: Online & OHE-100B, Mon & Wed, 12:30 – 14:20
Office hours: Mon 14:30 – 16:00, HNB-07A (Prof. Itti)
This class will use courses.uscden.net (Desire2Learn, D2L)
– Up to date information, lecture notes, lecture videos
– Homeworks posting and submission information
– Grades, relevant dates, links, etc.
Textbook: [AIMA] Artificial Intelligence: A Modern Approach, by Russell & Norvig. (3rd ed)
Optional (ALFE): Autonomous Learning from the Environment by Shen
Yunhao Ge – yunhaoge@usc.edu (50%)
Jincheng He – jinchenh@usc.edu (50%)
Hexiang Hu – hexiangh@usc.edu (25%)
Ang Li – ali355@usc.edu (50%)
Daniel Link – dlink@usc.edu (50%)
Setareh Nasihati Gilani – nasihati@usc.edu (25%)
Gozde Sahin – gsahin@usc.edu (50%)
2
CS 561: Artificial Intelligence
Course overview: foundations of symbolic intelligent systems. Agents, search, problem solving, logic, representation, reasoning, symbolic programming, and robotics.
Prerequisites: CS 455x, i.e., programming principles, discrete mathematics for computing, software design and software engineering concepts. Good knowledge of C++ and STL, or Java, or Python needed for programming assignments.
Grading: 20% for midterm-1 +
20% for midterm-2 +
30% for final +
30% for 3 mandatory homeworks/assignments
2
3
CS 561: Artificial Intelligence
Grading:
Grading is absolute and according to the following scale:
>= 90 A+ (honorary – shows as A on transcript)
>= 80 A
>= 75 A-
>= 70 B+
>= 60 B
>= 55 B-
>= 50 C+
>= 40 C
>= 35 C-
< 35 F
3
4
Practical issues
Class mailing list: will be setup on the D2L system and Piazza.
Homeworks: See class web page on D2L. Homeworks are programming assignments.
Jan 27 – HW1 out Topic: search
Feb 22 – HW1 due
Feb 24 – HW2 out Topic: game playing or constraint satisfaction
Mar 17 – HW2 due
Mar 22 – HW3 out Topic: logic reasoning and inference or neural networks
Apr 26 – HW3 due
Late homeworks: you lose 20% of the homework’s grade per 24-hour period that you are late. Beware, the penalty grows very fast: grade = points * (1 – n * 0.2) where n is the number of days late (n=0 if submitted on time, n=1 if submitted between 1 second and 24h late, etc).
Homework grading: your hws will be graded by an A.I. agent (given to you in advance for testing) through the online system at vocareum.com.
Grade review / adjustment: Requests will be considered up to 2 weeks after the grade is released. After that, it will be too late and requests for grading review will be denied.
Exams:
Midterm 1: Monday March 1, 12:30 – 2:00pm
Midterm 2: Wednesday March 31, 12:30 – 2:00pm
Final exam: Friday May 7, 11:00am – 1:00pm
5
6
7
8
9
More on homeworks and grading
In each homework you will implement some algorithms from scratch.
But our goal is to focus on A.I. algorithms, not on low-level programming. Hence I recommend C++/STL so that you can use the STL containers (queue, map, etc) instead of pointers and memory management. But the language you use is up to you.
Code editing, compiling, testing: we will use www.vocareum.com which will be linked to desire2learn (this is in progress at this time).
Vocareum supports several languages, the choice of which you use is up to you: C, C++, C++11, Java, Python, etc.
Your program should take no command-line arguments. It should read a text file called “input.txt” that contains a problem definition. It should write a file “output.txt” with your solution. For each homework, format for files input.txt and output.txt will be specified and examples will be given to you.
The grading will, 50 times:
Create an input.txt file
Run your code
Compare output.txt created by your program with the correct one.
If your outputs for all 50 test cases are correct, you get 100 points.
Otherwise, you get 100 – 4xN points where N is the number of failed test cases, or 0 if failed more than 25 cases.
Vocareum.com
10
gcc - 5.5
valgrind - 3.11
ar - 2.26.1
php - 7.0.32
python2 - 2.7.12
python3 - 3.5.2, 3.6.4
Java 1.8 - 1.8.0_191
perl - 5.22.1
make - 4.1
11
TA office hours
Yunhao Ge - yunhaoge@usc.edu (50%) Wednesdays 4-6pm
Jincheng He - jinchenh@usc.edu (50%) Tuesdays 2-4pm
Hexiang Hu - hexiangh@usc.edu (25%) Fridays 4-6pm
Ang Li - ali355@usc.edu (50%) Thursdays 4-6pm
Daniel Link - dlink@usc.edu (50%) Mondays 3-5pm
Setareh Nasihati Gilani - nasihati@usc.edu (25%) Tuesdays 10am-12pm
Gozde Sahin - gsahin@usc.edu (50%) Tuesdays 12-2pm
Academic Integrity
Familiarize yourself with the USC Academic Integrity guidelines.
Violations of the Student Conduct Code will be filed with the Office of Student Judicial Affairs, and appropriate sanctions will be given.
Homework assignments are to be solved individually.
You are welcome to discuss class material in review groups, but do not discuss how to solve the homeworks.
Exams are closed-book with no questions allowed.
Please read and understand:
http://policy.usc.edu/student/scampus/
https://sjacs.usc.edu/students/
Academic Integrity
All students are responsible for reading and following the Student Conduct Code. Note that the USC Student Conduct Code prohibits plagiarism.
Some examples of what is not allowed by the conduct code: copying all or part of someone else's work (by hand or by looking at others' files, either secretly or if shown), and submitting it as your own; giving another student in the class a copy of your assignment solution; and consulting with another student during an exam. If you have questions about what is allowed, please discuss it with the instructor.
Students who violate university standards of academic integrity are subject to disciplinary sanctions, including failure in the course and suspension from the university. Since dishonesty in any form harms the individual, other students, and the university, policies on academic integrity will be strictly enforced. Violations of the Student Conduct Code will be filed with the Office of Student Judicial Affairs.
14
Piazza
We will use piazza.com for questions and answers related to class material.
Please register here:
http://piazza.com/usc/spring2021/csci561
Guidelines:
You may ask any question related to material covered in lectures, discussions, or exams.
You may ask clarification questions only related to the homework definitions.
You may not ask for advice on how to solve some aspect of a homework problem.
You may not post code snippets related to homework problems.
You may not post test cases or input/output examples related to homework problems.
As a general rule, remember that homeworks are to be solved strictly individually.
17
Why study AI?
Search engines
Labor
Science
Medicine /
Diagnosis
Appliances /
Internet of Things (IoT)
What else?
Why study AI?
Why study AI?
DARPA Robotics Challenge
20
21
22
Wearable computing
Zypad
Google glass
Microsoft Hololens
23
What is AI?
The exciting new effort to make computers think … machines with minds, in the full and literal sense”
(Haugeland 1985)
“The art of creating machines that perform functions that require intelligence when performed by people” (Kurzweil, 1990)
“The study of mental faculties through the use of computational models”
(Charniak et al. 1985)
A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes” (Schalkol, 1990)
Systems that think like humans
Systems that think rationally
Systems that act like humans
Systems that act rationally
24
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:
More general
Its goal of rationality is well defined
25
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.
26
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?
27
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.
28
Acting Humanly: The Full Turing Test
Trap door
Problem:
1) Turing test is not reproducible, constructive, and amenable to mathematic analysis.
2) What about physical interaction with interrogator and environment?
29
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.
30
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.
Core focus in this course
31
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.
32
CAPTCHAs or “reverse Turing tests”
Vision is a particularly difficult one for machines…
Gave rise to “Completely Automated Public Turing test to tell Computers and Humans Apart” (CAPTCHA)
wikipedia
33
AI Prehistory
33
34
AI History
35
AI State of the art
Have the following been achieved by AI?
Pass the Turing test
World-class chess or go playing
Playing table tennis
Autonomous cross-country driving
Solving mathematical problems
Discovering and proving mathematical theories
Engaging in a meaningful conversation
Understanding spoken language
Observing and understanding human emotions
Expressing emotions
…
36
AI State of the art
37
38
AI State of the art
39
AI State of the art
40
AI State of the art
41
AI State of the art
42
General Introduction
01-Introduction. [AIMA Ch 1] Course Schedule. Homeworks, exams and grading. Course material, TAs and office hours. Why study AI? What is AI? The Turing test. Rationality. Branches of AI. Research disciplines connected to and at the foundation of AI. Brief history of AI. Challenges for the future. Overview of class syllabus.
Intelligent Agents. [AIMA Ch 2] What is
an intelligent agent? Examples. Doing the right
thing (rational action). Performance measure.
Autonomy. Environment and agent design.
Structure of agents. Agent types. Reflex agents.
Reactive agents. Reflex agents with state.
Goal-based agents. Utility-based agents. Mobile
agents. Information agents.
Course Overview
sensors
effectors
Agent
43
Course Overview (cont.)
02-Problem solving and search. [AIMA Ch 3] Example: measuring problem. Types of problems. More example problems. Basic idea behind search algorithms. Complexity. Combinatorial explosion and NP completeness. Polynomial hierarchy.
03-Uninformed search. [AIMA Ch 3] Depth-first. Breadth-first. Uniform-cost. Depth-limited. Iterative deepening. Examples. Properties.
04/05-Informed search. [AIMA Ch 4] Best-first. A* search. Heuristics. Hill climbing. Problem of local extrema. Simulated annealing. Genetic algorithms.
3 l
5 l
9 l
Using these 3 buckets,
measure 7 liters of water.
Traveling salesperson problem
How can we solve complex problems?
44
Course Overview (cont.)
Practical applications of search.
06/07-Game playing. [AIMA Ch 5] The minimax algorithm. Resource limitations. Aplha-beta pruning. Elements of
chance and non-
deterministic games.
tic-tac-toe
44
45
Course Overview (cont.)
Search under constraints
08-Constraint satisfaction. [AIMA Ch 6] Node, arc, path, and k-consistency. Backtracking search. Local search using min-conflicts.
Map coloring
45
46
Course Overview (cont.)
9-Agents that reason logically 1. [AIMA Ch 7] Knowledge-based agents. Logic and representation. Propositional (boolean) logic.
10-Agents that reason logically 2. [AIMA Ch 7] Inference in propositional logic. Syntax. Semantics. Examples.
Towards intelligent agents
wumpus world
Note: room not available
Week of Sept 16
47
Course Overview (cont.)
Building knowledge-based agents: 1st Order Logic
11-First-order logic 1. [AIMA Ch 8] Syntax. Semantics. Atomic sentences. Complex sentences. Quantifiers. Examples. FOL knowledge base. Situation calculus.
12-First-order logic 2.
[AIMA Ch 8] Describing actions.
Planning. Action sequences.
48
Course Overview (cont.)
Reasoning Logically
13/14-Inference in first-order logic. [AIMA Ch 9] Proofs. Unification. Generalized modus ponens. Forward and backward chaining.
Example of
backward chaining
49
Course Overview (cont.)
Examples of Logical Reasoning Systems
15-Logical reasoning systems.
[AIMA Ch 9] Indexing, retrieval
and unification. The Prolog language.
Theorem provers. Frame systems
and semantic networks.
Semantic network
used in an insight
generator (Duke
university)
50
Course Overview (cont.)
Systems that can Plan Future Behavior
16-Planning. [AIMA Ch 10] Definition and goals. Basic representations for planning. Situation space and plan space. Examples.
51
Course Overview (cont.)
Center of largest area
Center of gravity
17-Fuzzy logic. [handout]. Fuzzy variables, fuzzy inference, aggregation, defuzzification.
Handling fuzziness, change, uncertainty.
52
Course Overview (cont.)
18-Learning from examples. [AIMA 18 + handout]. Supervised learning, learning decision trees, support vector machines.
Handling fuzziness, change, uncertainty.
53
Course Overview (cont.)
Learning with Neural networks
19/20-Learning with Neural Networks.
[Handout + AIMA 18] Introduction to perceptrons, Hopfield networks, self-organizing feature maps. How to size a network? What can neural networks achieve? Advanced concepts – convnets, deep learning, stochastic gradient descent, dropout learning, autoencoders, applications and state of the art.
54
Course Overview (cont.)
21/22-Probabilistic reasoning. [AIMA Ch 13, 14, 15]
Reasoning under uncertainty – probabilities, conditional independence, Markov blanket, Bayes nets. Probabilistic reasoning in time. Hidden Markov Models, Kalman filters, dynamic Bayesian networks.
Handling fuzziness, change, uncertainty.
55
Course Overview (cont.)
23-Probabilistic decision making. [AIMA 16, 17] – utility theory, decision networks, value iteration, policy iteration, Markov decision processes (MDP), partially-observable MDP (POMDP).
Handling fuzziness, change, uncertainty.
56
Course Overview (cont.)
24-Probabilistic reasoning over time. [AIMA 15]
Temporal models, Hidden Markov Models, Kalman filters, Dynamic Bayesian Networks, Automata theory.
Handling fuzziness, change, uncertainty.
57
Course Overview (cont.)
25-Probability-based learning. [AIMA 20-21]
Probabilistic Models, Naïve Bayes Models, EM algorithm, Reinforcement Learning.
Handling fuzziness, change, uncertainty.
58
Course Overview (cont.)
What challenges remain?
Towards intelligent machines. [AIMA Ch 26, 27] The challenge of robots: with what we have learned, what hard problems remain to be solved? Different types of robots. Tasks that robots are for. Parts of robots. Architectures. Configuration spaces. Navigation and motion planning. Towards highly-capable robots. What have we learned. Where do we go from here?
robotics@USC
59
Defining intelligent agents
Intelligent Agents (IA)
Environment types
IA Behavior
IA Structure
IA Types
60
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 effectors to maximize progress towards its goals.
61
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
62
Rational Agents
Environment
Agent
percepts
actions
?
Sensors
Effectors
How to design this?
63
A Windshield Wiper Agent
How do we design a agent that can wipe the windshields
when needed?
Goals?
Percepts?
Sensors?
Effectors?
Actions?
Environment?
64
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 …
65
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
66
Interacting Agents
Collision Avoidance Agent (CAA)
Goals: Avoid running into obstacles
Percepts: Obstacle distance, velocity, trajectory
Sensors: Vision, proximity sensing
Effectors: 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
Effectors: Steering Wheel, Accelerator, Brakes
Actions: Steer, speed up, brake
Environment: Freeway
67
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
68
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 ?
69
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 Yes, to the best of its knowledge
Rational = Optimal Yes, to the best of its abilities (incl. its constraints)
Rational Omniscience
Rational Clairvoyant
Rational Successful
70
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
Implementation: Look-Up-Table, Closed Form, Algorithm, 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?
71
Look up table
agent
obstacle
sensor
Distance Action
10 No action
5 Turn left 30 degrees
2 Stop
72
Closed form
Output (degree of rotation) = F(distance)
E.g., F(d) = 10/d (distance cannot be less than 1/10)
73
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
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
74
Environment Types
Characteristics
Accessible vs. inaccessible
Deterministic vs. nondeterministic
Episodic vs. nonepisodic
Hostile vs. friendly
Static vs. dynamic
Discrete vs. continuous
75
Environment Types
Characteristics
Accessible vs. inaccessible
Accessible: sensors give access to complete state of the environment.
Deterministic vs. nondeterministic
Deterministic: the next state can be determined based on the current state and the action.
Episodic vs. nonepisodic (Sequential)
Episode: each perceive and action pairs
In episodic environments, the quality of action does not depend on the previous episode and does not affect the next episode.
Example: Episodic: mail sorting system; non-episodic: chess
76
Environment Types
Characteristics
Hostile vs. friendly
Static vs. dynamic
Dynamic if the environment changes during deliberation
Discrete vs. continuous
Chess vs. driving
77
Environment types
Environment Accessible Deterministic Episodic Static Discrete
Operating System
Virtual
Reality
Office Environment
Mars
78
Environment types
Environment Accessible Deterministic Episodic Static Discrete
Operating System Yes Yes No No Yes
Virtual
Reality Yes Yes Yes/no No Yes/no
Office Environment No No No No No
Mars
No Semi No Semi No
The environment types largely determine the agent design.
79
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.)
80
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?
agent
obstacle
sensors
81
Using a look-up-table to encode f : P* A
Example: Collision Avoidance
Sensors: 3 proximity sensors
Effectors: Steering Wheel, Brakes
How to generate: for each p Pl Pm Pr
generate an appropriate action, a S B
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 rows
Total possible combinations (ways to fill table): 27*3*2=162
How to select action? Search.
agent
obstacle
sensors
82
Agent types
Reflex agents
Reflex agents with internal states
Goal-based agents
Utility-based agents
Learning agents
83
Agent types
Reflex agents
Reactive: No memory
Reflex agents with internal states
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
84
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?
Learning agents
How can I adapt to the environment?
How can I learn from my mistakes?
85
Reflex agents
86
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?
87
Reflex agents w/ state
88
Goal-based agents
89
Utility-based agents
90
Learning agents
91
Critic: Determines outcomes of
actions and gives feedback
Problem generator: creates new experiences
to promote learning
Learning element:
Takes feedback from
critic and improves
performance element
Summary on intelligent agents
Intelligent Agents:
Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through its effectors 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: Reflex, state-based, goal-based, utility-based, learning
Rational Action: The action that maximizes the expected value of the performance measure given the percept sequence to date
92