Artificial Intelligence

Artificial Intelligence & Strong vs. Weak AI:

1. Definition of AI: The subfield of computer science dedicated to engineering computational systems and software agents capable of performing tasks that typically require human cognitive intelligence—such as perception, heuristic reasoning, problem-solving, learning, and contextual decision-making.
2. Strong AI (General AI / AGI): Theoretical systems possessing generalized human-level or superhuman cognitive capabilities across any intellectual domain, with genuine self-awareness, abstraction, and intentionality.
3. Weak AI (Narrow AI): Practical systems engineered and optimized to execute specific, bounded tasks (e.g. AlphaGo, facial recognition, Siri, spam filtering) without autonomous consciousness or cross-domain cognitive transfer.

Intelligent Agent & PEAS Framework:

An Intelligent Agent is an autonomous entity that perceives its environment through sensors, processes information through internal reasoning logic, and directs its activity through actuators to maximize its expected performance measure.

PEAS Description for an Automated Taxi Driver:

• P (Performance Measure): Passenger safety, speed/arrival time, legal compliance (traffic laws), passenger comfort, and fuel efficiency/profit maximization.
• E (Environment): Urban and highway roadways, pedestrian footpaths, vehicular traffic, weather conditions (rain, fog), road construction, and diverse passengers.
• A (Actuators): Steering wheel, accelerator, brake pedal, horn, turn signals, and digital passenger interface/display.
• S (Sensors): Video cameras, LiDAR, radar, ultrasonic sonar sensors, GPS receiver, speedometer, accelerometer, and engine diagnostic telemetry.

Informed vs. Uninformed Search:

Admissibility Condition in $A^*$ Search:

A heuristic function $h(n)$ is admissible if it never overestimates the actual cost to reach the nearest goal state from node $n$.

Mathematically:

where:

• $h(n)$ is the estimated cost from node $n$ to the goal.
• $h^*(n)$ is the true optimal cost from node $n$ to the goal.

Significance: Admissibility is the necessary and sufficient condition for tree-search $A^*$ to guarantee optimality (discovering the absolute least-cost solution path).

The Horizon Effect:

The Horizon Effect occurs in depth-limited heuristic game playing (e.g. chess, checkers) when an inevitable, catastrophic adverse event (such as the loss of a Queen) is pushed beyond the maximum search horizon by executing delaying, sub-optimal intermediate moves (such as spite checks).

• Because the search engine cannot see beyond its fixed depth limit (the horizon), it erroneously believes it has avoided the catastrophe, while in reality it merely delayed it at the cost of worsening its positional advantage.
• Mitigation: Quiescence search, which dynamically extends search depth in unstable (non-quiescent) tactical capture positions until tactical calm is restored.

Four Fundamental Intelligent Agent Architectures:

1. Simple Reflex:  [Sensors] -> [Condition-Action Rules] -> [Actuators]
2. Model-Based:    [Sensors] -> [State + How World Evolves] -> [Condition-Action Rules] -> [Actuators]
3. Goal-Based:     [Sensors] -> [State] + [Goals / Future Planning] -> [Actuators]
4. Utility-Based:  [Sensors] -> [State] + [Utility Function / Trade-offs] -> [Actuators]

---

1. Simple Reflex Agent:

• Operates strictly on condition-action rules: $\text{IF } condition \text{ THEN } action$.
• Ignores percept history; only reacts to current percept.
• Effective only in fully observable environments; suffers infinite loops in partially observable states.

2. Model-Based Reflex Agent:

• Maintains internal state tracking unobserved aspects of the current environment.
• Encapsulates two types of world knowledge:
  1. How the world evolves independently of the agent.
  2. How the agent’s own actions affect the environment.
• Can operate successfully in partially observable environments.

3. Goal-Based Agent:

• Combines state knowledge with explicit goals describing desirable terminal situations.
• Incorporates search and planning algorithms to determine multi-step sequences of actions to reach goals.
• Highly flexible: easily reconfigured by changing target goals without reprogramming behavioral rules.

4. Utility-Based Agent:

