Skip to content
CampusPrep
AL-304 · Artificial Intelligence/Quick Revision Short Notes

Artificial Intelligence (AL-304) - Unit 1 Short Notes

How unit 1 is examined

What AI is, its goals and need, production systems and search; most marks come from A*/AO*, heuristic search, hill climbing and AI goals.

Fundamental of Artificial Intelligence

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Artificial Intelligence is the branch of computer science that builds machines and programs able to perform tasks that normally need human intelligence, such as reasoning, learning, perceiving and decision making.</mark>

Key points.

  1. Intelligence is the ability to acquire, understand and apply knowledge.
  2. Acting humanly means passing the Turing test (an interrogator cannot tell machine from person); today LLM chatbots pass short chats, but the total test also needs vision and robotics.
  3. Thinking humanly is cognitive modelling; it is feasible mainly in research cognitive architectures (SOAR, ACT-R), as the brain is poorly understood.
  4. Thinking rationally uses logic (laws of thought); it works in well-defined domains such as theorem provers, but logic struggles with uncertainty.
  5. Acting rationally means a rational agent doing the action with the best expected outcome; it is the most feasible today, e.g. autonomous agents, self-driving cars, recommenders and AlphaGo.
  6. Acting rationally suits a rational agent best: it is general and mathematically well defined, works when perfect logic is impossible, and the humanly approaches copy human irrationality and errors.
  7. AI is interdisciplinary: computer science gives algorithms, hardware (GPUs) and programming languages; mathematics logic and probability; statistics learning and Bayes nets; economics decision theory and MDPs; linguistics grammars for NLP; psychology and cognitive science models of thought; neuroscience neural networks; control theory feedback; philosophy ethics.
  8. Each field fills another's gap, e.g. control theory plus vision gave self-driving cars.
Approach Goal Method
Acting humanly Behave like a person Turing test
Thinking humanly Think like a person Cognitive modelling
Thinking rationally Think correctly Logic
Acting rationally Best outcome Rational agent

Answer frame. Definition; table; points 2-6; for interdisciplinary points 7-8; close: modern AI follows the rational-agent view.

Asked: [7 marks] (Dec 2023) Discuss the feasibility of the four approaches of AI (acting humanly, thinking humanly, thinking rationally, acting rationally) today. Which is best suited for a rational agent and why? Asked: [7 marks] (Dec 2024) Why is AI considered an interdisciplinary field, and how does it incorporate knowledge from multiple domains? Asked: [7 marks] (Dec 2025) Define Artificial Intelligence and explain its motivation and need.

History

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. AI began as a field in 1956 at the Dartmouth workshop, where John McCarthy named it "artificial intelligence".

Key points.

  1. Alan Turing proposed the Turing test in 1950; expert systems led the 1970s-80s and deep learning the boom since 2010.

Motivation and need of AI

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>The motivation of AI is to mimic human cognition and automate intelligent work; the need is to solve complex, data-heavy problems faster and at larger scale than humans.</mark>

Key points.

  1. Automation: by mimicking human cognition, AI takes over repetitive mental tasks such as data entry and inspection.
  2. Big data and scale: AI finds patterns in data no human could read and serves millions of users 24x7.
  3. Complexity: route planning, protein folding and games have huge search spaces.
  4. Hazardous work: robots operate in mines, space and disaster zones.
  5. Accuracy and speed: AI gives consistent real-time decisions, e.g. fraud detection.
  6. Need by ability: reasoning (diagnosis), learning (recommendations), perception (self-driving cars decide in milliseconds), NLP (chatbots), decisions (logistics).

Answer frame. Definition; motivation (1, 4), need (2, 3, 5), mapping (6); close: AI is essential to modern technology.

Asked: [7 marks] (Jun 2025, Dec 2025) What is the motivation and need of AI in modern technology?

Production systems

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A production system has a global database (working memory), IF-THEN rules, and a control strategy that chooses the rule to fire.

