Intelligent Explorer – Q-Learning Robot Navigation in a Grid

King Fahd University of Petroleum and Minerals

College of Computing and Mathematics

COE 292

Introduction to Artificial Intelligence

Topic 02: Goal Trees and Problem Solving

Topic 2 COE 292 Introduction to Artificial Intelligence 2

❖ Problem solving

• Review

• Trees

❖ Problem Reduction

• Tower of Hanoi

• Symbolic Integration [The start of AI]

❖ Understanding Goal Trees

❖ Conclusion

Outline

Topic 2 COE 292 Introduction to Artificial Intelligence 3

❖ As we concluded from previous lectures, successful

problem solving is aided by:

• Choosing the best representation for the problem, e.g. using

visual perception

• Identifying the initial and goal states

• Identifying all possible states

• Exposing constraints

Problem solving - Review

Topic 2 COE 292 Introduction to Artificial Intelligence 4

❖ A tree is commonly encountered data structure that

allows representing nonlinear hierarchical

relationships.

❖ A tree is a collection of nodes connected using edges

where a single node represents a value, a state or

something meaningful.

Problem solving – Goal trees

Level 3

Level 2

Level 1

Level 0 1

2 3

4 5 6 7 8

9

Root

Leaf

Topic 2 COE 292 Introduction to Artificial Intelligence 5

❖ Properties of trees:

• A node may have multiple successors

• Nodes with at least one successor is called a

parent and its successors are called children

• A node without a child is called a leaf node

• A node that has no parent is called the root

• Depth of a tree is the length of the path from

the root node to the farthest leaf node

▪Depth of shown tree is 3;

▪ Number of edges in the longest path from the root

to a leaf node

Problem solving – Goal trees

Level 3

Level 2

Level 1

Level 0 1

2 3

4 5 6 7 8

9

Root

Leaf

Topic 2 COE 292 Introduction to Artificial Intelligence 6

❖ The process of transforming a complex problem into a

series of simpler or easier problems whose solutions

can be combined to solve the original problem.

Problem Reduction

❖ It involves:

• Decomposing a complex problem

into simpler sub-problems.

• Solving each sub-problem

individually.

• Combining the solutions to solve

the original problem.

Topic 2 COE 292 Introduction to Artificial Intelligence 7

❖ Example: Factorial Function (n!)

𝑓 𝑛 = 𝑛! = 𝑛 × 𝑛 − 1 !

= 𝑛 × 𝑓(𝑛 − 1)

Problem Reduction: Example

❖ In Programming (Python), a recursive

function is a function that calls itself

❖ Creating such functions require:

• Basic step or base case

• Recursive case

• # Non-Recursive definition

• def fac1(n):

• f = 1

• for i in range(n, 1, -1):

• f = f * i

• return f

• # Recursive definition

• def fac2(n):

• if n == 1 : # Base case

• return 1

• else: # Recursive case

• return n * fac2(n - 1) We can visualize the problem reduction process by using a tree

Topic 2 COE 292 Introduction to Artificial Intelligence 8

❖ In problem reduction, we will use the Generate and

Test methodology where we will try to generate

different sub-solutions (sub-goals) then test them to

see if the goal is reached

❖ We will also use a goal tree which is a form of tree

structure used to represent problems that can be

broken down into smaller problems

Problem Reduction

Topic 2 COE 292 Introduction to Artificial Intelligence 9

❖ The state at which the problem is

broken into different sets of

independent problems is referred to as

the AND node

• Example:

❖ Sometimes we have different ways to

solve the problem, so we use

and OR node like the one shown

• Example:

Problem Reduction: AND node vs. OR node

To solve S1,

we must

solve?

න 𝑥2 + 𝑥 + 1

න sin 𝑥 cos 𝑥 𝑑𝑥

න 1

2 sin 2𝑥 𝑑𝑥 න 𝑢 𝑑𝑢 𝑤ℎ𝑒𝑟𝑒 𝑢 = sin 𝑥

න 𝑥2 + න 𝑥 + න 1

Note that the AND node has the

arch while the OR node does not

Topic 2 COE 292 Introduction to Artificial Intelligence 10

AND-OR Shortcut

S1

S2

S3 S4 S5

S1

S2

S3 S4

S5

S’2

To solve S1, we must solve?

To solve S1, is it necessary to solve 3?

Topic 2 COE 292 Introduction to Artificial Intelligence 11

❖ The Tower of Hanoi is a classic recursive problem involving:

• 3 pins: Source (A), Auxiliary (B), Destination (C)

• n disks, stacked in decreasing size on the source pin

