Artificial Intelligence

Chapter 3
Search, Optimization and Constraint Satisfaction

Post Graduate Program in IT Engineering
Artificial Intelligence • Post Graduate

Search, Optimization and Constraint Satisfaction

Introduction and Context

Artificial intelligence systems frequently act by searching through alternatives. A route planner searches possible paths, a diagnostic system searches hypotheses, a scheduling system searches assignments, and a game-playing program searches future positions. In each case, intelligence depends not only on finding a solution but also on controlling computational cost, representing uncertainty or restrictions, and selecting solutions that are useful according to an objective.

This chapter examines the principal computational paradigms for problem solving: uninformed and informed search, heuristic search, adversarial search, local search, constraint satisfaction, evolutionary computation, and mathematical optimization. These paradigms are related but not interchangeable. A shortest-path problem, a timetable problem, and a chess move-selection problem may all be called “search problems,” yet they differ in state representation, evaluation criteria, observability, and solution guarantees.

At postgraduate level, the central concern is algorithmic judgment: selecting an appropriate formulation, understanding assumptions and guarantees, engineering an effective search procedure, and evaluating trade-offs among completeness, optimality, time, memory, robustness, and interpretability.

Learning Objectives

After studying this chapter, the learner should be able to:

formulate an AI task as a state-space or optimization problem;
distinguish uninformed, informed, local, adversarial, and constraint-based search;
explain completeness, optimality, branching factor, depth, and computational complexity;
apply breadth-first, uniform-cost, depth-first, iterative-deepening, greedy, and A* search;
construct admissible and consistent heuristics and assess their limitations;
explain minimax and alpha-beta pruning for deterministic adversarial games;
model and solve constraint satisfaction problems using propagation and backtracking;
compare hill climbing, simulated annealing, genetic algorithms, and mathematical optimization;
evaluate practical and ethical implications of search-based AI systems.

1. Problem Formulation as Search

A search problem is commonly represented by the tuple

\langle S, A, Result, s_0, Goal, Cost \rangle,

where \(S\) is the set of states, \(A\) is the set of actions, \(Result(s,a)\) is the state produced by action \(a\) in state \(s\), \(s_0\) is the initial state, \(Goal\) identifies goal states, and \(Cost\) assigns a non-negative cumulative cost to a path. A solution is a sequence of actions leading from \(s_0\) to a goal state. An optimal solution has minimum path cost among all solutions.

The formulation is an abstraction. A road-navigation system need not represent every physical detail of a vehicle; it may represent only road intersections and travel costs. Good abstraction removes irrelevant detail without removing information needed to distinguish valid from invalid solutions.

A search tree records alternative paths generated from the initial state, whereas a search graph recognizes that different paths may reach the same state. Graph search maintains an explored set to avoid repeated expansion. This distinction is important because repeated states can cause exponential growth or infinite loops even when a finite solution exists.

Important performance properties are:

Completeness: whether the algorithm is guaranteed to find a solution whenever one exists.
Optimality: whether it returns a least-cost solution.
Time complexity: the number of generated or expanded nodes.
Space complexity: the maximum number of nodes stored.
Branching factor \(b\): the typical number of successors per state.
Solution depth \(d\): the depth of the shallowest goal.
Maximum depth \(m\): the greatest depth considered or possible.

Complexity estimates using \(b\), \(d\), and \(m\) are asymptotic approximations. They assume a roughly uniform branching factor and do not replace empirical evaluation.

2. Uninformed Search

Uninformed, or blind, search uses no domain-specific estimate of distance to a goal. Its decisions depend on the structure of the frontier and, in some methods, path cost.

2.1 Breadth-First Search

Breadth-first search (BFS) expands the shallowest unexpanded node first, normally using a FIFO queue. If every action has equal cost, BFS is complete and optimal because the first goal found is at the smallest depth. With variable action costs, however, shallowest does not necessarily mean cheapest; BFS is not generally cost-optimal in that setting.

For finite branching factor \(b\), BFS has time and space complexity approximately \(O(b^{d+1})\), because it stores a large frontier at the shallowest goal level. Its principal engineering weakness is memory consumption.

2.2 Uniform-Cost Search

