Artificial Intelligence Search and Optimization Syllabus

When combining two admissible heuristics, which should you use, and why is the answer 'the maximum'?

Given admissible heuristics $h_{1}$ and $h_{2}$, use $h(n) = \max\{h_{1}(n), h_{2}(n)\}$. The maximum is still admissible (never exceeds the true cost) and dominates each individual heuristic, so it expands no more nodes than either alone — a more accurate estimate that stays a valid lower bound.

Define heuristic dominance and explain why a dominating heuristic is preferable.

Heuristic $h_{2}$ dominates $h_{1}$ if $h_{2}(n) \geq h_{1}(n)$ for all nodes $n$, with both admissible. A dominating heuristic is preferable because it is closer to the true cost, so A* with $h_{2}$ never expands more nodes than with $h_{1}$ (aside from tie-breaking). Higher heuristic values mean better-informed, more efficient search.

How can relaxed problems be used to design admissible heuristics?

A relaxed problem is one with fewer restrictions on actions; the exact cost of an optimal solution to the relaxed problem is an admissible heuristic for the original. Because the relaxed problem's solution set is a superset, its optimal cost is a lower bound. Example: allowing an 8-puzzle tile to move to any square yields the misplaced-tiles heuristic; allowing moves to any adjacent square yields Manhattan distance.

What is the effective branching factor $b^{*}$, and how is it used to compare heuristics?

If A* generates $N$ nodes and finds a solution at depth $d$, the effective branching factor $b^{*}$ is the branching factor a uniform tree of depth $d$ would need to contain $N+1$ nodes: $$N + 1 = 1 + b^{*} + (b^{*})^{2} + \dots + (b^{*})^{d}.$$ A well-designed heuristic gives $b^{*}$ close to 1; it is a standard measure of heuristic quality.

What is a pattern database, and how does it provide admissible heuristics?

A pattern database stores exact solution costs for every possible configuration of a subset (pattern) of the problem's components (e.g., a subset of puzzle tiles), computed by backward search from the goal. Looking up the cost of the current subproblem gives an admissible heuristic, since solving the subproblem is a relaxation of solving the whole problem.

Describe the Hill-Climbing (steepest-ascent) search algorithm.

Hill-Climbing is a local search that keeps a single current state and repeatedly moves to the neighboring state with the highest objective (or lowest cost) value, terminating when no neighbor is better. It uses no search tree — only the current node and its immediate successors — so it uses very little memory but keeps no history.

What three landscape features cause Hill-Climbing to fail, and name two variants that mitigate them.

Hill-Climbing gets stuck at: (1) local maxima, (2) ridges (sequences of local maxima hard to navigate), and (3) plateaux/shoulders (flat regions). Mitigations include stochastic hill climbing, first-choice hill climbing, and random-restart hill climbing, which restarts from random states until a goal is found and is complete with probability approaching 1.

Describe the Simulated Annealing algorithm and its acceptance rule for worse moves.

Simulated Annealing combines hill climbing with random moves. At each step it picks a random neighbor; if it improves the objective (positive $\Delta E$) it is always accepted, otherwise it is accepted with probability $e^{\Delta E / T}$, where $\Delta E < 0$ is the change in value and $T$ is the temperature. $T$ starts high and is gradually lowered per a cooling schedule, so bad moves become less likely over time.

In Simulated Annealing, what happens to behavior as temperature $T \to \infty$ and as $T \to 0$, and what does theory say about optimality?

As $T \to \infty$, the acceptance probability $e^{\Delta E / T} \to 1$, so it behaves like a random walk; as $T \to 0$, worse moves are almost never accepted, so it behaves like greedy hill climbing. If $T$ is lowered slowly enough, Simulated Annealing finds the global optimum with probability approaching 1.

How does Local Beam Search work, and how does it differ from running $k$ parallel random restarts?

Local Beam Search keeps $k$ states at once. At each step it generates all successors of all $k$ states; if any is a goal it halts, otherwise it selects the $k$ best from the entire pool for the next round. Unlike $k$ independent restarts, information is shared: useful states attract search effort, so beams effectively abandon unpromising states and concentrate on productive regions.

