i. Simple Reflex Agent:

A Simple Reflex Agent is the most fundamental category of intelligent agents that selects actions strictly based on the current percept, completely ignoring the historical sequence of past percepts. It operates using condition-action rules (e.g., IF status == Dirty THEN action = Suck). It can only succeed in fully observable environments; if the environment is partially observable, it can suffer from infinite loops and thrashing behavior.

ii. The State of the Art (SOTA) in AI:

State-of-the-Art (SOTA) refers to the highest level of general technological development and performance achieved at a specific time. In modern AI, SOTA systems represent frontier capabilities across multiple domains, including:

• Large Language & Multimodal Foundation Models: Advanced reasoning and understanding systems like GPT-4o, Gemini 1.5/2.0 Pro, and Claude 3.5 Sonnet.
• Autonomous Physical Agents: Commercial Level-4 autonomous vehicles (Waymo, Tesla FSD) and humanoid robotics.
• Scientific Discovery: DeepMind's AlphaFold 3 (3D molecular biology and protein structure prediction).
• Superhuman Game Playing: AlphaGo, AlphaZero, and Stockfish NNUE exceeding all human grandmasters.

i. Artificial Intelligence (AI):

Artificial Intelligence is the branch of computer science dedicated to engineering computational systems that can perceive their environment, learn from experience, reason logically, and autonomously perform tasks that typically require human cognitive intelligence (such as decision-making, visual perception, and problem-solving).

ii. Rationality:

Rationality is the property of an agent acting to do the "right thing"—mathematically defined as selecting actions that maximize its expected performance measure given the percept sequence observed so far and its built-in domain knowledge. Rationality does not mean omniscience or perfection; it means optimal expected performance under uncertainty.

1. Scientific Definition of Intelligence vs. Dictionary Definition:

• Dictionary Definition: "The ability to acquire and apply knowledge and skills" (Oxford/Webster). This definition is human-centric, vague, and lacks quantifiable operational metrics for computational systems.
• Scientific Definition: A computational entity's capacity to perceive environmental states via sensors, construct internal world models, evaluate alternative candidate action sequences using expected utility, and execute actions via actuators to achieve specific goals under uncertainty and resource constraints.

2. Methods Used to Define Artificial Intelligence:

1. Thinking Humanly: Cognitive modeling approach; reverse-engineering the neural and psychological workings of the human mind.
2. Thinking Rationally: The "Laws of Thought" approach; formalizing deductive inference using mathematical logic (syllogisms, First-Order Logic).
3. Acting Humanly: The Turing Test approach; evaluating whether a machine can converse indistinguishably from a human interrogator.
4. Acting Rationally: The Rational Agent approach; building systems that act to achieve the best expected outcome based on their beliefs and percepts.

3. Which Definition is Most Appropriate and Why:

The Acting Rationally (Rational Agent) approach is universally recognized as the most appropriate standard in contemporary AI because:

• It is mathematically objective and quantifiable via expected utility theory.
• It is more general than human thought, as humans frequently behave irrationally due to emotional biases or cognitive limits.
• It facilitates rigorous engineering and algorithmic optimization (search, probabilistic reasoning, reinforcement learning).

"Can machine think?" & Alan Turing's Imitation Game:

In his seminal 1950 paper Computing Machinery and Intelligence, British mathematician Alan Turing argued that the metaphysical question "Can machines think?" is too ambiguous. He proposed replacing it with an operational behavioral benchmark called the Imitation Game (The Turing Test):

• Setup: A human interrogator is situated in a separate room from two respondents: a human and a digital computer. Communication occurs solely via text terminals.
• Rule: The interrogator poses arbitrary questions across any topic. The computer tries to fool the interrogator into believing it is the human, while the human tries to assist the interrogator in making the correct identification.
• Pass Criterion: If the interrogator cannot reliably tell the machine from the human after 5 minutes of conversation (error rate \(\ge 30\%\)), the computer is said to exhibit thinking intelligence.

Properties of an Intelligent Agent:

1. Autonomy: Acts on its own experience rather than solely on pre-programmed instructions.
2. Reactivity: Perceives environmental stimuli and responds promptly.
3. Proactiveness: Goal-directed behavior; takes initiative to accomplish objectives.
4. Social Ability: Communicates and coordinates with other agents and humans.

Can all agents be called 'rational'? Justify with example.

Answer: NO. An agent is strictly rational only if its selected action maximizes the mathematical expectation of its performance measure given its percept sequence and built-in knowledge base.

