Unit1-Introduction
Course: C231 Introduction to AI
Introduction to AI: Part II
Alessandra Russo, Mark Law
{a.russo, mark.law}@imperial.ac.uk
© Alessandra Russo Unit 1 – Introduction, slide 1
Course: C231 Introduction to AI
A brief history
© Alessandra Russo Unit 1 – Introduction, slide 2
20th century Understanding computation.
Several models of computation (e.g. Turing machine)
1950 First applications of computers were AI programs
Ø Program that learns to play checkers
Ø Logic Theorist that discovers proofs in propositional logic
Ø Perceptron (first work on formal neurons), by Rosenblatt
1970 – 80 Complex knowledge representations (McCharty and Hayes)
Ø How to represent the knowledge needed to solve a problem.
Ø Chat-80: a Q&A system to answer geographical questions.
1970 – 88 Domain specific expert systems
Ø Formal language for AI reasoning (Prolog)
1990 – 2000 Sub-disciplines of AI (e.g. perception, probabilistic and
decision-theoretic, reasoning, planning).
2000 – Machine learning, vision, robotics,…
Course: C231 Introduction to AI
Intelligent Agent
© Alessandra Russo Unit 1 – Introduction, slide 3
q Robot agents
q Digital assistant
q Software agent
q …..
Course: C231 Introduction to AI
A Robot Agent
© Alessandra Russo Unit 1 – Introduction, slide 4
Environment System
Domain
model
action
reaction observation
Reasoning and Planning
Course: C231 Introduction to AI
A Robot Agent
© Alessandra Russo Unit 1 – Introduction, slide 5
Environment System
Domain
model
action
reaction
’
observation
Exogenous Events
Course: C231 Introduction to AI
Environment System
Domain
model
action
reaction
’
A Robot Agent
© Alessandra Russo Unit 1 – Introduction, slide 6
Domain
model
observation
Learning new knowledge
Course: C231 Introduction to AI
© Alessandra Russo Unit 1 – Introduction, slide 7
A Robot Agent
1 2 5 6
3
4
pickup
mo
ve
(3
)
move(5)
m
ov
e(5
)
putdown
3
4
5
P(success) = r
P(
su
cc
es
s)
= p
P(success) = q
Object smashed
r1:0.7 : succeeds(pickup, T).
r2:0.9 : succeeds(move(L1, L2), T) :-
holdsAt(at(L1), T),
connected(L1, L2),
L2 != loc3.
r3:0.9 : succeeds(putdown, T) :-
not happened(move(loc2, loc3), T-2).
r4:0.1 : succeeds(putdown, T) :-
happened(move(loc2, loc3), T-2).
Learned knowledge
+
Past experience
Prior Knowledge
Course: C231 Introduction to AI
© Alessandra Russo Unit 1 – Introduction, slide 8
A Robot Agent
r1:0.7 : succeeds(pickup, T).
r2:0.9 : succeeds(move(L1, L2), T) :-
holdsAt(at(L1), T),
connected(L1, L2),
L2 != loc3.
r3:0.9 : succeeds(putdown, T) :-
not happened(move(loc2, loc3), T-2).
r4:0.1 : succeeds(putdown, T) :-
happened(move(loc2, loc3), T-2).
Learned knowledge
+
1 2 6
3
4
pickup
m
ov
e(
4)
m
ove(4)
move(5)
mo
ve(5
)
putd
own
3
4
5
putdown
5a
5b 0.7
0.9
0.
9
0.9
0.9
0.9
0.1
Past experience
Prior Knowledge
Course: C231 Introduction to AI
Reasoning and learning
through human-robot dialogue
© Alessandra Russo Unit 1 – Introduction, slide 9
Machine learning has recently been
able to support highly accurate NLP
Ø SyntaxNet (from Google)
Ø Core-NLP (from Stanford)
But, limited in extracting common-
sense and domain expert knowledge,
Symbolic reasoning and symbolic
learning support deeper semantic
understanding
https://1drv.ms/v/s!Aq-g0J2JpSjPox7CC5YSCvXLYNgl
Oizuu.com
Course: C231 Introduction to AI
Representation in problem solving
© Alessandra Russo Unit 1 – Introduction, slide 10
Ø Representation schema: form of knowledge used in an agent
Ø Representation: internal representation of knowledge
Ø Knowledge base: representation of all the knowledge that
is stored in an agent
Course: C231 Introduction to AI
How should a representation be?
© Alessandra Russo Unit 1 – Introduction, slide 11
We are interested in representations that are:
Ø Expressive enough to captures knowledge needed to solve a
problem.
Ø Close to the problem that need to be solve: declarative, compact
and easy to maintain.
Ø Amenable to efficient computations, and able to trade off
accuracy and computation time.
Ø Can be automatically acquired from people, past experience and
data, i.e. learnable!
Course: C231 Introduction to AI
What should a solution be?
© Alessandra Russo Unit 1 – Introduction, slide 12
Given an informal description of a problem, what is a solution?
Ø Optimal solutions: robot travelling minimal distance
Ø Satisficing solution: good enough to deliver some items
Ø Approximately optimal solutions: robot travelling distance
that is close enough to the optimal distance.
Ø Probable solutions: something that is likely to be a solution
Typically four classes of solutions:
Course: C231 Introduction to AI
From problem to representation
© Alessandra Russo Unit 1 – Introduction, slide 13
Given the type of solutions we want to compute, how do we
represent the problem?
Ø What level of abstraction of the problem to represent?
Ø What individuals and relations in the world we need to represent?
Ø How can an agent represent the knowledge?
Ø How can an agent acquire the information from data, sensing,
experience, or other agents?
Course: C231 Introduction to AI
Choosing level of abstraction
© Alessandra Russo Unit 1 – Introduction, slide 14
Model the problem with multiple levels of abstraction.
Low-level of abstraction High level of abstraction
GPS Co-locations
E-
E+
E-
Accept call Alice
at 9:30
Reject call from Bob at 10:30
E+
Course: C231 Introduction to AI
Reasoning
© Alessandra Russo Unit 1 – Introduction, slide 15
Reasoning, process by which an agent manipulates information to
search through the space of possibilities to determine how to
complete its task.
Ø Offline computation: done by the agent before it has to act.
It uses background knowledge and data.
Ø Online computation: done by the agent between observing the
environment and acting in the environment. It uses both
background knowledge and observations to decide what to do.
Three forms of reasoning:
Deductive Abductive Inductive
Course: C231 Introduction to AI
Different levels of complexity
© Alessandra Russo Unit 1 – Introduction, slide 16
Models of the environment:
Ø States
Ø Features
Ø Relational descriptions: individuals/objects and relations
Uncertainty:
Ø Sensing uncertainty
Ø Effect uncertainty
Preferences:
Ø Trade-off between the desirability of various outcomes. Ordinal and
cardinal preferences.
Number of agents:
Ø Single agent
Ø Multiple agents (adversarial versus cooperative agents).
Course: C231 Introduction to AI
© Alessandra Russo Unit 1 – Introduction, slide 17
Objectives
Ø Modelling a problem
Ø Different representations and semantics (e.g. (non-)monotonicity and constraints)
Ø Different forms of reasoning . (e.g. deductive and abductive inference)
Ø Abductive reasoning
Ø Some Typical AI Problems
Ø Planning (e.g. abductive planning, Sat-Planning, ASP)
Ø Diagnosis
Ø Problem solving in ASP.
Ø Sat Solving
Ø How to define a SAT problem
Ø Algorithms
Ø Applications
Ø Answer Set Programming
Ø Language and semantics (e.g. (non-)determinism, preferences)
Ø Bottom-up reasoning
Course: C231 Introduction to AI
© Alessandra Russo Unit 1 – Introduction, slide Number 18
Reading Material
Ø Prolog Programming for Artificial Intelligence,
Ivan Bratko Pearson 2012.
Ø Artificial Intelligence, Foundations of Computational Agents,
David Poole and Alan Mackworth
Ø Answer Set Solver, Clingo.
https://potassco.org
Ø Knowledge Representation, Reasoning, and the Design of
Intelligent Agents – Michael Gelfond & Yulia Gelfond Kahl
Januray 2014
Ø Some research papers
Slides and notes, complemented with information given
during lectures and tutorials.
Course: C231 Introduction to AI
Unit 1 – Introduction, slide 19
Main Topics
© Alessandra Russo
Deductive, Abductive and Inductive Reasoning
Top-down approach
» Algorithm and use of integrity constraints
» Semantics, soundness and completeness properties
» Reasoning about events and Goal-directed planning
Abductive Reasoning
Keys aspects of AI and computational agents
Answer Set Programming and Stable Model Semantics
» Language, Syntax and Semantics
» Non-deterministic rules, and optimisation statements
SAT Solving
Bottom-up approach
» Weak constraints and notion of best explanation
» Semantics, soundness and completeness properties