Uniform-cost search (UCS) expands the node with the smallest path cost \(g(n)\). It is equivalent to Dijkstra’s algorithm when applied to a graph with non-negative edge costs. UCS is complete and optimal if every step cost is at least a positive constant \(\epsilon>0\), and graph-search duplicate handling is correctly implemented. If zero-cost cycles are allowed, termination and duplicate management require additional care.

UCS is appropriate when costs differ materially, for example when a route planner trades distance against tolls and energy. Its weakness is that it may explore a very large region before discovering a goal.

2.3 Depth-First and Iterative-Deepening Search

Depth-first search (DFS) follows one branch as far as possible before backtracking. It has low space complexity, approximately \(O(bm)\) for a tree implementation, but is not complete in infinite-depth spaces or spaces containing cycles unless cycle checking or depth limits are used. It is not generally optimal.

Iterative-deepening depth-first search (IDDFS) repeatedly performs depth-limited DFS with limits 0, 1, 2, and so on. It combines the low memory requirement of DFS with the shallow-solution completeness and unit-cost optimality of BFS. Its repeated expansion of upper-level nodes is often acceptable because most nodes occur at the deepest level. IDDFS is especially useful when solution depth is unknown and action costs are uniform.

3. Informed and Heuristic Search

An informed algorithm uses additional problem knowledge. A heuristic function \(h(n)\) estimates the cost from node \(n\) to a goal. The path cost already incurred is \(g(n)\), and A* defines

f(n)=g(n)+h(n).

The heuristic does not need to be exact. Its value lies in ordering alternatives so that promising states are examined earlier.

3.1 Greedy Best-First Search

Greedy best-first search selects the node with the smallest \(h(n)\). It can be fast when the heuristic is informative, but it ignores the cost already incurred. Consequently, it may select an apparently nearby goal reached through an expensive path and is not generally optimal. It can also be incomplete in infinite spaces or spaces with cycles without suitable graph-search controls.

3.2 A* Search

A* selects the smallest \(f(n)=g(n)+h(n)\). The heuristic is admissible if

0\le h(n)\le h^*(n),

where \(h^(n)\) is the true minimum cost from \(n\) to a goal. Under standard conditions, including non-negative step costs and appropriate graph-search handling, A tree search is optimal with an admissible heuristic. For graph search, the usual sufficient condition is a consistent (or monotone) heuristic:

h(n)\le c(n,n')+h(n')

