Group A — Short Answer Questions (1 Mark Each)

Ans: Artificial Intelligence is the branch of computer science concerned with building rational agents — systems that perceive their environment through sensors and act through actuators so as to maximise their expected performance measure. It covers thinking/acting humanly (cognitive modelling, Turing Test) and thinking/acting rationally (logic- and utility-based decision making).

Ans: The Turing Test (Alan Turing, 1950) is a test of a machine's ability to exhibit intelligent behavior indistinguishable from that of a human through natural language text interaction.

Ans: An Intelligent Agent is anything that perceives its environment through sensors and acts upon it through actuators, defined abstractly by an agent function \(f : P^{*} \to A\) mapping every percept sequence to an action. It is rational if, for each percept sequence, it selects the action expected to maximise its performance measure given its built-in knowledge.

Ans: PEAS is the standard specification of a task environment written before designing an agent: Performance measure, Environment, Actuators and Sensors. For an automated taxi — performance: safe, fast, legal, comfortable trip; environment: roads, traffic, pedestrians; actuators: steering, accelerator, brake, horn; sensors: cameras, GPS, speedometer.

Ans: The Environment is everything external to the agent that it perceives through its sensors and can alter through its actuators; together with the performance measure it forms the task environment. Environments are classified as fully/partially observable, deterministic/stochastic, episodic/sequential, static/dynamic, discrete/continuous and single-agent/multi-agent.

Ans: An environment is Fully Observable if the agent's sensors give it access to the complete state of the environment at each point in time, so it need not maintain any internal state to keep track of the world. Example: chess with a visible board.

Ans: An environment is Partially Observable when noisy, inaccurate or incomplete sensors leave part of the state hidden, so the agent must maintain an internal belief state of the world. Example: an automated taxi that cannot sense what other drivers intend, or poker with hidden cards.

