Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

Module 3

PROBLEM-SOLVING

INFORMED SEARCH STRATEGIES

❖ Informed search strategy is one that uses problem-specific knowledge beyond the
definition of the problem itself can find solutions more efficiently than can an
uninformed strategy. The general approach we consider is called best-first search.

❖ Best-first search is an instance of the general algorithm in which a node is selected

for expansion based on an evaluation function, f(n).

❖ The evaluation function is construed as a cost estimate, so the node with the lowest
evaluation is expanded first.

❖ The implementation of best-first graph search is identical to that for uniform-cost

search except for the use of f instead of g to order the priority queue.

❖ The choice of f determines the search strategy. Most best-first algorithms include as a
component of a heuristic function, denoted h(n): h(n) = estimated cost of the cheapest
path from the state at node n to a goal state.

✓ A search strategy that uses problem-specific knowledge can find solutions more efficiently

than an uninformed strategy.

✓ We use best-first search as general approach. A node is selected for expansion based on an

evaluation function f(n).

✓ Informed search algorithms include a heuristic function h(n) as part of f(n).

✓ Often f(n) = g(n) + h(n)

✓ h(n) = estimate of the cheapest cost from the state at node n to a goal state; h(goal) = 0.

1|Page
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

Greedy best-first search

• Greedy best-first search is a form of best-first search that expands first the node with
the Greedy best-first Search lowest h(n) value the node that appears to be closest to the
goal on the grounds that this is likely to lead to a solution quickly.

• So, the evaluation function f (n) = h(n).

• Let us see how this works for route finding problems in Romania; we use the straight
line distance heuristic, which we will call hSLD.

• If the goal is Bucharest, we need to know Straight-line distance the straight-line

distances to Bucharest, which are shown in Figure 3.22. For example,
hSLD(Arad)=366. Notice that the values of hSLD cannot be computed from the
problem description itself (that is, the ACTIONS and RESULT functions).

• Moreover, it takes a certain amount of world knowledge to know that hSLD is

correlated with actual road distances and is, therefore, a useful heuristic.

• Figure 3.23 shows the progress of a greedy best-first search using hSLD to find a path
from Arad to Bucharest.

• The first node to be expanded from Arad will be Sibiu because the heuristic says it is
closer to Bucharest than is either Zerind or Timisoara.

• The next node to be expanded will be Fagaras because it is now closest according to
the heuristic.

• Fagaras in turn generates Bucharest, which is the goal.

• For this particular problem, greedy best-first search using hSLD finds a solution without
ever expanding a node that is not on the solution path. The solution it found does not
have optimal cost, however: the path via Sibiu and Fagaras to Bucharest is 32 miles
longer than the path through Rimnicu Vilcea and Pitesti.
2|Page
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• This is why the algorithm is called “greedy”—on each

3|Page
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)
• iteration it tries to get as close to a goal as it can, but greediness can lead to worse results
than being careful.

• Greedy best-first graph search is complete in finite state spaces, but not in infinite ones.

• The worst-case time and space complexity is O(|V|).

• With a good heuristic function, however, the complexity can be reduced substantially,
on certain problems reaching O(bm).
A* search: Minimizing the total estimated solution cost

Conditions for optimality: Admissibility and consistency- Optimality of A*

In order for A* to be optimal

• h(n) must be admissible, i.e. it never overestimates the cost to reach the goal.

• Then, as a consequence, f(n) = g(n) + h(n) never overestimates the true cost of a

4|Page
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

solution along the current path through n.

• h(n) must be consistent (monotonic) in graph search, i.e. for every node n and every

successor n’ of n generated by action a, This is a form of the triangle inequality.

• Every consistent heuristic is also admissible.

• The graph-search version of A* is optimal if h(n) is consistent. We show this in 2 steps:

• If h(n) is consistent, then the values of f(n) along any path are nondecreasing Optimality
of A* (Graph Search) nondecreasing.

• Whenever A* selects a node n for expansion, the optimal path to that node has been
found. otherwise there must be another frontier node n’ on the optimal path from start
node to n; as f is nondecreasing along any path, n’ would have lower f-cost than n and
would have been selected first.

