AI Exam Cheat Sheet: Agents, Search, Logic, Planning
AI builds agents that perceive, decide and act rationally; most problems reduce to searching a state space guided by heuristics, constraints or logic.
Core Principles
- Rationality: maximise expected performance measure from percepts and knowledge, not perfection.
- PEAS: define any task by Performance, Environment, Actuators, Sensors.
- Agent ladder: simple reflex, model-based reflex, goal-based, learning agent.
- Greedy best-first uses h(n) only and may return non-optimal paths; A* uses g(n)+h(n).
- Admissible heuristic never overestimates; consistent heuristic satisfies triangle inequality.
- Alpha-beta prunes provably irrelevant branches, so it returns the same minimax value.
- CSP: propagate constraints (node, arc/AC-3) and order variables by MRV during backtracking.
- Propositional logic handles facts; FOL adds objects and quantifiers; resolution proves by refutation.
- Goal-stack planning orders actions sequentially; nonlinear planning orders only where constraints demand.
Formulas
- Blocks/Hanoi minimum moves: $$M = 2^{n}-1$$
- A* evaluation: $$f(n)=g(n)+h(n)$$
- Consistency condition: $$h(n)\leq c(n,n')+h(n')$$
- Simulated annealing acceptance of worse move: $$P=e^{-\Delta/T}$$
Key Terms
- Admissibility: Heuristic never overestimates true optimal remaining cost; guarantees A* optimality.
- Arc consistency: Every value in X's domain has a compatible value in Y's domain; enforced by AC-3.
- Causal link: Planner records that action A achieves precondition p of action B; threats must be resolved.
- Resolution: Negate the query, combine clauses with complementary literals, reach empty clause.
- Local beam search: Keeps k states, expands all, retains best k successors each iteration.
Pitfalls to Avoid
- Using an overestimating heuristic in A* loses optimality, returning costlier routes.
- Treating Google Search as a single rule engine misdescribes a system combining many ML models.
- Skipping forward checking or arc consistency enlarges backtracking search, wasting time on doomed branches.
Related cheat sheets
More like this