Artificial Intelligence

State space. Take an undirected graph with start $S$, goal $G$ and two other nodes $A$, $B$. Edge costs (local costs) and heuristic values:

The true cost to the goal is $h^*(S)=6$, $h^*(A)=7$, $h^*(B)=3$, $h^*(G)=0$. Since $h\le h^*$ everywhere, $h$ is admissible. It is also consistent: for example $h(S)=2\le c(S,A)+h(A)=1+1$ and $h(A)=1\le c(A,S)+h(S)=1+2$.

Greedy best-first search (f(n) = h(n)) is not complete. It always expands the node with the smallest $h$, ignoring the cost so far and (in tree search) repeated states.

From $A$ the only successor is $S$, and $h(S)=2<h(B)=3$, so $S$ is chosen again, then $A$ again, and so on. The search oscillates $S\to A\to S\to A\dots$ forever and node $B$ (the only way to $G$) is never expanded. Hence greedy search fails to find a solution although one exists, so it is incomplete (in an infinite or looping state space).

A* search (f(n) = g(n) + h(n)) is complete here. Because $g$ grows with every move, a looping path eventually has a larger $f$ than the path that reaches the goal.

(Ties at $f=6$ are broken in favour of the goal/shallower node; any other tie-break only delays by finitely many steps, since each further loop $S\to A\to S$ raises $f$ by 2.)

Solution: $S\to B\to G$ with cost $3+3=6$, which is optimal.

Conclusion. Greedy search can loop on the cheapest-looking heuristic and never reach the goal, whereas A* is complete (finite branching factor, all step costs $\ge\epsilon>0$) and, with an admissible heuristic, also optimal. A* guarantees a solution whenever one exists, as shown above.

Resolution in FOPL. Resolution is a refutation-based inference rule. To prove that a query $\alpha$ follows from a knowledge base $KB$:

1. Convert every sentence of $KB$ to first-order logic.
2. Convert to clause (conjunctive normal) form: eliminate $\rightarrow$, move $\neg$ inward, standardise variables, Skolemise $\exists$, drop $\forall$.
3. Negate the query, convert it to clauses and add it to the set.
4. Repeatedly pick two clauses containing complementary literals, unify them (finding a most general unifier $\theta$) and add the resolvent.
5. If the empty clause ($\square$) is derived, the set is contradictory, so $KB\models\alpha$.

Conversion to FOPL.

1. $\forall x\; loves(Pugu,x)\rightarrow star(x)$
2. $\forall x\; hero(x)\wedge\neg rehearse(x)\rightarrow\neg act(x)$
3. $hero(Anmol)$
4. $\forall x\; hero(x)\wedge\neg work(x)\rightarrow\neg rehearse(x)$
5. $\forall x\; \neg act(x)\rightarrow\neg star(x)$

Goal: $\neg work(Anmol)\rightarrow\neg loves(Pugu,Anmol)$. Its negation is $\neg work(Anmol)\wedge loves(Pugu,Anmol)$.

Clause form.

• C1: $\neg loves(Pugu,x)\vee star(x)$
• C2: $\neg hero(x)\vee rehearse(x)\vee\neg act(x)$
• C3: $hero(Anmol)$
• C4: $\neg hero(x)\vee work(x)\vee\neg rehearse(x)$
• C5: $act(x)\vee\neg star(x)$
• C6: $\neg work(Anmol)$ (negated goal)
• C7: $loves(Pugu,Anmol)$ (negated goal)

Resolution proof.

The empty clause is derived, so the negated goal is inconsistent with the knowledge base. Hence "If Anmol does not work, then Pugu does not love Anmol" is proved.

Mathematical model of an artificial neural network. An ANN is built from simple processing units (artificial neurons) joined by weighted connections. A single neuron receives inputs $x_1,\dots,x_n$ with weights $w_1,\dots,w_n$ and a bias $b$. It first forms the net input

$net=\sum_{i=1}^{n}w_ix_i+b$

and then applies an activation function $f$ to give the output

$y=f(net)=f\Big(\sum_{i=1}^{n}w_ix_i+b\Big)$

Common activation functions are:

• Step / threshold: $f(net)=1$ if $net\ge0$, else $0$ (or $-1$ for the bipolar case).
• Sigmoid: $f(net)=\dfrac{1}{1+e^{-net}}$.
• Tanh: $f(net)=\tanh(net)$.

Neurons are arranged in layers (input, hidden, output). Knowledge is stored in the weights, and learning means adjusting them.

Hebbian learning. Hebb's rule states that "neurons that fire together wire together": if two connected neurons are active together, the connection between them is strengthened. For input $x_i$ and target (output) $y$ the weight update is

$w_i^{new}=w_i^{old}+x_i\,y,\qquad b^{new}=b^{old}+y$

Training algorithm.

1. Initialise all weights and bias to $0$.
2. For each training pair $(x,t)$: set the activation $y=t$, update $w_i=w_i+x_it$ and $b=b+t$.
3. After all patterns have been presented once the weights are final (Hebb learning needs only one pass).

Example: AND function with bipolar inputs and targets.

Start with $w_1=w_2=b=0$.

Final weights: $w_1=2,\ w_2=2,\ b=-2$.

Check: with $y=\text{sign}(2x_1+2x_2-2)$:

• $(1,1)$: $2>0\Rightarrow 1$
• $(1,-1)$: $-2\Rightarrow -1$
• $(-1,1)$: $-2\Rightarrow -1$
• $(-1,-1)$: $-6\Rightarrow -1$

All four outputs match the targets, so the network has learned the AND function.

Artificial Intelligence (AI) is the branch of computer science concerned with designing machines and programs that can perform tasks which normally require human intelligence, such as learning, reasoning, problem solving, perception and understanding language. The term was coined by John McCarthy in 1956.

Definitions from the perspective of thought process. Russell and Norvig classify the definitions of AI along two dimensions: thought/reasoning versus behaviour, and human-like versus rational. The thought-process view contains two approaches:

1. Thinking humanly (the cognitive modelling approach). AI is "the exciting new effort to make computers think... machines with minds, in the full and literal sense" (Haugeland, 1985), or "the automation of activities that we associate with human thinking, such as decision making, problem solving, learning" (Bellman, 1978). To say a program thinks like a human, we must know how humans think, which we learn through introspection, psychological experiments and brain imaging. Cognitive science combines AI models with experimental techniques to test theories of the mind (e.g. the General Problem Solver of Newell and Simon).