Key points.

  1. Classes: monotonic (a rule never blocks an earlier-applicable rule, e.g. chemical synthesis); non-monotonic (it can, e.g. bridge); partially commutative (any allowable reordering of a rule sequence reaches the same state, e.g. robot navigation); commutative = monotonic and partially commutative (theorem proving).
  2. Unlike plain state-space search, where operators are fixed inside the program, knowledge sits in editable rules; unlike an algorithmic program with a fixed step sequence, control picks whichever rule matches.
  3. Advantages: rules are explainable, modular and easily updated, and suit expert systems, diagnosis and game agents.

Asked: [7 marks] (Dec 2025) Explain production systems and their characteristics.

Characteristics of production systems

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Production systems are modular, modifiable, uniform and natural, and separate knowledge from control.</mark>

Key points.

  1. Modularity: each rule is independent, so it is added or removed without touching others.
  2. Modifiability: rules or control change easily, with no tangled control flow.
  3. Uniformity: every rule has the same IF-THEN format.
  4. Naturalness: rules read like expert knowledge, so they are easy to explain.
  5. Separation of knowledge and control: rules say what to do while the interpreter decides when.
  6. Weaknesses: opacity and inefficiency, since every cycle matches all rules.

Example (water jug). Jugs of 4 L and 3 L, no marks; state $(x,y)$ litres; start $(0,0)$; goal $(2,y)$.

R1 fill 4:          x<4    -> (4,y)
R2 fill 3:          y<3    -> (x,3)
R3 empty 4:         x>0    -> (0,y)
R4 empty 3:         y>0    -> (x,0)
R5 pour 3->4 full:  x+y>=4 -> (4,y-(4-x))
R6 pour 4->3 full:  x+y>=3 -> (x-(3-y),3)
R7 pour all 3->4:   x+y<=4 -> (x+y,0)
R8 pour all 4->3:   x+y<=3 -> (0,x+y)

Solution: (0,0) R2 (0,3) R7 (3,0) R2 (3,3) R5 (4,2) R3 (0,2) R7 (2,0).

Feature Production system State-space search Logic-based Connectionist
Knowledge IF-THEN rules States and operators Facts and axioms Learned weights
Control Separate interpreter Fixed algorithm Inference and proof Parallel activation
Change Add a rule Redefine operators Add axioms Retrain
Explainable Yes Partly Yes No

Answer frame. Three components; water jug rules and path; points 1-6; comparison table; close with uses (MYCIN).

Asked: [7 marks] (Jun 2024, Dec 2025) What are the essential characteristics of production systems and how do they differ from other AI problem-solving approaches? Asked: [7 marks] (Jun 2025) What is production system? Explain it with an example. Discuss the characteristics of a production system.

Goals and contribution of AI to modern technology

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>The goals of AI are to build expert systems and to implement human intelligence in machines, so they can reason, learn, perceive, communicate and decide.</mark>

Key points.

  1. AI has a scientific objective, to understand intelligence, and an engineering objective, to build intelligent systems.
  2. Core goals are reasoning and problem solving, knowledge representation, learning from data, perception and NLP, robotics, automation of routine work, and decision making under uncertainty.
  3. Technology: machine learning powers recommendations and forecasting; expert systems capture specialist knowledge; computer vision powers face unlock and self-driving.
  4. Healthcare: AI reads medical images for early diagnosis, assists robotic surgery, speeds drug discovery and personalises medicine.
  5. Climate and cities: climate prediction models forecast disasters, AI optimises energy grids and traffic routing, and satellites track emissions.
  6. Education: intelligent tutoring systems, automated grading and personalised learning paths.
  7. Manufacturing and daily life: predictive maintenance, inspection robots, voice assistants and fraud detection.

Future impact. Autonomous transport and AI-assisted science will spread, with bias, privacy, jobs and safety as key challenges.

Answer frame. Define intelligence and AI; objectives (1), goals (2), contributions 3-7, future impact. For "human life" or "global challenges" stress 4-7.

