=========================================================================== PROBLEM SOLVING --------------------------------------------------------------------------- Problem Spaces A problem is characterized by (i) a set of goals, (ii) a set of objects, and (iii) a set of operations. All three - goals, objects and operations - may evolve during problem solving. Any of the three may be undefined of ill-defined. The problem space corresponding to a problem is an abstract space that encompasses all valid states that can be generated by the application of any combination of operators on any combination of objects. The problem space may contain one or more solutions (combination of operations and objects) that achieve the goals. Space search refers to the search for a solution in a problem space. --------------------------------------------------------------------------- Knowledge, Inference and Control Knowledge may be classified into: (i) the world knowledge (e.g., operators) (ii) the control knowledge (e.g., heuristics) Control in knowledge systems refers to the questions ``what operator to apply next?'' ``what inference to draw next?'' An inference generates new knowledge state from the current knowledge state and additional world knowledge. In the following, we assume mininal world knowledge and focus on control knowledge, i.e., knowledge useful for control of inferencing. --------------------------------------------------------------------------- Control Strategies Different control strategies are characterized by different kinds of control knowledge. Four basic kinds of control knowledge: (i) no control knowledge (this is the degenerate case) (ii) evaluation functions (iii) heuristics (iv) goals --------------------------------------------------------------------------- Strategy 1: No Control Knowledge (Blind Search) The case of no control knowledge leads to blind (and exhaustive) search of the problem space. Two basic blind search strategies are breadth-first search and depth-first search. %---------------------------------------------------------------------------- Strategy 2: Evaluation Functions This strategy uses an evaluation function that help determine the "goodness" of the various options. Hill climbing, sometimes also called the gradient descent (or ascent), is an example of this strategy: (i) Find the path with steepest gradient. (ii) Keep expanding this path as long as it is improving. Hill climbing is a very efficient search strategy It never backtracks. But it is not guaranteed to find a solution Also, the solution found need not be globally optimal - the strategy can get stuck in a locally optimal solution This is because hill climbing uses only local knowledge for controlling search Example [from Rich and Knight]: Consider the following problem from blocks world: -A- -H- -H- -G- -G- -F- -F- -E- -E- -D- -D- -C- -C- -B- -B- -A- ---------- ---------- initial state goal state Suppose that a robot can move only one block at a time. Then there is only one move possible from the initial state: Put -H- on the table. This leads to this current state: -H- -G- -F- -E- -D- -C- -B- -A- ----------- current state >From the current state, three moves are possible, leading to the following three possible states: -A- -H- -G- -F- -E- -D- -C- -B- ---------- next state 1 -H- -G- -F- -E- -D- -C- -H- -B- -A- ----------- next state 2 -G- -F- -E- -D- -C- -B- -A- -H- --------------- next state 3 So which of the three moves should the robot make? Clearly the first move is not good because the next state 1 is the same as the initial state. But how does one decide between 2 and 3? Suppose that the robot has an evaluation function, i.e., a function for evaluating the goodness of a state. Example: add one point for every block that is resting on the thing it is supposed to rest on, and subtract one point for every block that is sitting on the wrong thing. This evaluation function gives a value of 4 for the initial state, 8 for the goal state, 6 for the current state, and 4 for each of the three possible next states. Suppose that the robot is following the strategy of hill climbing. Since the value of current state (6) is more than the value of the initial state (4), hill climbing results in making the move to the current state. But since the values of each of the three possible next states is 4 (<6), hill climbing gets stuck at the current state. This is the local minima for this problem. In general, hill climbing works only if the solution path is monotonically increasing. %---------------------------------------------------------------------------- Local vs. Global Optimization The evaluation function in hill climbing provides only local guidance for search. This leads to local optima, but not necessarily global optima. So why not use global optimization strategies instead of local optimization strategies such as hill climbing? Because global optimization strategies require knowledge of a good global evaluation function - and this knowledge is generally not available for AI problems. Note that some kinds of neural networks (for example, perceptrons) use the strategy of hill climbing and thus get stuck in local minima. Some current work on neural networks (for example, simulated annealing) explores how to modify the strategy of hill climbing in order to get out of local minima. %---------------------------------------------------------------------------- Strategy 3: Heuristics Heuristics Heuristic search refers to the use of heuristic knowledge for space search. A heuristic is a rule of thumb. Heuristic knowledge typically is domain specific: domain-specific heuristics exploit world knowledge to prune the search space by eliminating some nodes in the search tree from further expansion Two basic types of heuristic search methods (i) forward chaining, and (ii) backward chaining. Forward Chaining: Start from initial state and find the goal state Backward Chaining: Start from the goal state and find the initial state. (This is also called goal reduction): In some AI problems, the goal state is not well specified - only some properties of the goal state are known. For such problems backward chaining is not appropriate - backward chaining is possible only if the goal state is well specified, and only the sequence of operators connecting the initial and goal states is desired. Bidirectional combines these two search strategies. %----------------------------------------------------------------------- Strategy 4: Goals Goal-directed control of search is one of the earliest AI ideas. It was first articulated in a theory called Means-Ends Analysis (MEA) which was developed by Allen Newell and Herbert Simon in the mid 1950s. The theory was embodied in a series of computer programs called General Problem Solver (GPS). One of the main problems with other search methods (such as hill climbing and forward chaining) is that they do not use information about the goal state to constrain the search for the solution path. The key idea in MEA/GPS is that reasoning (problem solving, understanding, learning) is goal-directed. That is, the goal provides the control knowledge for directing the search of the problem space. %---------------------------------------------------------------------------- Means-Ends Analysis MEA explores problem spaces MEA uses a functionally organized memory in which the operators are indexed by the goals to which they are applicable Memory is represented in the form of a operator-difference table MEA proposes three kinds of problem-solving goals: TRANSFORM, REDUCE and APPLY It also proposes goal-specific methods: Goal: Transform the current state to the goal state Method: Compare the current state with the current goal state Find differences (each difference represents a reasoning goal) Heuristically select the biggest (or hardest) difference Goal: Reduce the difference on the current state Method: Use the difference as a probe into the operator-difference table to find applicable operators Goal: Apply the operator to the current state Methhod: Test the preconditions of the operator If the preconditions are met then apply the operator to form a new current state If the preconditions are not met then form the new goal state with the preconditions as the goals MEA's search strategy: 1. Compare the current state (CS) with current goal state (CGS) 2. Find the differences d(CS,CGS). 3. Select the biggest difference d1 4. Select operator O to reduce difference d1. 5. Use MEA recursively to get from CS to the precondition state (PreS) of operator O. 6. Apply O to CS 7. Use MEA recursively to get from the postondition state (PostS) of operator O. %---------------------------------------------------------------------------- MEA/GPS EXAMPLE: The Monkey and Bananas problem ------------------------- | ! | | ! Bananas | ^ | | | | | | ^ | o / | | | | \/ Box | | | | / Monkey --- | | h2 ^ | h1 | /\ | | | | | h3 | | \\ --- | | | v ------------------------- v v Pos1 Pos2 Pos3 Environment: Monkey's height = h1 Monkey's position = Pos1 Box's height = h3 Box's position = Pos3 Banana's height = h2 Banana's position = Pos2 Problem: Initial State: Monkey's position = Pos1 Monkey's height = h1 Contents of Monkey's Hands = Empty Goal State: Contents of Monkey's Hands = Bananas [Monkey's position = dont care; Monkey's height = dont care] Operators: Walk: Precondition: None Postcondition: Monkey's position = X Climb-Box: Precondition: Monkey's position = Box's position Postcondition: Monkey's height = h1+h3 Move-Box: Precondition: Monkey position = Box's position Postcondition: Monkey's and Box's position = Y Grasp-Bananas: Precondition: Monkey's height = or > Bananas's height Monkey's position = Bananas's position Postcondition: Contents of Monkey's hands = Bananas Differences: D1 = Contents of Monkey's Hands D2 = Monkey's position D3 = Monkey's height Difference Ordering: D1, D3, D2 Table of Connections (operator-difference table): | D1 | D2 | D3 | ----------------|---------|---------|---------| Walk | | X | | Move-Box | | X | | Climb-Box | | | X | Grasp-Bananas | X | | | ----------------|---------|---------|---------| %---------------------------------------------------------------------------- Current state 1 (or CS1) Monkey's position = Pos1 Monkey's height = h1 Contents of Monkey's Hands = Empty Current goal state (or CGS1) Contents of Monkey's Hands = Bananas [Monkey's position = dont care; Monkey's height = dont care] Goals: (AND (Transform Reduce Apply)) Goal: Transform CS1 into CGS1 Method: Find differences Difference: D1 Goal: Reduce D1 Method: Find applicable operator from operator-difference table Applicable operator: is Grasp-Bananas Goal: Apply Grasp-Bananas to CS1 Preconditions: Monkey's height = Bananas's height Monkey's position = Bananas's position Preconditions not satisfied by CS1 Form new goal states: Monkey's height = Bananas's height Monkey's position = Bananas's position Current goal state (CGS2) Monkey's height = Bananas' height Monkey's position = Bananas's position Goals: (AND (Transform Reduce Apply) Goal: Transform CS1 into CGS2 Method: Find differences Differences: (AND (D2 D3)) Select difference D3: (goal Monkey's height = Bananas's height) because of difference ordering D3 > D2 [suspend difference D2: (goal Monkey's position = Bananas's position)] Goal: Reduce D3 Method: Find applicable operator Applicable operator: Climb-Box Goal: Apply Climb-Box to CS1 Precondition: Monkey's position = Box's position Form new goal state: Monkey's position = Box's position Current goal state (CGS3) Monkey's position = Box's position Goal: Transform CS1 into CGS3 Method: Find differences Difference: D2 Goal: Reduce D2 Method: Find applicable operator Applicable operators: (OR (Move-Box Walk)) Select Move-Box (arbitrarily) [hold operator Walk] Goal: Apply Move-Box to CS1 Precondition: Monkey's position = Box's position Form new goal state: Monkey's position = Box's position But this is the same as CGS3 Abandon goal Apply Move-Box to CS1 Backtrack to last choice Current state is CS1, current goal state is CSG3 Goal is Reduce D2 Applicable operators are (OR (Move-Box Walk)) Now select Walk Goal: Apply Walk to current state Precondition = none Precondition is satisfied Apply operator Walk to current state Form new current state (CS2) binding variable X to Box's position (Pos3) ----------------------------------------------- Now use MEA recursively from this current state Current state (CS2) Monkey's position = Box's position = Pos3 Monkey's height = h1 Contents of Monkey's Hands = Empty Current goal state (or CGS1' same as CSG1) Contents of Monkey's Hands = Bananas [Monkey's position = dont care; Monkey's height = dont care] Goals: (AND (Transform Reduce Apply)) Goal: Transform CS2 into CSG1' Method: Find differences Difference: D1 Goal: Reduce D1 Method: Find applicable operator from operator-difference table Applicable operator: is Grasp-Bananas Goal: Apply Grasp-Bananas to CS2 Preconditions: Monkey's height = Bananas's height Monkey's position = Bananas's position Preconditions not satisfied by CS2 Form new goal state: Monkey's height = Bananas's height Monkey's position = Bananas's position Current goal state (CGS2') Monkey's height = Bananas' height Monkey's position = Bananas's position Goals: (AND (Transform Reduce Apply) Goal: Transform CS2 into CSG2' Method: Find differences Differences: (AND (D2 D3)) Select difference D3: (goal Monkey's height = Bananas's height) because of difference ordering D3 > D2 [suspend difference D2: (goal Monkey's position = Bananas's position)] Goal: Reduce D3 Method: Find applicable operator Applicable operator: Climb-Box Goal: Apply Climb-Box to CS2 Precondition: Monkey's position = Box's position Precondition is satisfied Apply operator Climb-Box to current state Form new current state (CS3) -------------------------------- Now use MEA recursively from CS3 Current state (CS3) Monkey's position = Box's position = Pos3 Monkey's height = h1+h3 Contents of Monkey's Hands = Empty Current goal state (or CGS1'' same as CSG1' and CSG1) Contents of Monkey's Hands = Bananas [Monkey's position = dont care; Monkey's height = dont care] Goals: (AND (Transform Reduce Apply) Goal: Transform CS3 into CSG1'' Method: Find differences Difference: D1 Goal: Reduce D1 Method: Find applicable operator from operator-difference table Applicable operator: is Grasp-Bananas Goal: Apply Grasp-Bananas to CS3 Preconditions: Monkey's height = Bananas's height Monkey's position = Bananas's position Preconditions not satisfied by CS3 Form new goal state: Monkey's height = Bananas's height Monkey's position = Bananas's position Current goal state (CGS2'') Monkey's height = Bananas's height Monkey's position = Bananas's position Goal: Transform CS3 into CSG2'' Method: Find differences Differences: D2 Goal: Reduce D2 Method: Find applicable operator No available operator is applicable BACKTRACK to last choice Current state is CS2, Current goal state is CGS2' Goal is Transform CS2 into CSG2' Difference is (AND (D2 D3)) Select difference D2: (goal Monkey's position = Bananas's position) Goal: Reduce D2 Method: Find applicable operator Applicable operator: Move-Box Goal: Apply Move-Box to CS2 Precondition: Monkey's position = Box's position Precondition is satisfied Apply operator Move-Box to CS2 bidnging variable Y to Banana's position (pos2) Form new current state (CS3') ----------------------------------------------- Now use MEA recursively from CS3' Current state (CS3') Monkey's position = Bananas' position = Pos2 Monkey's height = h1 Contents of Monkey's Hands = Empty Current goal state (or CGS1''' same as CSG1, CSG1', CSG1'') Contents of Monkey's Hands = Bananas [Monkey's position = dont care; Monkey's height = dont care] Goals: (AND (Transform Reduce Apply)) Goal: Transform CS3' into CSG1''' Method: Find differences Difference: D1 Goal: Reduce D1 Method: Find applicable operator from operator-difference table Applicable operator: is Grasp-Bananas Goal: Apply Grasp-Bananas to CS3' Preconditions: Monkey's height = Bananas's height Monkey's position = Bananas's position Preconditions not satisfied by CS3' Form new goal state: Monkey's height = Bananas's height Monkey's position = Bananas's position Current goal state (CGS2''') Monkey's height = Bananas' height Monkey's position = Bananas's position Goals: (AND (Transform Reduce Apply) Goal: Transform CS3' into CGS2''' Method: Find differences Differences: D3 Goal: Reduce D3 Method: Find applicable operator Applicable operator: Climb-Box Goal: Apply Climb-Box to CS3' Precondition: Monkey's position = Box's position Precondition is satisfied Apply operator Climb-Box to CS3' Form new current state (CS4') ---------------------------- Now use MEA recursively from CS4' Current state (CS4') Monkey's position = Bananas' position = Pos2 Monkey's height = h1+h3 Contents of Monkey's Hands = Empty Current goal state (or CGS1'''' same as CSG1, CSG1', CSG1'', CSG1''') Contents of Monkey's Hands = Bananas [Monkey's position = dont care; Monkey's height = dont care] Goals: (AND (Transform Reduce Apply)) Goal: Transform CS4' into CSG1'''' Method: Find differences Difference: D1 Goal: Reduce D1 Method: Find applicable operator from operator-difference table Applicable operator: is Grasp-Bananas Goal: Apply Grasp-Bananas to CS4' Preconditions: Monkey's height = Bananas's height Monkey's position = Bananas's position Preconditions are satisfied by CS4' Apply operator Grasp Banana's to CS4' Form new current state CS5 Contents of Monkey's Hands = Bananas This is the goal state %---------------------------------------------------------------------------- Discussion of MEA Strategic control in MEA is hierarchical, recursive and goal directed MEA uses problem reduction: it decomposes a problem into subproblems. MEA shows how problem decomposition can occur. MEA relates problem solving and memory: problem-solving is goal directed, memory organization is goal oriented MEA makes a very general statement about intelligence: intelligent behavior is goal-directed. MEA has been shown to be cognitively plausible for a class of problems (e.g., well-specified problems, knowledge in the form of well-specified operators, etc.) %---------------------------------------------------------------------------- Copyright (c) 1994-97 Ashok K. Goel Associate Professor of Computer and Cognitive Science College of Computing, Georgia Institute of Technology ===========================================================================