Justification with Counter-Example:

• Consider a Simple Reflex Vacuum Cleaner in a partially observable environment with two rooms (A and B). If its sensors cannot detect which room it is currently in and its reflex rule is IF current_square == Clean THEN move_Right, upon arriving in room B and finding it clean, it will attempt to move Right again, repeatedly hitting the wall and wasting energy in an infinite loop while dirt accumulates in room A. Because this behavior minimizes expected performance rather than maximizing it, the agent is irrational.
• Similarly, a smart thermostat that turns on maximum air conditioning during sub-zero freezing weather is an agent, but it is demonstrably irrational.

How can you express the goals of rational agents? Explain with example.

The goals of a rational agent are formally captured through a Performance Measure (or Utility Function \(U: S \to \mathbb{R}\)) that maps an environmental sequence of states to real-valued desirability scores. A rational agent expresses its objective mathematically as maximizing its Expected Utility:

Concrete Example (Automated Taxi Driver):

Instead of a naive binary goal ("Reach destination: True/False"), a rational taxi agent expresses its goals as a multi-attribute utility function:

This allows the agent to make rational trade-offs—such as choosing a slightly longer route that guarantees high safety over a risky, illegal shortcut.

i. PEAS Specification for AI Traffic Regulator (ATR):

ii. Environment Characterization with Reasoning:

• Deterministic vs. Stochastic → Stochastic: Traffic flow cannot be calculated deterministically. Driver reaction times, vehicle breakdowns, sudden lane changes, and pedestrian crossings introduce fundamental randomness.
• Episodic vs. Sequential → Sequential: A traffic signal decision made at 8:00 AM directly impacts traffic queue density and bottleneck formation at 8:15 AM. Every action cascades into future states.

iii. Agent Architecture Selection:

Most Suitable Structure: Utility-Based Agent (with Learning):

Reasoning: A Simple Reflex agent cannot handle partial observability and creates phantom gridlocks. A Goal-Based agent only recognizes binary goals ("clear the junction: Yes/No"), but cannot balance trade-offs. Traffic control inherently involves conflicting objectives (e.g., delaying side-street vehicles by 30 seconds to allow a massive 100-car highway platoon to pass, or pausing all traffic for an ambulance). A Utility-Based Agent maps state sequences to continuous real-valued happiness scores, enabling optimal mathematical trade-offs under heavy uncertainty.

i. PEAS Specification for Autonomous Rescue Robot:

ii. Characterization of Environment (with Reasoning):

• Fully vs. Partially Observable → Partially Observable: Murky floodwaters, collapsed roofs, and rain obscure human victims and submerged hazards from sensor range.
• Deterministic vs. Stochastic → Stochastic: Shifting flood currents, drifting debris, and changing weather cannot be predicted with 100% certainty.
• Episodic vs. Sequential → Sequential: Navigating through a narrow waterway consumes battery and alters the robot's future reachability to distant victims.
• Discrete vs. Continuous → Continuous: Robot position, velocity, water currents, steering angles, and sensor readings vary continuously over real numbers.

iii. Agent Architecture Selection:

Most Suitable Structure: Utility-Based Agent (with Learning):

