Unit 2: Problem Solving & Search in AI; AI problem design - Subjective Questions

Problem formulation is the process of deciding what actions and states to consider, given a goal. It abstracts a real-world problem into a well-defined structure that a search algorithm can solve.

A search problem is formally defined by five components:

• Initial state: The state from which the agent begins (e.g., In(Arad)).
• Actions: A description of the possible actions available in a given state, given by ACTIONS(s).
• Transition model: Describes what each action does, defined by RESULT(s, a) which returns the resulting state.
• Goal test: Determines whether a given state is a goal state.
• Path cost: A function that assigns a numeric cost to each path; often the sum of step costs .

Together, the initial state, actions, and transition model implicitly define the state space of the problem — the set of all reachable states. A solution is a sequence of actions leading from the initial state to a goal state, and an optimal solution has the lowest path cost among all solutions.

State space search is a technique used in AI to find a sequence of actions (a path) that transforms an initial state into a goal state by exploring the space of possible states.

Graph Representation:

• Nodes represent the states of the problem.
• Edges represent the actions (transitions) that move the agent from one state to another.
• Each edge may carry a cost (step cost) representing the resource required to perform that action.

Path:

• A path in the state space is a sequence of states connected by a sequence of actions.
• The path cost is the sum of the costs of the individual edges along the path.

Key ideas:

• The state space is often exponentially large or infinite, so it is generated on the fly rather than stored explicitly.
• A search tree is built over the state space, where the root is the initial state and branches represent actions. The same state may appear multiple times in the tree (as repeated nodes).
• The goal of search is to find a path from the root to a node satisfying the goal test, ideally the optimal (least-cost) one.

Uninformed search (also called blind search) refers to search strategies that have no additional information about states beyond that provided in the problem definition. They can only generate successors and distinguish a goal state from a non-goal state; they cannot estimate how close a state is to the goal.

Comparison of BFS and DFS (let = branching factor, = depth of shallowest goal, = maximum depth of the tree):

Key takeaways:

• BFS guarantees the shallowest solution but has heavy memory demands.
• DFS is memory-efficient but may get stuck in deep or infinite branches and is not optimal.
• Variants like Uniform-Cost Search (optimal for varying step costs) and Iterative Deepening DFS (combines BFS optimality with DFS memory efficiency) address these limitations.

Uniform-Cost Search (UCS) is an uninformed search strategy that expands the node with the lowest path cost (cumulative cost from the start node), rather than the shallowest node.

Working:

• Uses a priority queue ordered by the path cost .
• The goal test is applied when a node is selected for expansion (not when generated), because a cheaper path to the goal may still be found.
• A node's cost is updated if a cheaper path to it is discovered.

Optimality conditions:

• UCS is optimal provided that every step cost is non-negative (, and typically to guarantee termination).
• It is also complete under the same condition.

Difference from BFS:

• BFS orders nodes by depth (number of steps) and is optimal only when all step costs are equal.
• UCS orders nodes by actual path cost and is optimal even when step costs vary.
• When all step costs are equal, UCS behaves like BFS.

Complexity: Time and space are , where is the cost of the optimal solution and is the minimum step cost.

Best-First Search is a general search framework in which nodes are expanded based on an evaluation function . The node with the lowest value of is chosen for expansion using a priority queue. Different choices of yield different algorithms (Greedy, A*, UCS, etc.).

Greedy Best-First Search:

• Uses the heuristic function directly as the evaluation function: , where estimates the cost from node to the goal.
• It always expands the node that appears closest to the goal.

Example: In route-finding, might be the straight-line (Euclidean) distance to the destination.

Limitations:

• Not optimal: It ignores the cost already incurred , so it may find a suboptimal path.
• Not complete in its tree-search form: it can get stuck in loops or dead ends.
• Can be misled by a heuristic that looks locally promising but leads to a longer overall path.
• Worst-case time and space complexity is , but a good heuristic can reduce this dramatically.

A* search is a best-first search algorithm that combines the strengths of Uniform-Cost Search and Greedy Best-First Search by minimizing the total estimated cost of a solution through a node.

Evaluation function:

where:

• = actual cost from the start node to node ,
• = estimated (heuristic) cost from to the goal,
• = estimated total cost of the cheapest solution through .

Admissibility:

• A heuristic is admissible if it never overestimates the true cost to reach the goal:
  
  where is the true optimal cost from to the goal.
• Tree-search A* is optimal when is admissible.

Consistency (Monotonicity):

• A heuristic is consistent if for every node and successor generated by action :
  
• This is a triangle-inequality condition. Consistency implies admissibility.
• Graph-search A* is optimal when is consistent, because the values of along any path are non-decreasing.

