W4L3 - Problem Solving

Problem Solving

the transformation of a given situation (initial state) into a desired situation (goal state)
▪ How do I get to the grocery store?
▪ How do I fix my leaky sink?
▪ How do I find a meeting time that works for everyone in the group?
▪ How do I beat my opponent at chess?

Problem Space (name and explain the 3 states)

Initial state:

• What the problem is like at first

Intermediate state:

• The results after some action is applied to the problem

Goal State:

• The desired situation after the problem is solved

• To solve a problem is to search the problem space for a path from the initial state to the goal state.

Example problem: Driving to work, what is the initial state, intermediate states and goal state

• Initial state: You are at home.

• Intermediate states: You are at a particular intersection.

  • Operators: drive in one direction or another

• Goal state: You are at work.
  

Searching for a solution path

What are three ways of searching for a solution path?

Brute force

Heuristics

Means-end analysis

Searching for solution path: Brute Force

▪ Try all possible paths
▪ This takes too long – chess has 1020 states!

Searching for solution path: Heuristics

▪ Informal rules that are easy to use
▪ Doesn’t guarantee a solution, but will usually succeed in much less time than brute force
▪ E.g. look for your keys in the usual places

Searching for solution path: Means-end analysis

▪ An effective heuristic for most problems: measure the biggest difference between your current state and the goal state, then use an operator that reduces the distance

Subgoals

• On your way to the goal state, you might want to first get to a particular intermediate state.

• This breaks down the problem into parts and makes it easier to solve.

• E.g. “First, get to campus; then, get to the correct building; then, find the classroom.”

• Each subgoal still takes several steps to achieve

The general problem solver

▪ A program built by Alan Newell and Herb Simon (1972) to simulate human problem solving through means-end analysis
▪ First represent the problem and the goal; then identify subgoals and operators
▪ The GPS defines its operators as production rules

Practice question: In the Tower of Hanoi problem, what is the goal state?

To have all disk from largest (on the bottom) to smallest (on the top), on the target peg

Example of goal and subgoal of tower of Hanoi (pro

▪ IF the destination peg is clear and the largest disk is free, THEN move the largest disk to the destination peg.
▪ IF the largest disk is not free, THEN set up a subgoal that will free it.
▪ IF the subgoal of freeing a has been set up and a smaller disk is on that disk, THEN move the smaller disk.

Understanding production rules

• These are not step by step instructions to solving the problem

• They are possible actions that can be taken in a given situation

• The GPS identifies the actions that can be taken in each state

• Then it chooses actions using means-end analysis

  • What is the biggest difference between the current state and the next subgoal

  • Which action would reduce this difference the most?

Is the GPS useful?

• The GPS can solve the Tower of Hanoi problem and many other famous puzzles

• When humans talk out loud as they try to solve these puzzles, they use similar steps to the GPS

• The GPS’s mistakes are not always the same as a human’s mistakes

  • E.g. humans use “hill climbing” – try to reduce the distance to the goal without subgoals

  • So humans make mistakes by not realizing when they need to go backwards

  • The GPS doesn’t make these mistakes!

Cognitive modeling: What is it good for?

• The modularity assumption allows for zeroing in on specific processes

• Models are more precise than theories and can be tested with experiments

• But modularity is only an approximation of the truth

• How can it be reconciled with neuroscience?

• And with the non-modular, ecological context that we live in?