for every edge from \(n\) to successor \(n'\), with \(h(goal)=0\). Consistency implies admissibility and ensures that \(f\)-values do not decrease along a path. If a graph-search implementation permits reopening states when a cheaper path is found, admissibility can still support optimality under broader conditions.

A* is complete when branching is finite and each step cost is bounded below by a positive constant. Its worst-case time and space requirements remain exponential in solution depth; a good heuristic reduces the effective search substantially but does not remove the worst-case difficulty.

3.3 Designing Heuristics

A heuristic can be derived by relaxing constraints. In the 8-puzzle, the number of misplaced tiles is admissible because each misplaced tile requires at least one move. Manhattan distance—the sum of row and column distances of tiles from their goal positions—is also admissible when a move shifts one tile by one grid position, because it ignores interference among tiles. Manhattan distance dominates the misplaced-tile heuristic: it is never smaller and is often more informative, while remaining admissible.

If two admissible heuristics \(h_1\) and \(h_2\) are available, \(h(n)=\max(h_1(n),h_2(n))\) is also admissible and is at least as informative as either individually. Combining heuristics by addition is not automatically admissible; it requires a justification such as disjoint cost components.

Heuristics may also be learned from data. Learned estimates can be highly effective but require validation, monitoring for distribution shift, and safeguards when an incorrect estimate can produce unsafe decisions. In safety-critical applications, a conservative verified heuristic or a bounded-suboptimal method may be preferable.

3.4 Bounded and Memory-Limited Search

Weighted A uses \(f_w(n)=g(n)+w h(n)\), with \(w\ge1\). If \(h\) is admissible and implementation assumptions hold, weighted A can provide a bounded trade-off between solution quality and speed; the precise bound depends on the algorithm and weighting scheme, so it must not be asserted without specifying those conditions. Recursive best-first search and memory-bounded A* variants reduce memory use by discarding and later regenerating nodes. These methods are valuable when the full frontier cannot fit in memory, but their performance depends strongly on heuristic quality and regeneration overhead.

4. Adversarial Search and Game Playing

In a deterministic, turn-taking, zero-sum game with perfect information, one player’s gain is the other player’s loss. A game can be represented by an initial state, legal actions, a transition model, terminal tests, and a utility function. Unlike ordinary planning, the agent must account for an opponent who actively chooses actions that undermine its objective.

4.1 Minimax

Minimax assumes that MAX chooses actions maximizing utility and MIN chooses actions minimizing it. At terminal states, utility is evaluated directly. At a MAX node,

V(s)=\max_{a\in Actions(s)}V(Result(s,a)),

and at a MIN node,

V(s)=\min_{a\in Actions(s)}V(Result(s,a)).

For finite games with accurate terminal utilities, minimax returns an optimal move against a rational opponent. Exhaustive search is often infeasible, so practical systems stop at a depth limit and use an evaluation function. A typical evaluation function combines domain features, for example material advantage, positional safety, and mobility in a board game. Such evaluations are approximations and can be exploited by opponents if they contain systematic weaknesses.

4.2 Alpha-Beta Pruning

Alpha-beta pruning returns the same minimax decision while avoiding branches that cannot affect the final choice. Alpha \(\alpha\) is the best value MAX can guarantee along the current path; beta \(\beta\) is the best value MIN can guarantee. A branch can be pruned when \(\alpha\ge\beta\).

With poor move ordering, alpha-beta has the same order of worst-case time as minimax. With ideal ordering, the effective explored depth can approach twice that of minimax for the same computational effort. This is an upper-bound intuition, not a guarantee for arbitrary positions. Move ordering, transposition tables, iterative deepening, and domain-specific move generation are central engineering techniques.

Game-playing systems also face horizon effects: a depth-limited search may overlook a consequence just beyond its cutoff. Quiescence search extends analysis in tactically unstable positions. In stochastic or imperfect-information games, expectiminimax, belief-state search, Monte Carlo tree search, or decision-theoretic methods may be more appropriate than ordinary minimax.

5. Local Search and Optimization

Local search maintains one or a small number of current candidate solutions rather than an explicit frontier of complete paths. It is appropriate when the objective is the quality of a final configuration and the path to that configuration is irrelevant. Examples include layout design, timetable construction, parameter tuning, and vehicle routing.

5.1 Hill Climbing

Hill climbing repeatedly moves to a neighboring state with a better objective value. Variants include steepest-ascent, stochastic, and first-choice hill climbing. It uses little memory but may stop at a local optimum, plateau, or ridge. Random-restart hill climbing runs the method from multiple initial states and retains the best result; it is often effective when good solutions are distributed across several basins of attraction.

5.2 Simulated Annealing

Simulated annealing sometimes accepts a worsening move to escape local optima. For a minimization problem, a move increasing objective cost by \(\Delta E>0\) may be accepted with probability

P(accept)=e^{-\Delta E/T},

where \(T>0\) is the current temperature. This formula assumes a dimensionless energy difference or, more generally, that \(\Delta E/T\) is dimensionless after suitable scaling. As temperature decreases according to a cooling schedule, worsening moves become less likely. The method is not guaranteed to reach a global optimum under ordinary finite schedules; theoretical convergence results require very slow schedules and conditions rarely practical at scale.

5.3 Evolutionary Computation

A genetic algorithm maintains a population of encoded candidate solutions. A generation normally involves fitness evaluation, selection, crossover, mutation, and replacement. Selection increases the representation of high-fitness candidates; crossover recombines representations; mutation introduces variation. Constraint handling may use repair operators, penalty functions, feasibility-preserving encodings, or multiobjective treatment.

Evolutionary methods are useful for discontinuous, non-differentiable, noisy, or multi-modal objectives. They require choices about representation, population size, mutation rate, selection pressure, and termination. They can converge prematurely, consume many evaluations, and produce solutions that are difficult to explain. Their stochastic results should be assessed across repeated runs using confidence intervals or suitable non-parametric comparisons rather than a single lucky run.

6. Constraint Satisfaction Problems

A constraint satisfaction problem (CSP) consists of variables \(X_1,\ldots,X_n\), domains \(D_1,\ldots,D_n\), and constraints restricting allowable combinations of values. A solution assigns every variable a domain value while satisfying all constraints. Examples include examination timetabling, employee rostering, configuration, and map coloring.

Constraints may be unary, binary, or global. A binary constraint relates two variables; an all-different constraint requires a set of variables to take distinct values. CSPs differ from ordinary path search because the order of assigning variables is often incidental, while propagation can eliminate impossible values before a complete assignment is constructed.

6.1 Backtracking and Heuristics

Backtracking search assigns variables recursively and returns to an earlier decision when a constraint is violated. Three heuristics are especially important:

Minimum remaining values (MRV): select the variable with the smallest current domain.
Degree heuristic: break ties using the variable involved in the largest number of unassigned constraints.
Least-constraining value: try the value that eliminates the fewest options for neighboring variables.

These heuristics do not change worst-case exponential complexity, but they can reduce practical search dramatically.

6.2 Constraint Propagation

Forward checking removes values from neighboring domains whenever a variable is assigned. If any future domain becomes empty, the branch is abandoned immediately. Arc consistency is stronger. For a binary constraint between variables \(X_i\) and \(X_j\), an arc from \(X_i\) to \(X_j\) is consistent if every value in the domain of \(X_i\) has at least one supporting value in the domain of \(X_j\). Algorithms such as AC-3 repeatedly remove unsupported values until no more can be removed or a domain becomes empty.

Propagation is valuable because it detects failure before full assignment. However, consistency of individual arcs does not guarantee a global solution, and stronger consistency usually requires greater computational cost. Modern solvers combine propagation with backjumping, conflict-directed learning, nogood recording, and specialized global constraints.

6.3 SAT, Integer Programming, and Hybrid Solving

Many CSPs can be translated into Boolean satisfiability (SAT), mixed-integer linear programming (MILP), or constraint programming (CP). SAT excels at logical structure and conflict learning; MILP is powerful when relationships can be expressed linearly and objective costs are important; CP provides rich finite-domain constraints and propagation. Hybrid systems may use CP for combinatorial feasibility and MILP for resource allocation. Formulation quality often matters more than the nominal choice of solver.

7. Mathematical Optimization

Optimization seeks a feasible solution minimizing or maximizing an objective function. A general form is

\min_{x} f(x) \quad \text{subject to } g_i(x)\le0,\; i=1,\ldots,m,

\quad h_j(x)=0,\; j=1,\ldots,p.

Here \(x\) is the decision vector, \(f\) is the objective, and \(g_i,h_j\) express inequality and equality constraints. Linear programming has linear objective and constraints; integer programming restricts some variables to integer values; nonlinear programming permits nonlinear relationships.

Convex optimization is especially important because, under standard regularity conditions, every local optimum is global. For non-convex problems, local methods may return different solutions depending on initialization. Lagrangian methods, gradient-based algorithms, branch-and-bound, cutting planes, and metaheuristics provide different trade-offs between proof of optimality and scalability.

A professional solution should distinguish a feasible solution from a proven optimum, report solver tolerances and termination status, and test sensitivity to changed costs, capacities, and constraints. An apparently optimal plan may be operationally poor if it is fragile, unfair, or based on inaccurate data.

8. Illustrative Case: University Examination Timetabling

Background. A university must schedule examinations into rooms and time slots. Students enrolled in multiple courses must not have overlapping examinations. Rooms have capacities and equipment constraints, invigilators have availability limits, and institutional policy may require minimum spacing between examinations.

Problem formulation. Each examination is a variable. Its domain contains feasible time-room combinations. Hard constraints prevent student conflicts, room collisions, capacity violations, and unavailable-room assignments. Soft constraints express preferences such as avoiding multiple examinations on one day, spreading assessments, and minimizing late-evening sessions. The objective may minimize a weighted penalty for soft-constraint violations.

Analysis. A naïve assignment search has a huge branching factor. A CSP model is appropriate because constraints can eliminate values early. Student conflicts form a graph: highly connected examinations should receive priority. The solver can use MRV to select the most restricted examination, degree to resolve ties, and forward checking or generalized arc consistency to remove incompatible placements. A CP-SAT or MILP formulation can provide an alternative, especially when explicit resource variables and penalty costs are required.

Approach. First, assign hard constraints and verify feasibility. Next, apply propagation and search with conflict learning. If no perfect soft solution exists, optimize a transparent weighted objective. Multiple schedules can be generated and evaluated for robustness, fairness across student groups, room utilization, and sensitivity to late enrolment changes. Human schedulers should review exceptional cases rather than merely accepting the numerical objective.

Outcome. In an illustrative deployment, propagation rapidly rejects room-time combinations that conflict with large student cohorts, while a penalty-aware optimizer improves spacing without violating hard constraints. The resulting schedule is not judged solely by its objective score: administrators also inspect accessibility, travel time between buildings, and whether particular programs systematically receive undesirable slots.

Learning points. The case demonstrates that representation determines tractability; hard and soft constraints must be distinguished; optimization should not hide policy choices; and human oversight is necessary when the objective incompletely represents institutional values.

9. Practical Engineering, Governance, and Limitations

Search algorithms can be computationally expensive, stochastic, and sensitive to formulation. Best practices include:

1. define states, actions, costs, constraints, and termination conditions explicitly;

2. test on small instances where exhaustive verification is possible;

3. instrument node expansions, memory, runtime, solution quality, and constraint violations;

4. use deterministic seeds for debugging and repeated independent runs for evaluation;

5. separate hard safety constraints from preferences and penalties;

6. report infeasibility, approximation, timeout, and optimality gaps honestly;

7. validate solutions against real operational data and adversarial edge cases;

8. preserve an audit trail of model versions, heuristics, weights, and solver settings.

Search-based AI may allocate scarce resources, prioritize inspections, or influence access to services. If costs or constraints encode historical discrimination, optimization can reproduce it efficiently. A mathematically optimal solution can still be legally impermissible or ethically unacceptable. Governance therefore requires fairness assessment, privacy protection, explainable policy choices, contestability, and human accountability. In safety-critical systems, a fallback policy and formally verified constraints may be more important than marginal improvements in average objective value.

10. Contemporary Directions

Current research combines classical search with learned components. Neural networks can estimate heuristics, rank moves, guide branching, or predict promising variables. Neural-guided search is powerful but introduces distribution-shift and verification challenges. Large-scale planning increasingly uses hierarchical search, retrieval of reusable subplans, and learned world models.

Portfolio solvers select among algorithms according to instance characteristics. Parallel search distributes frontier nodes, populations, or independent random restarts, although duplicate work and synchronization overhead must be managed. Multiobjective optimization treats competing goals explicitly, producing a Pareto frontier rather than concealing trade-offs in one arbitrary weighted sum. Robust and distributionally aware optimization address uncertainty in demand, travel time, failures, and model predictions.

The enduring principle is hybridization: exact methods provide guarantees where possible, heuristics provide speed, learning provides instance-specific guidance, and human expertise defines acceptable objectives and constraints.

Chapter Summary

Search formulates intelligent action as exploration of states, paths, assignments, or candidate solutions. Uninformed methods differ in frontier discipline: BFS is optimal for equal step costs, UCS handles non-negative variable costs, DFS saves memory but lacks general guarantees, and IDDFS combines low memory with shallow-solution guarantees under unit costs. Informed search uses heuristics; A* balances accumulated cost and estimated remaining cost, with admissibility and consistency supporting optimality under stated assumptions.

Adversarial search models strategic opponents through minimax, while alpha-beta pruning reduces computation without changing the minimax result. Local search optimizes complete configurations using neighborhood moves, randomization, temperature schedules, or populations. CSPs represent variables, domains, and constraints; backtracking, variable/value ordering, and propagation make large combinatorial problems tractable. Mathematical optimization distinguishes feasibility, local quality, and proven global optimality, particularly through linear, integer, nonlinear, and convex formulations.

Effective professional practice requires careful formulation, empirical benchmarking, transparent objectives, sensitivity analysis, and honest reporting of guarantees. Because search systems can distribute opportunities and resources, fairness, privacy, auditability, and human accountability are integral engineering requirements rather than optional additions.

Key Terms

State space: Set of states reachable or considered in a problem.

Action: An operation that transforms one state into another.

Frontier: Generated but not yet expanded search nodes.

Completeness: Guarantee of finding a solution if one exists.

Optimality: Guarantee that the returned solution has minimum cost or maximum utility.

Branching factor: Typical number of successors per state.

Heuristic: Domain-informed estimate used to guide search.

Admissible heuristic: Heuristic that never overestimates true remaining cost.

Consistent heuristic: Heuristic satisfying the triangle-like monotonicity condition across every edge.

A*: Search using the evaluation function \(g+h\).

Minimax: Adversarial search method assuming optimal opposing players.

Alpha-beta pruning: Elimination of minimax branches that cannot affect the decision.

Local optimum: State better than all neighboring states but not necessarily globally best.

Simulated annealing: Stochastic local search that may accept worsening moves.

Genetic algorithm: Population-based evolutionary optimization method.

Constraint satisfaction problem: Variables, domains, and constraints defining allowable assignments.

Arc consistency: Property that every value has support in the connected variable’s domain.

Feasible solution: Solution satisfying all hard constraints.

Pareto frontier: Set of non-dominated solutions in multiobjective optimization.

Optimality gap: Difference or bound separating a known solution from a proven optimum.

Review Questions

Short Answer Questions

1. What is the difference between a search tree and a search graph?

2. Under what condition is breadth-first search optimal?

3. Define an admissible heuristic.

4. What is the purpose of alpha-beta pruning?

5. How does forward checking improve CSP backtracking?

Long Answer Questions

1. Compare BFS, UCS, DFS, and IDDFS in terms of completeness, optimality, time, and space.

2. Explain A* search, including the roles of \(g(n)\), \(h(n)\), admissibility, and consistency.

3. Describe minimax and alpha-beta pruning, and discuss the effect of move ordering.

4. Explain how MRV, degree heuristics, least-constraining values, and arc consistency work together in CSP solving.

5. Critically compare hill climbing, simulated annealing, genetic algorithms, and mathematical optimization.

Analytical / Application Questions

1. Design a heuristic for a warehouse robot route-planning problem. Explain whether it is admissible and how you would test that claim.

2. Formulate a university examination timetable as a CSP with hard and soft constraints. Propose a search and propagation strategy.

3. A scheduling optimizer produces the lowest numerical penalty but assigns consistently undesirable time slots to one student group. Analyze the likely modeling problem and propose technical and governance remedies.

Multiple Choice Questions with Answers

Question 1

Which search strategy expands the node with the lowest cumulative path cost?

A. Breadth-first search

B. Uniform-cost search

C. Greedy best-first search

D. Depth-first search

Correct Answer: B. Uniform-cost search

Question 2

For A* tree search, which property of h(n) is sufficient for optimality under the standard nonnegative-cost assumptions?

A. It always overestimates the remaining cost

B. It is admissible

C. It is equal to zero at every state

D. It depends only on path depth

Correct Answer: B. It is admissible

Question 3

Which condition permits alpha-beta pruning of a branch?

A. g(n) is zero

B. The node is at even depth

C. Alpha is greater than or equal to beta

D. The evaluation function is linear

Correct Answer: C. Alpha is greater than or equal to beta

Question 4

What does the MRV heuristic select in a constraint satisfaction problem?

A. The variable with the largest domain

B. The variable with the smallest remaining domain

C. The value with the highest numerical cost

D. The least connected variable

Correct Answer: B. The variable with the smallest remaining domain

Question 5

In simulated annealing for minimization, what happens to the acceptance probability of a fixed worsening move as temperature decreases?

A. It increases to one

B. It remains constant

C. It decreases

D. It becomes negative

Correct Answer: C. It decreases

Question 6

Which statement about breadth-first search is correct?

A. It is always optimal with arbitrary positive edge costs

B. It is optimal when all action costs are equal

C. It uses less memory than depth-first search

D. It uses a priority queue ordered by heuristic value

Correct Answer: B. It is optimal when all action costs are equal

Question 7

A heuristic h(n) is consistent when it satisfies which relationship for every edge from n to n'?

A. h(n) is greater than c(n,n') plus h(n')

B. h(n) equals g(n)

C. h(n) is less than or equal to c(n,n') plus h(n')

D. h(n) is always greater than zero

Correct Answer: C. h(n) is less than or equal to c(n,n') plus h(n')

Question 8

What is the principal purpose of arc consistency?

A. To guarantee a globally optimal assignment

B. To remove values lacking support in a neighboring domain

C. To maximize the number of variables

D. To replace all constraints with objectives

Correct Answer: B. To remove values lacking support in a neighboring domain

Question 9

Which method maintains a population of candidate solutions and applies selection, crossover, and mutation?

A. Genetic algorithm