Transcript PowerPoint Presentation - Computing Science

Knowledge
Representation
Fall 2013
COMP3710 Artificial Intelligence
Computing Science
Thompson Rivers University
Course Outline


Part I – Introduction to Artificial Intelligence
Part II – Classical Artificial Intelligence


Knowledge Representation
Searching




Knowledge Represenation and Automated Reasoning





Search Methodoloties
Advanced Search
Genetic Algorithms (relatively new study area)
Propositinoal and Predicate Logic
Inference and Resolution for Problem Solving
Rules and Expert Systems
Part III – Machine Learning
Part IV – Advanced Topics
TRU-COMP3710
Knowledge Representation
2
Unit Outcomes
TRU-COMP3710
Knowledge Representation
3
Reference

Chapter 3. Knowledge Representation
TRU-COMP3710
Knowledge Representation
4
Unit Outline












Introduction
The Need for a Good Representation
Example: Semantic Nets
Inheritance
Example: Frames
Object-Oriented Programming
Search Spaces
Semantic Trees
Search Trees
Combinatorial Explosion
Problem Reduction
Goal Trees
TRU-COMP3710
Knowledge Representation
5
The Need for a Good Representation

If, for a given problem, we have a means of checking a proposed
solution, then we can solve the problem by testing all possible answers.
– Marvin Minsky

How to make a system solve a problem?


A computer needs a representation of a problem in order to solve it.
A representation must be:




Efficient – not wasteful in time or resources.
Useful – allows the computer to solve the problem.
Meaningful – really relates to the problem.
Any good idea?
TRU-COMP3710
Knowledge Representation
6
Example: Semantic Nets



A semantic net is a graph with nodes, connected by edges.
The nodes represent objects or properties.
The edges represent relationships between the objects.
TRU-COMP3710
Knowledge Representation
7
Inheritance


Inheritance is the process by which a subclass inherits properties from
a superclass.
Example:



Mammals give birth to live young.
Fido is a mammal.
Therefore fido gives birth to live young.

In some cases, as in the example above, inherited values may need to
be overridden. (Fido may be a mammal, but if he’s male then he
probably won’t give birth).

Can we expand semantic nets to include inheritance?
TRU-COMP3710
Knowledge Representation
8
Example: Frames

A sort of extension of semantic nets with inheritance
A frame system consists of a number of frames, connected by edges,
like a semantic net.
Class frames describe classes.
Instance frames describe instances.
Each frame has a number of slots.
Each slot can be assigned a slot value.

How to implement?





TRU-COMP3710
Knowledge Representation
9
Object-Oriented Programming


Object oriented programming languages such as Java, C++.
Use ideas such as:




inheritance
multiple inheritance
overriding default values
procedures and demons
TRU-COMP3710
Knowledge Representation
10
Search Spaces





Do we always need to use such representations?
Representation is really problem-specific.
Many problems in AI can be represented as search spaces.
A search space is a representation of the set of all possible choices in a
given problem, one or more of which are the solution to the problem.
State spaces


A state is a set of values of all instances.
States are connected by paths that represent actions.
TRU-COMP3710
Knowledge Representation
11
Search Trees






Trees are easier to handle than graphs.
Semantic trees – a type of semantic net.
Used to represent search spaces.
Root node has no predecessor.
Leaf nodes have no successors.
Goal nodes (of which there may be more than one) represent solutions
to a problem.

What is the problem then, when you know what the goal is?


How about the 8-puzzle game?
What do we have to do when we do not know what the goal is?
TRU-COMP3710
Knowledge Representation
12
Search Trees




H, I, J, K, M, N and O are leaf nodes.
A is the root node.
L is the goal node.
There is only one complete path:

A, C, F, L
TRU-COMP3710
Knowledge Representation
13
Search Trees – Missionaries & Cannibals






Three missionaries and three cannibals
Want to cross a river using one canoe.
Canoe can hold up to two people.
Can never be more cannibals than missionaries on either side of the
river.
Aim: To get all safely across the river without any missionaries being
eaten.
How to solve?
TRU-COMP3710
Knowledge Representation
14
Search Trees – Missionaries & Cannibals



The first step in solving the problem is to choose a suitable
representation, i.e., a state (a set of values of all instances).
We will show number of cannibals, missionaries and canoes on each
side of the river. All the objects.
Start state is therefore:





(# of missionaries, # of cannibals, # of boats)
(3,3,1) at the starting side; (0,0,0) at the ending side
In fact, since the system is closed, we only need to represent one side
of the river, as we can deduce the other side.
We will represent the finishing side of the river, and omit the starting
side.
So start state and goal state are:

(0,0,0), (3,3,1)
TRU-COMP3710
Knowledge Representation
15
Search Trees – Missionaries & Cannibals



Now we have to choose suitable operators that can be applied:
What are the possible states from (0, 0, 0)?
Can we build up a search tree?
TRU-COMP3710
Knowledge Representation
16
Search Trees – Missionaries & Cannibals

Cycles have been removed.



What does this mean?
Nodes represent states, edges
represent operators.
There are two shortest paths that lead
to the solution.
TRU-COMP3710
Knowledge Representation
17
Search Trees – Combinatorial Explosion

Problems that involve assigning values to a set of variables can grow
exponentially with the number of variables.


E.g., what is the total number of possible cases with
n variables and m values for each variable?
How about the 9 tile puzzle?

This is the problem of combinatorial explosion.
Some such problems can be extremely hard to solve (NP-Complete,
NP-Hard), i.e., it takes long time to solve.

What do we have to do then?


Selecting the correct representation can help to reduce this, as can using
heuristics (see chapter 4).
TRU-COMP3710
Knowledge Representation
18
Search Trees – Problem Reduction







Breaking a problem down into smaller subproblems (or sub-goals).
Can be represented using goal trees (or andor trees).
Nodes in the tree represent sub-problems.
The root node represents the overall problem.
Some nodes are and nodes, meaning all their
children must be solved.
E.g. to solve the Towers of Hanoi problem
with 4 disks, you can first solve the same
problem with 3 disks.
The solution is thus to get from the first
diagram on the left, to the second, and then to
apply the solution recursively.
TRU-COMP3710
Knowledge Representation
19
TRU-COMP3710
Knowledge Representation
20