Asked: [7 marks] (Nov 2022, Jun 2023) What is "Intelligence"? Explain the goals of AI in modern technology. / List and explain the goals of AI. Asked: [7 marks] (Nov 2022, Jun 2024, Dec 2025) Explain the contribution of AI in human life. / How can AI help solve global challenges such as climate change, healthcare or education? Give examples. Asked: [7 marks] (Nov 2022, Jun 2023, Dec 2025) Discuss goals of AI and its contribution to modern technology.

Search space

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. The search space (state space) is all states reachable from the initial state by legal actions, drawn as a graph or tree.

Key points.

  1. A problem is formally defined by initial state, actions, transition model RESULT(s,a) (the state after action a in s), goal test and path cost.
  2. 8-puzzle: initial state a tile layout; actions move the blank Up, Down, Left, Right; goal test the target layout; cost 1 per move.
  3. With branching factor $b$, shallowest goal depth $d$ and maximum depth $m$: BFS expands level by level and finds the shallowest goal; DFS goes deepest first and can loop forever on an infinite or cyclic space without a visited list.
  4. BFS suits a shallow goal, e.g. degrees of separation in a social network.
Point BFS DFS
Structure Queue (FIFO) Stack (LIFO)
Time $O(b^d)$ $O(b^m)$
Space $O(b^d)$ $O(bm)$
Complete, optimal Yes, yes (unit cost) No, no

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Social network; BFS finds A, B (1 hop), then C, D; DFS may go Me, A, C, D, B"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L153.2,50.5"/><path class="e" d="M55.8,136.5 L153.2,201.5"/><path class="e" d="M188,40 L279,40"/><path class="e" d="M188,212 L279,212"/><path class="e" d="M298,59 L298,193"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Me</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Social network; BFS finds A, B (1 hop), then C, D; DFS may go Me, A, C, D, B</figcaption></figure>

Example. Successors of $n$ are $2n$ and $2n+1$, goal 11.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 712 262" width="712" height="262" role="img" aria-label="State space for states 1 to 15"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="520" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="520" y1="103" x2="432" y2="167"/><line class="e" x1="520" y1="103" x2="608" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><line class="e" x1="608" y1="167" x2="564" y2="231"/><line class="e" x1="608" y1="167" x2="652" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">5</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="520" cy="103" r="17"/><text class="t" x="520" y="103" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">13</text><circle class="n" cx="608" cy="167" r="17"/><text class="t" x="608" y="167" dy=".35em" text-anchor="middle">7</text><circle class="n" cx="564" cy="231" r="17"/><text class="t" x="564" y="231" dy=".35em" text-anchor="middle">14</text><circle class="n" cx="652" cy="231" r="17"/><text class="t" x="652" y="231" dy=".35em" text-anchor="middle">15</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">State space for states 1 to 15</figcaption></figure>

BFS order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. DFS with limit 3: 1, 2, 4, 8, 9, 5, 10, 11.

Asked: [7 marks] (Dec 2023) Start state 1, successors of n are 2n and 2n + 1: draw the state space for states 1 to 15; with goal 11 list the visiting order for BFS and for DFS with limit 3. Asked: [7 marks] (Dec 2023) Describe the difference between Depth First Search (DFS) and Breadth First Search (BFS) with suitable example. Asked: [7 marks] (Jun 2025) Give an example of a problem for which breadth first search would work better than depth first search. Asked: [7 marks] (Jun 2025) How a problem is formally defined? List down the components of it?

Different search techniques: hill climbing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Hill climbing is a greedy local search that repeatedly moves to the best neighbouring state, stopping when no neighbour is better than the current state.</mark>