Reasoning: In life-threatening rescue missions, goals frequently conflict under severe resource constraints (e.g., whether to rescue one critically injured person immediately versus searching for a group of five victims before the robot's battery depletes). Only a Utility-Based Agent can assign real-valued utilities to risky alternatives, calculating expected utility to make rational trade-offs between speed, victim survival probability, and robot risk.

i. PAGE / PEAS Description for Automated Taxi Driver:

• Percepts (Sensors): Video feed from 360° cameras, LiDAR 3D point clouds, radar echoes, GPS coordinates, speedometer data, engine diagnostics, passenger voice commands.
• Actions (Actuators): Steering wheel angle, electronic throttle acceleration, brake pressure, gear shift, turn signals, horn, passenger cabin UI.
• Goals: Deliver passengers safely, legally, comfortably, and promptly to destination while maximizing operating profit.
• Environment: City streets, expressways, dynamic traffic, erratic pedestrians, road detours, weather conditions.

ii. Characterization of the Environment:

• Inaccessible (Partially Observable): The taxi cannot perceive what is around blind corners or inside the minds of other human drivers.
• Non-deterministic (Stochastic): Tires can skid, pedestrians can step off curbs without looking, and other vehicles behave unpredictably.
• Non-episodic (Sequential): Every driving action (e.g. changing lanes) fundamentally affects future opportunities, positioning, and safety.
• Dynamic: Traffic and pedestrians keep moving while the agent's computer processes sensor data and deliberates.
• Continuous: Velocity, steering angle, time, and coordinates are all continuous variables.

iii. Best Architecture & Justification:

Model-Based Utility Agent with Learning: Must maintain an internal model of the world (road network map, tracking obscured vehicles) and calculate continuous trade-offs between safety, ride smoothness, and travel speed using expected utility theory.

i. PEAS Specification for Game Playing AI - Chess:

• P (Performance): Win (+1), Draw (0), Loss (-1); board material evaluation, center control, king safety.
• E (Environment): 64-square chessboard, 32 game pieces, opposing human or AI player.
• A (Actuators): Display generated move on screen (algebraic notation like e2-e4) or robotic manipulator arm.
• S (Sensors): Digital board state input / optical camera tracking piece coordinates.

ii. Characterization of the Environment:

• Fully Observable: The complete state of the board and all pieces are visible at all times.
• Deterministic: Each move has a 100% predictable transition with zero random chance.
• Static: The board state does not change while the agent is calculating its next move (apart from the chess clock).
• Discrete: A finite set of discrete board squares and legal move actions.
• Multi-Agent (Competitive / Zero-Sum): Two agents competing where one agent's gain is exactly the opponent's loss.

1. State Space Diagram for Vacuum-Cleaner World:

The vacuum world in Figure 01 has 2 locations (\(A\) and \(B\)), and each location can be either Clean (\(C\)) or Dirty (\(D\)).

Total discrete states = \(2 \text{ (Agent locations)} \times 2^2 \text{ (Clean/Dirty combinations)} = 8 \text{ States}\):

  State 1: [Agent in A, A: Dirty, B: Dirty]   State 2: [Agent in B, A: Dirty, B: Dirty]
  State 3: [Agent in A, A: Clean, B: Dirty]   State 4: [Agent in B, A: Clean, B: Dirty]
  State 5: [Agent in A, A: Dirty, B: Clean]   State 6: [Agent in B, A: Dirty, B: Clean]
  State 7: [Agent in A, A: Clean, B: Clean]   State 8: [Agent in B, A: Clean, B: Clean]
            

Actions: Left, Right, Suck. From State 1, Suck → State 3; Right → State 2. From State 2, Suck → State 6; Left → State 1. All 8 states form a complete directed graph with transitions governed by the movement and cleaning actions.

2. Partial Tabulation Representation (Percept Sequences → Action):

Vacuum Cleaner World with 2 Rooms and 8 Locations (\(A_{11}, A_{12}, A_{21}, A_{22}, B_{11}, B_{12}, B_{21}, B_{22}\)):

Actions Available: Left, Right, Up, Down, Suck, NoOp.

1. How to Formulate a Search Problem (The 5 Core Elements):

1. Initial State \(s_0\): The state in which the agent starts (e.g. \(\text{In}(Arad)\)).
2. Actions \(ACTIONS(s)\): The set of legal moves executable from state \(s\).
3. Transition Model \(RESULT(s, a)\): Formal description of what each action does, returning successor state \(s'\).
4. Goal Test \(GOAL\text{-}TEST(s)\): A boolean predicate checking whether state \(s\) satisfies the goal condition (e.g. \(s == \text{In}(Bucharest)\)).
5. Path Cost Function \(c(s, a, s')\) & Total Cost \(g(n)\): Sum of individual step costs measuring the quality of the path.

2. Justification: "A search state keeps only the details needed for planning (abstraction)":

In real life, a traveling agent has infinite physical parameters: exact tire pressure, paint color, radio frequency, passenger clothing, and wind speed. If all these details were included in the state representation, the state space would become infinite and computationally intractable.

Abstraction is the deliberate process of removing irrelevant real-world details, preserving only the features essential for problem solving. In route planning, the state needs only the current city node (e.g., \(\text{In}(Sibiu)\)). All other features are abstracted away.

3. Explicit vs. Implicit State Space Representations (Spring 2022 Q2.b):

• Explicit Data Structure: Every state and transition edge is explicitly pre-allocated in memory (e.g., Adjacency Matrix, Adjacency List). Only usable for small graphs (\(|V| \le 10^5\)).
• Implicit Data Structure: States are generated dynamically on demand using generative successor functions / rules (e.g., in Chess or 8-Puzzle with \(10^{40}\) states, the graph is generated dynamically during search tree expansion).

Formal Search Problem Formulation: Traveling from Arad to Bucharest:

• Initial State: \(\text{In}(Arad)\)
• Actions Available: \(\{ \text{Go}(c) \mid c \text{ is directly connected to current city by road} \}\)
• Transition Model: \(RESULT(\text{In}(x), \text{Go}(y)) = \text{In}(y)\) if road \((x, y)\) exists.
• Goal Test: \(State == \text{In}(Bucharest)\)
• Path Cost: Sum of road segment distances in kilometers: \(g(n) = \sum \text{distance}(x, y)\).

Differentiate BFS, DFS, DLS, and UCS:

Where \(b\) = branching factor, \(d\) = shallowest goal depth, \(m\) = maximum tree depth, \(l\) = depth limit, \(C^*\) = optimal path cost, \(\epsilon\) = minimum step cost.

1. Definition of Heuristic:

A Heuristic is a problem-solving rule of thumb or domain-specific evaluation function \(h(n)\) that estimates the remaining cost from current node \(n\) to the nearest goal state. It does not guarantee a perfect solution by itself, but dramatically prunes the search space by guiding the algorithm toward promising paths.

2. Heuristics of the 8-Queens Problem:

• Cost Heuristic \(h(n)\): The number of pairs of queens that are attacking each other (either directly or indirectly along the same row or diagonal). A goal state has \(h(n) = 0\).
• Fitness Heuristic \(f(n)\): The number of non-attacking pairs of queens: \(f(n) = \binom{8}{2} - h(n) = 28 - h(n)\). The goal state maximizes fitness to \(f(n) = 28\).

3. Heuristics of the 8-Puzzle Problem (Autumn 2023 Q1.b):

• \(h_1\) (Misplaced Tiles): The number of tiles that are not in their target goal positions. It is admissible because every misplaced tile must be moved at least once.
• \(h_2\) (Manhattan Distance): The sum of vertical and horizontal distances that tiles are displaced from their goal positions: \(\sum |x_i - x_{goal}| + |y_i - y_{goal}|\). \(h_2\) strictly dominates \(h_1\) (\(h_2(n) \ge h_1(n)\) for all \(n\)) and is both admissible and consistent.

A* Search Tree from Arad to Bucharest (Romania Map):

Formula: \(f(n) = g(n) + h(n)\), where \(g(n)\) is exact path cost from Arad, and \(h(n)\) is straight-line distance to Bucharest from the table.

1. Step 1: Expand Arad:
   • \(g(\text{Arad}) = 0, h(\text{Arad}) = 366 \implies f(\text{Arad}) = 366\).
   • Successors:
     • Sibiu: \(g = 140, h = 253 \implies f = 393\)
     • Timisoara: \(g = 118, h = 329 \implies f = 447\)
     • Zerind: \(g = 75, h = 374 \implies f = 449\)
   • Select minimum \(f\): Sibiu (\(f = 393\)).
2. Step 2: Expand Sibiu:
   • Successors:
     • Fagaras: \(g = 140 + 99 = 239, h = 178 \implies f = 417\)
     • Rimnicu Vilcea: \(g = 140 + 80 = 220, h = 193 \implies f = 413\)
     • Oradea: \(g = 140 + 151 = 291, h = 380 \implies f = 671\)
   • Frontier: Rimnicu Vilcea (413), Fagaras (417), Timisoara (447), Zerind (449), Oradea (671).
   • Select minimum \(f\): Rimnicu Vilcea (\(f = 413\)).
3. Step 3: Expand Rimnicu Vilcea:
   • Successors:
     • Pitesti: \(g = 220 + 97 = 317, h = 98 \implies f = 415\)
     • Craiova: \(g = 220 + 146 = 366, h = 160 \implies f = 526\)
   • Frontier: Pitesti (415), Fagaras (417), Timisoara (447), Zerind (449), Craiova (526), Oradea (671).
   • Select minimum \(f\): Pitesti (\(f = 415\)).
4. Step 4: Expand Pitesti:
   • Successors:
     • Bucharest: \(g = 317 + 101 = 418, h = 0 \implies f = 418\)
     • Craiova: \(g = 317 + 138 = 455, h = 160 \implies f = 615\) (pruned, worse than existing).
   • Frontier: Fagaras (417), Bucharest (418), Timisoara (447), Zerind (449), Craiova (526), Oradea (671).
   • Select minimum \(f\): Fagaras (\(f = 417\)).
5. Step 5: Expand Fagaras:
   • Successors:
     • Bucharest: \(g = 239 + 211 = 450, h = 0 \implies f = 450\) (inferior to existing path of 418).
   • Frontier: Bucharest (418), Timisoara (447), Zerind (449), Bucharest (450), Craiova (526), Oradea (671).
   • Select minimum \(f\): Bucharest (\(f = 418\)) → Goal reached!

Final Solution Path: \(\text{Arad} \to \text{Sibiu} \to \text{Rimnicu Vilcea} \to \text{Pitesti} \to \text{Bucharest}\)

Total Solution Cost: \(140 + 80 + 97 + 101 = \mathbf{418\text{ km}}\).

Graph Specifications: Start = \(S\), Goal = \(G\).

Arc Costs: \(S \to A: 2\), \(S \to D: 5\), \(A \to B: 1\), \(A \to D: 2\), \(B \to C: 4\), \(B \to E: 5\), \(D \to E: 2\), \(E \to F: 4\), \(F \to G: 3\).

Heuristics to \(G\): \(h(S)=11.0, h(A)=10.4, h(B)=6.7, h(C)=4.0, h(D)=8.9, h(E)=6.9, h(F)=3.0, h(G)=0\).

Strategy 1: Uniform Cost Search (UCS) — Orders by \(g(n)\):

UCS Solution Path: \(S \to A \to D \to E \to F \to G\) • Cost: 13 • Total Nodes Expanded: 7.

Strategy 2: Greedy Best-First Search — Orders by \(h(n)\):

Greedy Solution Path: \(S \to D \to E \to F \to G\) • Cost: \(5 + 2 + 4 + 3 = 14\) • Total Nodes Expanded: 4.

Strategy 3: A* Search — Orders by \(f(n) = g(n) + h(n)\):

A* Solution Path: \(S \to A \to D \to E \to F \to G\) • Cost: 13 • Total Nodes Expanded: 7.

1. Search Tree Generation for A* Search Space:

Given the search graph with start \(S\) and goal \(G\), arc costs, parent pointers, and \(h^*(n)\) table: \(h^*(S)=9, h^*(A)=9, h^*(B)=4, h^*(C)=5, h^*(D)=\infty, h^*(E)=\infty, h^*(G)=0\).

Heuristics given in diagram: \(h(S)=8, h(A)=8, h(B)=4, h(C)=3, h(D)=\infty, h(E)=\infty, h(G)=0\).

2. Identifying the Inconsistency Problem:

Notice the edge between \(C\) and \(G\): Arc cost \(c(C, G) = 5\). Heuristic values: \(h(C) = 3\), but actual \(h^*(C) = 5\). However, on edge \(S \to C\): Arc cost is 8, \(h(S)=8, h(C)=3 \implies h(S) - h(C) = 5 \le 8\) (consistent). But on node \(A\): \(c(A, G) = 9\), \(h(A) = 8\). When expanding \(A\), if a node is closed and its heuristic drops steeply, standard graph search that permanently discards closed nodes will miss the optimal path!

3. How to Solve Any Problem That Arises (Fixing Graph Inconsistency):

1. Node Reopening: In graph search, if a new path to a previously closed node \(n\) is discovered with a strictly lower \(g(n)\) value, reopen node \(n\) and re-insert it into the Frontier (Open List).
2. Pathmax Equation: Enforce monotonicity along any step from \(n\) to child \(n'\) using: $$f(n') = \max(g(n') + h(n'), f(n))$$
3. Consistency Adjustment: Modify the heuristic function so it obeys the triangle inequality: \(h(n) \le c(n, a, n') + h(n')\).

Part (a): Find Solution Path and Cost by A* Graph Search:

Graph Setup: Start \(S\), Goal \(G\). Arc costs: \(S \to A: 1, S \to B: 1, A \to C: 1, B \to C: 2, C \to G: 3\). Heuristics: \(h(S)=2, h(A)=4, h(B)=1, h(C)=1, h(G)=0\).

1. Expand \(S\):
   • Child \(A\): \(g=1, h=4 \implies f(A) = 5\).
   • Child \(B\): \(g=1, h=1 \implies f(B) = 2\).
   Open List: \([B(2), A(5)]\). Expand minimum: Node \(B\).
2. Expand \(B\):
   • Child \(C\): \(g = 1 + 2 = 3, h = 1 \implies f(C) = 4\).
   Open List: \([C(4), A(5)]\). Expand minimum: Node \(C\).
3. Expand \(C\):
   • Child \(G\): \(g = 3 + 3 = 6, h = 0 \implies f(G) = 6\).
   Node \(C\) is placed into Closed List \(\{S, B, C\}\). Open List: \([A(5), G(6)]\).
4. Expand \(A\):
   • Child \(C\): via \(A\), path cost would be \(g(C) = 1 + 1 = 2\). But in strict graph search without node reopening, \(C\) is already in Closed List and is DISCARDED!
5. Expand \(G\): Goal reached with \(f(G) = 6\).

Returned Path: \(S \to B \to C \to G\) • Cost: 6.

Part (b): Determine whether the solution is optimal or not. If not, make it optimal:

1. Optimality Check: The solution \(S \to B \to C \to G\) (cost 6) is NOT OPTIMAL! The true optimal path is \(S \to A \to C \to G\) with cost \(1 + 1 + 3 = \mathbf{5} < 6\).

2. Cause of Failure: The heuristic is inconsistent (non-monotonic). Between node \(A\) and node \(C\):

The estimated distance drops by 3 over an edge of cost 1, violating the triangle inequality \(h(A) \le c(A, C) + h(C) = 1 + 1 = 2\).

3. How to Make it Optimal:

• Algorithmic Fix: Enable Reopening of Closed Nodes in Graph Search. When expanding \(A\), since \(g_{new}(C) = 2 < g_{old}(C) = 3\), update \(g(C) = 2\) and re-insert \(C\) into Open List with \(f(C) = 2 + 1 = 3\). Then \(C\) expands to \(G\) with optimal cost \(2 + 3 = 5\).
• Heuristic Fix: Make the heuristic consistent by reducing \(h(A)\) to \(\le 2\) (e.g., set \(h(A) = 2\)). Then \(f(A) = 1 + 2 = 3 < f(C)=4\), so \(A\) expands before \(C\), finding the optimal path naturally.

1. The Hill Climbing Algorithm:

Hill Climbing is an iterative local search algorithm that continuously moves in the direction of increasing heuristic value (uphill) without maintaining a search tree or frontier. The algorithm terminates when it reaches a peak where no neighbor has a higher value.

function HILL-CLIMBING(problem) returns a state that is a local maximum
  current = problem.INITIAL-STATE
  loop do
    neighbor = HIGHEST-VALUED-SUCCESSOR(current)
    if VALUE(neighbor) <= VALUE(current) then return current.STATE
    current = neighbor
            

2. Why Greedy Hill Climbing Has Very Low Memory Requirements (Spring 2024 Q3.a):

Hill Climbing is a local search method that only maintains a single current state and its immediate successors in memory. Unlike BFS or A* which maintain exponential open lists (\(O(b^d)\)), Hill Climbing requires \(O(1)\) memory space.

3. The Three Main Drawbacks & How to Deal With Them:

1. Local Maxima: A peak that is higher than all its neighboring states, but lower than the global maximum. The algorithm terminates prematurely thinking it found the optimum.
   Remedy: Random-Restart Hill Climbing (conducting multiple runs from random initial states).
2. Ridges: A sequence of local maxima joined together sloping upward. Because successors are evaluated along single coordinates, all immediate moves go downhill off the ridge, stalling the search.
   Remedy: Perform diagonal or macro-moves combining multiple operators.
3. Plateaux (Flat Local Maximum & Shoulders): A flat region where all adjacent states have identical evaluation values. The algorithm wanders aimlessly or gets stuck.
   Remedy: Allow a limited number of sideways moves (e.g. up to 100 consecutive equal-value steps) or use Simulated Annealing.

Analysis of the 8-Queens Grid Search:

i. Write a suitable heuristic function:

The standard heuristic function \(h(n)\) is defined as the number of pairs of queens attacking each other (either directly or indirectly along rows or diagonals). For a valid goal state, \(h(n) = 0\).

ii. What is the heuristic value of this start space?

By inspecting the board queens (one queen in each column) and counting all mutual attacks (e.g. queens sharing rows or diagonals), the heuristic value of the current configuration is \(h = \mathbf{17}\).

iii. How many total successors of the start space?

In the standard formulation of the 8-queens problem, each of the 8 columns has exactly 1 queen. In any single move, an operator shifts one queen to any other row within its column. Since each column has 8 rows, a queen has \(8 - 1 = 7\) available moves. Across all 8 columns:

iv. How to achieve 100% success for these types of problem?

• Random-Restart Hill Climbing: Run the hill climbing algorithm repeatedly from uniformly distributed random initial board states. Since each restart has an independent probability of success \(p \approx 0.14\), the probability of finding the global optimum after \(k\) runs is \(1 - (1 - p)^k\). As \(k\) increases, success rate approaches 100%.
• Simulated Annealing: Allow probabilistic downhill moves with probability \(e^{\Delta E / T}\) to escape local maxima and plateaux.
• Min-Conflicts Local Search: A specialized CSP heuristic that resolves 8-queens in almost linear time \(O(n)\) with 100% reliability even for \(10,000,000\) queens!

The Blocks World Problem (Local vs. Global Heuristic Functions):

Start State: Stack containing \([A \text{ on } H \text{ on } G \text{ on } F \text{ on } E \text{ on } D \text{ on } C \text{ on } B]\) resting on table.

Goal State: Stack containing \([H \text{ on } G \text{ on } F \text{ on } E \text{ on } D \text{ on } C \text{ on } B \text{ on } A]\) resting on table.

i. Two Different Types of Heuristic Functions & Their Values:

• Local Heuristic Function \(h_{local}\): Evaluates only individual support relationships.
  • For each block: \(+1\) if it rests on the correct block as specified in the goal state; \(-1\) if it rests on an incorrect block.
  • In the Start State: Every block rests on an incorrect block. For example, A is on H (incorrect), H is on G (correct in isolation, but below it everything is reversed). Local score is deeply negative.
• Global Heuristic Function \(h_{global}\): Evaluates the complete structural validity of the sub-stack beneath each block.
  • For each block: \(+n\) (where \(n\) is depth/height) if the block and the entire sub-stack underneath it perfectly matches the goal state; \(-n\) if any block in the support structure beneath it is incorrect.

ii. Solving the Blocks World Problem:

To reach the goal from the start stack, block A must be at the very bottom on the table. Therefore, all blocks above A must be unstacked onto the table first, creating empty space, and then reassembled in ascending sequence: Table → A → B → C → D → E → F → G → H.

iii. Which Heuristic Function Leads to a Local Maximum? (Autumn 2022 Q1.b Proof):

The Local Heuristic Function inevitably leads to a Local Maximum!

Reasoning: To place block A on the table, the agent must pick up blocks (like H, G, etc.) and move them to the table. When moving block H from G to the table, the local heuristic sees that H was resting on G (\(+1\)) and is now on the table (\(-1\)), so the heuristic value decreases! Greedy hill climbing refuses to make moves that decrease heuristic score, so it stalls immediately in a local maximum without solving the problem.

In contrast, the Global Heuristic Function recognizes that H resting on an incorrect foundation is fundamentally flawed (\(-n\)). Dismantling the stack removes the large negative penalty, creating a strictly uphill gradient that successfully reaches the global goal state.

Genetic Algorithm on 8-Queens Problem:

Population chromosomes: \(X_1 = 24748552, X_2 = 32752411, X_3 = 24415124, X_4 = 32543213\).

Fitness formula: \(f(X) = \text{number of non-attacking pairs} = 28 - \text{attacking pairs}\).

Given: \(f(X_1) = 24\) (4 attacking pairs), \(f(X_2) = 23\) (5 attacking pairs).

i) Evaluate the fitness of \(X_3\) and \(X_4\) (showing all calculations):

For \(X_3 = [2, 4, 4, 1, 5, 1, 2, 4]\):

• Row conflicts (same digit):
  • Digit 2 appears in col 1 and col 7 → 1 pair \((Q_1, Q_7)\).
  • Digit 4 appears in col 2, col 3, col 8 → \(\binom{3}{2} = 3\) pairs: \((Q_2, Q_3), (Q_2, Q_8), (Q_3, Q_8)\).
  • Digit 1 appears in col 4 and col 6 → 1 pair \((Q_4, Q_6)\).
  • Total Row Conflicts: \(1 + 3 + 1 = 5\).
• Diagonal conflicts (\(|r_i - r_j| == |c_i - c_j|\)):
  • \(Q_2(4)\) at col 2 and \(Q_4(1)\) at col 4: \(|4 - 1| = 3, |2 - 4| = 2 \implies\) no.
  • \(Q_5(5)\) at col 5 and \(Q_6(1)\) at col 6: \(|5 - 1| = 4, |5 - 6| = 1 \implies\) no.
  • \(Q_4(1)\) at col 4 and \(Q_5(5)\) at col 5: \(|1 - 5| = 4, |4 - 5| = 1 \implies\) no.
  • \(Q_1(2)\) at col 1 and \(Q_2(4)\) at col 2: \(|2 - 4| = 2, |1 - 2| = 1 \implies\) no.
  • \(Q_6(1)\) at col 6 and \(Q_7(2)\) at col 7: \(|1 - 2| = 1, |6 - 7| = 1 \implies\) 1 diagonal conflict \((Q_6, Q_7)\).
  • \(Q_5(5)\) at col 5 and \(Q_8(4)\) at col 8: \(|5 - 4| = 1, |5 - 8| = 3 \implies\) no.
  • \(Q_7(2)\) at col 7 and \(Q_8(4)\) at col 8: \(|2 - 4| = 2, |7 - 8| = 1 \implies\) no.
  • \(Q_3(4)\) at col 3 and \(Q_5(5)\) at col 5: \(|4 - 5| = 1, |3 - 5| = 2 \implies\) no.
  • \(Q_2(4)\) at col 2 and \(Q_5(5)\) at col 5: \(|4 - 5| = 1, |2 - 5| = 3 \implies\) no.
• Total attacking pairs in \(X_3 = 5 \text{ (row)} + 1 \text{ (diag)} = 6\).
• Fitness of \(X_3\) = \(28 - 6 = \mathbf{22}\).

For \(X_4 = [3, 2, 5, 4, 3, 2, 1, 3]\):

• Row conflicts:
  • Digit 3 appears in col 1, col 5, col 8 → \(\binom{3}{2} = 3\) pairs.
  • Digit 2 appears in col 2, col 6 → 1 pair.
  • Total Row Conflicts: \(3 + 1 = 4\).
• Diagonal conflicts:
  • \(Q_1(3)\) at col 1 and \(Q_2(2)\) at col 2: \(|3 - 2| = 1, |1 - 2| = 1 \implies\) 1 conflict.
  • \(Q_3(5)\) at col 3 and \(Q_4(4)\) at col 4: \(|5 - 4| = 1, |3 - 4| = 1 \implies\) 1 conflict.
  • \(Q_4(4)\) at col 4 and \(Q_5(3)\) at col 5: \(|4 - 3| = 1, |4 - 5| = 1 \implies\) 1 conflict.
  • \(Q_5(3)\) at col 5 and \(Q_6(2)\) at col 6: \(|3 - 2| = 1, |5 - 6| = 1 \implies\) 1 conflict.
  • \(Q_6(2)\) at col 6 and \(Q_7(1)\) at col 7: \(|2 - 1| = 1, |6 - 7| = 1 \implies\) 1 conflict.
  • \(Q_7(1)\) at col 7 and \(Q_8(3)\) at col 8: \(|1 - 3| = 2, |7 - 8| = 1 \implies\) no.
  • \(Q_3(5)\) at col 3 and \(Q_7(1)\) at col 7: \(|5 - 1| = 4, |3 - 7| = 4 \implies\) 1 conflict.
• Total attacking pairs in \(X_4 = 4 \text{ (row)} + 6 \text{ (diag)} = 10\).
• Fitness of \(X_4\) = \(28 - 10 = \mathbf{18}\).

ii) Perform Crossover on the Fittest Two Individuals at the Fourth Point:

The fitness values are: \(f(X_1) = 24, f(X_2) = 23, f(X_3) = 22, f(X_4) = 18\).

The fittest two individuals are \(X_1 = 24748552\) and \(X_2 = 32752411\).

Performing 1-point crossover at the 4th point (after the 4th digit):

Parent 1 (X1): [ 2  4  7  4 | 8  5  5  2 ]
Parent 2 (X2): [ 3  2  7  5 | 2  4  1  1 ]
------------------------------------------
Offspring Child 1: [ 2  4  7  4 | 2  4  1  1 ] = 24742411
Offspring Child 2: [ 3  2  7  5 | 8  5  5  2 ] = 32758552
            

1. Genetic Algorithms in Contrast to Biological Concepts:

Genetic Algorithms (GA) are stochastic search and optimization heuristics inspired by Charles Darwin's theory of natural evolution.

2. Why the Mutation Step Increases Diversification (Spring 2024 Q3.a):

Over successive generations, crossover solely recombines existing alleles present in the initial population. Without mutation, if an essential bit value is missing from the entire population, crossover can never generate it, leading to premature convergence and entrapment in sub-optimal local peaks. Mutation introduces brand new, random genetic variations, effectively exploring uncharted regions of the search space and preventing genetic stagnation.