Properties: A* is complete and optimally efficient — no other optimal algorithm using the same heuristic expands fewer nodes. Its main drawback is memory usage, since it keeps all generated nodes.

A heuristic function is a function that estimates the cost of the cheapest path from a node to a goal state. It provides problem-specific knowledge to guide search algorithms toward the goal more efficiently.

Properties of a good heuristic:

• Admissible: never overestimates the true cost ().
• Consistent: satisfies the triangle inequality.
• Informative (dominance): closer to the true cost yields fewer node expansions. If for all (both admissible), then dominates and is more efficient.
• Cheap to compute: the effort to compute should not outweigh the search savings.

Deriving heuristics from relaxed problems:

A relaxed problem is created by removing constraints on the actions. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem, since any real solution is also a solution to the relaxed problem.

8-Puzzle examples:

• = Number of misplaced tiles (relaxation: a tile can move anywhere in one step).
• = Sum of Manhattan distances of tiles from their goal positions (relaxation: a tile can move to any adjacent square regardless of whether it is blank).

Here dominates (), so generally expands fewer nodes while remaining admissible.

Uninformed (Blind) Search:

• Uses only the information in the problem definition (states, actions, goal test, cost).
• Has no domain knowledge about how close a state is to the goal.
• Examples: Breadth-First Search, Depth-First Search, Uniform-Cost Search, Iterative Deepening, Depth-Limited Search.

Informed (Heuristic) Search:

• Uses a heuristic function that provides an estimate of the cost from a node to the goal.
• Uses domain knowledge to guide the search more efficiently toward the goal.
• Examples: Greedy Best-First Search, A* Search, and their variants (IDA*, SMA*).

Comparison table:

Trade-offs:

• Informed search is usually faster and expands fewer nodes, but requires designing a good heuristic and computing it at each node.
• A poor or expensive heuristic can make informed search perform no better (or worse) than uninformed search.
• Uninformed search is simpler and general, applicable when no useful heuristic is available.

A Constraint Satisfaction Problem (CSP) is a problem defined by a set of variables that must be assigned values from their domains such that a set of constraints is satisfied. It represents states in a factored form rather than as atomic (black-box) states.

Three components:

1. Variables : The unknowns to be assigned values.
2. Domains : The set of allowable values for each variable.
3. Constraints : Rules specifying allowable combinations of values for subsets of variables.

A solution is a complete (every variable assigned) and consistent (all constraints satisfied) assignment.

Example — Map Coloring (Australia):

• Variables: The regions — WA, NT, SA, Q, NSW, V, T.
• Domains: Each variable can take a color from .
• Constraints: Adjacent regions must have different colors, e.g., , , , etc.

Advantages of the CSP formulation:

• Allows use of general-purpose solving techniques (backtracking, constraint propagation).
• Enables inference (e.g., arc consistency) to prune the search space efficiently.

Backtracking Search is a depth-first search tailored for CSPs. It assigns values to variables one at a time and backtracks when a variable has no legal value left, i.e., when a constraint is violated.

Algorithm outline:

• Select an unassigned variable.
• Try each value in its domain that is consistent with the current assignment.
• Recurse; if failure occurs, undo the assignment and try the next value.

Improving heuristics:

• Minimum Remaining Values (MRV): Choose the variable with the fewest legal values remaining. This fail-first heuristic detects failures early and prunes the tree.
• Degree heuristic: Tie-breaker for MRV — pick the variable involved in the most constraints on other unassigned variables.
• Least Constraining Value (LCV): When choosing a value, prefer the one that rules out the fewest choices for neighboring variables, keeping maximum flexibility.

Arc Consistency (AC-3):

• A variable is arc-consistent with respect to if, for every value in the domain of , there exists some value in the domain of satisfying the binary constraint between them.
• AC-3 is an algorithm that repeatedly enforces arc consistency by removing inconsistent values from domains, propagating changes through a queue of arcs.
• It is a form of constraint propagation / inference that reduces domains before or during search, often detecting failures early. Its time complexity is for constraints and domain size .

Optimization is the process of finding the values of variables (parameters) that minimize or maximize an objective (cost/loss) function . Many AI problems — such as training machine learning models — reduce to optimization.

Gradient-Based Optimization:

These methods use the gradient (vector of partial derivatives) of the objective function to iteratively move toward a minimum. The gradient points in the direction of steepest ascent, so to minimize, we step in the opposite direction.

Gradient Descent update rule:

Starting from an initial guess , the parameters are updated iteratively:

where:

• = parameter vector at iteration ,
• = learning rate (step size), controlling how far we move,
• = gradient of the objective evaluated at .

Variants:

