Unit2 - Subjective Questions

Problem Formulation is the process of deciding what actions and states to consider, given a goal. It is the first step in problem-solving agents.

A well-defined search problem consists of the following five components:

1. Initial State: The state in which the agent starts.
2. Actions: A description of possible actions available to the agent. Given a state , returns the set of actions executable in .
3. Transition Model: A description of what each action does. Result() returns the state that results from doing action in state .
4. Goal Test: Determines whether a given state is a goal state. It can be explicit (e.g., a specific location) or implicit (e.g., checkmate condition).
5. Path Cost: A function that assigns a numeric cost to each path. The problem-solving agent usually attempts to minimize this cost. It is often denoted as .

State Space Search is a mathematical model of a physical system where the set of all possible states is represented as a graph. Nodes represent states, and edges represent transitions (actions).

Water Jug Problem Example:
Given two jugs, a 4-gallon jug and a 3-gallon jug, and a pump. The goal is to measure exactly 2 gallons in the 4-gallon jug.

1. State Representation: We represent the state as an ordered pair , where:
   • = number of gallons in the 4-gallon jug ().
   • = number of gallons in the 3-gallon jug ().
2. Initial State: (Both jugs are empty).
3. Goal State: (Where is any amount).
4. Operators (Actions):
   • Fill 4-gallon jug:
   • Fill 3-gallon jug:
   • Empty 4-gallon jug:
   • Empty 3-gallon jug:
   • Pour from 3 to 4:
   • Pour from 4 to 3:

The search algorithm navigates from applying these operators until is reached.

Iterative Deepening Search (IDS) is a strategy that repeatedly applies Depth-Limited Search with increasing depth limits () until the goal is found.

Why it is preferred:

1. Memory Efficiency: Like DFS, its memory complexity is only , making it far superior to BFS in terms of space.
2. Completeness: Like BFS, it is complete (it will find a solution if one exists) provided the branching factor is finite.
3. Optimality: Like BFS, it is optimal if all step costs are identical.

Conclusion: IDS combines the benefits of BFS (optimality/completeness) and DFS (space efficiency), making it the preferred uninformed search method for large search spaces where the depth of the solution is unknown.

*A Search** is the most widely known form of best-first search. It evaluates nodes by combining the cost to reach the node, , and the estimated cost to get from the node to the goal, .

Evaluation Function:

• : The cost to reach node from the start state.
• : The estimated cost of the cheapest path from to the goal (heuristic).
• : The estimated total cost of the cheapest solution through .

Condition for Optimality:
A* is optimal if the heuristic is Admissible.

• Admissibility: A heuristic is admissible if it never overestimates the cost to reach the goal. Mathematically, , where is the true cost to reach the goal.
• In graph search, a stronger condition called Consistency (or monotonicity) is required.

Heuristic Function ():
A function that estimates the cost of the cheapest path from a node to a goal state. It injects domain-specific knowledge into the search algorithm to improve efficiency compared to uninformed search.

Properties:

1. Admissibility:

   • A heuristic is admissible if it never overestimates the cost to reach the goal.
   • i.e., for all nodes , where is the actual cost.
   • If is admissible, A* tree search is optimal.

2. Consistency (Monotonicity):

   • A heuristic is consistent if, for every node and every successor generated by action , the estimated cost of reaching the goal from is no greater than the step cost of getting to plus the estimated cost from to the goal.
   • Equation: (Triangle Inequality).
   • Consistency implies Admissibility.

Greedy Best-First Search:

• Evaluation Function: . It expands the node that appears to be closest to the goal.
• Strategy: Tries to get as close to the goal as possible as quickly as possible.
• Optimality: Not optimal. It may find a solution, but not necessarily the lowest-cost one.
• Completeness: Incomplete (can get stuck in loops), unless the state space is finite and check for repeated states.

*A Search:**

• Evaluation Function: . Considers both path cost so far and estimated cost to go.
• Strategy: Balances finding the shortest path with moving toward the goal.
• Optimality: Optimal (guaranteed to find the least-cost path if is admissible).
• Completeness: Complete.

A Constraint Satisfaction Problem (CSP) is a mathematical problem defined as a set of objects whose state must satisfy a number of constraints or limitations.