• Maps states onto real numbers via a Utility Function representing the degree of desirability/happiness.
• Resolves conflicting goals by evaluating trade-offs (e.g. speed vs. safety vs. fuel economy).
• Enables rational decision-making under uncertainty where goals can only be achieved probabilistically.

Comprehensive Comparison of Uninformed Search Strategies:

Let:

• $b$ = branching factor
• $d$ = depth of the shallowest goal node
• $m$ = maximum depth of the state space
• $l$ = depth cutoff limit for DLS

---

Key Architectural Insights:

1. BFS Memory Bottleneck: BFS is strictly memory-bound in real-world AI applications because it retains $O(b^d)$ nodes in RAM, causing out-of-memory crashes before CPU exhaustion.
2. IDDFS Superiority: IDDFS combines the modest linear memory footprint of DFS ($O(bd)$) with the completeness and optimality guarantees of BFS. Although top levels are regenerated, the computational overhead is negligible (typically less than 11% overhead for $b=10$) because the overwhelming majority of nodes reside at the lowest search depth.

Greedy Best-First Search vs. A* Search:

1. Greedy Best-First Search:

• Evaluates nodes using solely the heuristic estimation: $f(n) = h(n)$.
• Minimizes estimated distance to goal, ignoring accumulated past path cost $g(n)$.
• Prone to dead ends, cycles, and finding sub-optimal paths.

2. A* Search:

• Evaluates nodes using combined evaluation function:

  Swipe to see the full formula↔

  $$f(n) = g(n) + h(n)$$
  where $g(n)$ is actual cost incurred from root to $n$, and $h(n)$ is estimated cost from $n$ to goal.

---

Proof of A* Optimality (Admissible Heuristic):

Let $C^*$ be the optimal goal cost. Suppose for contradiction that $A^*$ terminates by selecting a sub-optimal goal $G_2$ with cost $g(G_2) > C^*$.

1. Since $G_2$ is a goal, $h(G_2) = 0$, so $f(G_2) = g(G_2) + 0 = g(G_2) > C^*$.
2. Prior to choosing $G_2$, there must exist at least one unexpanded node $n$ on the open frontier that lies on the true optimal path to the optimal goal $G$.
3. By admissibility, $h(n) \le h^*(n)$, meaning:

   Swipe to see the full formula↔

   $$f(n) = g(n) + h(n) \le g(n) + h^*(n) = C^*$$
4. Since $f(n) \le C^* < f(G_2)$, we have:

   Swipe to see the full formula↔

   $$f(n) < f(G_2)$$
5. A priority queue ordered by minimum $f$ will always expand $n$ before $G_2$.
6. This holds for all nodes on the optimal trajectory until $G$ itself is expanded with $f(G) = C^*$.
7. Thus, $G_2$ can never be selected ahead of the optimal goal. $\blacksquare$

Constraint Satisfaction Problem (CSP) & AC-3:

A CSP is formalized by a triplet $(X, D, C)$:

• $X = \{X_1, X_2, \dots, X_n\}$: A set of variables.
• $D = \{D_1, D_2, \dots, D_n\}$: A set of domains containing allowable values for each variable.
• $C = \{C_1, C_2, \dots, C_m\}$: A set of constraints restricting allowable combinations of assignments.

---

Arc Consistency Algorithm (AC-3):

A directed arc $(X_i, X_j)$ is arc consistent if for every value $x \in D_i$, there exists at least one value $y \in D_j$ that satisfies the constraint between $X_i$ and $X_j$.

AC-3 Algorithm Steps:

1. Initialize queue $Q$ with all directed binary arcs in the CSP: $\{(X_i, X_j), (X_j, X_i), \dots\}$.
2. While $Q$ is not empty:
   • Pop arc $(X_i, X_j)$.
   • If $\text{Revise}(CSP, X_i, X_j)$ deletes any value from $D_i$:
     • If $D_i = \emptyset$, return Failure (no consistent solution possible).
     • For each neighbor $X_k \in \text{Neighbors}(X_i) \setminus \{X_j\}$, insert arc $(X_k, X_i)$ into $Q$.
3. Return Success (domain reduced to arc-consistent values).

Example (Map Coloring):