2. Thinking rationally (the "laws of thought" approach). AI is "the study of mental faculties through the use of computational models" (Charniak and McDermott, 1985), or "the study of the computations that make it possible to perceive, reason and act" (Winston, 1992). It follows Aristotle's syllogisms and formal logic: correct reasoning patterns that always give correct conclusions from correct premises. The logicist tradition builds programs that represent problems in logical notation and prove conclusions. Its difficulties are that informal and uncertain knowledge is hard to express in logic, and that being able to solve a problem "in principle" is different from solving it in practice.

So, in terms of thought process, AI is either modelling how humans think or implementing correct (rational) reasoning in machines.

An agent's environment is the world it perceives through sensors and acts upon through actuators. Environments are classified by the following properties.

1. Fully observable vs partially observable. In a fully observable environment the sensors give the complete state at each moment (e.g. chess, crossword). In a partially observable one, sensors are noisy or incomplete (e.g. taxi driving, poker).

2. Deterministic vs stochastic. If the next state is completely determined by the current state and the agent's action, the environment is deterministic (chess). Otherwise it is stochastic (taxi driving, where traffic is unpredictable). An environment that is deterministic except for the actions of other agents is called strategic.

3. Episodic vs sequential. In an episodic environment the agent's experience is divided into independent episodes, and the current decision does not affect later ones (image classification on an assembly line). In a sequential environment the current decision affects future decisions (chess, driving).

4. Static vs dynamic. A static environment does not change while the agent deliberates (crossword puzzle). A dynamic one changes with time (taxi driving). If the environment does not change but the agent's score does with time, it is semi-dynamic (chess with a clock).

5. Discrete vs continuous. Discrete environments have a finite number of states, percepts and actions (chess). Continuous ones have infinitely many values (taxi driving: speed, position).

6. Single-agent vs multi-agent. Only one agent acts (crossword) versus several competing or cooperating agents (chess is competitive; taxi driving is partly cooperative).

7. Known vs unknown. In a known environment the agent knows the "laws" (outcomes of actions); in an unknown one it must learn them.

The hardest case is partially observable, stochastic, sequential, dynamic, continuous and multi-agent, such as driving a taxi.

Uniform cost search (UCS) is an uninformed search that expands the frontier node with the lowest path cost $g(n)$. It uses a priority queue ordered by $g(n)$, and the goal test is applied when a node is selected for expansion (not when generated). It is complete (if every step cost $\ge\epsilon>0$) and optimal.

Algorithm.

1. Put the start node in the priority queue with $g=0$.
2. Remove the node with the smallest $g$. If it is a goal, return the path.
3. Otherwise expand it; for every child compute $g(child)=g(parent)+cost$ and insert it (or update it if a cheaper path to an already-queued state is found).
4. Repeat from step 2.

Example. State space with start $S$ and goal $G$:

The path found is $S\to B\to G$ with cost $5+5=10$. Note that the path $S\to A\to G$ (cost 11) was generated first, but because the goal is tested only when selected, UCS returns the cheaper path. Hence UCS finds the least-cost solution.

Frame. A frame is a data structure for representing stereotyped knowledge about an object, concept or situation, proposed by Marvin Minsky (1975). It is a collection of slots (attributes) with fillers (values), and frames are organised in a hierarchy so that specific frames inherit properties from more general ones.

How knowledge is encoded.

• Each frame has a name and a set of slots.
• A slot holds a value, a default value, a range/type restriction, or a procedure (facet: if-needed, if-added, if-removed demons) that computes or reacts to a value.
• Frames are linked by is-a (class–subclass) and instance-of links, so a child frame inherits slot values from its parent unless overridden.
• Reasoning is done by filling slots, inheriting defaults and firing attached procedures.

Example.

Frame: Person
  is-a: Mammal
  legs: 2                      (default)
  can_speak: true

Frame: Student
  is-a: Person
  studies_at: (value: a college)
  roll_no: (value: integer)
  age: [15..40]                (range)
  if-needed: compute_age(date_of_birth)

Frame: Ram
  instance-of: Student
  studies_at: Patan College
  roll_no: 21
  age: 20

Asking for Ram.legs finds no local value, so the system follows instance-of to Student, then is-a to Person and inherits legs = 2. Frames therefore store structured knowledge compactly, support default reasoning and inheritance, and attach procedures to data.

Membership in a fuzzy set. In a classical (crisp) set an element either belongs ($1$) or does not belong ($0$). In a fuzzy set $A$ on a universe $X$, each element $x$ has a degree of membership $\mu_A(x)\in[0,1]$, given by the membership function $\mu_A:X\to[0,1]$. A value near $1$ means strong membership, near $0$ weak membership. A fuzzy set is written

$A=\{(x,\mu_A(x))\mid x\in X\}=\sum_i \mu_A(x_i)/x_i$

Constructing a fuzzy set. Let $X=\{10,20,30,40,50,60,70\}$ and let $A$ = "numbers close to 40", with the triangular membership function

$\mu_A(x)=\max\Big(0,\;1-\frac{|x-40|}{30}\Big)$

For example $\mu_A(20)=1-20/30=0.33$ and $\mu_A(30)=1-10/30=0.67$.

Hence

$A=\{0/10,\;0.33/20,\;0.67/30,\;1/40,\;0.67/50,\;0.33/60,\;0/70\}$

Here 40 fully belongs to the set, 30 and 50 belong to degree $0.67$, 20 and 60 to degree $0.33$, while 10 and 70 do not belong at all.

Genetic algorithm (GA) is a search and learning technique inspired by natural selection. A population of candidate solutions (chromosomes, usually bit strings) evolves over generations using selection, crossover and mutation, guided by a fitness function.

Algorithm.

1. Initialise: generate a random population of $N$ chromosomes.
2. Evaluate: compute the fitness $f(c)$ of every chromosome.
3. Repeat until the termination condition (a chromosome of sufficient fitness is found, or a maximum number of generations is reached):
   1. Selection: choose parents with probability proportional to fitness (roulette-wheel, tournament or rank selection).
   2. Crossover: with probability $p_c$, pair parents and exchange parts of their strings at a random crossover point to create offspring; otherwise copy the parents.
   3. Mutation: with a small probability $p_m$, flip each bit of the offspring.
   4. Replacement: form the new population from the offspring (optionally keeping the best individuals, i.e. elitism).
   5. Evaluate the fitness of the new population.
