29-02-2012, 02:14 PM
Principles of Arti cial Intelligence
[attachment=17789]
Goal-Based Agents
In this chapter, we consider the design of goal-based agents. The speci cation and design of goal-based
agents involves answering the following questions:
1. What is the goal to be achieved? This involves describing a situation we want to achieve, a set of
properties that we want to hold (when the agent succeeds at its goal), etc. This requires de ning a goal
test so which captures what it means to have achieved/satis ed the goal. While in some domains (e.g.,
chess) it is rather straightforward to specify the goal test, in others, it is not as obvious and requires
considerable thought. In general, the cognitive processes having to do with goal selection and goal
speci cation in humans and animals are poorly understood. Consequently, the design of autonomous
systems that select, prioritize, and update their goals is largely an unsolved problem in AI. In what
follows, we assume that the system designer or user will specify the goal to be achieved.
2. What are the actions that are available to the agent? We need to specify precisely all of the primitive
actions (including their preconditions and their expected e ects on the environment) that are sucient
(at least in principle) to achieve the goal. Early AI systems assumed that given an action (also called
an operator) and a description of the current state of the world, the action completely speci es the
conditions under which the action can be applied to the current world as well as the the exact state
of the world after the action is executed in the current world. Actions were viewed as atomic, discrete
events that can be thought of as occurring at an instant in time. Thus, the world is in a state before the
action is executed, and it makes a transition to a di erent state (speci ed implicitly or explicitly by the
e ects of the action) once the action is executed. For example, if \Mary is in class" and she performs
the action \go home" she will end up \at home."
2 Problem Solving as Search
A wide range of problems in AI|including, among others, theorem proving, game playing, planning, and
learning|can be formulated at an abstract level as essentially search problems.
As noted above, representation is a key issue in problem solving. Consider 17 sticks arranged in 6 squares
as shown in Figure 1. Suppose we are asked to remove just 5 sticks so that we are left with only 3 squares
(with no extra sticks). The number of possible ways is
5 . However, the problem could be represented as
that of removing 3 squares from the current con guration of 6 squares. The number of possibilities is just
3which is considerably smaller. Also note that the preceding discussion implicitly assumed that the squares
have to be of the same size. Thus, representation plays a key role in the formulation of search problems.
Pseudocode for a General Class of Search Algorithms
1. Let L = list of nodes yet to be examined (initialized to start node S).
2. If L is empty return FAIL.
Else, pick a node (n) in L.
3. If n is a goal node (i.e. n 2 G ), stop and return the path from S to n.
4. Otherwise remove the node n from L.
Add to L all of n's children labeling each with the corresponding path from
Return to step 2.
NOTE: If L is a queue we get BFS and if L is a stack we get DFS. In general, search algorithms di er
in terms of steps 2 and 4 are handled.
3.2 Analysis of Breadth-First Search and Depth-First Search
The search strategies are analyzed in terms of four criteria:
Space complexity: amount of memory during run-time
Time complexity: amount of time to nd a solution
Completeness: the search strategy is guaranteed to nd a solution, if one exists (at a nite depth)
Admissibility: the search strategy is guaranteed to nd the optimal (cheapest)solution if such a solu-
tion exists.
[attachment=17789]
Goal-Based Agents
In this chapter, we consider the design of goal-based agents. The speci cation and design of goal-based
agents involves answering the following questions:
1. What is the goal to be achieved? This involves describing a situation we want to achieve, a set of
properties that we want to hold (when the agent succeeds at its goal), etc. This requires de ning a goal
test so which captures what it means to have achieved/satis ed the goal. While in some domains (e.g.,
chess) it is rather straightforward to specify the goal test, in others, it is not as obvious and requires
considerable thought. In general, the cognitive processes having to do with goal selection and goal
speci cation in humans and animals are poorly understood. Consequently, the design of autonomous
systems that select, prioritize, and update their goals is largely an unsolved problem in AI. In what
follows, we assume that the system designer or user will specify the goal to be achieved.
2. What are the actions that are available to the agent? We need to specify precisely all of the primitive
actions (including their preconditions and their expected e ects on the environment) that are sucient
(at least in principle) to achieve the goal. Early AI systems assumed that given an action (also called
an operator) and a description of the current state of the world, the action completely speci es the
conditions under which the action can be applied to the current world as well as the the exact state
of the world after the action is executed in the current world. Actions were viewed as atomic, discrete
events that can be thought of as occurring at an instant in time. Thus, the world is in a state before the
action is executed, and it makes a transition to a di erent state (speci ed implicitly or explicitly by the
e ects of the action) once the action is executed. For example, if \Mary is in class" and she performs
the action \go home" she will end up \at home."
2 Problem Solving as Search
A wide range of problems in AI|including, among others, theorem proving, game playing, planning, and
learning|can be formulated at an abstract level as essentially search problems.
As noted above, representation is a key issue in problem solving. Consider 17 sticks arranged in 6 squares
as shown in Figure 1. Suppose we are asked to remove just 5 sticks so that we are left with only 3 squares
(with no extra sticks). The number of possible ways is
5 . However, the problem could be represented as
that of removing 3 squares from the current con guration of 6 squares. The number of possibilities is just
3which is considerably smaller. Also note that the preceding discussion implicitly assumed that the squares
have to be of the same size. Thus, representation plays a key role in the formulation of search problems.
Pseudocode for a General Class of Search Algorithms
1. Let L = list of nodes yet to be examined (initialized to start node S).
2. If L is empty return FAIL.
Else, pick a node (n) in L.
3. If n is a goal node (i.e. n 2 G ), stop and return the path from S to n.
4. Otherwise remove the node n from L.
Add to L all of n's children labeling each with the corresponding path from
Return to step 2.
NOTE: If L is a queue we get BFS and if L is a stack we get DFS. In general, search algorithms di er
in terms of steps 2 and 4 are handled.
3.2 Analysis of Breadth-First Search and Depth-First Search
The search strategies are analyzed in terms of four criteria:
Space complexity: amount of memory during run-time
Time complexity: amount of time to nd a solution
Completeness: the search strategy is guaranteed to nd a solution, if one exists (at a nite depth)
Admissibility: the search strategy is guaranteed to nd the optimal (cheapest)solution if such a solu-
tion exists.