• Let Variables $X_1, X_2$ share constraint $X_1 \ne X_2$.
• If $D_1 = \{\text{Red}\}$ and $D_2 = \{\text{Red}, \text{Green}\}$.
• Arc $(X_2, X_1)$ is revised: $y = \text{Red}$ in $D_2$ conflicts with $X_1 = \text{Red}$.
• Value $\text{Red}$ is pruned from $D_2$, reducing $D_2 = \{\text{Green}\}$. Arc consistency is achieved.

Minimax Algorithm & Alpha-Beta Pruning:

1. Minimax Algorithm:

Used in deterministic, perfect-information two-player zero-sum games (MAX vs. MIN):

• Complexity: Time $O(b^m)$, Space $O(bm)$. Exhaustive evaluation is computationally intractable for deep games (e.g. Chess $b \approx 35, m \approx 80$).

---

2. Alpha-Beta Pruning Optimization:

Prunes branches that cannot influence the final minimax decision at the root:

• $\alpha$ = Highest value found so far by MAX along the search path (lower bound on MAX’s payoff). Initialized to $-\infty$.
• $\beta$ = Lowest value found so far by MIN along the search path (upper bound on MIN’s payoff). Initialized to $+\infty$.

Pruning Conditions:

1. At MIN node: If $\beta \le \alpha$, prune remaining children ($alpha$-cutoff). MAX already has a better move elsewhere.
2. At MAX node: If $\alpha \ge \beta$, prune remaining children ($\beta$-cutoff). MIN already has a better defensive move elsewhere.

Efficiency Gain:

With perfect move ordering, alpha-beta reduces time complexity from $O(b^m)$ to $O(b^{m/2}) = O((\sqrt{b})^m)$. This effectively doubles the search depth reachable within the same CPU time limit.

Hill Climbing Search & Simulated Annealing:

Hill Climbing is an iterative local search algorithm that continually moves in the direction of increasing elevation (value) to find the peak of a state-space surface.

---

Three Primary Failure Modes:

1. Local Maximum: 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.
2. Ridge: A sequence of local maxima joined by steep slopes where standard orthogonal coordinate moves step down on either side, halting progress.
3. Plateau (Shoulder / Flat Maximum): A flat area of the state-space landscape where all neighboring states possess identical heuristic values, leaving the search with no directional gradient.

---

How Simulated Annealing Resolves These Limitations:

Inspired by metallurgy (gradual cooling of molten metal to form defect-free crystalline structures):

• Instead of purely greedy moves, it allows downhill (sub-optimal) moves with a probability governed by the Boltzmann distribution:

  Swipe to see the full formula↔

  $$P(\Delta E) = e^{\frac{\Delta E}{T}}$$
  where $\Delta E = E_{\text{next}} - E_{\text{current}} < 0$, and $T$ is temperature.
• When $T$ is high (early phase), the agent frequently accepts worse moves, escaping local maxima and exploring wide basins.
• As temperature $T$ gradually cools according to an annealing schedule ($T \to 0$), the probability of accepting downhill moves drops to zero, smoothly transitioning into standard greedy local optimization.

Step-by-Step A* Search Graph Traversal:

Evaluation function: $f(n) = g(n) + h(n)$

---

Iteration Trace:

Step 1: Initialize

• Open List: $\{[S: g=0, h=7, f=7]\}$
• Closed List: $\{\}$

Step 2: Expand $S$ ($f=7$)

• Successors of $S$:
  • $A: g = 0 + 3 = 3,\quad h = 6 \implies f(A) = 3 + 6 = 9$, Path: $S \to A$
  • $B: g = 0 + 2 = 2,\quad h = 5 \implies f(B) = 2 + 5 = 7$, Path: $S \to B$
  • $C: g = 0 + 4 = 4,\quad h = 6 \implies f(C) = 4 + 6 = 10$, Path: $S \to C$
• Open List: $\{[B: f=7], [A: f=9], [C: f=10]\}$
• Closed List: $\{S\}$

Step 3: Expand $B$ (Minimum $f=7$)