4. Return the fittest chromosome as the solution.

Pseudocode.

initialize population P(0) randomly
evaluate fitness of each member of P(0)
t = 0
while not terminated:
    P' = empty
    while |P'| < N:
        parent1, parent2 = select(P(t))
        child1, child2 = crossover(parent1, parent2, pc)
        mutate(child1, pm); mutate(child2, pm)
        add child1, child2 to P'
    P(t+1) = P'
    evaluate fitness of P(t+1)
    t = t + 1
return best individual in P(t)

Representing uncertain knowledge. Knowledge is uncertain when facts are incomplete, noisy or non-deterministic. It is represented with:

• Probability theory: each proposition has a degree of belief in $[0,1]$; full joint probability distributions, conditional probabilities, Bayes' rule and Bayesian (belief) networks are used.
• Certainty factors (as in MYCIN), Dempster–Shafer theory (belief and plausibility intervals), and fuzzy logic (degrees of truth/membership).
• Non-monotonic logics / default reasoning for conclusions that can be withdrawn.

Numerical part. We need $P(L=130\mid W=15)$. By the definition of conditional probability:

$P(L=130\mid W=15)=\frac{P(L=130,\,W=15)}{P(W=15)}$

From the table, $P(L=130,W=15)=0.42$.

The marginal probability of width 15 is the sum of its row:

$P(W=15)=0.12+0.42+0.06=0.60$

Therefore

$P(L=130\mid W=15)=\frac{0.42}{0.60}=0.7$

The probability that a CD cover has length 130 mm given a width of 15 mm is 0.7.

Machine vision in robotics is the use of cameras and image-processing algorithms to let a robot acquire, analyse and interpret images of its surroundings. It acts as the robot's "eyes", and the visual information is used to decide how to configure and use the other sensors.

Steps of machine vision.

1. Image acquisition: a camera (CCD/CMOS, stereo or depth camera) converts the scene into a digital image.
2. Pre-processing: noise removal, smoothing, contrast enhancement.
3. Segmentation and edge detection: separate objects from the background and find boundaries.
4. Feature extraction: corners, shapes, colour and texture.
5. Object recognition / interpretation: match features against models to identify objects, positions and orientation.

Use in configuring the robot's sensors.

• Choosing and placing sensors: vision defines the field of view, resolution, lighting and camera mounting (eye-in-hand on the gripper or fixed overhead) required for the task.
• Calibration: camera calibration relates image coordinates to real-world coordinates, so that the robot arm can reach what the camera sees.
• Sensor fusion: vision is combined with proximity, range (ultrasonic, laser), touch and force sensors. Vision gives the location of a target, range sensors give accurate distance, and tactile sensors confirm the grasp.
• Feedback control (visual servoing): the difference between the desired and the observed image position is used to correct the robot's motion continuously.
• Adaptation: based on what is detected (obstacle, object size, colour), the robot selects which sensors to activate and their thresholds.

Applications: part inspection, pick-and-place, assembly, navigation and obstacle avoidance of mobile robots, and sorting in industry.

Natural language processing (NLP) proceeds through several levels: lexical, syntactic, semantic, pragmatic and discourse analysis.

Syntactic analysis (parsing). It checks whether a sentence is grammatically well formed and builds its structure (a parse tree) using a lexicon and grammar rules, usually context-free rules such as:

• $S\rightarrow NP\;VP$
• $NP\rightarrow Det\;N$
• $VP\rightarrow V\;NP$

Parsing can be top-down or bottom-up (e.g. chart parsing, or augmented transition networks).

Example: "The boy eats an apple."

S
├── NP: Det(The) N(boy)
└── VP: V(eats)
        └── NP: Det(an) N(apple)

A sentence like "Boy the apple eats" fails syntactic analysis because no rule derives it.

Semantic analysis. It assigns meaning to the syntactic structure, producing a logical representation independent of context. Word senses are resolved and the roles (agent, object) are attached using the parse tree. For the example above:

$\exists x\,\exists y\; boy(x)\wedge apple(y)\wedge eats(x,y)$

It also rejects sentences that are grammatical but meaningless, e.g. "Colourless green ideas sleep furiously", or "The apple eats the boy" (violates the selectional restriction that the agent of eats must be animate). Ambiguity is handled here, e.g. "bank" (river bank or financial bank).

Summary: syntactic analysis answers "is the sentence well formed and how is it structured?", semantic analysis answers "what does it mean?". The outputs go on to pragmatic analysis, which interprets the meaning in context.

Knowledge base in FOPL. Predicates: $traffic(x)$, $driver(x)$, $chases(x,y)$, $catches(x,y)$, $horn(x)$, $smart(x)$, $frustrated(x)$.

1. Every traffic chases a driver: $\forall x\;traffic(x)\rightarrow\exists y\;(driver(y)\wedge chases(x,y))$
2. Every driver who horns is smart: $\forall x\;driver(x)\wedge horn(x)\rightarrow smart(x)$
3. No traffic catches any smart driver: $\forall x\forall y\;traffic(x)\wedge smart(y)\rightarrow\neg catches(x,y)$
4. Any traffic who chases some driver but does not catch him is frustrated: $\forall x\forall y\;traffic(x)\wedge driver(y)\wedge chases(x,y)\wedge\neg catches(x,y)\rightarrow frustrated(x)$

Goal: $(\forall x\;driver(x)\rightarrow horn(x))\rightarrow(\forall x\;traffic(x)\rightarrow frustrated(x))$.

Negated goal: $(\forall x\;driver(x)\rightarrow horn(x))\wedge\exists x\;(traffic(x)\wedge\neg frustrated(x))$.

Clause form (Skolem function $f(x)$ for the driver chased by $x$, constant $a$ for the unfrustrated traffic):

• C1: $\neg traffic(x)\vee driver(f(x))$
• C2: $\neg traffic(x)\vee chases(x,f(x))$
• C3: $\neg driver(x)\vee\neg horn(x)\vee smart(x)$
• C4: $\neg traffic(x)\vee\neg smart(y)\vee\neg catches(x,y)$
• C5: $\neg traffic(x)\vee\neg driver(y)\vee\neg chases(x,y)\vee catches(x,y)\vee frustrated(x)$
• C6: $\neg driver(x)\vee horn(x)$ (negated goal)
• C7: $traffic(a)$ (negated goal)
• C8: $\neg frustrated(a)$ (negated goal)

