仓库源文，站点原文

layout: post title: "KBAI 笔记 05 Means-Ends Analysis and Problem Reduction" date: "2019-01-01 08:34:58" categories: 计算机科学 excerpt: "Preview Means-Ends analysis and Problem reduction are very useful for we..."

auth: conge

• content {:toc}

Preview

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

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

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.

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.

• 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

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

• 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.

• 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

exercise with the sub-goal

Once again, Problem reduction does not guarantee success.

Means-Ends Analysis for Raven's Problem Matrix

• 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.

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

2017-01-23 first draft