5|Page
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

6|Page
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

Contours in State Space:

• As f-costs are nondecreasing along any path we can draw contours in the state space.

• See figure 3.25 on the following page

• With uniform-cost search (A* with h(n) = 0), contours are circular around the start state.

• With more accurate heuristics, the bands will stretch towards the goal state and become more

narrow

• If C* is the cost of the optimal solution path, then

• A* expands all nodes with f(n) < C*

• A* may expand some nodes with f(n) = C* before finding the goal state.

7|Page
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• Completeness requires that there are only finitely many nodes with cost less than or equal

to C*, which is true if all step costs exceed some finite ε and if b is finite.

A* is Optimally Efficient

• A* is optimally efficient for any given consistent heuristic, i.e. no other optimal

algorithm is guaranteed to expand fewer nodes than A* (except possibly for

nodes with f(n) = C*).

8|Page
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• This is because any algorithm that does not expand all nodes with f(n) < C* may

miss the optimal solution.

• So A* is complete, optimal and optimally efficient, but it still is not the solution

to all search problems:

• As A* keeps all generated solutions in memory it runs out of space long before it runs out of

time.

Memory-bounded Heuristic Search

How to reduce memory requirements of A*?

• Use iterative deepening A* (IDA*) .

• Cutoff used is f(n) = g(n) + h(n) rather than the depth.

• At each iteration, the cutoff value is the smallest f-cost of any node that exceeded

the cutoff on the previous iteration.

• This works well with unit step costs.

• It suffers from severe problems with real-valued costs.

Recursive Best-First Search (RBFS)

• Simple recursive algorithm that tries to mimic the operation of standard best-first search in
linear space .

• It is similar to recursive DFS, but uses a variable f_limit to keep track of the best alternative
path available from any ancestor of the current node.

• If the current node exceeds f_limit, the recursion unwinds back to the alternative path.
Then, RBFS replaces the f-value of each node on the path with a backed-up value, the best
value of its children.

• In this way, RBFS remembers the f-value of the best leaf in the forgotten subtree and may
decide to re- expand it later.

9|Page
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

Simplified Memory-bounded A* (SMA*)

• IDA* and RBFS use too little memory

• IDA* retains only 1 number between iterations (f-cost limit)

• RBFS retains more information, but uses only linear space

• SMA* proceeds just like A*, expanding the best leaf until memory is full. Then it must drop
an old node.

• SMA* always drops the worst leaf node (highest f value). (In case of ties with same f-value,
SMA* expands the newest leaf and deletes the oldest leaf).

10 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)
• Like RBFS, SMA* then backs up the value of the forgotten node to its parent. In this way
the ancestor of a forgotten subtree knows the quality of the best path in that subtree.

Heuristic Functions

• The 8-puzzle was one of the earliest heuristic search problems.

• As mentioned in Section 3.2, the object of the puzzle is to slide the tiles horizontally or
vertically into the empty space until the configuration matches the goal configuration
(Figure 3.28).

• The average solution cost for a randomly generated 8-puzzle instance is about 22 steps.

• The branching factor is about 3. (When the empty tile is in the middle, four moves are
possible; when it is in a corner, two; and when it is along an edge, three.)

• This means that an exhaustive tree search to depth 22 would look at about 322 ≈
3.1×1010 states.

• A graph search would cut this down by a factor of about 170,000 because only 9!/2 =181,
440 distinct states are reachable.

• (See Exercise 3.4.) This is a manageable number, but the corresponding number for the
15- puzzle is roughly 1013, so the next order of business is to find a good heuristic
function.

• If we want to find the shortest solutions by using A∗, we need a heuristic function that
never overestimates the number of steps to the goal.

• There is a long history of such heuristics for the 15-puzzle; here are two commonly
used candidates:

• h1 = the number of misplaced tiles. For Figure 3.28, all of the eight tiles are out of
position, so the start state would have h1 = 8.

• h1 is an admissible heuristic because it is clear that any tile that is out of place must be
moved at least once.
11 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• h2 = the sum of the distances of the tiles from their goal positions.