Resolution proof.

The empty clause is derived, so the negated goal is contradictory. Therefore "If all drivers horn, then all traffics are frustrated" is proved.

Mathematical model of a neural network. A neuron computes a weighted sum of its inputs plus a bias and passes it through an activation function:

$net=\sum_{i=1}^{n}w_ix_i+b,\qquad y=f(net)$

where $x_i$ are inputs, $w_i$ weights, $b$ the bias and $f$ the activation (step, sigmoid, tanh, ReLU). A network is a set of such neurons arranged in layers, with the output of one layer being the input of the next. For a multilayer network, layer $l$ computes $\mathbf a^{(l)}=f(W^{(l)}\mathbf a^{(l-1)}+\mathbf b^{(l)})$.

Training a neural network means finding values of the weights and biases that make the network's outputs match the desired outputs on a set of training examples. This is done iteratively: present an input, compare the actual output $y$ with the target $t$, measure the error (e.g. $E=\tfrac12\sum(t-y)^2$), and adjust the weights to reduce the error. Training ends when the error is acceptably small or a maximum number of epochs is reached. The trained weights then generalise to unseen inputs.

Perceptron learning algorithm (single neuron, step activation, learning rate $\alpha$, $0<\alpha\le1$):

1. Initialise weights $w_i$ and bias $b$ to small random values (or $0$).
2. For each training pair $(x,t)$ in the training set:
   1. Compute $net=\sum w_ix_i+b$.
   2. Compute the output $y=1$ if $net>\theta$, $y=0$ (or $-1$) otherwise.
   3. If $y\ne t$, update: $w_i\leftarrow w_i+\alpha(t-y)x_i$ and $b\leftarrow b+\alpha(t-y)$.
3. Repeat step 2 (one pass is one epoch) until no weight changes occur in a complete epoch (all patterns are correctly classified) or the maximum number of epochs is reached.

By the perceptron convergence theorem, the algorithm converges in a finite number of steps if the classes are linearly separable. It cannot learn non-separable functions such as XOR.

Turing test. Proposed by Alan Turing in 1950 ("Computing Machinery and Intelligence") as an operational definition of machine intelligence, replacing the question "Can machines think?".

Set-up (imitation game). There are three participants: a human interrogator (C) in one room, and a human (B) and a machine (A) in other rooms. The interrogator communicates with both only through a text terminal, asks any questions, and must decide which of the two is the machine. The machine tries to answer so as to be taken for the human.

Measuring intelligence. If, after a set time (Turing suggested about 5 minutes of questioning), the interrogator cannot reliably tell the machine from the human (e.g. is wrong in at least about 30% of trials), the machine is said to have passed the test and to exhibit human-level intelligent behaviour.

Capabilities a machine needs to pass:

• Natural language processing to communicate.
• Knowledge representation to store what it knows or hears.
• Automated reasoning to answer questions and draw new conclusions.
• Machine learning to adapt and detect patterns.

The total Turing test adds a video signal and physical objects, which also requires computer vision and robotics.