Ans: An environment is Deterministic if the next state is completely determined by the current state and the action executed by the agent, i.e. \(s' = T(s,a)\) with no element of chance. Example: the 8-puzzle or the simple vacuum-cleaner world.

Ans: An environment is Stochastic when the same action taken in the same state may lead to different next states, so outcomes must be described by a probability distribution \(P(s' \mid s, a)\). Example: taxi driving, where a tyre may burst or traffic may behave unpredictably.

Ans: The State Space is the set of all states reachable from the initial state by any legal sequence of actions. It forms a graph whose nodes are states and whose directed edges are actions, and a solution to the problem is a path in this graph from the initial state to a goal state.

Ans: The Initial State \(s_0\) is the state in which the agent begins problem solving, while a Goal State is any state satisfying the goal test. There may be many goal states, specified either explicitly (a listed configuration) or by an abstract property, e.g. "checkmate" in chess.

Ans: Path Cost is a function \(g(n)\) that assigns a numeric cost to a path from the initial state to node \(n\). It is normally additive, being the sum of the individual step costs, \(g(n) = \sum_i c(n_{i-1}, a_i, n_i)\), and an optimal solution is a path of minimum path cost.

Ans: Uninformed (Blind) Search uses only the information contained in the problem definition — it can generate successors and test whether a state is a goal, but has no domain-specific estimate of how close a state is to the goal. Examples: BFS, DFS, Depth-Limited Search, Uniform Cost Search and Iterative Deepening (IDDFS).

Ans: Informed (Heuristic) Search uses problem-specific knowledge in the form of a heuristic \(h(n)\) that estimates the cost from node \(n\) to the goal, and expands nodes in order of that estimate, so it reaches the goal far more efficiently than blind search. Examples: Greedy Best-First Search and A\(^{*}\) Search.

Ans: A Heuristic Function \(h(n)\) is a problem-specific function that estimates the cheapest cost of a path from node \(n\) to a goal state, with \(h(n) = 0\) at every goal node. It injects domain knowledge into an informed search — e.g. straight-line distance for route finding, or number of misplaced tiles / Manhattan distance for the 8-puzzle.

Ans: An Admissible Heuristic \(h(n)\) never overestimates the true minimal cost of reaching the goal from node \(n\): \(h(n) \le h^{*}(n)\) for all nodes \(n\), i.e. it is always optimistic. Admissibility is the condition that guarantees A\(^{*}\) tree search returns an optimal solution.

Ans: A Consistent (Monotonic) Heuristic obeys the triangle inequality \(h(n) \le c(n, a, n') + h(n')\) for every node \(n\) and every successor \(n'\) generated by action \(a\), with \(h(g) = 0\) at a goal. Consistency makes \(f(n) = g(n) + h(n)\) non-decreasing along any path and implies admissibility, so it is the stronger condition, guaranteeing optimality of A\(^{*}\) graph search.

Ans: Breadth-First Search expands the shallowest unexpanded node first, using a FIFO queue as its frontier. It is complete and is optimal when every step cost is equal, but requires time and space \(O(b^{d})\), where \(b\) is the branching factor and \(d\) the depth of the shallowest goal — memory is its limiting factor.

Ans: Depth-First Search expands the deepest unexpanded node first, using a LIFO stack (or recursion). Its advantage is linear space \(O(bm)\), but it is neither complete (it can loop forever in cyclic or infinite spaces) nor optimal, with worst-case time \(O(b^{m})\).

Ans: Uniform Cost Search expands the frontier node with the lowest path cost \(g(n)\), using a priority queue ordered by \(g\) and applying the goal test when a node is selected for expansion rather than when generated. It is complete and optimal for non-negative step costs bounded below by some \(\epsilon > 0\), and is exactly A\(^{*}\) with \(h(n) = 0\).

Ans: A\(^{*}\) Search is a best-first search that always expands the node with the smallest evaluation \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost already incurred to reach \(n\) and \(h(n)\) the estimated cost from \(n\) to the goal. It is complete and optimal when \(h\) is admissible (tree search) or consistent (graph search), and is optimally efficient — no other optimal algorithm expands fewer nodes for the same heuristic.

Ans: Greedy Best-First Search expands the node that appears nearest the goal, ordering the frontier by the heuristic alone, \(f(n) = h(n)\), and ignoring the cost \(g(n)\) already spent. This makes it fast but neither optimal nor complete (it can follow a false trail or loop) — precisely the difference from A\(^{*}\), which adds \(g(n)\).

Ans: Hill Climbing is a local search that keeps only the current state and repeatedly moves to the neighbour with the best objective value, halting when no neighbour is better. It maintains no search tree and never backtracks ("greedy local search"), so although it uses very little memory it can become stuck at local maxima, plateaux and ridges.

Ans: A Local Maximum is a state whose objective value is higher than that of all its neighbours but lower than the global maximum. Hill climbing terminates there because every available move leads downhill, so it returns a sub-optimal solution.

Ans: A Plateau is a flat region of the state space in which all neighbouring states have the same objective value, so there is no gradient for the search to follow and it wanders aimlessly. A plateau is either a flat local maximum, from which no escape exists, or a shoulder, from which progress uphill is still possible.

Ans: A Ridge is a narrow ascending crest of successively higher states whose slope cannot be followed by the available moves, because every single legal move from a point on the ridge steps downwards. Hill climbing therefore oscillates from side to side and stalls, even though the ridge as a whole slopes upward towards the goal.

Ans: Simulated Annealing is a stochastic local search that picks a random neighbour each iteration: an improving move is always accepted, while a worsening move of size \(\Delta E < 0\) is accepted with probability \(p = e^{\Delta E / T}\). The temperature \(T\) is reduced by a cooling schedule so that bad moves grow rarer, and if \(T\) is lowered slowly enough the algorithm reaches a global optimum with probability approaching 1.

Ans: A Constraint Satisfaction Problem is defined by a set of variables \(X = \{X_1, \ldots, X_n\}\), a domain \(D_i\) of allowed values for each variable, and a set of constraints \(C\) restricting the permissible combinations of values. A solution is a complete assignment to all variables that is consistent with every constraint — e.g. map colouring, N-Queens or cryptarithmetic.

Ans: Backtracking Search is the basic uninformed algorithm for CSPs: a depth-first search that assigns a value to one variable at a time and, whenever a variable has no value left consistent with the current partial assignment, undoes the most recent assignment and tries an alternative. Its efficiency is greatly improved by the MRV and degree heuristics, least-constraining-value ordering and forward checking.

Ans: A Game Tree is a tree whose root is the initial game position, whose nodes are game states, whose edges are legal moves, and whose successive plies alternate between the MAX and MIN players. Its leaves are terminal states labelled with a utility value evaluated from MAX's point of view (e.g. \(+1, 0, -1\)).

Ans: The Minimax Algorithm computes MAX's optimal move under the assumption that MIN also plays optimally, by backing terminal utilities up the game tree — taking the maximum of the children at MAX nodes and the minimum at MIN nodes. It performs a complete depth-first exploration, with time \(O(b^{m})\) and space \(O(bm)\).

Ans: Alpha-Beta Pruning is an adversarial search optimization for minimax game trees that prunes subtrees when \(\alpha \ge \beta\), where \(\alpha\) is max's best guaranteed choice and \(\beta\) is min's best choice.

Ans: In alpha-beta pruning, \(\alpha\) is the value of the best (highest) choice found so far for MAX anywhere along the current path — a lower bound that can only increase — and \(\beta\) is the value of the best (lowest) choice found so far for MIN — an upper bound that can only decrease. They are initialised to \(\alpha = -\infty\), \(\beta = +\infty\), and the remaining branches of a node are cut off as soon as \(\alpha \ge \beta\).

Ans: Knowledge Representation is the sub-field of AI concerned with encoding facts about the world in a formal symbolic form that a machine can store in a knowledge base and reason over by inference. A good scheme must have representational and inferential adequacy plus inferential and acquisitional efficiency; the main schemes are logic, production rules, semantic networks and frames.

Ans: A Knowledge Base is a set of sentences expressed in a knowledge representation language, each asserting some fact about the world (its axioms). A knowledge-based agent uses two operations on it: TELL, which adds a new sentence, and ASK, which queries what follows from it by entailment, \(KB \models \alpha\).

Ans: Propositional Logic is the simplest declarative logic, in which atomic propositions are either true or false and are combined using the connectives \(\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow\), their meaning fixed by truth tables. It is declarative and compositional, but has no objects, variables or quantifiers, so it cannot concisely express facts about classes of objects.

Ans: First-Order Logic (First-Order Predicate Logic) extends propositional logic with an ontology of objects, relations (predicates) and functions, together with variables and the quantifiers \(\forall\) and \(\exists\). It is therefore far more expressive: a single sentence \(\forall x \, (Man(x) \Rightarrow Mortal(x))\) states a rule about every object in the domain.

Ans: The Universal Quantifier \(\forall\) asserts that a sentence holds for every object in the domain — \(\forall x \, P(x)\) is true iff \(P\) is true for every substitution of an object for \(x\). Its natural companion connective is implication, as in \(\forall x \, (King(x) \Rightarrow Person(x))\); using \(\wedge\) instead would wrongly claim that everything is a king.

Ans: The Existential Quantifier \(\exists\) asserts that a sentence holds for at least one object in the domain — \(\exists x \, P(x)\). Its natural companion connective is conjunction, as in \(\exists x \, (Crown(x) \wedge OnHead(x, John))\), and it is dual to the universal quantifier: \(\exists x \, P(x) \equiv \neg \forall x \, \neg P(x)\).

Ans: A sentence is in Conjunctive Normal Form when it is written as a conjunction of clauses, each clause being a disjunction of literals: \((l_{11} \vee \cdots \vee l_{1k}) \wedge \cdots \wedge (l_{n1} \vee \cdots \vee l_{nm})\). Every sentence can be converted into a logically equivalent CNF, and CNF is the required input form for the resolution inference rule.

Ans: Resolution Refutation is proof by contradiction: to establish \(KB \models \alpha\) one converts \(KB \wedge \neg \alpha\) into CNF and repeatedly applies the resolution rule to clause pairs containing complementary literals. Deriving the empty clause \(\square\) shows \(KB \wedge \neg \alpha\) is unsatisfiable and hence proves \(\alpha\); resolution is refutation-complete.

Ans: Unification is the process of finding a substitution \(\theta\) that makes two logical expressions syntactically identical: \(UNIFY(p, q) = \theta\) such that \(p\theta = q\theta\). For example \(UNIFY(Knows(John, x),\, Knows(y, Jane)) = \{x/Jane,\ y/John\}\); the algorithm returns the Most General Unifier (MGU), the unifier that commits to the fewest variable bindings.

Ans: A Horn Clause is a disjunction of literals containing at most one positive literal, e.g. \(\neg P_1 \vee \neg P_2 \vee Q\), which is equivalent to the implication \(P_1 \wedge P_2 \Rightarrow Q\). A clause with exactly one positive literal is a definite clause, and entailment over definite clauses can be decided by forward or backward chaining in time linear in the size of the knowledge base.

Ans: Forward Chaining is data-driven, bottom-up inference: beginning from the known facts in the KB it repeatedly fires every rule whose premises are all satisfied and adds the conclusion as a new fact, until the query is derived or no further fact can be inferred. It is sound and complete for definite clauses, but may generate many conclusions irrelevant to the goal.

Ans: Backward Chaining is goal-driven, top-down inference: it starts from the query, finds rules whose conclusion unifies with it, and recursively proves each premise of those rules as a sub-goal until known facts are reached. It touches only goal-relevant facts and is the inference mechanism underlying logic programming (Prolog).

Ans: A Semantic Network is a graphical knowledge representation in which nodes denote objects, concepts or events and labelled directed arcs denote binary relations between them, chiefly IS-A (subclass/instance) and HAS-A (property) links. Properties are obtained by inheritance down the IS-A links, e.g. Sparrow IS-A Bird inherits "can fly".

Ans: A Frame (Minsky, 1975) is a structured record that represents a stereotyped object or situation as a collection of named slots with their fillers — values, defaults, constraints or procedural attachments (IF-NEEDED / IF-ADDED demons). Frames are organised in an is-a hierarchy so that a child frame inherits the slots of its parent, e.g. a Car frame with Wheels = 4, Fuel = Petrol.

Ans: Bayes' Theorem relates the posterior probability of a hypothesis to its prior and the likelihood of the evidence: \(P(H \mid E) = \dfrac{P(E \mid H)\, P(H)}{P(E)}\). It lets an agent convert the causal probability \(P(E \mid H)\), which is easy to obtain, into the required diagnostic probability \(P(H \mid E)\), and is the foundation of reasoning under uncertainty.

Ans: A Bayesian (Belief) Network is a directed acyclic graph whose nodes are random variables and whose edges denote direct conditional dependence, each node carrying a Conditional Probability Table \(P(X_i \mid Parents(X_i))\). Because every variable is conditionally independent of its non-descendants given its parents, it represents the full joint distribution compactly as \(P(x_1, \ldots, x_n) = \prod_{i=1}^{n} P(x_i \mid parents(X_i))\).

Ans: Fuzzy Logic (Zadeh, 1965) is a many-valued logic in which the truth of a proposition is a degree in the continuous interval \([0,1]\) instead of a crisp \(\{0,1\}\). It therefore models vague linguistic terms such as "tall", "hot" or "very dirty", with the standard operations \(\mu_{A \cap B} = \min(\mu_A, \mu_B)\), \(\mu_{A \cup B} = \max(\mu_A, \mu_B)\) and \(\mu_{\bar{A}} = 1 - \mu_A\).

Ans: A Membership Function \(\mu_A(x) : X \to [0,1]\) assigns to each element \(x\) of the universe of discourse \(X\) its degree of membership in the fuzzy set \(A\), where 0 denotes no membership and 1 full membership. Typical shapes are triangular, trapezoidal, Gaussian and sigmoidal; a crisp set is the special case in which \(\mu_A(x) \in \{0,1\}\).

Ans: An Expert System is an AI program that emulates the decision-making ability of a human expert within a narrow domain, built from a knowledge base of domain rules and facts plus an inference engine that applies them, supported by a user interface and an explanation facility. Classic examples are MYCIN (diagnosis of blood infections) and DENDRAL (molecular structure).

Ans: An Expert System Shell is an expert system with its domain knowledge removed — it supplies the ready-made inference engine, user interface, explanation facility and knowledge-base editor, so a developer need only add the domain-specific rules. This sharply reduces development effort; the classic example is EMYCIN, the shell derived from MYCIN.