Preview

• Means-Ends analysis and Problem reduction are very useful for well-defined problems.
• Both are problem-solving methods.

Means-Ends analysis and Problem Reduction are part of the fundamentals of KBAI

Exercise: The Block Problem

The real question is, how can we design an AI agent to come up and accomplish the series of operations.

State Space

State Space

A state space contains an initial state, a goal state, and many other states. We need to figure the path from the initial state to the goal state.

an example of state path

Differences in State Spaces

One way to find the path is at each state (current state), select an operation that will reduce the difference between the current state and the goal state (end). the application of the operator is the means. --> means-ends analysis.

Paste_Image.png

• from initial, there are three possible states can be generated, the distance of the states to the goal can be calculated.
• with each step, the distance between current state and the goal state are decreasing.

Process of Means-End Analysis in Summary

Quiz 1 Block Problem I

write all possible next states of the initial state calculate distance between each state to the goal

• so the AI agent need to choose the third option since Means-Ends analysis always seeks to reduce the distance.

number of possible states?

• there is only one state can reduce distance, that's moving "A" onto "B". But I could not lead to the goal state due to the fact that we can only move one block from the top if they were stacked together.

The states are all moving the state away from the goal

• Means-Ends analysis could not always lead us close to the goal.
• But the method is still a powerful method to many questions

---

Problem Reduction

Break hard problem into easy sub-problems The Block Problem: now the sub-goal is "C" over "D"

exercise with the sub-goal

a possible next states Distance to goal operation sequence to get to the sub-goal operation sequence to get to the goal

Once again, Problem reduction does not guarantee success.

Means-Ends Analysis for Raven's Problem Matrix

RMP v.s. Means-Ends Analysis

• The transformation between images can be expressed as the sequence of operators. The same operators are then applied to the other images.
• the correspondence of objects can be identified by relationship described by semantic networks. In the upper images, diamond inside a circle, in the lower image, circle inside the triangle. the correspondence are "Circle -> triangle" and "diamond -> circle".
• from the Problem Reduction point of view, the RPM problem is decomposed into three sub-goals: 1) extract operators from "A" to "B"; 2) apply the operators on "C" and come up with some candidates for "D"; and 3) test the candidates and select the best option.
• There is also "generate and test" method in the process.
• SN can support all the three problem-solving methods.
• These are the "weak" methods because the coupling of the method with the knowledge representation is weak.

recap

The methods introduced today are closely related to lecture 12 logic and lecture 13 planning.

2017-01-23 first draft