• The goal is to move all n disks from the source to the destination,

following 3 rules:

▪ Only one disk can be moved at a time (the uppermost disk on a stack)

▪ A disk can only be placed on top of a larger disk or an empty pin

• you cannot place a larger disk onto a smaller disk

❖ Example n = 3

Example: Tower Of Hanoi

Topic 2 COE 292 Introduction to Artificial Intelligence 12

❖ The Tree starts from the Initial state and details the

steps on how to reach the goal state

❖ The above Tree is up to the 2nd level, you can continue

until you reach the goal state.

Example of Tower of Hanoi

Level 0

Level 1

Level 2

depth

violate

constraints violate

constraints

Topic 2 COE 292 Introduction to Artificial Intelligence 13

Example of Tower of Hanoi

Topic 2 COE 292 Introduction to Artificial Intelligence 14

Example of Tower of Hanoi

Animation with n=4: https://www.openbookproject.net/py4fun/hanoi/hanoi3.html

Topic 2 COE 292 Introduction to Artificial Intelligence 15

❖ One possible solution (path from root to goal)

is shown on the left

❖ Attempt the problem if we have 7 disks instead of 3.

Example of Tower of Hanoi

The program is not intelligent, but it is programmed in a

way that makes it looks intelligent. The core algorithm is

only listing all possible combinations and eliminating

states that do not satisfy the input constraints.

If a computer program can give you the steps, is that

program "Intelligent"?

The minimal number of moves required to move n disks using 3 pins is 2n − 1

How about if moving up 2 disks is allowed?

Topic 2 COE 292 Introduction to Artificial Intelligence 16

❖ Goal Decomposition:

Example of Tower of Hanoi

Topic 2 COE 292 Introduction to Artificial Intelligence 17

❖ The root node, labeled “3AC” represents the original problem

of transferring all 3 disks from A to C.

❖ The goal can be decomposed into three sub-goals:

• 2AB, 1AC, 2BC.

• To achieve the goal, all 3 sub-goals must be achieved.

Example of Tower of Hanoi

3AC

Topic 2 COE 292 Introduction to Artificial Intelligence 18

Tower Of Hanoi – Detailed Solution

3AC

2AB 1AC 2BC

3AC

2AB

1AC

1AC 2BC

Topic 2 COE 292 Introduction to Artificial Intelligence 19

Tower Of Hanoi – Detailed Solution…

3AC

2AB

1AC 1AB

1AC 2BC

3AC

2AB

1AC 1AB 1CB

1AC 2BC

Topic 2 COE 292 Introduction to Artificial Intelligence 20

Tower Of Hanoi – Detailed Solution…

3AC

2AB 1AC

1AC 1AB 1CB

2BC

3AC

2AB 1AC 2BC

1AC 1AB 1CB 1BA

Topic 2 COE 292 Introduction to Artificial Intelligence 21

Tower Of Hanoi – Detailed Solution…

3AC

2AB 1AC 2BC

1AC 1AB 1CB 1BA 1BC

3AC

2AB 1AC 2BC

1AC 1AB 1CB 1BA 1BC 1AC

Topic 2 COE 292 Introduction to Artificial Intelligence 22

Tower Of Hanoi – Summary

3AC

2AB 1AC 2BC

1AC 1AB 1CB 1BA 1BC 1AC

The depth of the generated goal tree

required to move 3 disks is

The number of leaf nodes is

2 ?

7 ?

A gool tree for solving Tower of Hanoi using

the problem reduction method.

Total number of nodes is 10 ?

How about more pins; e.g. 4?

?

These are the AND-subgoals (all 3 steps must be

completed to achieve the main goal)

? ?

#moves always odd

Topic 2 COE 292 Introduction to Artificial Intelligence 23

❖ Draw goal tree for 𝑛 = 4 disks and 3 pins?

Pop-up Question

4AC

3AB

2AC 1AB 2CB

1AB 1AC 1BC 1CA 1CB 1AB

3BC

2BA 1BC 2AC

1BC 1BA 1CA 1AB 1AC 1BC

1AC

Hanoi(k)

Hanoi(n)

Topic 2 COE 292 Introduction to Artificial Intelligence 24

# Recursive Python function to solve the tower of hanoi

def TowerOfHanoi(n , source, destination, auxiliary):

if n==1:

print ("Move disk 1 from source",source,"to destination",destination)

return

TowerOfHanoi(n-1, source, auxiliary, destination)

print ("Move disk",n,"from source",source,"to destination",destination)

TowerOfHanoi(n-1, auxiliary, destination, source)

Example of Tower of Hanoi