Key points.

  1. It keeps only the current state, no OPEN list, so memory is $O(1)$, and never backtracks.
  2. Types: simple takes the first better neighbour; steepest-ascent the best of all; stochastic a random uphill neighbour (escapes some traps, converges slower).
  3. Local maximum: a peak better than its neighbours but not the best, where search stops.
  4. Plateau: all neighbours score equal, so there is no direction; ridge: a narrow slope that single moves cannot climb.
  5. Remedies: random restarts, simulated annealing, sideways moves.
  6. Advantages: little memory, fast, and it works in large or continuous spaces where full search is impossible.
Step 1: Evaluate the initial state; if goal, stop.
Step 2: Evaluate the neighbours; if no neighbour is better than the current state, stop and return it.
Step 3: Else move to the better (best) neighbour and repeat Step 2.

h |     /\   global max
  |  /\/  \____ plateau
  | /  local max
  +------------- states

Example (Dec 2023 blocks world). Stacks bottom to top. Initial: A; C-E; D-B. Goal: E; B-D; C-A.

  • Global h: +1 for a block whose whole support stack matches the goal, else -1. Initial: only C is correct, $h=-3$; goal $+5$.
  • Tie-break: scan stacks left to right; the first-generated best move wins.
Move Every successor, global h (X-T = X to table) Chosen
1 (from -3) E-T -1, B-T -1; six others -3 E-T, -1
2 (from -1) A-C +1, B-T +1; A-B, A-E, B-A, B-C, B-E -1; C-A, C-B, C-E, E-A, E-C, E-B -3 A-C, +1
3 (from +1) B-T +3; B-A, B-E +1; A-T, A-B, A-E, E-A, E-B -1 B-T, +3 
   E  B           B      A  B        A
A  C  D     A  C  D  E   C  D  E     C  D  E  B
 h = -3       h = -1       h = +1       h = +3
 Start        Move 1       Move 2       Move 3

Next D onto B gives +5, the goal.

Feature Hill climbing Best-first
Memory Current state OPEN and CLOSED
Local maxima Gets stuck Escapes
Complete No Yes, finite graphs
Strength Fast, little memory Reliable
Weakness Local optima, ridges High memory

Answer frame. Definition, steps, types; for the numerical state h, tie-break, scores per move, stacks with h; comparison table; limitations.

Asked: [7 marks] (Dec 2023) For the given Blocks World problem, use hill climbing to show the next 3 best moves; state and use a suitable global heuristic. Asked: [7 marks] (Dec 2024, Dec 2025) Compare and contrast hill climbing and best-first search algorithms. What are their strengths and weaknesses? Asked: [7 marks] (Dec 2025) Describe search space and hill climbing search technique. Pitfall: Do not say hill climbing is complete or optimal; it can stop at a local maximum.

Best-first search

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. ==Best-first search always expands the OPEN node with the lowest $f(n)=h(n)$, combining depth-first and breadth-first ideas.==

Key points.

  1. OPEN is a priority queue ordered by $h(n)$ and CLOSED stores expanded nodes.
  2. A child already on OPEN is not added again; if the new path is better, its value and parent are updated.
  3. Time and space are $O(b^m)$ worst case, as OPEN can hold every node.
  4. The tree version (no CLOSED) is incomplete, as it can loop; the graph version with CLOSED is complete on finite graphs. It is never optimal, as it ignores $g$.
  5. Advantages: fast with a good $h$ and simple; disadvantages: not optimal, misled by a poor $h$, high memory.
  6. Ties go to the first-generated node; uses: route finding, 8-puzzle.
