程序代写代做代考 Answer Set Programming prolog algorithm AI Unit1-Introduction

Unit1-Introduction

Course: C231 Introduction to AI

Introduction to AI: Part II
Alessandra Russo, Mark Law

{a.russo, mark.law}@imperial.ac.uk

Course: C231 Introduction to AI

A brief history

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

q Robot agents

q Digital assistant

q Software agent

q …..

Course: C231 Introduction to AI

A Robot Agent

Environment System

Domain
model

action

reaction observation

Reasoning and Planning

Course: C231 Introduction to AI

A Robot Agent

Environment System

Domain
model

action

reaction
’

observation

Exogenous Events

Course: C231 Introduction to AI

Environment System

Domain
model

action

reaction
’

A Robot Agent

Domain
model

observation

Learning new knowledge

Course: C231 Introduction to AI

A Robot Agent

1 2 5 6

pickup

mo
ve

(3
)

move(5)

m
ov

e(5
)

putdown

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

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

pickup

m
ov

e(
4)

m
ove(4)

move(5)

mo
ve(5

)
putd

own

5
putdown

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

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

Ø 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?

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?

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

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

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

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

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

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

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

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

Published by admin

Leave a Reply Cancel reply