# Driver code n = 3 TowerOfHanoi(n,'A','C','B') # A, C, B are the names of rods

# Base case

#Recursive case

The basic step/operation (irreducible) in Tower of Hanoi is moving one disk.

In the code, it is represented by “print” statement.

Move disk 1 from source A to destination C

Move disk 2 from source A to destination B

Move disk 1 from source C to destination B

Move disk 3 from source A to destination C

Move disk 1 from source B to destination A

Move disk 2 from source B to destination C

Move disk 1 from source A to destination C

Recursive calls ?

Basic steps?

Symbolic Integration using Problem Reduction

Topic 2 COE 292 Introduction to Artificial Intelligence 26

❖ The start of AI was with

Symbolic Integration

❖ Can you integrate the

following equation:

Symbolic Integration using Problem Reduction

න −5𝑥4

(1 − 𝑥2)5/2 𝑑𝑥

# Equation

a. න 1

𝑥 𝑑𝑥 = ln 𝑥

b. ׬ 𝑥𝑛 𝑑𝑥 = 𝑥𝑛+1

𝑛+1

c. න cos 𝑥 𝑑𝑥 = sin 𝑥

… …

• Given that you have an integral table as

the following:

• Apply Known Rules of Integration

• Decompose Complex Functions

(Reduction)

• Integration by Parts

• Substitution

• Partial Fraction

Topic 2 COE 292 Introduction to Artificial Intelligence 27

❖ Modeling the way a human solves an integration

problem

❖ Solution approach:

• Simplify the integral given to an easier problem that will help

us in solving the integral

❖ Problem Reduction will utilize a known transform to

reduce the original problem to a simpler one.

• We will denote each step of problem reduction by a Node

❖ Review your calculus basics!

Symbolic Integration using Problem Reduction

Topic 2 COE 292 Introduction to Artificial Intelligence 28

❖ Safe Transformations: always good to do

Review of Integration Facts

No Name Safe Transform

1. Sign Rule න −𝑓 𝑥 𝑑𝑥 = − න 𝑓 𝑥 𝑑𝑥

2. Constant

Rule න 𝑐𝑓 𝑥 𝑑𝑥 = 𝑐 න 𝑓 𝑥 𝑑𝑥

3. Sum Rule න ෍ 𝑓 𝑥 𝑑𝑥 = ෍ න 𝑓 𝑥 𝑑𝑥

4. Division ׬

𝑃(𝑥)