• Because tiles cannot move along diagonals, the distance we will count is the sum of the
horizontal and vertical distances. This is sometimes called the city block distance or
Manhattan distance.

• h2 is also admissible because all any move can do is move one tile one step closer to
the goal.
• Tiles 1 to 8 in the start state give a Manhattan distance of
• h2 = 3+1 + 2 + 2+ 2 + 3+ 3 + 2 = 18 .
• As expected, neither of these overestimates the true solution cost, which is 26.

Heuristic Functions:

The quality of any heuristic search algorithm depends on its heuristic

• Two admissible heuristics for the 8-puzzle:

• h1 = # misplaced tiles

12 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)
• h2 = sum of Manhattan dist. of all tiles to goal position

• h2 is better for search than h1.

• The effective branching factor b* may characterize the quality of a heuristics:

• If N is the # nodes generated by a search algorithm and d is the solution depth, then b* ist

the branching factor, which a uniform tree of depth d would need to have to contain N+1
nodes.

• The performance of heuristic search algorithms depends on the quality of their heuristic

function.

• Methods to construct good heuristics are: relaxing the problem definition, using a

pattern DB with precomputed solution costs, or automated learning from experience.

KNOWLEDGE-BASED AGENTS

Logical agents are always definite. each proposition is either true/false or unknown
(agnostic). Knowledge representation language - a language used to express knowledge
about the world.
• Declarative approach - language is designed to be able to easily express
knowledge for the world the language is being implemented for.
• Procedural approach - encodes desired behaviours directly in program code.
• Sentence - a statement expressing a truth about the world in the knowledge
representation language

Knowledge Base (KB) - a set of sentences describing the world

• Background knowledge - initial knowledge in KB

• Knowledge level -we only need to specify what the agent knows and what its goals
are in order to specify its behaviour
• Tell(P) - function that adds knowledge P to the KB

13 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• Ask(P) - function that queries the agent about the truth of P.

• Inference -the process of deriving new sentences from the knowledge base
✓ When the agent draws a conclusion from available information, it is

guaranteed to be correct if the available information is correct.

THE WUMPUS WORLD

K

14 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

The wumpus world is a cave consisting of rooms connected by passageways.

Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters
its room.
The wumpus can be shot by an agent, but the agent has only one arrow.
Some rooms contain bottomless pits that will trap anyone who wanders into these rooms
(except for the wumpus, which is too big to fall in).
The only mitigating feature of this bleak environment is the possibility of finding a heap of
gold.
Although the wumpus world is rather than by modern computer game standards, it illustrates
some important points about intelligence.
A sample wumpus world is shown in Figure 7.2. The precise definition of the task environment
is given, as suggested in Section 2.3, by the PEAS description:
Performance measure:
▪ +1000 for climbing out of the cave with the gold, –1000 for falling into a
pit or being eaten by the wumpus,
▪ –1 for each action taken and
▪ –10 for using up the arrow.
▪ The game ends either when the agent dies or when the agent climbs out of
the cave.
Environment:
▪ A 4×4 grid of rooms. The agent always starts in the square labelled [1,1],
facing to the right.
▪ The locations of the gold and the wumpus are chosen randomly, with a
uniform distribution, from the squares other than the start square. In
addition, each square other than the start can be a pit, with probability 0.2.
▪ Squares adjacent to wumpus are smelly.

15 | P a g e
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

▪ Squares adjacent to pit are breezy.

▪ Glitter iff gold is in the same square.
▪ Shooting kills wumpus if you are facing it.
▪ Shooting uses up the only arrow.
▪ Grabbing picks up gold if in same square.
▪ Releasing drops the gold in same square.