• Batch Gradient Descent: Uses the entire dataset for each update.
• Stochastic Gradient Descent (SGD): Uses one example per update — faster but noisier.
• Mini-batch Gradient Descent: A compromise using small batches.

Key considerations:

• A large may overshoot/diverge; a small converges slowly.
• Gradient descent can get stuck in local minima or saddle points for non-convex functions; for convex functions it converges to the global minimum.

Metaheuristics are high-level, problem-independent strategies that guide the search for near-optimal solutions in large, complex, or poorly-understood search spaces. Unlike gradient-based methods, they do not require derivatives and are useful for non-differentiable, discrete, or highly non-convex problems. They balance exploration (searching new areas) and exploitation (refining good solutions).

1. Simulated Annealing (SA):

• Inspired by the annealing process in metallurgy (slow cooling).
• At each step it considers a random neighboring solution. If it is better, it is accepted. If it is worse, it is accepted with probability:
  
  where is the increase in cost and is the temperature.
• The temperature starts high (allowing many uphill moves) and is gradually lowered according to a cooling schedule.
• Escaping local optima: By accepting worse moves early on, SA can climb out of local minima before settling.

2. Genetic Algorithms (GA):

• Inspired by natural selection. Maintains a population of candidate solutions (chromosomes).
• Uses operators:
  • Selection: fitter individuals are chosen to reproduce.
  • Crossover: combines parts of two parents to form offspring.
  • Mutation: randomly alters genes to introduce diversity.
• Escaping local optima: Mutation and crossover maintain population diversity, exploring multiple regions of the search space simultaneously.

Common features: Both are stochastic, do not guarantee the global optimum, and trade optimality for the ability to handle large, rugged search landscapes.

Computational complexity measures the resources (time and memory) required by an algorithm as a function of the problem size. In search, complexity is expressed in terms of:

• = branching factor (maximum number of successors of any node),
• = depth of the shallowest goal node,
• = maximum depth of the search tree/state space.

Time Complexity:

• Measures the number of nodes generated/expanded during the search.
• For uninformed search over a tree, this typically grows exponentially, e.g., for BFS.

Space Complexity:

• Measures the maximum number of nodes stored in memory at any time.
• BFS stores the entire frontier: (its main bottleneck).
• DFS stores only a single path plus siblings: (very efficient).

Comparison of common algorithms:

Key insight: For most search algorithms, memory is a bigger practical limitation than time. This motivates memory-bounded variants like IDA* and SMA*.

Data Requirements:

The data needed by an AI problem-solving system depends on the approach:

• Search-based methods require a well-defined problem model: state representation, action/transition model, goal test, and cost function. They may need little to no training data but rely on an accurate model.
• Heuristic methods require domain knowledge to design effective heuristic functions.
• Learning-based methods (e.g., reinforcement learning) require experience data — interactions with the environment (states, actions, rewards) — often in large quantities.
• Key data concerns: quality, quantity, representativeness, and relevance of the data to the problem.

Solution Metrics (Performance Measures):

Algorithms are evaluated using four standard criteria:

• Completeness: Is the algorithm guaranteed to find a solution if one exists?
• Optimality: Does it find the least-cost (best) solution?
• Time Complexity: How long does it take (nodes generated)?
• Space Complexity: How much memory does it require?

Additional practical metrics:

• Solution quality / cost (how good the found solution is),
• Convergence rate (for optimization/learning),
• Robustness and scalability to larger problem instances,
• Effective branching factor (a measure of heuristic quality in A*).

Reinforcement Learning (RL) is a machine learning paradigm in which an agent learns to make decisions by interacting with an environment to maximize a cumulative reward signal. Unlike supervised learning, the agent is not told which actions to take but discovers them through trial and error.

Agent-Environment Interaction Loop:

At each discrete time step :

1. The agent observes the current state .
2. It selects an action .
3. The environment transitions to a new state and returns a reward .
4. The loop repeats.

Key Elements:

• State (): A representation of the current situation of the environment.
• Action (): A choice the agent can make from the set of available actions.
• Reward (): A scalar feedback signal indicating how good the immediate outcome of an action was. The agent's objective is to maximize the expected cumulative reward (return).
• Policy (): A mapping from states to actions, , defining the agent's behavior. It can be deterministic or stochastic.

Additional concepts:

• Value function : expected long-term return from state .
• Return: often the discounted sum of rewards , where is the discount factor.
• Exploration vs. Exploitation trade-off is central to RL.

A sequential decision problem involves making a series of decisions over time, where each decision affects future states and rewards. When the environment satisfies the Markov property (the future depends only on the current state and action, not the full history), it is modeled as a Markov Decision Process (MDP).

Components of an MDP — the tuple :

• — set of states.
• — set of actions.
• — transition probability of reaching state from state after action .
• — reward function for the transition.
• — discount factor balancing immediate vs. future rewards.

