Search, Planning, and Heuristic Intelligence
State-space search
Problem formulation
Search problems are defined by states, initial states, actions, transition models, goal tests, and path costs. The objective is to find a path or policy that optimizes a criterion such as shortest cost or highest utility.
General search loop
-
1
Initialize the frontier with the start state.
-
2
Repeatedly select a node according to a search strategy.
-
3
Expand the node and add successors to the frontier.
-
4
Stop when a goal is found or the frontier is empty.
Uninformed vs informed search
Uninformed search
- Uses only problem structure
- Examples: BFS, DFS, uniform-cost search
Informed search
- Uses heuristics to guide expansion
- Examples: A*, greedy best-first search
What property makes optimal in graph search?
With an admissible heuristic, and especially when consistent, finds optimal solutions under standard assumptions.
Correct answer: An admissible and consistent heuristic
What does an admissible heuristic mean?
Admissibility preserves optimality guarantees for in appropriate settings.
Correct answer: It never overestimates the true cost to the goal.
Heuristic design
Good heuristics are informative, cheap to compute, and often derived from relaxed problems, abstractions, or learned estimators. Effective heuristic engineering can transform an intractable search space into a manageable one.
Planning perspective
Planning extends search by reasoning over action sequences, causal structure, and temporal constraints, enabling more scalable decision-making than blind enumeration.
Which algorithm is best known for combining path cost and heuristic cost?
A* ranks nodes by , combining accumulated cost and heuristic estimate.
Correct answer: A* search
Name one common source of heuristics in planning.
Relaxed problems ignore constraints to yield informative lower bounds or approximate guidance.
Correct answer: Relaxed problems