Limitations. It tests only behaviour, not real understanding (Searle's Chinese Room argument), is subjective, and rewards deception and human-like mistakes rather than rational intelligence.

PEAS framework. To design a rational agent we first specify its task environment with four components:

• P – Performance measure: the criterion that decides how successful the agent is.
• E – Environment: the surroundings in which the agent operates.
• A – Actuators: the means by which the agent acts on the environment.
• S – Sensors: the means by which the agent perceives the environment.

Specifying PEAS fixes what the agent has to perceive, what it may do and what counts as good behaviour, so that the agent program (simple reflex, model-based, goal-based, utility-based) can then be chosen.

Example 1: automated taxi driver.

Example 2: medical diagnosis system.

Thus, using PEAS the agent is configured by deciding its sensors, actuators and the performance measure that guides its decisions.

A semantic network represents knowledge as a graph: nodes are concepts/objects/values and labelled arcs are relations between them (is-a, instance-of, has-part, weight, less-than). Properties are inherited along is-a links.

Nodes and links for the given facts.

Diagram.

        Mammal
          ^
          | instance-of
        Human ----has-part----> Nose
          ^
          | is-a
        Person
          ^
          | instance-of
         Ram ----weight----> 60 kg
          |
          +--- weight less-than ---> Sita (weight of Sita)

Inference by inheritance: Ram is a Person, a Person is a Human, and a Human has a nose, so Ram has a nose. Similarly Ram inherits membership of Mammal through Human. The less-than arc states that Ram's weight is below Sita's weight, so Sita weighs more than 60 kg.

Crossover is the genetic operator that combines the genetic material of two parent chromosomes to produce new offspring, exchanging parts of the strings at chosen crossover points. It is the main source of new combinations in a genetic algorithm and is applied with a probability $p_c$ (typically 0.6 to 0.9).

Parents:

• C1 = 01100010
• C2 = 10101100

One-point crossover (point after the 3rd bit):

• C1 = 011 | 00010
• C2 = 101 | 01100

Swapping the tails:

• Offspring 1 = 011 + 01100 = 01101100
• Offspring 2 = 101 + 00010 = 10100010

Two-point crossover (points after the 2nd and 5th bits):

• C1 = 01 | 100 | 010
• C2 = 10 | 101 | 100

Swapping the middle segments:

• Offspring 1 = 01 + 101 + 010 = 01101010
• Offspring 2 = 10 + 100 + 100 = 10100100

Expert system. An expert system is a computer program that emulates the decision-making ability of a human expert in a narrow domain, using a knowledge base of facts and rules, and an inference mechanism to reach conclusions and explain them. Examples: MYCIN (diagnosis of blood infections), DENDRAL, XCON.

Components and working.

1. Knowledge base: domain facts and heuristic rules (usually IF–THEN) acquired from experts.
2. Working memory: facts about the current case.
3. Inference engine: applies the rules to the facts to derive new facts and conclusions.
4. User interface: the user enters the problem and receives advice.
5. Explanation facility: tells the user how and why a conclusion was reached.
6. Knowledge acquisition module: lets the knowledge engineer add and update knowledge.

Working: the user supplies symptoms/data through the interface; they are stored in working memory; the inference engine matches them against the rules in the knowledge base, fires applicable rules, adds new facts, and repeats until a conclusion is reached; the result and explanation are presented to the user.

Role of the inference engine. It is the "brain" of the system. It:

• Matches the rule conditions with the facts in working memory.
• Resolves conflicts when several rules apply (conflict resolution by priority, specificity or recency).
• Executes the chosen rule and updates working memory.
• Controls the reasoning strategy: forward chaining (data-driven, from facts to conclusions) or backward chaining (goal-driven, from a hypothesis back to supporting facts).
• Handles uncertainty (certainty factors) and supports the explanation facility.

Semantic analysis. After parsing, semantic analysis maps the syntactic structure to a context-independent meaning representation, normally logic or a frame.

• Lexical semantics: pick the correct word sense (e.g. bank = river side or financial institution) using the dictionary and surrounding words.
• Compositional semantics: the meaning of the sentence is built from the meanings of its parts following the parse tree, e.g. "Ram eats rice" becomes $eats(Ram, rice)$.
• Case/thematic roles: identify agent, object, instrument.
• Selectional restrictions: reject meaningless combinations such as "The rice eats Ram".

Pragmatic analysis. It interprets the sentence in terms of the actual context, the speaker's intention and world knowledge, so that the real meaning is obtained.

• Reference resolution: resolving pronouns and references using previous discourse. "Ram took the book from the shelf and read it": it = the book.
• Speech acts / intention: "Can you pass the salt?" is a request, not a question about ability.
• Context and world knowledge: "It is cold here" may mean "close the window".
• Discourse structure: connecting sentences into a coherent whole.

Example: "I saw the man with a telescope." Syntax and semantics give two readings (I used a telescope; the man had a telescope), and pragmatics uses the context to select the intended one.

Semantic analysis therefore answers "what does the sentence literally mean", and pragmatic analysis answers "what does the speaker actually mean in this situation".

Artificial intelligence draws on many disciplines. Three of them contribute as follows.

Philosophy.

• Whether formal rules can draw valid conclusions: Aristotle's syllogisms and logic led to the formal logic used in knowledge representation and reasoning.
• How the mind arises from a physical brain (dualism vs materialism), and where knowledge comes from (rationalism, empiricism). Empiricism underlies machine learning.
• Raised the questions of whether machines can think (Turing, Searle's Chinese Room), free will, and the ethics of intelligent machines.
• Utilitarian ideas about how an agent should choose actions to maximise outcomes influence rational-agent design.

Sociology.

• Studies how intelligent behaviour emerges in groups, which inspired multi-agent systems, swarm intelligence and cooperation or negotiation between agents.
• Studies the social effects of AI: employment, privacy, bias and fairness, trust, and acceptance of automation.
• Shapes human–computer interaction, chatbots and social robots, and ethical and legal norms for AI.

Economics.

• Decision theory and utility theory: how to choose actions to maximise expected utility under uncertainty. This is the basis of rational agents.
• Game theory: how rational agents behave when other agents' actions affect their payoff (multi-agent decisions, auctions, negotiation).
• Operations research and Markov decision processes: sequential decision making, resource scheduling and optimisation.
• Economic motives (productivity, cost) drive AI investment and applications.

Together these fields provide the logic, decision-making models and social context that AI builds upon.

Posterior probability. The posterior probability $P(H\mid E)$ is the revised probability of a hypothesis $H$ after observing evidence $E$. It is computed from the prior $P(H)$ and the likelihood $P(E\mid H)$ by Bayes' theorem:

$P(H\mid E)=\frac{P(E\mid H)\,P(H)}{P(E)}$

Numerical. Let $D$ = the patient has liver disease and $A$ = the patient is alcoholic.

• $P(D)=0.15$ (prior)
• $P(A)=0.05$
• $P(A\mid D)=0.07$

Required: $P(D\mid A)$.

$P(D\mid A)=\frac{P(A\mid D)\,P(D)}{P(A)}=\frac{0.07\times0.15}{0.05}=\frac{0.0105}{0.05}=0.21$

The chance that an alcoholic patient has liver disease is 0.21 (21%), higher than the prior 15%.

Admissible heuristic. A heuristic $h(n)$ estimates the cost of the cheapest path from node $n$ to a goal. It is admissible if it never overestimates the true cost:

$0\le h(n)\le h^*(n)\quad\text{for every node }n,\qquad h(\text{goal})=0$

where $h^*(n)$ is the actual least cost from $n$ to the goal. With an admissible heuristic, A* (tree search) is optimal.

Example. For route finding between cities, the straight-line distance to the destination is admissible, because no road can be shorter than the straight line. In the 8-puzzle, the number of misplaced tiles $h_1$ and the sum of Manhattan distances of tiles from their goal positions $h_2$ are both admissible, since each move shifts one tile by one square, so at least $h_1$ (or $h_2$) moves are needed.

Hill climbing search. It is a local search that keeps only the current state and repeatedly moves to the best neighbouring state, with no memory of the path and no look-ahead beyond the neighbours.

Working mechanism (steepest-ascent):

1. Start with an initial state (current).
2. Generate all neighbours of current and evaluate them using the objective/heuristic function.
3. If the best neighbour is better than current, move to it and go to step 2.
4. Otherwise (no neighbour is better) stop and return current.

Variants: simple hill climbing (take the first better neighbour), steepest-ascent (take the best), stochastic hill climbing (random better neighbour), and random-restart hill climbing.

Limitations.

• Local maxima: a state better than all its neighbours but not the global best; the search gets stuck.
• Plateau (flat area): neighbours have equal value, so there is no direction in which to move, and the search may wander.
• Ridges: a sequence of local maxima that cannot be climbed with single-step moves; the search oscillates.
• Not complete and not optimal; the result depends on the starting state.
• No backtracking, so it cannot recover from a bad choice.

Remedies: random restarts, allowing sideways moves, simulated annealing, and stochastic hill climbing.

Defining a problem. A problem is formally defined by five components:

1. Initial state: where the agent starts, e.g. In(Kathmandu).
2. Actions: the set of actions available in each state, e.g. Go(Pokhara).
3. Transition model: the state that results from doing an action in a state, $RESULT(s,a)$.
4. Goal test: checks whether a state is a goal, e.g. In(Pokhara).
5. Path cost: a function assigning a numeric cost to each path (sum of step costs, e.g. distance).

A solution is a sequence of actions from the initial state to a goal state; an optimal solution has the lowest path cost. The initial state, actions and transition model together form the state space.

Criteria for defining a good problem.

• The initial state and the goal must be stated precisely.
• The formulation must contain the relevant detail only (abstraction), removing irrelevant details but keeping it valid and useful.
• Actions must be well defined and executable, with a clear transition model.
• The goal test must be checkable, and the path cost must express what is to be minimised.
• The abstract solution must be expandable into a real solution, and the state space of manageable size.

Constraint Satisfaction Problem (CSP) vs real-world problem.

Example of CSP (map colouring): variables are the regions (e.g. Western Australia, Northern Territory, Queensland, ...), the domain is {red, green, blue}, and the constraint is that adjacent regions have different colours. Any complete assignment that satisfies all constraints is a solution.

Example of a real-world problem (route finding): the states are locations, the actions are road segments, and the path cost is distance or time. The agent must search for the cheapest route from the source to the destination while handling traffic and other uncertainties.

Many real-world problems (timetabling, scheduling) can be modelled as CSPs, which allows the efficient CSP algorithms to be used.

Expert system. An expert system is an AI program that captures the specialised knowledge of human experts in a narrow domain and uses it, through an inference engine, to give advice or make decisions at the expert's level, with the ability to explain its reasoning.

Example: MYCIN. It diagnoses bacterial blood infections and recommends antibiotics. It uses about 500 IF–THEN rules with certainty factors, e.g. IF the stain of the organism is gram-positive AND its morphology is coccus THEN there is suggestive evidence (0.7) that the organism is staphylococcus. Other examples: DENDRAL (chemical structure), PROSPECTOR (mineral exploration), XCON (computer configuration).

Basic structure: knowledge base, inference engine, working memory, user interface, explanation facility and knowledge acquisition module.

Stages of expert system development.

1. Identification: define the problem, the scope and the goals; identify the domain expert, knowledge engineer, users and the resources needed.
2. Conceptualisation: the knowledge engineer works with the expert to find the key concepts, relations and the problem-solving strategy (knowledge acquisition by interviews, observation, documents).
3. Formalisation (design): map the concepts into a formal representation such as rules, frames or semantic networks; choose the inference strategy (forward or backward chaining) and the tools/shell (e.g. CLIPS, Prolog).
4. Implementation: program the knowledge base and inference engine, and build the user interface and explanation facility; produce a working prototype.
5. Testing (validation and verification): run the system on test cases, compare with the expert's results, find errors in rules, and refine.
6. Maintenance and deployment: install the system for users, train them, update the knowledge as the domain changes, and fix faults.

The process is iterative: the testing results frequently lead back to earlier stages to refine the knowledge, and the system grows by rapid prototyping.

Natural language processing proceeds through levels, and syntactic and semantic analysis are the two middle levels that turn a string of words into a structure and then into a meaning.

Syntactic analysis (parsing)

Syntactic analysis checks whether a sentence is well formed according to a grammar and assigns it a structure (parse tree). It is performed as follows.

1. Lexical analysis: the sentence is split into tokens and each word is looked up in a lexicon to get its part of speech (noun, verb, determiner, etc.).
2. Grammar: a context-free grammar (CFG) gives the rewrite rules, for example
   • $S \rightarrow NP\ VP$
   • $NP \rightarrow Det\ N$
   • $VP \rightarrow V\ NP$
   • $Det \rightarrow the,\ N \rightarrow boy \mid ball,\ V \rightarrow hit$
3. Parsing: a parser (top-down, bottom-up, chart parser, or ATN) applies the rules to build the tree.

For "The boy hit the ball" the parse is $S \rightarrow [NP\ [Det\ the]\ [N\ boy]]\ [VP\ [V\ hit]\ [NP\ [Det\ the]\ [N\ ball]]]$. A sentence like "Hit the the boy" fails to parse and is rejected. Ambiguous sentences ("I saw the man with a telescope") give more than one tree.

Semantic analysis

Semantic analysis finds the meaning of the syntactically correct sentence and represents it in a form the computer can use, independent of the surface wording.

1. Word meanings: each word is mapped to its sense in the lexicon, and word sense disambiguation chooses the right one ("bank" of a river or a money bank) using context.
2. Compositional semantics: the meaning of a phrase is built from the meanings of its parts, following the parse tree. Each grammar rule has an attached semantic rule, for example the verb phrase "hit the ball" becomes $\lambda x.\ Hit(x, Ball)$ and the whole sentence becomes $Hit(Boy, Ball)$.
3. Output representation: the result is a logical form such as predicate logic, a semantic network, or a frame.
4. Consistency checks: selectional restrictions reject sentences that are grammatical but meaningless ("Colourless green ideas sleep furiously", or "The table ate the boy").

Thus syntax decides whether the sentence is grammatical and gives its structure, and semantics uses that structure to produce a context-free meaning that later pragmatic analysis interprets in context.

Rational agent

An agent is anything that perceives its environment through sensors and acts on it through actuators. A rational agent is one that, for each possible percept sequence, selects the action that is expected to maximise its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge it has. Rationality depends on four things: the performance measure, the agent's prior knowledge of the environment, the actions it can perform, and the percept sequence to date. Rationality is not omniscience: it maximises expected, not actual, performance. For example, a vacuum-cleaner agent that cleans a dirty square and moves on when the square is clean is rational for a performance measure of "clean squares over time".

Utility-based agent versus model-based agent

So a model-based agent answers "what is the world like now?", whereas a utility-based agent additionally answers "how happy will I be in the state that results from this action?".

State space representation

State space representation formulates a problem as a search over a graph. It is defined by:

1. States: all possible configurations of the problem; the set of all of them is the state space.
2. Initial state: where the search starts.
3. Operators (actions): rules that move from one state to another.
4. Goal test: a condition that identifies the goal state(s).
5. Path cost: a cost for each step, so that the best solution is the cheapest path.

A solution is a path (sequence of operators) from the initial state to a goal state.

Example: water jug problem

There is a 4-litre jug and a 3-litre jug, with no measuring marks. Get exactly 2 litres in the 4-litre jug.

• State: $(x, y)$ with $x$ = litres in the 4-litre jug ($0 \le x \le 4$) and $y$ = litres in the 3-litre jug ($0 \le y \le 3$).
• Initial state: $(0, 0)$. Goal: $(2, y)$ for any $y$.
• Operators:
  • Fill the 4-litre jug: $(x,y) \rightarrow (4,y)$ if $x<4$.
  • Fill the 3-litre jug: $(x,y) \rightarrow (x,3)$ if $y<3$.
  • Empty either jug on the ground: $(x,y)\rightarrow(0,y)$ or $(x,0)$.
  • Pour the 3-litre jug into the 4-litre jug until the latter is full: $(x,y)\rightarrow(4,\,y-(4-x))$ if $x+y\ge 4$, $y>0$.
  • Pour the 4-litre jug into the 3-litre jug until the latter is full: $(x,y)\rightarrow(x-(3-y),\,3)$ if $x+y\ge 3$, $x>0$.
  • Pour everything from one jug into the other when it fits: $(x,y)\rightarrow(x+y,0)$ if $x+y\le 4$, $y>0$, or $(0,x+y)$ if $x+y\le 3$, $x>0$.

One solution path:

$(0,0)\rightarrow(0,3)\rightarrow(3,0)\rightarrow(3,3)\rightarrow(4,2)\rightarrow(0,2)\rightarrow(2,0)$

The steps are: fill the 3-litre jug; pour it into the 4-litre jug; fill the 3-litre jug again; pour into the 4-litre jug until full (leaving 2 litres in the 3-litre jug); empty the 4-litre jug; pour the 2 litres into the 4-litre jug. The 4-litre jug now holds 2 litres, so the goal is reached in 6 steps. Searching this graph with BFS, DFS or A* finds such paths.

Forward chaining

Forward chaining is a data-driven inference method. It starts from the known facts in the knowledge base, repeatedly finds rules whose premises (antecedents) are all satisfied, fires them to add their conclusions as new facts, and continues until the goal (query) is derived or no new facts can be added. It uses Generalised Modus Ponens on definite clauses.

Algorithm

1. Put all known facts in working memory.
2. Find every rule whose premises all match facts in working memory.
3. Fire a rule (using conflict resolution if several match) and add its conclusion if it is new.
4. If the query is now in working memory, stop with success. If no rule can add a new fact, stop with failure. Otherwise go to step 2.

Example

Rules:

• R1: $Missile(x) \rightarrow Weapon(x)$
• R2: $Enemy(x, America) \rightarrow Hostile(x)$
• R3: $Missile(x) \wedge Owns(Nono, x) \rightarrow Sells(West, x, Nono)$
• R4: $American(p) \wedge Weapon(q) \wedge Sells(p,q,r) \wedge Hostile(r) \rightarrow Criminal(p)$

Facts: $American(West)$, $Missile(M1)$, $Owns(Nono, M1)$, $Enemy(Nono, America)$.

Query: $Criminal(West)$?

• Pass 1: R1 fires with $x=M1$, adding $Weapon(M1)$; R2 fires with $x=Nono$, adding $Hostile(Nono)$; R3 fires with $x=M1$, adding $Sells(West, M1, Nono)$.
• Pass 2: R4 now has all premises with $p=West$, $q=M1$, $r=Nono$, so $Criminal(West)$ is added.

The query is in working memory, so West is a criminal. Forward chaining is sound and complete for definite clauses, but it may derive many facts irrelevant to the query.

(a) All animals who can bark are dogs.

$\forall x\ (Animal(x) \wedge CanBark(x) \rightarrow Dog(x))$

(b) Someone is firing a gun.

$\exists x\ (Person(x) \wedge Firing(x, Gun))$

(or, treating the gun as an object, $\exists x\,\exists g\,(Person(x) \wedge Gun(g) \wedge Fires(x, g))$).

(c) All tigers are not fierce.

$\forall x\ (Tiger(x) \rightarrow \neg Fierce(x))$

This says that no tiger is fierce. (The alternative reading, "not all tigers are fierce", would be $\neg\forall x\,(Tiger(x)\rightarrow Fierce(x))$, which is equivalent to $\exists x\,(Tiger(x)\wedge\neg Fierce(x))$; the usual intended meaning is the first.)

Game

In AI, a game is a competitive multi-agent environment in which the agents' goals conflict, so each agent must consider the opponent's possible replies. Games such as chess, tic-tac-toe and checkers are usually deterministic, turn-taking, two-player, zero-sum games of perfect information. A game is defined by the initial state, the players, the legal moves (actions), the result of a move, a terminal test (win, lose, draw) and a utility function giving the final payoff. Games are solved with adversarial search such as minimax with alpha-beta pruning.

Depth-limited search

Depth-limited search is depth-first search with a predefined depth limit $l$: nodes at depth $l$ are treated as if they had no successors. In games the cut-off nodes are evaluated with a heuristic evaluation function instead of the true terminal utility.

Benefits

• It needs little memory, only $O(bl)$ space, like DFS.
• It always terminates, because the depth is bounded, so it avoids the infinite-path problem of plain DFS.
• It is fast and gives an answer within time limits, which is essential in large games where the full tree is far too big (chess has about $10^{40}$ positions).
• If the depth of the goal is known, it finds the goal efficiently.

Limitations

• It is incomplete if the goal lies deeper than $l$ ($l<d$).
• It is not optimal if $l>d$, because a deeper, costlier solution may be found first.
• Choosing a good limit is hard without knowing the depth of the solution.
• In games, the result depends on the quality of the evaluation function, and the horizon effect can cause bad moves because a disaster just beyond the limit is not seen.
• Time is still $O(b^l)$, exponential in the limit.

Fuzzy logic

Fuzzy logic is a form of many-valued logic, introduced by Lotfi Zadeh, in which the truth of a statement is a degree between 0 and 1 rather than only true or false. It models vagueness such as "hot", "tall" or "high speed". A fuzzy set $A$ has a membership function $\mu_A(x)\in[0,1]$. For example, a temperature of 35 °C may belong to the set "hot" with $\mu = 0.7$. A fuzzy system has four steps: fuzzification (crisp input to membership degrees), rule evaluation using IF-THEN rules, aggregation of the rule outputs, and defuzzification (for example the centroid) to a crisp output. The standard fuzzy operators are:

• Union: $\mu_{A\cup B}(x)=\max(\mu_A(x),\mu_B(x))$
• Intersection: $\mu_{A\cap B}(x)=\min(\mu_A(x),\mu_B(x))$
• Complement: $\mu_{\bar A}(x)=1-\mu_A(x)$

Operators of a genetic algorithm

A genetic algorithm evolves a population of candidate solutions (chromosomes) by repeatedly applying three operators, guided by a fitness function.

1. Selection (reproduction): fitter chromosomes are chosen as parents with higher probability, using roulette-wheel selection, tournament selection or rank selection. This passes good traits to the next generation.
2. Crossover (recombination): two parents exchange parts of their strings to produce offspring. In single-point crossover at point 3, parents $101|10$ and $010|01$ give children $10101$ and $01010$. Variants are two-point and uniform crossover. It is applied with a high probability (about 0.6 to 0.9).
3. Mutation: randomly flips bits (or changes genes) with a small probability, for example $10110\rightarrow10010$. It maintains diversity and prevents premature convergence to a local optimum.

The cycle of selection, crossover and mutation is repeated until a stopping condition (maximum generations or acceptable fitness) is reached.

Reinforcement learning: example

In reinforcement learning an agent learns by interacting with an environment, receiving rewards or penalties for its actions, and learning a policy that maximises the cumulative reward. There is no labelled training data.

Example: a robot learning to escape a maze. At each cell (state) it chooses to move up, down, left or right (action). It receives $-1$ per step, $-10$ for hitting a wall and $+100$ for reaching the exit. After many trials, using an algorithm such as Q-learning, $Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma\max_{a'}Q(s',a')-Q(s,a)]$, it learns the shortest route. Other examples are a chess program (AlphaGo) learning from wins and losses, and a self-driving car learning to drive.

Types of artificial neural networks

1. Single-layer feedforward network (perceptron): the inputs connect directly to the output neurons. It can solve only linearly separable problems.
2. Multilayer feedforward network (MLP): one or more hidden layers between input and output; signals flow in one direction, and it is trained by backpropagation. It can learn non-linear functions.
3. Recurrent network: has feedback connections, so the output depends on past states. It is used for sequences such as speech, text and time series (Elman, Hopfield networks, LSTM).
4. Convolutional neural network (CNN): uses convolution and pooling layers, mainly for image recognition.
5. Self-organising map (Kohonen network): unsupervised, maps high-dimensional input to a low-dimensional grid by competitive learning.
6. Radial basis function network: uses radial basis functions as activation in the hidden layer, for function approximation and classification.

(a) Pragmatic analysis

Pragmatic analysis is the last level of natural language understanding. It interprets the meaning of a sentence in its real context: the situation, the speaker's intention, the previous discourse and world knowledge. Semantic analysis gives literal meaning; pragmatics gives the intended meaning. For example, "Can you pass the salt?" is literally a question about ability but pragmatically a request; "It is cold here" may mean "please close the window". Pragmatic analysis also resolves references ("He" in "Ram told Hari that he was late"), understands indirect speech acts, handles irony and presupposition, and applies discourse knowledge from earlier sentences. It is done with context models, discourse structure, and a knowledge base about the speaker, the listener and the world.

(b) Unification and lifting

Unification is the process of finding a substitution $\theta$ that makes two logical expressions identical. $UNIFY(p,q)=\theta$ such that $SUBST(\theta,p)=SUBST(\theta,q)$. For example:

• $Knows(John,x)$ and $Knows(John,Jane)$ unify with $\theta=\{x/Jane\}$.
• $Knows(John,x)$ and $Knows(y,Mother(y))$ unify with $\theta=\{y/John,\ x/Mother(John)\}$.
• $Knows(John,x)$ and $Knows(x,Jane)$ fail without standardising apart (variables renamed), because $x$ cannot be both $John$ and $Jane$.

The algorithm returns the most general unifier (MGU), and uses an occurs check to prevent $x$ from unifying with $f(x)$.

Lifting means applying inference rules directly at the level of first-order expressions with variables, rather than first converting to propositional logic by instantiating all variables. Generalised Modus Ponens is a lifted rule: from $p_1',\dots,p_n'$ and $(p_1\wedge\dots\wedge p_n\rightarrow q)$ with $SUBST(\theta,p_i')=SUBST(\theta,p_i)$, infer $SUBST(\theta,q)$. Lifting is much more efficient, because it uses only the substitutions that are needed, and unification is the tool that makes it possible.

(c) Turing test

Proposed by Alan Turing in 1950 ("Computing Machinery and Intelligence") as an operational definition of intelligence. A human interrogator asks written questions to two hidden parties, a human and a computer. If after the conversation the interrogator cannot reliably tell which is the machine, the machine is said to have passed and to be intelligent. To pass, the computer needs natural language processing, knowledge representation, automated reasoning and machine learning. The total Turing test adds a video signal and objects to pass through the hatch, which also requires computer vision and robotics. Criticism includes Searle's Chinese Room argument that imitating behaviour is not understanding.

State representation

Write a state as the cell of tile 1 and the cell of tile 2, using TL, TR (top row) and BL, BR (bottom row). The two blank cells are implied. A move slides a tile into an adjacent empty cell (left, right, up or down). Two tiles on four cells give $4\times3=12$ states, labelled:

The heuristic $h(n)$ is the number of misplaced tiles compared with the goal (tile 1 should be in TR, tile 2 in BL). Every move costs 1.

State space graph (edges, all moves reversible)

• A: B, C
• B: A, D, E, F
• C: A, F, G, J
• D: B, K
• E: B, K
• F: B, C
• G: C, L
• H: K, L
• I: K, L
• J: C, L
• K: D, E, H, I
• L: G, H, I, J

Greedy best-first search (always expand the open node with the smallest $h$; ties broken alphabetically; visited states are not re-opened)

Greedy best-first search finds the goal L. The solution path, following parent links, is

$A \rightarrow C \rightarrow G \rightarrow L$

that is: move tile 2 down, move tile 2 left, move tile 1 right, at a path cost of 3. This is also optimal here, since each tile must move at least once and tile 2 needs two moves. The search used only $h$ to choose nodes, so it is not guaranteed to be optimal in general, but it finds the goal in this puzzle.