• Successors of $B$:
  • $E: g = 2 + 3 = 5,\quad h = 2 \implies f(E) = 5 + 2 = 7$, Path: $S \to B \to E$
  • $F: g = 2 + 6 = 8,\quad h = 4 \implies f(F) = 8 + 4 = 12$, Path: $S \to B \to F$
• Open List: $\{[E: f=7], [A: f=9], [C: f=10], [F: f=12]\}$
• Closed List: $\{S, B\}$

Step 4: Expand $E$ (Minimum $f=7$)

• Successors of $E$:
  • $G: g = 5 + 3 = 8,\quad h = 0 \implies f(G) = 8 + 0 = 8$, Path: $S \to B \to E \to G$
• Open List: $\{[G: f=8], [A: f=9], [C: f=10], [F: f=12]\}$
• Closed List: $\{S, B, E\}$

Step 5: Expand $G$ (Minimum $f=8$)

• $G$ is the goal state! When a goal node is removed from Open list for expansion, $A^*$ terminates with guaranteed optimality.

---

Summary Table:

---

Final Solution:

• Optimal Path: $S \to B \to E \to G$
• Total Path Cost: $g(G) = 8$

Minimax with Alpha-Beta Pruning Complete Trace:

                     A (MAX)  [alpha=-inf, beta=+inf]
                    /       \
                   /         \
            B (MIN)           C (MIN)
           /   |   \         /   |   \
          D    E    F       G    H    I
         [4]  [6]  [2]     [8]  [1]  [9]

---

Step-by-Step Traversal Trace:

1. At Root Node A (MAX):

   • Initialize $\alpha = -\infty, \beta = +\infty$.
   • Visit first child B (MIN) passing $\alpha = -\infty, \beta = +\infty$.

2. At Node B (MIN):

   • Initialize for B: $\alpha = -\infty, \beta = +\infty$.
   • Evaluate child D: Value = $4$.
     • $\beta = \min(+\infty, 4) = 4$.
     • Check: $\alpha (- \infty) < \beta (4) \implies$ No cutoff.
   • Evaluate child E: Value = $6$.
     • $\beta = \min(4, 6) = 4$.
     • Check: $\alpha (- \infty) < \beta (4) \implies$ No cutoff.
   • Evaluate child F: Value = $2$.
     • $\beta = \min(4, 2) = 2$.
     • Check: $\alpha (- \infty) < \beta (2) \implies$ No cutoff.
   • All children of B evaluated.
   • Return minimax value of $B = 2$.

3. Back at Root Node A (MAX):

   • Updates from left child B:
     • $\alpha = \max(-\infty, 2) = 2$.
     • $\beta$ remains $+\infty$.
   • Visit second child C (MIN) passing $\alpha = 2, \beta = +\infty$.

4. At Node C (MIN):

   • Inherits bounds: $\alpha = 2, \beta = +\infty$.
   • Evaluate child G: Value = $8$.
     • $\beta = \min(+\infty, 8) = 8$.
     • Check: $\alpha (2) < \beta (8) \implies$ No cutoff.
   • Evaluate child H: Value = $1$.
     • $\beta = \min(8, 1) = 1$.
     • Check Cutoff Condition:

       Swipe to see the full formula↔

       $$\beta (1) \le \alpha (2) \implies \text{\textbf{ALPHA CUTOFF OCCURS!}}$$
     • Since $\beta \le \alpha$, MIN at node C can already guarantee a score of at most $1$. MAX at root A already has guaranteed score of $2$ from branch B. Therefore, MAX will never choose branch C regardless of what follows.
   • Pruning: Child I (value 9) is PRUNED and never evaluated!
   • Node C terminates with value $\le 1$ (effective value $1$).

5. Back at Root Node A (MAX):

   • $\alpha = \max(2, 1) = 2$.
   • Final minimax value at root $A = 2$.

---

Final Evaluation Summary:

• Minimax Value of Node B: $2$
• Minimax Value of Node C: $1$ (with pruning)
• Minimax Value of Node A (Root): $2$
• Pruned Branch: Node I is pruned under node C ($\alpha$-cutoff).
• Optimal Move for MAX: Move to Node B.