3 | Searching for solutions

Question 1

What is heuristic knowledge?

Answer 1

The difficulty of search and the fact that humans are able to solve some search problems efficiently suggests that computer agents should exploit knowledge about special cases to guide them to a solution. This extra knowledge beyond the search space is called heuristic knowledge.

Question 2

What is a state space?

Answer 2

One general formulation of intelligent action is in terms of a state space. A state contains all of the information necessary to predict the effects of an action and to determine whether a state satisfies the goal. State-space searching assumes:

• The agent has perfect knowledge of the state space and is planning for the case where it observes what state it is in: there is full observability.
• The agent has a set of actions that have known deterministic effects.
• The agent can determine whether a state satisfies the goal.

Question 3

What is a solution?

Answer 3

A solution is a sequence of actions that will get the agent from its current state to a state that satisfies the goal.

Question 4

What does a state-space problem consists of?

Answer 4

• a set of states
• a distinguished state called the start state
• for each state, a set of actions available to the agent in that state
• an action function that, given a state and an action, returns a new state
• a goal specified as a Boolean function, goal(s), that is true when state s satisfies the goal, in which case we say that s is a goal state
• a criterion that specifies the quality of an acceptable solution. For example, any sequence of actions that gets the agent to the goal state may be acceptable, or there may be costs associated with actions and the agent may be required to find a sequence that has minimal total cost. A solution that is best according to some criterion is called an optimal solution. We do not always need an optimal solution, for example, we may be satisfied with any solution that is within 10% of optimal.

Question 5

What does a directed graph consist of?

Answer 5

a set N of nodes and a set A of arcs, where an arc is an ordered pair of nodes.

Question 6

What is a cycle (in terms of graphs)?

Answer 6

A cycle is a nonempty path where the end node is the same as the start node

Question 7

What is a directed graph without any cycles called?

Answer 7

directed acyclic graph (DAG)

Question 8

What is the forward branching factor (in terms of graphs)?

Answer 8

the number of outgoing arcs from the node.

Question 9

What is the backward branching factor (in terms of graphs)?

Answer 9

the number of incoming arcs to the node.

Question 10

What is the concept of the generic search algorithm?

Answer 10

The intuitive idea behind the generic search algorithm, given a graph, a start node, and a goal predicate, is to explore paths incrementally from the start node. This is done by maintaining a frontier (or fringe) of paths from the start node. The frontier contains all of the paths that could form initial segments of paths from the start node to a goal node. (See Figure 3.3, where the frontier is the set of paths to the gray shaded nodes.) Initially, the frontier contains the trivial path containing just the start node, and no arcs. As the search proceeds, the frontier expands into the unexplored nodes until a goal node is encountered.

Question 11

What is the breadth-first search algorithm?

Answer 11

In breadth-first search the frontier is implemented as a FIFO (first-in, first-out) queue. Thus, the path that is selected from the frontier is the one that was added earliest.

This approach implies that the paths from the start node are generated in order of the number of arcs in the path. One of the paths with the fewest arcs is selected at each iteration.

Question 12

When is the breadth-first search algorithm useful?

Answer 12

the problem is small enough so that space is not a problem (e.g., if you already need to store the graph) and you want a solution containing the fewest arcs.

Question 13

What is the depth-first search algorithm?

Answer 13

In depth-first search, the frontier acts like a LIFO (last-in, first-out) stack of paths. In a stack, elements are added and removed from the top of the stack. Using a stack means that the path selected and removed from the frontier at any time is the last path that was added.

Question 14

When is the depth-first search algorithm useful?

Answer 14

space is restricted

many solutions exist, perhaps with long paths, particularly for the case where nearly all paths lead to a solution or

the order in which the neighbors of a node are added to the stack can be tuned so that solutions are found on the first try.

Question 15

When is the depth-first search algorithm a poor method?

Answer 15

it is possible to get caught in infinite paths, which occurs when the graph is infinite or when there are cycles in the graph

solutions exist at shallow depth, because in this case the search may explore many long paths before finding the short solutions, or

there are multiple paths to a node, for example, on a n×n
grid, where all arcs go right or down, there are exponentially paths from the top-left node, but only n2 nodes.

Question 16

What is iterative deepening?

Answer 16

One way to combine the space efficiency of depth-first search with the optimality of breadth-first search is to use iterative deepening. The idea is to recompute the elements of the breadth-first frontier rather than storing them. Each recomputation can be a depth-first search, which thus uses less space.

Iterative deepening repeatedly calls a depth-bounded searcher, a depth-first searcher that takes in an integer depth bound and never explores paths with more arcs than this depth bound. Iterative deepening first does a depth-first search to depth 1 by building paths of length 1 in a depth-first manner. If that does not find a solution, it can build paths to depth 2, then depth 3, and so on until a solution is found. When a search with depth-bound n
fails to find a solution, it can throw away all of the previous computation and start again with a depth-bound of n+1. Eventually, it will find a solution if one exists, and, as it is enumerating paths in order of the number of arcs, a path with the fewest arcs will always be found first.

Question 17

What is lowest-cost-first search?

Answer 17

