Artificial Intelligence Chapter 3: Problem Solving and Searching
This
chapter describes one kind of goal-based agent called a problem-solving
agent. Problem-solving agents use atomic representations, —that is,
states of the world are considered as wholes, with no internal structure
visible to the problem solving algorithms. Goal-based agents that use
more advanced factored or structured representations are usually called
planning agents.
Our discussion of problem solving begins with precise definitions of problems and their solutions and give several examples to illustrate these definitions. We then describe several
general-purpose search algorithms that can be used to solve these problems. We will see
several uninformed search algorithms—algorithms that are given no information about the
problem other than its definition. Although some of these algorithms can solve any solvable
problem, none of them can do so efficiently. Informed search algorithms, on the other hand,
can do quite well given some guidance on where to look for solutions.
Our discussion of problem solving begins with precise definitions of problems and their solutions and give several examples to illustrate these definitions. We then describe several
general-purpose search algorithms that can be used to solve these problems. We will see
several uninformed search algorithms—algorithms that are given no information about the
problem other than its definition. Although some of these algorithms can solve any solvable
problem, none of them can do so efficiently. Informed search algorithms, on the other hand,
can do quite well given some guidance on where to look for solutions.
Intelligent agents are supposed to maximize their performance measure. As we mentioned
in Chapter 2, achieving this is sometimes simplified if the agent can adopt a goal and aim at
satisfying it. Let us first look at why and how an agent might do this.
in Chapter 2, achieving this is sometimes simplified if the agent can adopt a goal and aim at
satisfying it. Let us first look at why and how an agent might do this.
Imagine an agent in the city of Arad, Romania, enjoying a touring holiday. The agent’s
performance measure contains many factors: it wants to improve its suntan, improve its Romanian, take in the sights, enjoy the nightlife (such as it is), avoid hangovers, and so on. The decision problem is a complex one involving many tradeoffs and careful reading of guidebooks. Now, suppose the agent has a nonrefundable ticket to fly out of Bucharest the following day. In that case, it makes sense for the agent to adopt the goalof getting to Bucharest. Courses of action that don’t reach Bucharest on time can be rejected without further consideration and the agent’s decision problem is greatly simplified. Goals help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider. Goal formulation, based on the current situation and the agent’s performance measure, is the first step in problem solving.
performance measure contains many factors: it wants to improve its suntan, improve its Romanian, take in the sights, enjoy the nightlife (such as it is), avoid hangovers, and so on. The decision problem is a complex one involving many tradeoffs and careful reading of guidebooks. Now, suppose the agent has a nonrefundable ticket to fly out of Bucharest the following day. In that case, it makes sense for the agent to adopt the goalof getting to Bucharest. Courses of action that don’t reach Bucharest on time can be rejected without further consideration and the agent’s decision problem is greatly simplified. Goals help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider. Goal formulation, based on the current situation and the agent’s performance measure, is the first step in problem solving.
Outline: Problem solving and search
•Introduction
to Problem Solving
•Complexity
•Uninformed
search
•Problem
formulation
•Search
strategies: depth-first, breadth-first
•Informed
search
•Search
strategies: best-first, A*
•Heuristic
functions
Download Full chapter From
https://www.scribd.com/doc/309049639/Artificial-Intelligence-Chapter-3-Problem-Solving-and-Searching
No comments:
Post a Comment