𝐺(𝑥) ➔ Divide (if the degree of 𝑃(𝑥) is greater than the

degree of 𝐺(𝑥) perform long division

Note that point 1 and 2 are the same but we will treat them differently for

ease of understanding

Topic 2 COE 292 Introduction to Artificial Intelligence 29

❖ Heuristic Transformations:

• Sometimes useful, do not always work

Review of Integration Facts

No Name Heuristic Transform

A. Trigonometric 𝑓 sin 𝑥 , cos 𝑥 , tan 𝑥 , csc 𝑥 , sec 𝑥 , cot 𝑥 = 𝑔1 sin 𝑥 , cos 𝑥 = 𝑔2 tan 𝑥 , csc 𝑥 = 𝑔3 cot 𝑥 , sec 𝑥

B. Trigonometric

to polynomial න 𝑓 tan 𝑥 𝑑𝑥 = න

𝑓 𝑦

1 + 𝑦2 𝑑𝑦

C. Polynomial to

trigonometric

If you see the term 1 − 𝑥2 in an integral do a substitution

of 𝑥 = sin 𝑦

D. Polynomial to

trigonometric

If you see the term 1 + 𝑥2 in an integral do a substitution

of 𝑥 = tan 𝑦

Topic 2 COE 292 Introduction to Artificial Intelligence 30

Trigonometric Identities

Reciprocal identities

Pythagorean identities Sum and Difference Identities

Product to sum formulas

sin 𝐴 ± 𝐵 = sin 𝐴 cos 𝐵 ± cos 𝐴 sin(𝐵)

cos 𝐴 ± 𝐵 = cos 𝐴 cos 𝐵 ∓ sin 𝐴 sin(𝐵)

tan 𝐴 ± 𝐵 = tan (A) ± tan (B)

1∓tan (A) tan (B)

cos 𝐴 cos 𝐵 = 1

2 cos 𝐴 − 𝐵 + cos(𝐴 + 𝐵)

sin 𝐴 sin 𝐵 = 1

2 cos 𝐴 − 𝐵 − cos(𝐴 + 𝐵)

sin 𝐴 cos 𝐵 = 1

2 sin 𝐴 + 𝐵 + sin(𝐴 − 𝐵)

cos 𝐴 sin 𝐵 = 1

2 sin 𝐴 + 𝐵 − sin(𝐴 − 𝐵)

Topic 2 COE 292 Introduction to Artificial Intelligence 31

❖ We will use Generate and test methodology as shown below:

Solving the Symbolic Integration Problem

Look in

the table

for a

solution

Apply safe

transformation

Apply Heuristic

transformation

Find a problem to

work on

If n

o s

o lu

ti o n

If s

af e

tr an

sf o rm

at io

n c

an

b e

ap p li

ed

If no safe transformation

can be applied

Start

If solution

found

Done

Topic 2 COE 292 Introduction to Artificial Intelligence 32

❖ The original integration problem can be simplified to:

න −5𝑥

4

1 − 𝑥2 5/2 𝑑𝑥 → න

5𝑥 4

1 − 𝑥2 5/2 𝑑𝑥 → න

𝑥 4

1 − 𝑥2 5/2 𝑑𝑥

❖ Using the safe transforms

න −𝑓(𝑥)𝑑𝑥 = − න 𝑓(𝑥)𝑑𝑥 , න 𝑐𝑓(𝑥)𝑑𝑥 = 𝑐 න 𝑓(𝑥)𝑑𝑥 𝑓

❖ The reduced problem is simpler now but still

significantly hard, need more transformations

Symbolic Integration Problem

A B C

A

B

C

Topic 2 COE 292 Introduction to Artificial Intelligence 33

❖ By substituting Heuristic Transformation (C) and (A) 𝑥 = sin 𝑦

𝑑𝑥 = cos 𝑦𝑑𝑦

𝑓 sin 𝑥 , cos 𝑥 , tan 𝑥 , csc 𝑥 , sec 𝑥 , cot 𝑥

= 𝑔 sin 𝑥 , cos 𝑥 = 𝑔 tan 𝑥 , csc 𝑥

❖ The problem can be simplified to:

׬ 𝑥

4

1−𝑥2 5/2 𝑑𝑥 → ׬

sin 4

𝑦

1−sin2 𝑦 5/2 cos 𝑦𝑑𝑦 → ׬

sin 4

𝑦

cos4 𝑦 𝑑𝑦

❖ The integration ׬ sin4 𝑦

cos4 𝑦 𝑑𝑦 can be reduced to solving either

• ׬ 1

cot4 𝑦 𝑑𝑦, or

• ׬ tan4 𝑦 𝑑𝑦

Symbolic Integration Problem

which one will you choose?

A

B

C

D

E

F G

G

D EC

F

Topic 2 COE 292 Introduction to Artificial Intelligence 34

❖ Using the Heuristic Transformation (B) we get

׬ 𝑓(tan(𝑥))𝑑𝑥 = ׬ 𝑓(𝑦)

1+𝑦2 𝑑𝑦

❖ and substituting (𝑧 = tan(𝑦)) we can write

׬ tan4 𝑦𝑑𝑦 → ׬ 𝑧4

1+𝑧2 𝑑𝑧

❖ Since the power of the numerator is larger than the power of

the denominator, we can simplify by doing long division (safe

transformation 4), thus the equation is further simplified to:

׬ 𝑧

4

1+𝑧2 𝑑𝑧 → ׬ 𝑧

2 − 1 +

1

1+𝑧2 𝑑𝑧

Symbolic Integration Problem

A

B

C

D

E

F G

H

I

H

IH

Topic 2 COE 292 Introduction to Artificial Intelligence 35

❖ Using Safe Transformation 3 (Integral Sum Rule) we can write:

׬ 𝑧2 − 1 + 1

1+𝑧2 𝑑𝑧 → ׬ 𝑧2𝑑𝑧 + ׬ −𝑑𝑧 + ׬ 1

1+𝑧2 𝑑𝑧

❖ The first can be found using: Done

׬ 𝑥𝑛𝑑𝑥 = 𝑥𝑛+1

𝑛+1

❖ The second term can be simplified using:

׬ −𝑓(𝑥)𝑑𝑥 = − ׬ 𝑓(𝑥)𝑑𝑥

❖ Let us concentrate on the third term:

׬ 1

1+𝑧2 𝑑𝑧

Symbolic Integration Problem

A

B

C

D

E

F G

H

I

J K M

J K M

L

Topic 2 COE 292 Introduction to Artificial Intelligence 36

❖ By doing the following substitution

𝑧 = tan 𝑤 → 𝑑𝑧 = 1

cos2 𝑤 𝑑𝑤

❖ We can write:

׬ 1

1+𝑧2 𝑑𝑧 → ׬ 1

1+tan2𝑤 ×

1

cos2 𝑤 𝑑𝑤 → ׬

1

sec2 𝑤 sec2𝑤𝑑𝑤 → ׬ 𝑑𝑤 = 𝑤

❖ The above can be solved using

׬ 𝑥𝑛𝑑𝑥 = 𝑥𝑛+1

𝑛+1 ∎

Symbolic Integration Problem

A

B

C

D

E

F G

H

I

J K

L

M

N

N

Topic 2 COE 292 Introduction to Artificial Intelligence 37

❖ Rearranging nodes with symbols we get

❖ A Goal Tree

Symbolic Integration Problem - Goal Trees

A

B

C

D

E

F G

H

I

J K

L

M

N The solution to problem A …

AND node

Topic 2 COE 292 Introduction to Artificial Intelligence 38

❖ General Tree structure

• A tree has nodes and edges where edges connect two

nodes within the tree

• A branch appears when the node has more than one edge.

AND/OR node

• Root: the original problem

• Edges: transformation or rules applied

• Leaf nodes: solved sub-problems (part of the solution), or

unsolved sub-problems (not part of the solution)

• Internal nodes: sub-problems

• A tree depth is 9: the number of transformations to reach

to the solution

Understanding Goal Trees:

A

B

C

D

E

F G

H

I

J K

L

M

N

?

Topic 2 COE 292 Introduction to Artificial Intelligence 39

❖ In the integration program, the following was observed:

• Problem Set: The program was tested on 56 freshman-level integration problems.

• Success Rate: 54 out of 56 problems were successfully solved.

• Tree Depth:

▪ Worst-case depth: 9

▪ Average depth: 3, suggesting efficient solution paths.

▪ Unused branches: path that was did not need to solve it to produce a solution, e.g. Node F

Understanding Goal Trees

A

B

C

D

E

F G

H

I

J K

L

M

N

Topic 2 COE 292 Introduction to Artificial Intelligence 40

❖ Tree depth gives a lot of information such as:

• Problem complexity: Greater depth means more steps, indicating a more complex problem.

• Identifying the level of intelligence: An entity (such as a person, computer, etc.) that can solve higher

depth problems is more intelligent than programs that solve less depth problems

• Solution comparison: Among several solutions to a problem, the one with the shortest tree is smarter

❖ Considering tree depth as the shortest depth to finding a solution, If we

have different programs and

• Same problem: A shorter solution = smarter program.

• Different problems: the larger the maximum depth each program could solve, the smarter program.

▪ We can also consider how many times each program produced a goal tree depth exactly equal to the

actual problem depth or the difference between each program's depth and the actual depth

❖ Goal trees also help us answer:

• “How” question: Go down the tree (step-by-step breakdown).

• “Why” question: Go up the tree (purpose of a step).

Understanding Goal Trees

Topic 2 COE 292 Introduction to Artificial Intelligence 41

❖ Start with safe transformations, the ones that are guaranteed to simplify or

solve part of the integration problem.

❖ Then apply heuristic transformations, the ones that could work.

❖ As you apply transformations, you are transforming the main problem

into smaller subproblems.

❖ This simplification schema, may create

• "and node“: the problem splits into multiple sub-problems (all must be solved)

• "or node“: the problem can be solved by one of several possible transformations.

❖ The resulting schema is usually called a "problem reduction tree", "and/or

tree" or "goal tree".

❖ Note: In an "OR node, consider how many transformations are needed after

choosing an option and how simple each option is to solve.

Strategy to Solve Symbolic Integration Summary

Topic 2 COE 292 Introduction to Artificial Intelligence 42

1.Start by evaluating what kind of knowledge is involved.

[Integration Tables; Transformations; Goal Tree]

2.Understand how the knowledge is represented. Each category

of knowledge has its own way of being represented.

[Expressions; Tables; Goal Trees as Procedures]

3.Know how the knowledge is used.[Transformations to make

problems simpler; Integration Tables to trim bottom of Tree]

4.Know how much knowledge is required to solve the problem.

[26 integration tables; 12 safe transformations; 12 heuristic

transformations]

To get the Goal Tree of a Certain Problem

Topic 2 COE 292 Introduction to Artificial Intelligence 43

❖ Many problems can be visually represented in form of

goal trees

❖ Trees aid our understanding of the problem and show

the difficulty of the problem by looking at the depth of

the tree

❖ A Goal Tree program can answer questions about its

own behavior by reporting steps up (why questions)

or down (how questions) in the actions it takes.

Conclusion