Step 1: Put start on OPEN; if OPEN is empty, fail.
Step 2: Remove the lowest-h node n to CLOSED; if n is the goal, stop.
Step 3: Add new children of n to OPEN (update those already there); go to Step 1.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-03" viewBox="0 0 467 424" width="467" height="424" role="img" aria-label="h values S 10, A 3, B 5, C 6, D 7, E 2, F 4, G 0 (goal)"><style>#dsfig-u1-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-03 .t{fill:#16181D;font-weight:500}#dsfig-u1-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-03 .dot{fill:#16181D}#dsfig-u1-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-03 .ah{fill:#454C5A}#dsfig-u1-03 .ah.hi{fill:#2340B8}#dsfig-u1-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-03 .e{stroke:#B1B7C3}html.dark #dsfig-u1-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-03 .t{fill:#E6E8ED}html.dark #dsfig-u1-03 .t.inv{fill:#0F1115}html.dark #dsfig-u1-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-03 .dot{fill:#E6E8ED}html.dark #dsfig-u1-03 .ann{fill:#8FA3FF}html.dark #dsfig-u1-03 .lbl{fill:#858D9C}html.dark #dsfig-u1-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-03 .ah{fill:#B1B7C3}html.dark #dsfig-u1-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,201.5 L151.5,137.6" marker-end="url(#ah3)"/><path class="e" d="M55.8,222.5 L151.5,286.4" marker-end="url(#ah3)"/><path class="e" d="M184.8,115.5 L280.5,51.6" marker-end="url(#ah3)"/><path class="e" d="M187.6,129.7 L277.4,147.7" marker-end="url(#ah3)"/><path class="e" d="M187.6,294.3 L277.4,276.3" marker-end="url(#ah3)"/><path class="e" d="M184.8,308.5 L280.5,372.4" marker-end="url(#ah3)"/><path class="e" d="M317,272.2 L406,272.2" marker-end="url(#ah3)"/><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="298" r="18"/><text class="t" x="169" y="298" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="151.8" r="18"/><text class="t" x="298" y="151.8" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="298" cy="272.2" r="18"/><text class="t" x="298" y="272.2" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="298" cy="384" r="18"/><text class="t" x="298" y="384" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="427" cy="272.2" r="18"/><text class="t" x="427" y="272.2" dy=".35em" text-anchor="middle">G</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">h values S 10, A 3, B 5, C 6, D 7, E 2, F 4, G 0 (goal)</figcaption></figure>