What is stochastic beam search, and what problem does it solve?

Stochastic beam search selects the $k$ successors with probability proportional (increasing) to their objective value, rather than deterministically choosing the top $k$. This maintains diversity and prevents the $k$ states from clustering in a small region of the space — the concentration problem of plain local beam search — analogous to natural selection.

Outline the main steps of a Genetic Algorithm.

A Genetic Algorithm: (1) starts with a population of $k$ randomly generated individuals (states encoded as strings); (2) evaluates each with a fitness function; (3) selects parents with probability proportional to fitness; (4) applies crossover at a random crossover point to combine parent strings; (5) applies random mutation; (6) repeats over generations until a satisfactory individual or limit is reached.

In Genetic Algorithms, define fitness function, crossover, and mutation.

The fitness function rates each individual (higher = better) and biases selection. Crossover combines two parent strings by splitting each at a random point and exchanging the parts, producing offspring. Mutation randomly alters individual elements of a string with a small probability, introducing new genetic material and helping escape local optima.

Why can crossover make Genetic Algorithms effective, and what is the role of the encoding/schema?

Crossover is effective when the string encoding groups related components into contiguous blocks (schemata), so that useful sub-solutions (building blocks) are preserved and combined across individuals. If the representation is arbitrary, crossover just shuffles information randomly and offers little benefit over mutation-only stochastic beam search.

In continuous-space optimization, what is the gradient, and state the gradient-ascent update rule.

For an objective $f(\mathbf{x})$ over continuous variables, the gradient is the vector of partial derivatives $$\nabla f = \left( \frac{\partial f}{\partial x_{1}}, \frac{\partial f}{\partial x_{2}}, \dots, \frac{\partial f}{\partial x_{n}} \right).$$ Gradient ascent updates the state by $\mathbf{x} \leftarrow \mathbf{x} + \alpha \nabla f(\mathbf{x})$, where $\alpha$ is the step size (learning rate).

What is the Newton–Raphson method for continuous optimization, and what does the Hessian represent?

Newton–Raphson finds where the gradient is zero using the update $$\mathbf{x} \leftarrow \mathbf{x} - \mathbf{H}_{f}^{-1}(\mathbf{x})\, \nabla f(\mathbf{x}),$$ where $\mathbf{H}_{f}$ is the Hessian matrix of second partial derivatives, $H_{ij} = \frac{\partial^{2} f}{\partial x_{i} \partial x_{j}}$. The Hessian captures the local curvature, giving faster convergence than plain gradient methods near an optimum.

What problems can arise with the step size $\alpha$ in continuous gradient-based optimization?

If $\alpha$ (step size) is too small, convergence is very slow; if too large, the search overshoots the optimum and may diverge or oscillate. Techniques such as line search (adjusting $\alpha$ each step, e.g., doubling until $f$ stops improving) and using the Hessian help choose an effective step size.

How is a search problem with nondeterministic actions represented, and what is a solution to it?

With nondeterministic actions, each action can lead to several possible outcomes, described by a RESULTS function returning a set of states. The agent must reason about belief-like sets of contingencies. A solution is not a linear sequence but a contingency plan (conditional plan / strategy) with branches such as 'if state = s then action a else action b', accounting for every possible outcome.

Describe the AND-OR search tree used for nondeterministic problems.

An AND-OR tree has two node types: OR nodes, where the agent chooses one action (only one branch need succeed), and AND nodes, representing the environment's nondeterministic outcomes, where the plan must handle every branch (all must succeed). A solution is a subtree that has a goal node at every leaf, specifies one action at each OR node, and includes every branch at each AND node.

What is a belief state, and how does the search space change under partial observability?

A belief state is the set of physical states the agent believes it could currently be in, given its percept history. Under partial observability the agent searches in belief-state space rather than physical-state space; actions map belief states to belief states, and the goal is a belief state all of whose members are goal states.