Actuators:
▪ Turn Left (90°),
▪ Turn Right (90°),
▪ Forward,
▪ Grab (gold),
▪ Shoot (arrow),
▪ Climb (at 1,1)
Sensors:
▪ The agent has five sensors, each of which gives a single bit of information
▪ In the square containing the wumpus and in the directly (not diagonally)
adjacent squares, the agent will perceive a Stench.
▪ In the squares directly adjacent to a pit, the agent will perceive a Breeze.
▪ In the square where the gold is, the agent will perceive a Glitter.
▪ When an agent walks into a wall, it will perceive a Bump.
▪ When the wumpus is killed, it emits a woeful Scream that can be
perceived anywhere in the cave.
▪ Stench, Breeze, Glitter, Bump, Scream.
• Observable? No . only local perception
• Deterministic? Yes . outcomes exactly specified
• Episodic? No . sequential at the level of actions
• Static? Yes . Wumpus and Pits do not move
16 | P a g e
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• Discrete? Yes
• Single-agent? Yes . Wumpus is essentially a natural feature.

17 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)
LOGIC

Logics - formal languages for representing information such that conclusions can be drawn

▪ Syntax -description of a representative language in terms of well-formed sentences of the

language
▪ Semantics -defines the meaning (truth) of a sentence in the representative
language w.r.t. each possible world
▪ Model - the world being described by a KB
▪ Satisfaction - model m satisfies a sentence α, if α is true in m.
▪ Entailment - the concept that a sentence follows from another sentence:
• α ╞ β if α is true then β must also be true
▪ Logical inference - the process of using entailment to derive conclusions
▪ Model checking - enumeration of all possible models to ensure that a sentence α
is true in all models in which KB is true
▪ M(α) is the set of all models of α.
▪ Using the notation just introduced, we can write

18 | P a g e
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

• The KB is false in models that contradict what the agent knows— for example, the KB
is false in any model in which [1,2] contains a pit, because there is no breeze in [1,1].
• There are in fact just three models in which the KB is true, and these are shown
surrounded by a solid line in Figure 7.5. Now let us consider two possible conclusions.

19 | P a g e
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)
• If KB is true in the real world then any sentence α derived from KB by a sound inference
procedure is also true in the real world.
• So, while an inference process operates on “syntax”—internal physical configurations
such as bits in registers or patterns of electrical blips in brains—the process
corresponds to the real-world relationship whereby some aspect of the real world is the
case6 by virtue of other aspects of the real world being the case.
• This correspondence between world and representation is illustrated in Figure 7.6.

20 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

PROPOSITIONAL LOGIC: A VERY SIMPLE LOGIC

21 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)
Syntax

Semantics

22 | P a g e
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

23 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

A simple knowledge base

Now that we have defined the semantics for propositional logic, we can construct a knowledge
base for the wumpus world. We focus first on the immutable aspects of the wumpus world,
leaving the mutable aspects for a later section. For now, we need the following symbols for
each [x, y] location:

24 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

A simple inference procedure

❖ Models are assignments of true or false to every proposition symbol. Returning to our
wumpus-world example, the relevant proposition symbols are B1,1, B2,1, P1,1, P1,2,
P2,1, P2,2, and P3,1.
❖ With seven symbols, there are 27 =128 possible models; in three of these, KB is true
(Figure 7.9). In those three models, ￢P1,2 is true, hence there is no pit in [1,2].
❖ On the other hand, P2,2 is true in two of the three models and false in one, so we cannot
yet tell whether there is a pit in [2,2]. Figure 7.9 reproduces in a more precise form the
reasoning illustrated in Figure 7.5.
❖ A general algorithm for deciding entailment in propositional logic is shown in Figure
7.10. Like the BACKTRACKING-SEARCH algorithm on page 215, TT- ENTAILS?
performs a recursive enumeration of a finite space of assignments to symbols.
❖ The algorithm is sound because it implements directly the definition of entailment, and
complete because it works for any KB and α and always terminates—there are only
finitely many models to examine.

25 | P a g e
 Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

Of course, “finitely many” is not always the same as “few.” If KB and α contain n symbols in
all, then there are 2n models. Thus, the time complexity of the algorithm is O(2n). (The space
complexity is only O(n) because the enumeration is depth-first.)

26 | P a g e
Artificial Intelligence-BCS515B Akash Karna(CSE,AIT)

60% of portions are over

27 | P a g e