Components:

1. Variables (): A set of variables, .
2. Domains (): A set of domains, , where each variable has a set of possible values .
3. Constraints (): A set of constraints that specify allowable combinations of values for a subset of variables.

Example: Map Coloring

• Variables: The regions (e.g., ).
• Domains: The colors (e.g., ).
• Constraints: Adjacent regions must have different colors (e.g., $WA
  eq NT$).

Backtracking Search is a depth-first search algorithm used for finding solutions to CSPs. It builds candidates for the solution incrementally and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Key Steps:

1. Select Unassigned Variable: Choose a variable that hasn't been assigned a value yet.
2. Order Domain Values: Iterate through values in the domain of .
3. Check Consistency: For each value, check if assigning it to violates any constraints with current assignments.
4. Assign & Recurse: If consistent, assign the value and recursively call the function for the next variable.
5. Backtrack: If a variable has no legal values left, return failure, remove the last assignment, and try the next value for the previous variable.

It is often improved using heuristics like Minimum Remaining Values (MRV) and Forward Checking.

Hill Climbing is a local search optimization algorithm. It maintains a single current state and iteratively moves to a neighboring state with a better value (higher utility/lower cost). It terminates when no neighbor is better than the current state.

Problems/Limitations:

1. Local Maxima: A peak that is higher than each of its neighboring states but lower than the global maximum. The algorithm gets stuck here, thinking it has reached the top.
2. Plateaux: A flat area of the state-space landscape. It can be a flat local maximum or a shoulder. The algorithm may wander aimlessly because all moves result in the same value.
3. Ridges: A sequence of local maxima that is difficult for greedy algorithms to navigate. The orientation of the high ground is such that every single move (North, South, East, West) leads down, even though the peak is still upwards in a diagonal direction.

Gradient Descent is a first-order iterative optimization algorithm for finding a local minimum of a differentiable function. It takes steps proportional to the negative of the gradient (or approximate gradient) of the function at the current point.

Update Rule:

Differentiation:

1. Batch Gradient Descent:
   • Calculates the gradient using the entire dataset to perform a single update.
   • Stable convergence but computationally very expensive and slow for large datasets.
2. Stochastic Gradient Descent (SGD):
   • Calculates the gradient using one single sample (or a small batch) at each iteration.
   • Much faster and consumes less memory.
   • Convergence is noisy (fluctuates) but allows it to jump out of local minima.

Metaheuristics are higher-level procedure-independent heuristics designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem, especially with incomplete information or limited computation capacity.

Simulated Annealing:

• Inspired by the process of annealing in metallurgy (heating metal and cooling it slowly to toughen it).
• It is a probabilistic technique for approximating the global optimum of a given function.
• Unlike Hill Climbing, it allows downhill moves (worse moves) to escape local maxima.
• The probability of accepting a worse move depends on the "Temperature" (). High initially allows frequent bad moves (Exploration); as decreases, the algorithm becomes more greedy (Exploitation).
• Acceptance probability: where is the change in value.

Genetic Algorithms are a search heuristic inspired by Charles Darwin’s theory of natural evolution. They reflect the process of natural selection where the fittest individuals are selected for reproduction.

Core Operators:

1. Selection:

   • The process of choosing the fittest individuals from the current population to be parents for the next generation.
   • Common method: Roulette Wheel Selection or Tournament Selection, where better fitness scores have a higher probability of being chosen.

2. Crossover (Recombination):

   • The most significant phase. Two parent strings are combined to produce offspring.
   • A crossover point is chosen at random within the genes. Offspring are created by exchanging the genes of parents until the crossover point.
   • Example: Parent A ($11111$), Parent B ($00000$) Offspring ($11100$).

3. Mutation:

   • Used to maintain genetic diversity.
   • Involves flipping the value of one or more bits in the chromosome string with a low probability.
   • Helps prevent the algorithm from getting stuck in local optima by introducing random changes.

In AI search, complexity determines the efficiency and feasibility of an algorithm.

Variables used:

• : Branching factor (maximum number of successors of any node).
• : Depth of the shallowest goal node.
• : Maximum length of any path in the state space.

1. Time Complexity:

• Measures how long an algorithm takes to find a solution.
• Measured in terms of the number of nodes generated or expanded.
• Example: BFS Time Complexity is .