The simplest search method that is guaranteed to find a minimum cost path is lowest-cost-first search, which is similar to breadth-first search, but instead of expanding a path with the fewest number of arcs, it selects a path with the lowest cost. This is implemented by treating the frontier as a priority queue ordered by the cost function.

Question 18

What is a heuristic function h(c)?

Answer 18

A heuristic function h(n), takes a node n and returns a non-negative real number that is an estimate of the cost of the least-cost path from node n to a goal node. The function h(n) is an admissible heuristic if h(n) is always less than or equal to the actual cost of a lowest-cost path from node n to a goal.

Question 19

What is heuristic depth-first search

Answer 19

A simple use of a heuristic function in depth-first search is to order the neighbors that are added to the stack representing the frontier. The neighbors can be added to the frontier so that the best neighbor is selected first. This is known as heuristic depth-first search. This search selects the locally best path, but it explores all paths from the selected path before it selects another path. Although it is often used, it suffers from the problems of depth-first search, and is not guaranteed to find a solution and may not find an optimal solution.

Question 20

What is a greedy best-first search?

Answer 20

Another way to use a heuristic function is to always select a path on the frontier with the lowest heuristic value. This is called greedy best-first search. This method sometimes works well. However, it can follow paths that look promising because they appear (according to the heuristic function) close to the goal, but the path explored may keep getting longer.

Question 21

What is A* search?

Answer 21

A∗ search uses both path cost, as in lowest-cost-first, and heuristic information, as in greedy best-first search, in its selection of which path to expand. For each path on the frontier, A∗ uses an estimate of the total path cost from the start node to a goal node constrained to follow that path initially. It uses cost(p), the cost of the path found, as well as the heuristic function h(p), the estimated path cost from the end of p to the goal.

Question 22

What is iterative deepening A* search?

Answer 22

Iterative Deepening A∗ (IDA∗) performs repeated depth-bounded depth-first searches. Instead of the bound being on the number of arcs in the path, it is a bound on the value of f(n). The threshold is initially the value of f(s), where s is the start node. IDA∗ then carries out a depth-first depth-bounded search but never expands a path with a higher f-value than the current bound. If the depth-bounded search fails and the bound was reached, the next bound is the minimum of the f-values that exceeded the previous bound. IDA∗ thus checks the same nodes as A∗, perhaps breaking ties differently, but recomputes them with a depth-first search instead of storing them.

Question 23

What is an admissible heuristic?

Answer 23

a non-negative function h of nodes, where h(n) is never greater than the actual cost of the shortest path from node n to a goal.

Question 24

What is cycle pruning?

Answer 24

A simple method of pruning the search, while guaranteeing that a solution will be found in a finite graph, is to ensure that the algorithm does not consider neighbors that are already on the path from the start. Cycle pruning or loop pruning checks whether the last node on the path already appears earlier on the path from the start node to that node.

Question 25

What is multiple-path pruning?

Answer 25

Multiple-path pruning is implemented by maintaining an explored set (traditionally called closed list) of nodes that are at the end of paths that have been expanded. The explored set is initially empty. When a path ⟨n0,…,nk⟩ is selected, if nk is already in the explored set, the path can be discarded. Otherwise, nk is added to the explored set, and the algorithm proceeds as before.

Question 26

What is Depth-first branch-and-bound search?

Answer 26

The idea of a branch-and-bound search is to maintain the lowest-cost path to a goal found so far, and its cost. Suppose this cost is bound. If the search encounters a path p such that cost(p)+h(p)≥bound, path p can be pruned. If a non-pruned path to a goal is found, it must be better than the previous best path. This new solution is remembered and bound is set to the cost of this new solution. The searcher then proceeds to search for a better solution.

Branch-and-bound search generates a sequence of ever-improving solutions. The final solution found is the optimal solution.

Question 27

What is backward and forward search

Answer 27

• In backward search, the frontier starts with a node labeled goal. The neighbours of goal are the goal nodes {n:goal(n)}. The neighbours of the other nodes are given in the in the inverse graph. The search stops when it
finds the start node. Once goal is expanded, the frontier contains all of the goal nodes.

• Forward search searches from the start node to the goal nodes in the original graph.

Question 28

What is dynamic programming?

Answer 28

Dynamic programming is a general method for optimization that involves computing and storing partial solutions to problems. Solutions that have already been found can be retrieved rather than being recomputed. Dynamic programming algorithms are used throughout AI and computer science.

Dynamic programming can be used for finding paths in finite graphs by constructing a cost-to-goal function for nodes that gives the exact cost of a minimal-cost path from the node to a goal.

Question 29

What is island driven search?

Answer 29

One of the ways that search may be made more efficient is to identify a limited number of places where the forward search and backward search could meet. For example, in searching for a path from two rooms on different floors, it may be appropriate to constrain the search to first go to the elevator on one level, go to the appropriate level and then go from the elevator to the goal room. Intuitively, these designated positions are islands in the search graph, which are constrained to be on a solution path from the start node to a goal node.

Question 30

What is bidirectional search?

Answer 30

The idea of bidirectional search is to search forward from the start and backward from the goal simultaneously. When the two search frontiers intersect, the algorithm needs to construct a single path that extends from the start node through the frontier intersection to a goal node. It is a challenge to guarantee that the path found is optimal.