Artificial Intelligence 1
In Artificial Intelligence the terms problem solving and search refer to a large body of core ideas that deal with deduction, inference, planning, commonsense reasoning, theorem proving, and related processes. Applications of these general ideas are found in programs for natural language understanding, information retrieval, automatic programming, robotics, scene analysis, game playing, expert systems, and mathematical theorem proving.
Problem-Solving Systems
Three components of problem-solving systems are database, operators and control strategy.
Database
The database can consist of a variety of different kinds of data structures including arrays, lists, sets of predicate calculus expressions, property list structures, and semantic networks. In robot problem solving, a current situation is a world model consisting of statements describing the physical surroundings of the robot, and the goal is a description that is to be made true by a sequence of robot actions.
Operators
The second component of problem-solving systems is a set of operators that are used to
manipulate the database. Sometimes the set of operators consists of only a few general rules of inference that generate new assertions from existing ones.
Control Strategy
The third component of a problem-solving system is a control strategy for deciding what
to do next—in particular, what operator to apply and where to apply it. Control strategy can investigate various operator sequences in parallel or alternately choose among number of sequences that look relatively promising. The assumption is having a database containing descriptions of multiple task-domain situations or states. If description of a task-domain situation is too large for multiple versions to be stored explicitly, it can use backtracking.
Reasoning Forward & Backward
Forward reasoning is application of operators to those structures in the database that describe the task-domain situation—to produce a modified situation towards goal. Reasoning backward is when the goal statement, or problem statement, is converted to one or more subgoals that are easier to
solve and whose solutions are sufficient to solve the original problem. These subgoals may in
turn be reduced to sub-subgoals, and so on, until each of them is either accepted to be a trivial problem or its solution is accomplished by the solution of its subproblems.
Bottom-up & Top-down Approaches
The former approach is said to use forward reasoning and to be data-driven or bottom-up. The latter uses backward reasoning and is goal-directed or top-down. The distinction between forward and backward reasoning assumes that the current task-domain situation or state is distinct from the goal.
Means-ends Analysis
Means-ends analysis combines the two. it involves comparing the current goal with a current task-domain situation to extract a difference between them. This difference is then used to index that (forward) operator most relevant to reducing the difference. If this especially relevant operator cannot be immediately applied to the present problem state, subgoals are set up to change the problem state so that the relevant operator can be applied. After these subgoals are solved, the relevant operator is applied and the resulting, modified situation becomes a new starting point from which to solve for the original goal.
State-space Representation
A problem-solving system that uses forward reasoning and whose operators each work by producing a single new object—a new state—in the database is said to represent problems in a state-space representation.
A state space can be treated as a directed graph whose nodes are states and whose arcs are operators transforming one state to another.
The complete specification of a state-space problem has three components. One is a set 0 of operators or operator schemata. In addition, one must define a set S of one or more initial states and find a predicate defining a set G of goal states. A state-space problem is then the triple (S, 0, G). A solution to the problem is a finite sequence of applications of operators that changes an initial state into a goal state.
A common variation on state-space problems requires finding not just any path but one of minimum cost between an initial node and a goal node. In this case, each arc of the graph is labeled with its cost. Because the state-space graph is usually too large to represent explicitly, the problem of searching for a solution becomes one of generating just enough of the graph to contain the desired solution path.
Problem-reduction Representation
A system using backward reasoning, distinguished by the fact that its operators can change a single object into a conjunction of objects, will be said to employ a problem reduction representation. The transformations permitted are defined as operators. An operator may change a single problem into several subproblems; to solve the former, all the subproblems must be solved. Several different operators may be applicable to a single problem, or the same operator may be applicable in several different ways. A problem whose solution is immediate is called a primitive problem. Such representation consists of, initial problem, operators for transformation and set of primitive problems.
Game Tree
A game-playing problem must be represented so as to take into account the opponent's possible moves as well as the player's own. The usual representation is a game tree, which shares many features of a problem-reduction representation.
Theorem-proving Representation
Another variation is relevant to theorem-proving systems, many of which use forward reasoning and operators (rules of inference) that act on conjunctions of objects in the database. It is possible to define a theorem-proving representation that provides for multiple-input, single-output operators
Graph Representation
In either a state-space or a problem-reduction representation, achieving the desired goal can be equated with finding an appropriate finite sequence of applications of available operators. a tree may be used to represent the set of problem states produced by operator applications. The root node of the tree represents the initial problem situation or state. Each of the new states that can be produced from this initial state by the application of just one operator is represented by a successor node of the root node. Subsequent operator applications produce successors of these nodes, etc. Each operator application is represented by a directed arc of the tree.
In general, the states are represented by a graph rather than by a tree since there may exist different paths from the root to any given node. For problems in which the goal can be reduced to sets of subgoals, AND/OR graphs provide a means for keeping track of which subgoals have been attempted and of combinations of subgoals which are sufficient to achieve the original goal.
Search Space
Producing a goal-condition state is conducted by searching a graph to find a satisfying node . For problem-reduction on the other hand we use AND/OR graph.
If it is already established graph or tree that we will apply search algorithm to find out the goal node. The implicit graph will be called the state space or, if generalized to cover non-state-space representations such as AND/OR graphs or game trees, the search space.
Search Graph or Search Tree
If we are constructing a tree or graph as the search proceeds, so at a particular state, the only nodes included are those for which paths from the initial state have actually been discovered so far, we explicitly refer to it search graph or search tree.
Combinatorial Explosion
Examining all sequences of n moves, for example, would require operating in a search space in which the number of nodes grows exponentially with n. Such a phenomenon is called a combinatorial explosion.
Heuristic Rule
A heuristic (heuristic rule, heuristic method) is a rule of thumb, strategy, trick, simplification, or any other kind of device which drastically limits search for solutions in large problem spaces. Heuristics do not guarantee optimal solutions; in fact, they do not guarantee any solution at all; all that can be said for a useful heuristic is that it offers solutions which are good enough most of the time.
Heuristic Search
It is a key contributor to AI for efficient problem-solving. Some graph-searching methods can use heuristic knowledge from the problem domain to help focus the search
Blind search corresponds approximately to the systematic generation and testing of search space elements, but it operates within a formalism that leaves room for additional information about the specific problem domain to be introduced, rather than excluding it by definition. If such
information, going beyond that needed merely to formulate a class of problems as search problems, is in fact introduced, it may be possible to restrict search drastically. Whether or not the restriction is foolproof, the search is then called heuristic rather than blind.
STRIPS/APSTRIPS/Planning
STRIPS augments its initial set of operators by discovering, generalizing, and remembering
macro-operators, composed of sequences of primitive operators, as it gains problem-solving
experience. ABSTRIPS program implements the idea of planning, in the sense of defining and solving problems in a search space from which unimportant details have been omitted.
AND/OR Graphs
It is constructed following,
1. Each node represents either a single problem or a set of problems to be solved. The graph contains a start node corresponding to the original problem.
2. A node representing a primitive problem, called a terminal node, has no descendants.
3. For each possible application of an operator to problem P, transforming it to a set of subproblems, there is a directed arc from P to a node representing the resulting subproblem set.
4. If P can be solved by any one of sets A, B, or C can be solved, then A, B, and C are called OR nodes.
5. If a set of subproblems can be solved only if its members can all be solved, the subproblem nodes are called AND nodes. To distinguish them from OR nodes, the arcs leading to AND node successors of a common parent are joined by a horizontal line.
Solution Graph/Solution Tree
To find a solution to the initial problem, we limit the graph to demonstrate only partially enough that the start node can be solved. Such a subgraph is called a solution graph or, in the more restricted case of an AND/OR tree, a solution tree.
Solvable/Unsolvable Node
A node is solvable if:
Similarly, a node is unsolvabie if:
State Space to Problem Reduction
There can be 2 approaches. The graph becomes an AND/OR graph with only OR nodes. Data structures representing states are simply problem descriptions consisting state information along with an implicit goal.
The other variation is redefining operators. Each such operator, taking state i to state j, becomes an operator applicable to the problem of getting from state i to a goal state.
Problem Reduction to State Space
It has 2 components, (a) the description of the goal to be achieved and (b) the initial state. Each state S of the corresponding state-space representation is a pair consisting of a stack of goals (gi, ..., gO) to be achieved and a current state s of the world. So the final state will be with empty stack of goals. For that, we also need another operator, which becomes applicable whenever the goal on top of the stack represents a primitive problem. Its function is to remove that primitive problem from the stack and, at the same time, to change the state s to reflect its solution.
Game Tree
A complete game tree is a representation of all possible plays of a 2-player game. An AND/OR tree is sufficient to reflect this opposition. The root node is the initial state, in which it is the first player's turn to move. Its successors are the states he can reach in one move, represented by OR nodes; their successors are the states resulting from the other player's possible replies which are AND
nodes, since they represent sets of moves to which player one must be able to respond. Terminal states are those representing a win, loss, or draw. Each path from the root node to a terminal node gives a different complete play of the game. Because the players take turns, OR nodes and AND nodes appear at alternate levels of the tree. In the language of AND/OR graphs, the tree displays the search space for the problem of showing that player one can win. A node representing such win corresponds to a primitive problem; a node representing a win for opponent or a draw, is an unsolvabie problem.
Blind State-space Search
(S, 0, G), where S is a set of one or more initial states, 0 is a set of operatorson states, and G is a set of goal states.
The state space is commonly identified with a directed graph in which each node is a state and each arc represents the application of an operator transforming a state to a successor state. A solution is a path from a start state to a goal state. Goal states may be defined either explicitly or as the set of states satisfying a given predicate.
The search for a solution is conducted by making just enough of the state-space graph explicit to contain a solution path. If the order in which potential solution paths are considered is arbitrary, using no domain-specific information to judge where the solution is likely to lie, the search is called blind search.
Assumptions:
A procedure exists for finding all the successors of a given node—that is, all the states that can be reached from the current state by a single operator application. Such a procedure is said to expand the given node.
The state-space graph is a tree. The implication is that there is only one start state (the root) and that the path from the start node to any other node is unique.
Whenever a node is expanded, creating a node for each of its successors, the successor nodes contain pointers back to the parent node. When a goal node is finally generated, this feature makes it possible to trace the solution path.
Breadth-first Search
It considers every possible operator sequence of length n before any sequence of length n+l. Thus, although the search may be an extremely long one, it is guaranteed eventually to find the shortest
possible solution sequence if any solution exists.
(1) Put the start node on a list, called OPEN, of unexpended nodes. If the start node is a goal node, the solution has been found. (2) If OPEN is empty, no solution exists. (3) Remove the first node, n, from OPEN and place it in a list, called CLOSED, of expanded nodes. (4) Expand node n. If it has no successors, go to (2). (5) Place all successors of node n at the end of the OPEN list. (6) If any of the successors of node n is a goal node, a solution has been found. Otherwise, go to (2).
Uniform-cost Search
Add a nonnegative cost with every arc, that will enable finding the cheapest path. If all arcs have
equal cost, the algorithm reduces to breadth-first search.
(1) Put the start node, s, on a list called OPEN of unexpanded nodes. If the start node is a goal node, a solution has been found. Otherwise, set g(s) = 0. (2) If OPEN is empty, no solution exists.
(3) Select from OPEN a node i such that g(i) is minimum. If several nodes qualify, choose node i to be a goal node if there is one; otherwise, choose among them arbitrarily. Move node i from OPEN to a list, CLOSED, of expanded nodes. (4) If node i is a goal node, the solution has been found. (5) Expand node i. If it has no successors, go to (2). (6) For each successor node j of node i, compute g(j) = g(i) + c(i,j) and place all the successor nodes j In OPEN. (7) Go to (2).
Depth-first Search
The depth of a node in a tree is defined as follows:
The depth of the start node is 0.
The depth of any other node is one more than the depth of its predecessor.
To prevent consideration of paths that are too long, a maximum is often placed on the depth of nodes to be expanded. Even if such a depth bound is used, the solution path found is not necessarily the shortest one.
(1) Put the start node on a list, OPEN, of unexpended nodes. If it is a goal node, a solution has been found. (2) If OPEN is empty, no solution exists. (3) Move the first node, n, on OPEN to a list CLOSED of expanded nodes. (4) If the depth of node n is equal to the maximum depth, go to (2).
(5) Expand node n. If it has no successors, go to (2). (6) Place all successors of node n at the beginning of OPEN. (7) If any of the successors of node n is a goal node, a solution has
been found. Otherwise go to (2).
Bidirectional Search
Combine backward reasoning with, fully described goal state in advance and easily applicable inverse operators and replace a single search graph, which is likely to grow exponentially,by
two smaller graphs: one starting from the initial state and one starting from the goal. The
search terminates (roughly) when the two graphs Intersect. Bidirectional search can be blind or heuristic.
S-OPEN and S-CLOSED are lists of unexpended and expanded nodes, respectively, generated from the start node. T-OPEN and T-CLOSED are lists of unexpended and expanded nodes, respectively, generated from the terminal node. The cost associated with the arc from node n to node x is denoted c(n,x). For a node x generated from the start node, gs(x) measures the shortest path found so far from a to x. For a node x generated from the terminal node, gt(x) measures the shortest path found so far from x to t.
(1) Put s in S-CLOSED, with gs(s) = 0. Expand node s, creating a node for each of its successors. For each successor node x, place x on S-OPEN, attach a pointer back to s, and set gs(x) to c(s,x). Correspondingly, put t in TCLOSED, with gt(t) *0. Expand node t, creating a node for each of its
predecessors. For each predecessor node x, place x on T-OPEN, attach a pointer forward to t, and set gt(x) = c(x,t).
(2) Decide whether to go forward or backward. If forward, go to (3); if backward, to (4). (move backward if T-OPEN contains fewer nodes than SOPEN; otherwise, forward. It is assumed that a solution path does exist, so the chosen list will be nonempty.)
(3) Select from S-OPEN a node n at which gs(n) is minimum. Move n to SCLOSED.
If n is also In T-CLOSED, go to (5). Otherwise, for each successor x of n:
(4) Select from T-OPEN a node n at which gt(n) is minimum. Move n to T-CLOSED
If n is also in S-CLOSED, go to (5). Otherwise, for each predecessorx of n:
(5) Consider the set of nodes that are in both S-CLOSED and either T-CLOSED or T-OPEN. Select from this set a node n for which gs(n) + gt(n) is minimum; and exit with the solution path obtained by tracing the path from n back to s and forward to t.
Blind AND/OR Graph Search
Each OR node successor of node n represents a set of subproblems. If the set of subproblems represented by an OR node m has more than one element, then there are directed arcs from m to nodes representing the individual elements of the set. These successors are called AND nodes.
A node or problem is said to be solved if one of the following conditions holds:
1. The node is in the set of terminal nodes. 2. The node has AND nodes as successors and all these successors are solved. 3. The node has OR nodes as successors and any one of these successors is solved.
A node is said to be unsolvabie if one of the following conditions is true:
1 . The node has no successors and is not in the set of terminal nodes. 2. The node has AND nodes as successors and one or more of these successors is unsolvabie. 3. The node has OR nodes as successors and all of these succesors are unsolvable.
BFS of AND/OR Tree
(1) Put the start node on a list, OPEN, of unexpended nodes.
(2) Remove the first node, n, from OPEN.
(3) Expand node n—generating all its immediate successors and, for each successor m, if m represents a set of more than one subproblem, generating successors of m corresponding to the individual subproblems. Attach, to each newly generated node, a pointer back to its immediate predecessor. Place all the new nodes that do not yet have descendants at the end of OPEN.
(4) If no successors were generated in (3), then
(a) Label node n unsolvabie.
(b) If the unsolvability of n makes any of its ancestors unsolvabie, label these ancestors unsolvable.
(c) If the start node is labeled unsolvabie, exit with failure.
(d) Remove from OPEN any nodes with an unsolvabie ancestor.
(5) Otherwise, if any terminal nodes were generated in (3), then
(a) Label these terminal nodes solved.
(b) If the solution of these terminal nodes makes any of their ancestors solved, label these ancestors solved.
(c) If the start node is labeled solved, exit with success.
(d) Remove from OPEN any nodes that are labeled solved or that have a solved ancestor.
(6) Go to step 2.
Bounded DFS of AND/OR Tree
Change only Step 3
(3') the depth of n is less than the depth bound, then: Expand node n, generating all its immediate successors and, for each successor m, if m represents a set of more than one subproblem, generating successors of m corresponding to the individual subproblems. Attach, to each newly generated node,
pointer back to its immediate predecessor. Place all the new nodes that do not yet have descendants at the beginning of OPEN.
Heuristic Information
Deciding which node to expand next, instead of doing the expansions in a strictly breadth-first or depth-first order
Deciding which successor or successors to generate—instead of blindly generating ail possible
successors at one time. A node to which some but not all applicable operators have been applied is said to have been partially developed or partially expanded. Another variant is means-ends analysis.
Deciding that certain nodes should be discarded, or pruned, from the search tree. Sometimes applied just to save simply to save the space needed to retain a large number of apparently unpromising nodes on a list of candidates for possible future expansion.
Ordered Search
The general idea is always to expand the node that seems "most promising." A search that implements this idea is called an ordered search or best-first search. The evaluation function is f*s it is defined so that the more promising a node is, the smaller is the value of f*. The node selected for expansionIs one at which f" is minimum. It is assumed that the state space contains multiple solution paths with different costs; the problem is to find the optimal. Key questions can be (a) how to find good (but not optimal) solutions with reasonable amounts of search effort and (b) how to bound both the search effort and the extent to which the solution produced is less than optimal.
A*
Since f* evaluates nodes in light of the need to find a minimal cost solution, it considers the value of each node n as having two components: the cost of reaching n from the start node, and the cost of reaching a goal from node n. Accordingly, f" is defined by where g* estimates the minimum cost of a path from the start node to node n, and h* estimates the minimum cost from node n to a goal. The value f*(n) thus estimates the minimal cost of a solution path passing through node n. The actual costs, which f*, g*, and h* only estimate, are denoted by f, g, and h, respectively. It is assumed that ail arc costs are positive.
The function h* is the carrier of heuristic information and can be defined in any way appropriate to the problem domain. Admissibility condition requires that h*(n) is always <= h(n), the actual cost of an optimal path from n to a goal node.
It can be shown that if h* satisfies the admissibility condition and if, in addition, all arc costs are positive and can be bounded from below by a positive number, then A* is guaranteed to find a solution path of minimal cost if any solution path exists. This property is called the property of admissibility.
The more nearly h* approximates h, the better the algorithm will perform. If h* were identically equal to h, an optimal solution path would be found without ever expanding a node off the path. If h* is identically zero, A* reduces to the blind uniform-cost algorithm.
An optimality result for A* is, If A and A* are admissible algorithms such that A* is more informed than A, then A* never expands a node that is not also expanded by A.
The difficulty of computing h* also affects the total computational effort. One might prefer an h* that evaluates nodes more accurately in most cases but sometimes overestimates the distance to a goal, thus yielding an inadmissible algorithm. The choice of h* and the resulting heuristic power of the algorithm depend upon a compromise among these considerations.
A final question one might consider is the number of. node expansions, as opposed to
the number of distinct nodes expanded by A*.
Graph Traverser Algorithm
f* = s (1 - w)g* + wh*
where w is a constant in [0, 1] giving the relative importance to be attached to g and h. Choosing w = 1 gives the Graph Traverser algorithm; w = 0 gives breadth-first search; and w = .5 is equivalent to the A* function f* = g* + h*.
Problem-Solving Systems
Three components of problem-solving systems are database, operators and control strategy.
Database
The database can consist of a variety of different kinds of data structures including arrays, lists, sets of predicate calculus expressions, property list structures, and semantic networks. In robot problem solving, a current situation is a world model consisting of statements describing the physical surroundings of the robot, and the goal is a description that is to be made true by a sequence of robot actions.
Operators
The second component of problem-solving systems is a set of operators that are used to
manipulate the database. Sometimes the set of operators consists of only a few general rules of inference that generate new assertions from existing ones.
Control Strategy
The third component of a problem-solving system is a control strategy for deciding what
to do next—in particular, what operator to apply and where to apply it. Control strategy can investigate various operator sequences in parallel or alternately choose among number of sequences that look relatively promising. The assumption is having a database containing descriptions of multiple task-domain situations or states. If description of a task-domain situation is too large for multiple versions to be stored explicitly, it can use backtracking.
Reasoning Forward & Backward
Forward reasoning is application of operators to those structures in the database that describe the task-domain situation—to produce a modified situation towards goal. Reasoning backward is when the goal statement, or problem statement, is converted to one or more subgoals that are easier to
solve and whose solutions are sufficient to solve the original problem. These subgoals may in
turn be reduced to sub-subgoals, and so on, until each of them is either accepted to be a trivial problem or its solution is accomplished by the solution of its subproblems.
Bottom-up & Top-down Approaches
The former approach is said to use forward reasoning and to be data-driven or bottom-up. The latter uses backward reasoning and is goal-directed or top-down. The distinction between forward and backward reasoning assumes that the current task-domain situation or state is distinct from the goal.
Means-ends Analysis
Means-ends analysis combines the two. it involves comparing the current goal with a current task-domain situation to extract a difference between them. This difference is then used to index that (forward) operator most relevant to reducing the difference. If this especially relevant operator cannot be immediately applied to the present problem state, subgoals are set up to change the problem state so that the relevant operator can be applied. After these subgoals are solved, the relevant operator is applied and the resulting, modified situation becomes a new starting point from which to solve for the original goal.
State-space Representation
A problem-solving system that uses forward reasoning and whose operators each work by producing a single new object—a new state—in the database is said to represent problems in a state-space representation.
A state space can be treated as a directed graph whose nodes are states and whose arcs are operators transforming one state to another.
The complete specification of a state-space problem has three components. One is a set 0 of operators or operator schemata. In addition, one must define a set S of one or more initial states and find a predicate defining a set G of goal states. A state-space problem is then the triple (S, 0, G). A solution to the problem is a finite sequence of applications of operators that changes an initial state into a goal state.
A common variation on state-space problems requires finding not just any path but one of minimum cost between an initial node and a goal node. In this case, each arc of the graph is labeled with its cost. Because the state-space graph is usually too large to represent explicitly, the problem of searching for a solution becomes one of generating just enough of the graph to contain the desired solution path.
Problem-reduction Representation
A system using backward reasoning, distinguished by the fact that its operators can change a single object into a conjunction of objects, will be said to employ a problem reduction representation. The transformations permitted are defined as operators. An operator may change a single problem into several subproblems; to solve the former, all the subproblems must be solved. Several different operators may be applicable to a single problem, or the same operator may be applicable in several different ways. A problem whose solution is immediate is called a primitive problem. Such representation consists of, initial problem, operators for transformation and set of primitive problems.
Game Tree
A game-playing problem must be represented so as to take into account the opponent's possible moves as well as the player's own. The usual representation is a game tree, which shares many features of a problem-reduction representation.
Theorem-proving Representation
Another variation is relevant to theorem-proving systems, many of which use forward reasoning and operators (rules of inference) that act on conjunctions of objects in the database. It is possible to define a theorem-proving representation that provides for multiple-input, single-output operators
Graph Representation
In either a state-space or a problem-reduction representation, achieving the desired goal can be equated with finding an appropriate finite sequence of applications of available operators. a tree may be used to represent the set of problem states produced by operator applications. The root node of the tree represents the initial problem situation or state. Each of the new states that can be produced from this initial state by the application of just one operator is represented by a successor node of the root node. Subsequent operator applications produce successors of these nodes, etc. Each operator application is represented by a directed arc of the tree.
In general, the states are represented by a graph rather than by a tree since there may exist different paths from the root to any given node. For problems in which the goal can be reduced to sets of subgoals, AND/OR graphs provide a means for keeping track of which subgoals have been attempted and of combinations of subgoals which are sufficient to achieve the original goal.
Search Space
Producing a goal-condition state is conducted by searching a graph to find a satisfying node . For problem-reduction on the other hand we use AND/OR graph.
If it is already established graph or tree that we will apply search algorithm to find out the goal node. The implicit graph will be called the state space or, if generalized to cover non-state-space representations such as AND/OR graphs or game trees, the search space.
Search Graph or Search Tree
If we are constructing a tree or graph as the search proceeds, so at a particular state, the only nodes included are those for which paths from the initial state have actually been discovered so far, we explicitly refer to it search graph or search tree.
Combinatorial Explosion
Examining all sequences of n moves, for example, would require operating in a search space in which the number of nodes grows exponentially with n. Such a phenomenon is called a combinatorial explosion.
Heuristic Rule
A heuristic (heuristic rule, heuristic method) is a rule of thumb, strategy, trick, simplification, or any other kind of device which drastically limits search for solutions in large problem spaces. Heuristics do not guarantee optimal solutions; in fact, they do not guarantee any solution at all; all that can be said for a useful heuristic is that it offers solutions which are good enough most of the time.
Heuristic Search
It is a key contributor to AI for efficient problem-solving. Some graph-searching methods can use heuristic knowledge from the problem domain to help focus the search
Blind search corresponds approximately to the systematic generation and testing of search space elements, but it operates within a formalism that leaves room for additional information about the specific problem domain to be introduced, rather than excluding it by definition. If such
information, going beyond that needed merely to formulate a class of problems as search problems, is in fact introduced, it may be possible to restrict search drastically. Whether or not the restriction is foolproof, the search is then called heuristic rather than blind.
STRIPS/APSTRIPS/Planning
STRIPS augments its initial set of operators by discovering, generalizing, and remembering
macro-operators, composed of sequences of primitive operators, as it gains problem-solving
experience. ABSTRIPS program implements the idea of planning, in the sense of defining and solving problems in a search space from which unimportant details have been omitted.
AND/OR Graphs
It is constructed following,
1. Each node represents either a single problem or a set of problems to be solved. The graph contains a start node corresponding to the original problem.
2. A node representing a primitive problem, called a terminal node, has no descendants.
3. For each possible application of an operator to problem P, transforming it to a set of subproblems, there is a directed arc from P to a node representing the resulting subproblem set.
4. If P can be solved by any one of sets A, B, or C can be solved, then A, B, and C are called OR nodes.
5. If a set of subproblems can be solved only if its members can all be solved, the subproblem nodes are called AND nodes. To distinguish them from OR nodes, the arcs leading to AND node successors of a common parent are joined by a horizontal line.
Solution Graph/Solution Tree
To find a solution to the initial problem, we limit the graph to demonstrate only partially enough that the start node can be solved. Such a subgraph is called a solution graph or, in the more restricted case of an AND/OR tree, a solution tree.
Solvable/Unsolvable Node
A node is solvable if:
- it is a terminal node (a primitive problem);
- it is a nonterminal node whose successors are AND nodes that are all solvable;or
- it is a nonterminal node whose successors are OR nodes and at least one of them is solvable.
Similarly, a node is unsolvabie if:
- it is a nonterminal node that has no successors (a nonprimitive problem to which no operator applies);
- it is a nonterminal node whose successors are AND nodes and at least one of them is unsolvabie;or
- it is a nonterminal node whose successors are OR nodes and all of them are unsolvabie.
State Space to Problem Reduction
There can be 2 approaches. The graph becomes an AND/OR graph with only OR nodes. Data structures representing states are simply problem descriptions consisting state information along with an implicit goal.
The other variation is redefining operators. Each such operator, taking state i to state j, becomes an operator applicable to the problem of getting from state i to a goal state.
Problem Reduction to State Space
It has 2 components, (a) the description of the goal to be achieved and (b) the initial state. Each state S of the corresponding state-space representation is a pair consisting of a stack of goals (gi, ..., gO) to be achieved and a current state s of the world. So the final state will be with empty stack of goals. For that, we also need another operator, which becomes applicable whenever the goal on top of the stack represents a primitive problem. Its function is to remove that primitive problem from the stack and, at the same time, to change the state s to reflect its solution.
Game Tree
A complete game tree is a representation of all possible plays of a 2-player game. An AND/OR tree is sufficient to reflect this opposition. The root node is the initial state, in which it is the first player's turn to move. Its successors are the states he can reach in one move, represented by OR nodes; their successors are the states resulting from the other player's possible replies which are AND
nodes, since they represent sets of moves to which player one must be able to respond. Terminal states are those representing a win, loss, or draw. Each path from the root node to a terminal node gives a different complete play of the game. Because the players take turns, OR nodes and AND nodes appear at alternate levels of the tree. In the language of AND/OR graphs, the tree displays the search space for the problem of showing that player one can win. A node representing such win corresponds to a primitive problem; a node representing a win for opponent or a draw, is an unsolvabie problem.
Blind State-space Search
(S, 0, G), where S is a set of one or more initial states, 0 is a set of operatorson states, and G is a set of goal states.
The state space is commonly identified with a directed graph in which each node is a state and each arc represents the application of an operator transforming a state to a successor state. A solution is a path from a start state to a goal state. Goal states may be defined either explicitly or as the set of states satisfying a given predicate.
The search for a solution is conducted by making just enough of the state-space graph explicit to contain a solution path. If the order in which potential solution paths are considered is arbitrary, using no domain-specific information to judge where the solution is likely to lie, the search is called blind search.
Assumptions:
A procedure exists for finding all the successors of a given node—that is, all the states that can be reached from the current state by a single operator application. Such a procedure is said to expand the given node.
The state-space graph is a tree. The implication is that there is only one start state (the root) and that the path from the start node to any other node is unique.
Whenever a node is expanded, creating a node for each of its successors, the successor nodes contain pointers back to the parent node. When a goal node is finally generated, this feature makes it possible to trace the solution path.
Breadth-first Search
It considers every possible operator sequence of length n before any sequence of length n+l. Thus, although the search may be an extremely long one, it is guaranteed eventually to find the shortest
possible solution sequence if any solution exists.
(1) Put the start node on a list, called OPEN, of unexpended nodes. If the start node is a goal node, the solution has been found. (2) If OPEN is empty, no solution exists. (3) Remove the first node, n, from OPEN and place it in a list, called CLOSED, of expanded nodes. (4) Expand node n. If it has no successors, go to (2). (5) Place all successors of node n at the end of the OPEN list. (6) If any of the successors of node n is a goal node, a solution has been found. Otherwise, go to (2).
Uniform-cost Search
Add a nonnegative cost with every arc, that will enable finding the cheapest path. If all arcs have
equal cost, the algorithm reduces to breadth-first search.
(1) Put the start node, s, on a list called OPEN of unexpanded nodes. If the start node is a goal node, a solution has been found. Otherwise, set g(s) = 0. (2) If OPEN is empty, no solution exists.
(3) Select from OPEN a node i such that g(i) is minimum. If several nodes qualify, choose node i to be a goal node if there is one; otherwise, choose among them arbitrarily. Move node i from OPEN to a list, CLOSED, of expanded nodes. (4) If node i is a goal node, the solution has been found. (5) Expand node i. If it has no successors, go to (2). (6) For each successor node j of node i, compute g(j) = g(i) + c(i,j) and place all the successor nodes j In OPEN. (7) Go to (2).
Depth-first Search
The depth of a node in a tree is defined as follows:
The depth of the start node is 0.
The depth of any other node is one more than the depth of its predecessor.
To prevent consideration of paths that are too long, a maximum is often placed on the depth of nodes to be expanded. Even if such a depth bound is used, the solution path found is not necessarily the shortest one.
(1) Put the start node on a list, OPEN, of unexpended nodes. If it is a goal node, a solution has been found. (2) If OPEN is empty, no solution exists. (3) Move the first node, n, on OPEN to a list CLOSED of expanded nodes. (4) If the depth of node n is equal to the maximum depth, go to (2).
(5) Expand node n. If it has no successors, go to (2). (6) Place all successors of node n at the beginning of OPEN. (7) If any of the successors of node n is a goal node, a solution has
been found. Otherwise go to (2).
Bidirectional Search
Combine backward reasoning with, fully described goal state in advance and easily applicable inverse operators and replace a single search graph, which is likely to grow exponentially,by
two smaller graphs: one starting from the initial state and one starting from the goal. The
search terminates (roughly) when the two graphs Intersect. Bidirectional search can be blind or heuristic.
S-OPEN and S-CLOSED are lists of unexpended and expanded nodes, respectively, generated from the start node. T-OPEN and T-CLOSED are lists of unexpended and expanded nodes, respectively, generated from the terminal node. The cost associated with the arc from node n to node x is denoted c(n,x). For a node x generated from the start node, gs(x) measures the shortest path found so far from a to x. For a node x generated from the terminal node, gt(x) measures the shortest path found so far from x to t.
(1) Put s in S-CLOSED, with gs(s) = 0. Expand node s, creating a node for each of its successors. For each successor node x, place x on S-OPEN, attach a pointer back to s, and set gs(x) to c(s,x). Correspondingly, put t in TCLOSED, with gt(t) *0. Expand node t, creating a node for each of its
predecessors. For each predecessor node x, place x on T-OPEN, attach a pointer forward to t, and set gt(x) = c(x,t).
(2) Decide whether to go forward or backward. If forward, go to (3); if backward, to (4). (move backward if T-OPEN contains fewer nodes than SOPEN; otherwise, forward. It is assumed that a solution path does exist, so the chosen list will be nonempty.)
(3) Select from S-OPEN a node n at which gs(n) is minimum. Move n to SCLOSED.
If n is also In T-CLOSED, go to (5). Otherwise, for each successor x of n:
- (a) If x is on neither S-OPEN nor S-CLOSED, then add it to S-OPEN. Attach a pointer back to n and the path cost gs(x) = gs(n) + c(n,x).
- (b) If x was already on S-OPEN, a shorter path to x may have just been found. Compare the previous path cost, gs(x), with the new cost gs(n) + c(n,x). If the latter Is smaller, set gs(x) to the new path cost and point x back to n instead of its predecessor on the longer path.
- (c) If x was already on S-CLOSED, do nothing; although a new path to x has been found, its cost must be at least as great as the cost of the path already known. Return to (2).
(4) Select from T-OPEN a node n at which gt(n) is minimum. Move n to T-CLOSED
If n is also in S-CLOSED, go to (5). Otherwise, for each predecessorx of n:
- (a) If x is on neither T-OPEN nor T-CLOSED, then add it to T-OPEN. Attach a pointer forward to n and the path cost gt(x) = gt(n) + c(x,n).
- (b) If x was already on T-OPEN and a shorter path from x to t has just been found, reduce the stored value of gt(x), and point x forward to n (instead of to its successor on the longer path).
- (c) If x was already on T-CLOSED, do nothing. Return to (2).
(5) Consider the set of nodes that are in both S-CLOSED and either T-CLOSED or T-OPEN. Select from this set a node n for which gs(n) + gt(n) is minimum; and exit with the solution path obtained by tracing the path from n back to s and forward to t.
Blind AND/OR Graph Search
Each OR node successor of node n represents a set of subproblems. If the set of subproblems represented by an OR node m has more than one element, then there are directed arcs from m to nodes representing the individual elements of the set. These successors are called AND nodes.
A node or problem is said to be solved if one of the following conditions holds:
1. The node is in the set of terminal nodes. 2. The node has AND nodes as successors and all these successors are solved. 3. The node has OR nodes as successors and any one of these successors is solved.
A node is said to be unsolvabie if one of the following conditions is true:
1 . The node has no successors and is not in the set of terminal nodes. 2. The node has AND nodes as successors and one or more of these successors is unsolvabie. 3. The node has OR nodes as successors and all of these succesors are unsolvable.
BFS of AND/OR Tree
(1) Put the start node on a list, OPEN, of unexpended nodes.
(2) Remove the first node, n, from OPEN.
(3) Expand node n—generating all its immediate successors and, for each successor m, if m represents a set of more than one subproblem, generating successors of m corresponding to the individual subproblems. Attach, to each newly generated node, a pointer back to its immediate predecessor. Place all the new nodes that do not yet have descendants at the end of OPEN.
(4) If no successors were generated in (3), then
(a) Label node n unsolvabie.
(b) If the unsolvability of n makes any of its ancestors unsolvabie, label these ancestors unsolvable.
(c) If the start node is labeled unsolvabie, exit with failure.
(d) Remove from OPEN any nodes with an unsolvabie ancestor.
(5) Otherwise, if any terminal nodes were generated in (3), then
(a) Label these terminal nodes solved.
(b) If the solution of these terminal nodes makes any of their ancestors solved, label these ancestors solved.
(c) If the start node is labeled solved, exit with success.
(d) Remove from OPEN any nodes that are labeled solved or that have a solved ancestor.
(6) Go to step 2.
Bounded DFS of AND/OR Tree
Change only Step 3
(3') the depth of n is less than the depth bound, then: Expand node n, generating all its immediate successors and, for each successor m, if m represents a set of more than one subproblem, generating successors of m corresponding to the individual subproblems. Attach, to each newly generated node,
pointer back to its immediate predecessor. Place all the new nodes that do not yet have descendants at the beginning of OPEN.
Heuristic Information
Deciding which node to expand next, instead of doing the expansions in a strictly breadth-first or depth-first order
Deciding which successor or successors to generate—instead of blindly generating ail possible
successors at one time. A node to which some but not all applicable operators have been applied is said to have been partially developed or partially expanded. Another variant is means-ends analysis.
Ordered Search
The general idea is always to expand the node that seems "most promising." A search that implements this idea is called an ordered search or best-first search. The evaluation function is f*s it is defined so that the more promising a node is, the smaller is the value of f*. The node selected for expansionIs one at which f" is minimum. It is assumed that the state space contains multiple solution paths with different costs; the problem is to find the optimal. Key questions can be (a) how to find good (but not optimal) solutions with reasonable amounts of search effort and (b) how to bound both the search effort and the extent to which the solution produced is less than optimal.
A*
Since f* evaluates nodes in light of the need to find a minimal cost solution, it considers the value of each node n as having two components: the cost of reaching n from the start node, and the cost of reaching a goal from node n. Accordingly, f" is defined by where g* estimates the minimum cost of a path from the start node to node n, and h* estimates the minimum cost from node n to a goal. The value f*(n) thus estimates the minimal cost of a solution path passing through node n. The actual costs, which f*, g*, and h* only estimate, are denoted by f, g, and h, respectively. It is assumed that ail arc costs are positive.
The function h* is the carrier of heuristic information and can be defined in any way appropriate to the problem domain. Admissibility condition requires that h*(n) is always <= h(n), the actual cost of an optimal path from n to a goal node.
It can be shown that if h* satisfies the admissibility condition and if, in addition, all arc costs are positive and can be bounded from below by a positive number, then A* is guaranteed to find a solution path of minimal cost if any solution path exists. This property is called the property of admissibility.
The more nearly h* approximates h, the better the algorithm will perform. If h* were identically equal to h, an optimal solution path would be found without ever expanding a node off the path. If h* is identically zero, A* reduces to the blind uniform-cost algorithm.
An optimality result for A* is, If A and A* are admissible algorithms such that A* is more informed than A, then A* never expands a node that is not also expanded by A.
The difficulty of computing h* also affects the total computational effort. One might prefer an h* that evaluates nodes more accurately in most cases but sometimes overestimates the distance to a goal, thus yielding an inadmissible algorithm. The choice of h* and the resulting heuristic power of the algorithm depend upon a compromise among these considerations.
A final question one might consider is the number of. node expansions, as opposed to
the number of distinct nodes expanded by A*.
Graph Traverser Algorithm
f* = s (1 - w)g* + wh*
where w is a constant in [0, 1] giving the relative importance to be attached to g and h. Choosing w = 1 gives the Graph Traverser algorithm; w = 0 gives breadth-first search; and w = .5 is equivalent to the A* function f* = g* + h*.
Comments
Post a Comment