suggested characteristics:
To solve a problem, one needs to identify options
Problem solving is essentially search
Characteristics of Search
A problem to solve: Water Jug Problem
You are given two jugs, a 4-gal. one and a 3-gal. one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gal. jug?
Solution: Define state space, give initial & final state(s), ops?
A representation:
domain for x is 0,1,2,3,4 : domain for y is 0,1,2,3
Thus (4,2) represents what...
Control (operators):
Missionaries and Cannibals:
Three missionaries and three cannibals (or 2 and 3 ...)
Different stories [perspectives ;-) ]
Book wants missionaries > cannibals or will eat
Formal Description: Pictorally:
State-space
The Monkey and Banana Problem:
Pictorally:
Representation:
State-space:
Initial state:
When (why) is depth-first good?
When (why) is breadth-first good? Bad - if all lead to result at same level (can be wasteful)
(process&memory intensive)
Would like to join the two together to get
Heuristics...allows for Best-first searches
Generate all, use a heuristic function to pick best
Heuristics allow jumps in search or direct path
Most problems in AI are NP (nondeterministic polynomial) exponentional time
Heuristics improve efficiency but possibly sacrifice completeness
Trying to understand why a heuristic works, or why it doesn't, often leads to a deeper understanding of the problem.
A heuristic function could be as simple as a "closeness measure"
(an apparent situation and possible options can generate over and over this set of states)
(here, our problem is not to recognize that a problem exists, rather we have a known problem
How can it be represented
The state space for the problem can be a set of ordered pairs (x,y) where x is the # of gallons in the 4-gal. jug, y is the 3-gal.
The start state is ?
The Goal state is (2,n), success does not depend on the 3-gal. jug
pour either out, fill either one, pour one into another, etc.
Generate State Space ... control technique of try all possible ops.
alternatives: 7,5,3 gallon jugs
If more M than C will covert
If more C than M will eat
Initial state
Final state
transformations:
(monkey position, on/off box, box position, banana in hand)
Final state:
Ops:
(move-self(x,y), move-box(x,y), climb-on-box, climb-off-box, grab banana)
Requirements for Control Strategies:
state-space description
operators
Two common control strategies
Both will lead to the answer (if one exists)
Both are OK for simple problems, otherwise combinatorial explosion for larger
maybe quicker (shorter) answer
less memory (can trash if not successful) (good when lots of solutions)
Bad
possibly not shortest path..."blind alleys"
Shortest path
maximum goodness of both. (local vs global)
(e.g., Branch-and-Bound - more later)
| Forward search | vs | Backward search |
| data-driven | goal-driven (assume hypothesis) | |
| discover | verify/deny a conclusion (not for monkey&banana) |
* Chess: 8 X 8 board, 32 pieces about 10120 board positions
- humans don't memorize such lists
- even with computers it is infeasable to consider all
- all are not even legal anyway! (discuss cognitive psych study)
(experts and memory)
we need a representation for describing patterns and allowable substitutions
Searching a path: efforts are in
Depth-first
Generate & Test
What does (1) mean. If a "complete" solution must be generated before it is tested than this means exhaustive depth-first search... (at each state, not at goal yet but still don't know if future generation of this path may be successful). If generation done systematically will find a solution eventually, if one exists. If problem space is very large - could take a very long time.
If the generation is done randomly, we get the British Museum algorithm and
no guarantee that a solution will ever be found.
In a sense, almost all search techniques are a form of
generate and test (in pure generate and test, the test responds with only yes or no.)
Hill climbing is a local method - moves are determined by being better than previous.
What if reach:
Beam Search
breadth-first except only downward from the best 'w' nodes at each level (not exponential...if b is branching factor - wb nodes) ... prunes, may lose goal, not optimal
Best-First Search
Like hill-climbing except
in hill-climbing, one move is selected and all others are rejected (never considered unless add backtracking)
Branch and Bound (Dykstra's shortest path algorithm)
provides an optimal path (heuristic here is length (absolute) )
(distances)
During search, many incomplete paths are encountered
Example: Shortest distance Start to Goal: Page 1 , Page 2 ,
Page 3 (I looked it up, there was no more nodes on the S-A-B-C link, hence the C with value 11 ended (not a path to G))
* More knowledge means less search Heuristic Search Techniques
Which search procedures work (given a problem)?
Which procedures are efficient?
Which procedures are easy to implement?
Weak Methods of control:
(weak but provide framework)
Breadth-first
The most straight-forward way to implement generate and test is as a depth-first search tree with backtracking
British Museum algorithm, a reference to the fact that if a sufficient number of monkeys were placed in front of a set of typewriters and left alone long enough, then their implementation of this algorithm would generate all the books the museum contains. (Monkeys at keyboards writing Shakespeare if enough time)
Hill-Climbing
generate and test with a closeness heuristic function
need an adjustable parameter and a way to measure
this is "steepest-ascent" (gets best rather than first that is better than the previous)
a. test if goal state
b. use function to determine which is "closest"
(procedure takes one step in each fixed set of directions, moves to the best alternative)
(procedure stops when node reached where all nodes children have lower values)
Solutions:
backtrack (would need to maintain a list of paths)
jump
apply >1 rule before test
increase the number of directions used for probing
the best available state is selected even if the value is lower than the value of the previous state
notice with each advancement we get closer to a "shorter" answer, but remember to consider the time to calculate and sort
- shortest one is extended one level, creating as many new incomplete paths as branches. Consider these and remaining old ones ... extend shortest path.
- terminate when shortest incomplete path is longer than shortest complete path (ensures optimum)
* Search is seductive.
While involved in many tasks, tuning a search procedure is rarely the right thing to do. More often, the right thing is to improve understanding, thereby reducing the need for search.
weak methods are too general
reduce the search space even more
| branch and bound | (best) - now | |
| estimate | (promising) - now and later | |
| dynamic programming | (know way (past) -- already better (waste him)) |
(solution to problem is viewed as the result of sequence of decisions (want optimal))
Dynamic Programming uses principle of optimality
An optimal decision sequence has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequence with regard to the state that results from the first decision.
f' = g + h' f is heuristic measure of goodness
g is how good the node is now
h is how much farther to go to goal
' means it is an estimate
Example A* and use of dynamic programming on right side bottom
still not enough focus on the problem....want to constrain space given knowledge
Constraint Satisfaction and Backtracking
Goal: to discover some problem state that satisfies a given set of constraints
Before going back to this in CSCI 356, let's look at what really makes a problem interesting
Let's add another piece into the puzzle adversaries
- fixed limits on time, cost, material
- not new search method - rather it
constrains space by augmenting description of state with list of constraints