For a sensorless (conformant) problem, how are the initial belief state and the result of an action defined?

In a sensorless problem the agent has no percepts, so the initial belief state is the set of all possible physical states. The predicted belief state after action $a$ is $b' = \{\, \text{RESULT}(s, a) : s \in b \,\}$ (the union of results over all states in the current belief state $b$). A solution is an unconditional action sequence leading to a belief state of only goal states.

How does the prediction–observation update cycle work for search with partial observations?

Each cycle has: (1) Prediction — compute the belief state from the action, $\hat{b} = \text{PREDICT}(b, a)$; (2) Observation Prediction — determine possible percepts; (3) Update — for a received percept $o$, filter to states consistent with it: $b' = \{\, s \in \hat{b} : o = \text{PERCEPT}(s) \,\}$. Percepts partition the predicted belief state and generally shrink it, reducing uncertainty.

What distinguishes an Online Search Agent from an offline search agent?

An offline agent computes a complete solution before acting in the real world. An online search agent interleaves computation and action: it takes an action, observes the resulting environment, then decides the next action. Online search is necessary in unknown environments (where the agent must explore to learn the map) and in dynamic or semidynamic domains where planning ahead fully is infeasible.

What is the competitive ratio for an online search agent, and why might it be unbounded?

The competitive ratio is the ratio of the total path cost the online agent actually incurs to the cost of the optimal path it could have taken with full knowledge of the space; smaller is better, with 1 being ideal. It can be infinite (unbounded) if the agent encounters dead ends or irreversible actions (irreversible states) from which the goal becomes unreachable, making no algorithm competitive in the worst case.

How does Online DFS explore, and what environments does it require to be effective?

Online DFS acts like depth-first search but physically moves: it tries untried actions from the current state, remembers outcomes, and when stuck it physically backtracks by taking the reverse action to a previous state. It works well only in state spaces where actions are reversible (safely explorable); it can fail badly with irreversible actions since it cannot 'teleport' back like offline DFS.

What is the LRTA* (Learning Real-Time A*) algorithm, and how does it update heuristic estimates?

LRTA* is an online agent that stores a table of current cost estimates $H(s)$ (initialized to $h(s)$). It moves to the neighbor with the lowest estimated cost-to-goal and then updates its estimate of the state just left to $$H(s) \leftarrow \min_{a} \big( c(s, a, s') + H(s') \big).$$ These updates make estimates more accurate (increasing them out of dead ends), so the agent eventually learns to reach the goal and improves over repeated trials.

What is the Minimax algorithm, and what does the minimax value of a node represent?

Minimax computes the optimal move in a two-player, zero-sum, perfect-information game assuming both players play optimally. The minimax value of a node is the utility (for MAX) of being in the corresponding state, given optimal play by both sides: MAX nodes take the maximum of children's values, MIN nodes take the minimum, and terminal nodes use the utility function.

Give the recursive definition of the minimax value of a state.

$$\text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal} \\ \max_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if PLAYER}(s) = \text{MAX} \\ \min_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if PLAYER}(s) = \text{MIN} \end{cases}$$ MAX maximizes utility while MIN minimizes it, alternating by whose turn it is.

State the time and space complexity of the Minimax algorithm and its main practical limitation.

Minimax performs a complete depth-first exploration of the game tree with time complexity $O(b^{m})$ and space complexity $O(bm)$ (or $O(m)$ if actions are generated one at a time), where $b$ is the number of legal moves and $m$ is the maximum depth. Its limitation is that $O(b^{m})$ is infeasible for real games (e.g., chess), motivating alpha–beta pruning and depth-limited evaluation functions.

Compare Greedy Best-First Search and A* Search in terms of evaluation function, optimality, and typical efficiency.

Greedy Best-First uses $f(n) = h(n)$, is not optimal and not always complete, but is often fast because it heads straight for the goal. A* uses $f(n) = g(n) + h(n)$, is complete and optimal with an admissible/consistent heuristic, and is optimally efficient — but may expand many more nodes and use more memory because it accounts for path cost so far.