2. Space Complexity:

• Measures how much memory is required to perform the search.
• Measured in terms of the maximum number of nodes stored in memory at any one time.
• Example: DFS Space Complexity is , whereas BFS is .

To compare search algorithms, we evaluate them on four criteria:

1. Completeness:
   • Does the algorithm guarantee finding a solution when there is one? If the state space is infinite, completeness usually requires a systematic search.
2. Optimality:
   • Does the strategy find the optimal solution (the one with the lowest path cost) among all possible solutions?
3. Time Complexity:
   • How long does it take to find a solution? Usually measured by the number of nodes generated during the search.
4. Space Complexity:
   • How much memory is needed to perform the search? This is often the limiting factor in AI problems.

Reinforcement Learning (RL) is a type of machine learning where an agent learns to make decisions by performing actions in an environment and receiving feedback (rewards or penalties).

Key Components:

1. Agent: The entity that makes decisions and takes actions (e.g., a robot or a software program).
2. Environment: The world through which the agent moves and responds to (e.g., a maze or a video game).
3. State (): A snapshot of the environment at a specific time. It represents the current situation of the agent.
4. Action (): The set of all possible moves the agent can make in a given state.
5. Reward (): A scalar feedback signal from the environment indicating how good or bad the action taken was. The goal is to maximize cumulative reward.

The Exploration vs. Exploitation dilemma is a fundamental challenge in Reinforcement Learning:

1. Exploration:

   • The agent tries new actions that it hasn't tried before (or has tried rarely) to discover their effects.
   • Goal: To gather information about the environment. While it might lead to negative rewards initially, it may reveal better long-term strategies.

2. Exploitation:

   • The agent chooses actions that it already knows yield high rewards based on past experience.
   • Goal: To maximize immediate rewards using current knowledge.

The Trade-off: If an agent only exploits, it may get stuck in a sub-optimal strategy. If it only explores, it never benefits from its learning. A balance is required (e.g., using -greedy strategy where the agent explores with probability and exploits with probability ).

A Markov Decision Process (MDP) is a mathematical framework used to describe an environment in reinforcement learning and sequential decision making. It assumes the Markov Property: the future state depends only on the current state and action, not the history.

Tuple Representation: An MDP is defined by a 5-tuple :

1. (State Space): A set of all valid states in the environment.
2. (Action Space): A set of all valid actions the agent can take.
3. (Transition Probability): is the probability of transitioning to state given the current state and action . (Defines the dynamics).
4. (Reward Function): is the immediate reward received after transitioning from to via action .
5. (Discount Factor): A number between $0$ and $1$ () that determines the importance of future rewards. A value close to 0 makes the agent "myopic" (greedy), while closer to 1 makes it far-sighted.

The 8-puzzle consists of a board with 8 numbered tiles and one blank space.

1. States: A state description specifies the location of each of the 8 tiles and the blank in one of the nine squares.
2. Initial State: Any configuration of the board (e.g., random arrangement).
3. Actions (Operators): The blank space moves Left, Right, Up, or Down. (Alternatively viewed as moving a tile into the blank space).
4. Goal Test: Checks whether the state matches the goal configuration (usually ordered $1, 2, 3...$ with blank at the end).
5. Path Cost: Each step costs 1 unit. The path cost is the total number of steps taken to reach the goal.

Note: The state space size is (since half are reachable), which is $181,440$ reachable states.

Data Requirements refer to the nature, volume, and quality of information needed to formulate and solve an AI problem effectively.

1. Training Data: For learning-based search (like RL or heuristic learning), large amounts of labeled or interactive data are required.
2. State Representation: The data must accurately capture the nuances of the environment. Incomplete data leads to Partially Observable environments, making the search harder.
3. Quality: Noisy data (errors in transition models or sensors) can mislead search algorithms. Garbage In, Garbage Out (GIGO) applies.
4. Quantity:
   • Simple Search: Requires minimal data (just the rules/transition model).
   • Complex Optimization/Learning: Requires massive datasets to generalize well.
5. Relevance: Data must be relevant to the goal. Irrelevant features increase the state space dimensionality unnecessarily (Curse of Dimensionality).