A dense, scannable revision card for Artificial & Computational Intelligence (AIMLCZG557) — contact sessions CS1 through CS8, the mid-semester syllabus. Definitions, formulas and decision tables only; for the full plain-language explanation behind each line, open the slides explained.
CS1 — AI & intelligent agents
- AI = building rational agents. Four views (think/act × human/rational); this course = act rationally.
- Agent perceives via sensors, acts via actuators. Agent = architecture + program. Agent function maps percept history to action: \(f : P^* \to A\)
- Rational = maximise expected performance measure given the percept sequence + built-in knowledge. ≠ omniscient, ≠ perfect; bounded by available compute.
- PEAS specifies any task: Performance measure, Environment, Actuators, Sensors.
CS2 — Environments, agent types & problem solving
Environment axes (6)
| Axis | Easy ↔ Hard |
|---|---|
| Observability | Fully observable ↔ Partially observable |
| Agents | Single ↔ Multi-agent |
| Determinism | Deterministic ↔ Stochastic |
| Episodic? | Episodic ↔ Sequential |
| Dynamics | Static ↔ Dynamic |
| Values | Discrete ↔ Continuous |
Real world = hardest on every axis (partially observable, multi-agent, stochastic, sequential, dynamic, continuous).
Five agent types (increasing power)
Simple reflex → Model-based reflex (remembers state) → Goal-based (aims at a goal) → Utility-based (optimises a utility) → Learning (improves; has performance element + learning element + critic + problem generator).
Problem-solving agent & problem definition
Loop: formulate → search → execute. A problem = 5 parts: initial state, actions, transition model RESULT(s,a), goal test, path cost. Solution = a path; optimal = least-cost path. Search = order of node expansion over a frontier; judged on completeness / time / space / optimality.
CS3 — Uninformed & informed search
| Algorithm | Frontier | Complete? | Optimal? | Time | Space |
|---|---|---|---|---|---|
| BFS | FIFO queue | Yes | Only if equal step costs | \(O(b^d)\) | \(O(b^d)\) |
| UCS | Priority queue on g | Yes | Yes | \(O(b^{1+\lfloor C^*/\varepsilon\rfloor})\) | large |
| DFS | LIFO stack | No (infinite) | No | \(O(b^m)\) | \(O(bm)\) |
| DLS | DFS + limit ℓ | If ℓ ≥ d | No | \(O(b^\ell)\) | \(O(b\ell)\) |
| IDS | repeated DLS | Yes | Like BFS | \(O(b^d)\) | \(O(bd)\) |
UCS notes: goal-test at expansion (not generation); replace a frontier node if a cheaper path is found. IDS = best of BFS (optimal, low space) + DFS (low space), small repeat cost.
Informed (heuristic) search
- Greedy: fast, but not complete or optimal.
- A*: optimal when h is admissible and (for graph search) consistent.
- Admissible: \(h(n) \leq h^*(n)\) — never overestimates.
- Consistent (monotonic): \(h(n) \leq c(n,n') + h(n')\) for every successor \(n'\).
- Consistent ⇒ admissible (not the reverse). \(h = 0\) ⇒ A* becomes UCS. A larger admissible \(h\) dominates (expands fewer nodes).
CS4 — Heuristic design & local search
Where good heuristics come from
- Relaxed problems — drop constraints ⇒ exact cost of the relaxed problem is an admissible h. 8-puzzle: \(h_1\) = misplaced tiles, \(h_2\) = Manhattan distance; \(h_2\) dominates \(h_1\).
- Pattern databases — precompute exact sub-problem costs.
- Landmarks — precomputed distances to anchor states.
- Learning — fit a heuristic h(s, θ) (e.g. neural net).
Quality measured by effective branching factor b* (→ 1 is best).
Local search
Keep one current state, move to a better neighbour, ignore the path. Tiny memory; great for optimization (8-queens, scheduling, VLSI). Every state has an objective / fitness value.
- Hill climbing — greedy "move to best neighbour". Stuck at local maxima, plateaus, ridges.
- Fixes: random-restart, stochastic hill climbing, simulated annealing.
- Simulated annealing: accept a worse move with probability \(P = e^{-\Delta E / T}\) with temperature \(T\) cooling over time (high \(T\) = explore, low \(T\) = exploit).
CS5 — Beam, genetic algorithms, online search & ACO
- Local beam search: keep k states, pool all successors, keep best k. Stochastic variant picks k probabilistically to preserve diversity.
- Genetic algorithm: population + fitness + selection (roulette wheel) + crossover (single/multi/uniform-point) + mutation, over generations. Crossover exploits, mutation explores; no convergence guarantee.
- Offline vs online: offline has a full model up front (BFS/UCS/A*/HC/beam); online agents act–observe–update because the world is unknown/dynamic.
Ant Colony Optimization (ACO)
\(\alpha\) = pheromone weight, \(\beta\) = visibility weight, \(\rho\) = evaporation, \(Q\) = deposit constant. Evaporation = exploration; reinforcement (shorter tour ⇒ bigger deposit) = exploitation.
CS6 — ACO worked example + Neural Architecture Search
- ACO on TSP: 5 cities, start node 4, α=0.5, β=0.75, ρ=0.1, Q=100 → tour 4→2→3→5→1→4; evaporate 10%, deposit 100/cost.
- NAS = bilevel optimization: evolve the architecture ("DNA") via GA; learn the weights via gradient descent.
- Neuroevolution = GA loop on networks (create → train → fitness → select → breed → repeat).
- NEAT: grow graphs from minimal; innovation numbers align genes in crossover; speciation protects diversity. Only tiny networks.
- DeepNEAT: each node = a whole layer (Conv/Dense/LSTM + hyperparams). Produces messy, non-reusable structures.
- CoDeepNEAT: co-evolve two populations — blueprints (skeleton; nodes = module placeholders) + modules (reusable sub-networks). Phenotype = drop a chosen module into each blueprint node.
CS7 — Adversarial search & minimax
- Adversarial search: ≥ 2 agents, conflicting goals, zero-sum (your gain = opponent's loss). Plan around the opponent's best reply.
- Game = 6 parts: S0, PLAYER(s), ACTIONS(s), RESULT(s,a), TERMINAL-TEST(s), UTILITY(s,p). Players = MAX (maximise) and MIN (minimise). Win/Draw/Loss = +1/0/−1.
- Game tree: levels alternate MAX/MIN. Back up values — max at MAX nodes, min at MIN nodes.
- Minimax = "maximise the minimum": MAX picks the branch whose worst case is best (not the branch with the biggest leaf — MIN moves in between).
- Depth limit + static evaluation: real trees are too big to reach leaves. Cut off at depth d, estimate non-terminal states with a fast eval function.
CS8 — Alpha-beta pruning & MCTS
Alpha-beta pruning
- Same result as minimax, fewer nodes. α = best (highest) for MAX so far (init −∞); β = best (lowest) for MIN so far (init +∞).
- Prune when β ≤ α — remaining siblings can't change the decision.
- At MAX node: if value > α, α = value. At MIN node: if value < β, β = value. Then test β ≤ α.
- Move ordering matters: best-first ordering ⇒ \(\sim O(b^{d/2})\) nodes (roughly doubles reachable depth); worst ordering ⇒ no pruning.
Monte Carlo Tree Search (MCTS)
Replaces a hand-written eval with random rollouts. Four phases per iteration:
| Phase | What it does |
|---|---|
| Selection | Descend from root by UCB (balance win-rate vs visits) to a node with unexplored moves |
| Expansion | Add one child for an unexplored legal move |
| Simulation | Random / light-heuristic playout to a terminal result (rollout) |
| Backpropagation | Update visit count + win score along the path |
UCB \(= \dfrac{w_i}{n_i} + c\sqrt{\dfrac{\ln N}{n_i}}\) — exploitation (high win rate) + exploration (few visits); every option tried once. Suits two-player, sequential, perfect-information, finite games (Go, chess, tic-tac-toe). Basis of AlphaGo.
References
- T1 — Russell & Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2022 (course textbook).
- R3 — Rich, Knight & Nair, Artificial Intelligence, 3rd ed., Tata McGraw Hill.
- Course: BITS Pilani WILP — Artificial & Computational Intelligence (AIMLCZG557).