Objective: Find an optimal policy that maximizes the expected cumulative discounted reward:

Bellman Equation (for the state-value function under policy ):

Bellman Optimality Equation:

These recursive equations express the value of a state in terms of the values of successor states and form the basis of algorithms like Value Iteration and Policy Iteration.

Both are informed best-first search algorithms that use a heuristic, but they differ in their evaluation function and guarantees.

Comparison table:

Why Greedy is NOT optimal:

• It uses only , the estimated cost to the goal, ignoring the cost already spent to reach .
• It may repeatedly choose the node that looks closest to the goal, following a path that is short-sighted but has a high total cost, thereby missing the cheaper overall route.

Why A* IS optimal:

• It balances both (cost incurred) and (estimated remaining cost).
• With an admissible heuristic, never overestimates the true cost of a solution through . Hence A* will never expand a suboptimal goal before the optimal one, because any node on the optimal path has , while a suboptimal goal has .

Conclusion: By accounting for the actual cost so far, A* corrects the myopia of Greedy search and guarantees the least-cost solution.

The 8-queens problem requires placing 8 queens on an chessboard such that no two queens attack each other — no two share the same row, column, or diagonal.

As a CSP:

• Variables: One per column, (the row position of the queen in each column).
• Domains: Each (rows).
• Constraints: For all : (different rows) and (not on the same diagonal).

1. Incremental Formulation (for tree search):

• States: Any arrangement of 0 to 8 queens on the board.
• Initial state: Empty board.
• Actions: Add a queen to an empty square.
• Goal test: 8 queens placed with none attacking each other.
• Problem: Naive version has sequences. A better version places one queen per column, reducing states drastically to .

2. Complete-State Formulation (for local search):

• States: All 8 queens on the board (one per column), possibly with conflicts.
• Initial state: A random complete configuration.
• Actions: Move a queen within its column to reduce conflicts.
• Goal test / objective: Zero pairs of attacking queens.
• Used by local search / hill-climbing methods, which start with a full assignment and iteratively improve it. The objective is to minimize the number of attacking pairs (heuristic = number of conflicts).

Comparison: The incremental formulation builds solutions step-by-step (suited to backtracking), while the complete-state formulation modifies full configurations (suited to local search and metaheuristics).

Exploration vs. Exploitation Dilemma:

In reinforcement learning, an agent faces a fundamental trade-off when selecting actions:

• Exploitation: Choosing the action currently believed to yield the highest reward based on existing knowledge. This maximizes immediate gain.
• Exploration: Choosing a different, possibly suboptimal action to gather more information about the environment, which may lead to better rewards in the future.

The dilemma: If the agent only exploits, it may get stuck with a suboptimal action, never discovering better alternatives. If it only explores, it wastes opportunities to earn known rewards. A good agent must balance the two to maximize long-term cumulative reward.

-Greedy Strategy:

A simple and widely used method to balance the trade-off:

• With probability (small, e.g., 0.1), the agent explores by choosing a random action.
• With probability , the agent exploits by choosing the action with the highest estimated value (greedy action).

Refinements:

• Decaying : Start with a high (more exploration early) and gradually reduce it over time so the agent increasingly exploits as it learns.
• Alternative strategies include softmax/Boltzmann action selection and Upper Confidence Bound (UCB) methods.

Hill Climbing is a local search algorithm that continually moves in the direction of increasing value (or decreasing cost) — it keeps only the current state and moves to the best neighbor. It is like climbing a hill in dense fog while suffering from amnesia.

Challenges / Problems:

• Local Maxima: A peak that is higher than its neighbors but lower than the global maximum. The algorithm halts here, mistaking it for the best solution.
• Plateaus (flat regions): An area where neighboring states have the same value. The search cannot decide which way to move and may wander aimlessly or stop prematurely. A special case is a shoulder, from which progress is possible.
• Ridges: A sequence of local maxima where each step in the available directions leads downhill, even though the overall ridge slopes upward — making it hard to navigate with simple moves.

Mitigation Strategies:

• Random-Restart Hill Climbing: Run the search from multiple random initial states and keep the best result. This dramatically increases the chance of finding the global optimum.
• Stochastic Hill Climbing: Choose randomly among uphill moves, with probability weighted by steepness.
• Simulated Annealing: Allow occasional downhill moves (with decreasing probability) to escape local optima.
• Sideways moves: Permit a limited number of moves across a plateau to escape shoulders.
• Local Beam Search / Genetic Algorithms: Maintain multiple states in parallel to explore several regions simultaneously.

Trade-off: These methods use very little memory and can handle large state spaces but sacrifice the completeness and optimality guarantees of systematic search.