Step Expand OPEN after (sorted by h)
1 S A3, B5
2 A B5, C6, D7 (A's children are worse, so switch back to B)
3 B E2, F4, C6, D7
4 E G0, F4, C6, D7
5 G goal; path S-B-E-G
Point Informed Uninformed
--- --- ---
Knowledge Uses $h(n)$ Problem only
Examples Greedy best-first, A* BFS, DFS, UCS
Time, memory Exponential worst, less with good $h$ BFS $O(b^d)$; DFS $O(b^m)$, $O(bm)$
Complete A* yes; greedy tree search no BFS, UCS yes; DFS no
Optimality A* (admissible $h$) BFS (unit cost), UCS

Uniform-cost search (UCS) always expands the node with the lowest path cost $g(n)$.

Map example (Romania). With straight-line $h$ (Sibiu 253, Fagaras 176, Rimnicu Vilcea 193), greedy goes Arad, Sibiu, Fagaras, Bucharest (cost 450) and misses the 418 route via Rimnicu Vilcea and Pitesti; BFS ignores distances.

Answer frame. $f(n)=h(n)$; graph with the OPEN table per step; steps; pros and cons (4-5). For informed versus uninformed give the table and the map example.

Asked: [10 marks] (Jun 2023) Explain the Best First Search algorithm in detail? Asked: [7 marks] (Dec 2023) State the difference between informed search and uninformed search with suitable example.

Heuristic search algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A heuristic $h(n)$ estimates the cost from node $n$ to the goal, and heuristic search uses it to expand the most promising nodes first.</mark>

Key points.

  1. Heuristic search trades a guarantee of the best answer for speed.
  2. Generate-and-test produces candidates and tests each; a 3-digit lock needs up to 1,000 tries, and a known first digit cuts this to 100.
  3. 8-puzzle heuristics: $h_1$ misplaced tiles, $h_2$ sum of Manhattan distances; for start 283/164/7_5 and goal 123/8_4/765, $h_1=4$ and $h_2=1+2+1+1=5$, both admissible.
  4. Advantages of all heuristic techniques: they cut the nodes expanded, solve problems too large for blind search, and are simple to add to any search.
  5. Limitations: results may be sub-optimal; they are incomplete, as greedy search can loop forever on an infinite or cyclic space; local minima and plateaus; high memory; overestimation: with S-A 1, A-G 1, S-B 1, B-G 2 and $h(A)=5$ (true 1), $f(A)=6>f(B)=3$, so A* returns S-B-G at cost 3 and misses the cost-2 path.
  6. Mitigation: keep $h$ admissible; use $\max(h_1,h_2)$; use CLOSED to stop loops. Random restart reruns hill climbing from random starts. Simulated annealing accepts a worse move with probability $e^{-\Delta/T}$. Beam search keeps only the best $k$ nodes per level, bounding memory. IDA* runs depth-first with a rising $f$ cutoff in $O(d)$ memory.
Technique Advantage Limitation
Generate-and-test Simple, exhaustive Blind and slow
Hill climbing Fast, $O(1)$ memory Local maxima, plateaus
Best-first Fast with good $h$ Not optimal, high memory
A* Optimal if $h$ admissible High memory

Answer frame. $h(n)$; best-first steps and the OPEN trace (S, A, B, E, G); techniques (2, table); advantages 4, risks 5 and mitigation 6 in two columns.

Asked: [7 marks] (Nov 2022, Dec 2025) Write Heuristic search algorithm. Explain it with suitable example. Asked: [7 marks] (Dec 2024) Explore the potential risks and limitations of heuristic search algorithms in AI. How can these risks be mitigated? Asked: [7 marks] (Nov 2022, Dec 2025) Explain heuristic search techniques with examples.

A* and AO* search techniques

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. ==A* is a best-first search that orders nodes by $f(n)=g(n)+h(n)$, where $g(n)$ is the cost from the start to $n$ and $h(n)$ the estimated cost from $n$ to the goal.==

Key points.

  1. It combines uniform-cost ($g$) with greedy best-first ($h$); it is popular as it is complete, optimal and optimally efficient (no optimal algorithm with the same $h$ expands fewer nodes).
  2. Admissible means $h(n)\le h^*(n)$, never overestimating; then A* is optimal in tree search.
  3. Consistent means $h(n)\le c(n,n')+h(n')$, so $f$ never decreases; it implies admissible and makes A* optimal in graph search.
  4. Time and space are exponential, $O(b^d)$ worst case; memory is its weakness. Uses: route finding, games, robot paths.
  5. A* is complete when the branching factor is finite and every step cost is at least some $\epsilon>0$.
  6. AO* searches AND-OR graphs: an OR node costs its minimum child, an AND arc the sum of its children plus arc costs (trip = book travel AND book hotel).
  7. AO* is admissible (finds the least-cost solution graph) when $h$ never overestimates; it suits problem reduction, planning and theorem proving.
Algorithm $f(n)$ Complete Optimal
Dijkstra / UCS $g$ ($h=0$) Yes Yes
Greedy best-first $h$ No (tree) No
A* $g+h$ Yes Yes, admissible $h$ 
Step 1: Put start on OPEN, g=0, f=h.
Step 2: Move least-f node n to CLOSED; if goal, stop.
Step 3: For each successor m, g(m)=g(n)+cost, f=g+h; add to OPEN or update if cheaper; go to Step 2.

AO* Step 1: Graph G holds only INIT; compute h(INIT).
Step 2: Trace marked arcs from INIT to the best partial solution.
Step 3: Expand one unsolved node on it; a node with no successors costs FUTILITY.
Step 4: Revise costs up to INIT (OR min, AND sum), mark best arcs; a node is SOLVED when its marked arc's nodes all are.
Step 5: Repeat from Step 2 until INIT is SOLVED or its cost exceeds FUTILITY.

AO example* (OR = min, AND = sum + arc costs; each arc 1; $h$: B 7, C 2, D 3, E 4, F 3; G solved, cost 5).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-04" viewBox="0 0 338 338" width="338" height="338" role="img" aria-label="A has OR choice B, or the AND arc C+D; C has OR children E, F"><style>#dsfig-u1-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-04 .t{fill:#16181D;font-weight:500}#dsfig-u1-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-04 .dot{fill:#16181D}#dsfig-u1-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-04 .ah{fill:#454C5A}#dsfig-u1-04 .ah.hi{fill:#2340B8}#dsfig-u1-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-04 .e{stroke:#B1B7C3}html.dark #dsfig-u1-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-04 .t{fill:#E6E8ED}html.dark #dsfig-u1-04 .t.inv{fill:#0F1115}html.dark #dsfig-u1-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-04 .dot{fill:#E6E8ED}html.dark #dsfig-u1-04 .ann{fill:#8FA3FF}html.dark #dsfig-u1-04 .lbl{fill:#858D9C}html.dark #dsfig-u1-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-04 .ah{fill:#B1B7C3}html.dark #dsfig-u1-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M53.4,155.6 L154.2,54.8" marker-end="url(#ah4)"/><path class="e" d="M59,169 L148,169" marker-end="url(#ah4)"/><path class="e" d="M53.4,182.4 L154.2,283.2" marker-end="url(#ah4)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah4)"/><path class="e" d="M187,163 L278.1,132.6" marker-end="url(#ah4)"/><path class="e" d="M187,175 L278.1,205.4" marker-end="url(#ah4)"/><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="169" r="18"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="169" cy="298" r="18"/><text class="t" x="169" y="298" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">G</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">A has OR choice B, or the AND arc C+D; C has OR children E, F</figcaption></figure>

  1. Expand A: via B 1+7=8; via AND C,D (1+2)+(1+3)=7, so mark the AND arc.
  2. Expand C: C=min(1+4,1+3)=4, so C,D=(1+4)+(1+3)=9 exceeds 8; revise A to 8 and switch to B.
  3. Expand B: B=1+5=6, so A via B=7.

Solution A-B-G, cost 7.

Example (Dec 2023). Find A to J; node g+h: A 0+10 expands B 6+8, F 3+6; F expands G 4+5, H 10+3; G expands D 5+7, I 7+1; I expands H 9+3 (replaces 10+3), J 10+0, and D 12+7 (rejected, D already has f=12). J (f=10) is popped next: the goal counts only when popped.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-05" viewBox="0 0 668 322" width="668" height="322" role="img" aria-label="A* tree, node label g+h; H moved from F to I after the update"><style>#dsfig-u1-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-05 .t{fill:#16181D;font-weight:500}#dsfig-u1-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-05 .dot{fill:#16181D}#dsfig-u1-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-05 .ah{fill:#454C5A}#dsfig-u1-05 .ah.hi{fill:#2340B8}#dsfig-u1-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-05 .e{stroke:#B1B7C3}html.dark #dsfig-u1-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-05 .t{fill:#E6E8ED}html.dark #dsfig-u1-05 .t.inv{fill:#0F1115}html.dark #dsfig-u1-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-05 .dot{fill:#E6E8ED}html.dark #dsfig-u1-05 .ann{fill:#8FA3FF}html.dark #dsfig-u1-05 .lbl{fill:#858D9C}html.dark #dsfig-u1-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-05 .ah{fill:#B1B7C3}html.dark #dsfig-u1-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="129.5" y1="37" x2="52.5" y2="101"/><line class="e" x1="129.5" y1="37" x2="591.5" y2="101"/><line class="e" x1="591.5" y1="101" x2="283.5" y2="165"/><line class="e" x1="283.5" y1="165" x2="206.5" y2="229"/><line class="e" x1="283.5" y1="165" x2="437.5" y2="229"/><line class="e" x1="437.5" y1="229" x2="360.5" y2="293"/><line class="e" x1="437.5" y1="229" x2="514.5" y2="293"/><rect class="n" x="96" y="22" width="67" height="30" rx="8"/><text class="t" x="129.5" y="37" dy=".35em" text-anchor="middle">A 0+10</text><rect class="n" x="23" y="86" width="59" height="30" rx="8"/><text class="t" x="52.5" y="101" dy=".35em" text-anchor="middle">B 6+8</text><rect class="n" x="562" y="86" width="59" height="30" rx="8"/><text class="t" x="591.5" y="101" dy=".35em" text-anchor="middle">F 3+6</text><rect class="n" x="254" y="150" width="59" height="30" rx="8"/><text class="t" x="283.5" y="165" dy=".35em" text-anchor="middle">G 4+5</text><rect class="n" x="177" y="214" width="59" height="30" rx="8"/><text class="t" x="206.5" y="229" dy=".35em" text-anchor="middle">D 5+7</text><rect class="n" x="408" y="214" width="59" height="30" rx="8"/><text class="t" x="437.5" y="229" dy=".35em" text-anchor="middle">I 7+1</text><rect class="n" x="331" y="278" width="59" height="30" rx="8"/><text class="t" x="360.5" y="293" dy=".35em" text-anchor="middle">H 9+3</text><rect class="n" x="481" y="278" width="67" height="30" rx="8"/><text class="t" x="514.5" y="293" dy=".35em" text-anchor="middle">J 10+0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">A* tree, node label g+h; H moved from F to I after the update</figcaption></figure>

Path A-F-G-I-J with cost 10.

Feature A* AO*
Graph OR graph AND-OR graph
Output Single optimal path Optimal solution subgraph
Advantage Optimal if admissible Less memory on decomposable problems
Disadvantage High memory Complex; optimality fails with interacting subgoals or improper cost propagation

Answer frame. $f=g+h$; tree; steps; points 1-5 and the three-row table; for A* and AO* add 6-7, AO* steps, example, comparison table; close: A* is optimal with admissible $h$.

Asked: [8 marks] (Nov 2022, Jun 2023, Jun 2024) Explain the A* algorithm in detail. / How does A* combine elements of other search algorithms, and why is it popular? Asked: [7 marks] (Dec 2023) Explain how A* search different with AO* search technique. Discuss the advantage and disadvantage of both the techniques? Asked: [7 marks] (Dec 2023) Find the cheapest path from A to J using A* (h: A10 B8 C5 D7 E3 F6 G5 H3 I1 J0) and draw the search tree with cost at each node. Asked: [7 marks] (Dec 2023, Dec 2025) Discuss A* and AO* search algorithms.

Last-minute revision

  • Four views: act/think humanly or rationally.
  • Production system = database + rules + control; commutative = monotonic + partially commutative.
  • Water jug 4 L/3 L: (0,0), (0,3), (3,0), (3,3), (4,2), (0,2), (2,0).
  • A* $f=g+h$, optimal if $h\le h^*$; UCS/Dijkstra is $h=0$, greedy is $f=h$.
  • AO*: AND sums, OR takes the minimum; example A-B-G cost 7.
  • BFS $O(b^d)$ time and space; DFS $O(b^m)$ time, $O(bm)$ space.
  • Dec 2023 A*: A-F-G-I-J, cost 10; blocks world h -3, -1, +1, +3.

Memory hooks

  • Turing = Talk test; Rational = Right action.
  • A* = Actual so far + Aim ahead (g + h).
  • AND needs All, OR needs One.

Coverage checklist

  • Fundamental of Artificial Intelligence: 3 questions.
  • history: none.
  • motivation and need of AI: 1.
  • Production systems: 1.
  • Characteristics of production systems: 2.
  • goals and contribution of AI to modern technology: 3.
  • search space: 4.
  • different search techniques: hill Climbing: 3.
  • Best first Search: 2.
  • heuristic search algorithm: 3.
  • A* and AO* search techniques etc: 5.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in