Module 3

3.5 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 efficientlythan 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.

3.5.1 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. This is why
the algorithm is called “greedy”—on each 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).
3.5.2 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 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:

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

[Link] 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.
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.
• 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*).
• 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.

3.5.3 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.
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 fvalue). (In case of ties with same f-value, SMA* expands
the newest leaf and deletes the oldest leaf)
• 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.

3.6 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.
• 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
• 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. Thus

• 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.
7.1 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
• 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.

7.2 THE WUMPUS WORLD

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
tame 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
▪ 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
• Discrete? Yes
• Single-agent? Yes . Wumpus is essentially a natural feature.
7.3 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 satifies 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

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.
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.
7.4 PROPOSITIONAL LOGIC: A VERY SIMPLE LOGIC

7.4.1 Syntax
7.4.2 Semantics
7.4.3 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:

7.4.4 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.
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.)