Epoch 3: Solving problems by searching

Let us continue with our journey further with the AI, a modern approach. 

In this chapter we look into how an AI agent achieves a goal with a sequence of actions. These types of agents are also known as problems solving agents. Before this we will just look at the diagram below. 

In an atomic representation each state of the world is indivisible, it has no internal structure. A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value. Structured representations underlie relational databases and first-order logic.

The axis along which atomic, factored, and structured representations lie is the axis of increasing expressiveness. Roughly speaking, a more expressive representation can capture, at least as concisely, everything a less expressive one can capture, plus some more.

 

PROBLEM-SOLVING AGENTS 

Whenever we have to solve a problem, what has to be achieved, has to be analyzed in the first place which then formulates the goal.

Goal formulation, based on the current situation and the agent’s performance measure, is the first step in problem solving. The agent’s task is to find out how to act, now and in the future, so that it reaches a goal state. Problem formulation is the process of deciding what actions and states to consider, given a goal. The environment also plays an important role for the AI agent which should be decided, if it doesn’t know the environment then it must randomize the environment and act accordingly. To be more specific about what we mean by “examining future actions,” we must be more specific about properties of the environment. So, the environment can either be observable or non-observable. We also assume the environment is discrete, so at any given state there are only finitely many actions to choose from. We will assume the environment is known, so the agent knows which states are reached by each action.

Finally, we assume that the environment is deterministic, so each action has exactly one outcome. These are certain assumptions which we need to make before entering a problem and solving the problem. The process of looking for a sequence of actions that reaches the goal is called search. A search algorithm takes a problem as input and returns a solution in the form of an action sequence. Once a solution is found, the actions it recommends can be carried out. This is called the execution phase. Thus, we have a simple “formulate, search, execute” design for the agent.

Fun Meme!!

After formulating a goal and a problem to solve, the agent calls a search procedure to solve it. It then uses the solution to guide its actions, doing whatever the solution recommends as the next thing to do—typically, the first action of the sequence—and then removing that step from the sequence. Once the solution has been executed, the agent will formulate a new goal. Notice that while the agent is executing the solution sequence it ignores its percepts when choosing an action because it knows in advance what they will be. An agent that carries out its plans with its eyes closed, so to speak, must be quite certain of what is going on. Control theorists call this an open-loop system, because ignoring the percepts breaks the loop between agent and environment.

Well-defined problems and solutions

A problem can be defined formally by five components: 

·         The initial state that the agent starts in.

·         A description of the possible actions available to the agent. Given a particular state s, ACTIONS(s) returns the set of actions that can be executed in s.

·         A description of what each action does; the formal name for this is the transition model, specified by a function RESULT(s, a) that returns the state that results from doing action a in state s.

·         The goal test, which determines whether a given state is a goal state. Sometimes there is an explicit set of possible goal states, and the test simply checks whether the given state is one of them.

·         A path cost function that assigns a numeric cost to each path. The problem-solving agent chooses a cost function that reflects its own performance measure.

A solution to a problem is an action sequence that leads from the initial state to a goal state. Solution quality is measured by the path cost function, and an optimal solution has the lowest path cost among all solutions.

Formulating problems

In the preceding section we proposed a formulation of the problem, in terms of the initial state, actions, transition model, goal test, and path cost. The process of removing detail from a representation is called abstraction. The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem. We don’t consider many things while we think of formulating a problem, the choice of a good abstraction thus involves removing as much detail as possible while retaining validity and ensuring that the abstract actions are easy to carry out. Were it not for the ability to construct useful abstractions, intelligent agents would be completely swamped by the real world. 

A real-world problem is one whose solutions people actually care about. Such problems tend not to have a single agreed-upon description, but we can give the general flavor of their formulations.

Toy problems

Consider a vacuum cleaner AI agent. Problem for it can be formulated as follows:

·         States: The state is determined by both the agent location and the dirt locations. The agent is in one of two locations, each of which might or might not contain dirt. Thus, there are 2 × 22 = 8 possible world states. A larger environment with n locations has n ・ 2^n states.

·         Initial state: Any state can be designated as the initial state.

·         Actions: In this simple environment, each state has just three actions: Left, Right, and Suck. Larger environments might also include Up and Down.

·         Transition model: The actions have their expected effects, except that moving Left in the leftmost square, moving Right in the rightmost square, and Sucking in a clean square have no effect.

·         Goal test: This checks whether all the squares are clean.

·         Path cost: Each step costs 1, so the path cost is the number of steps in the path.

SEARCHING FOR SOLUTIONS

 Having formulated some problems, we now need to solve them. A solution is an action sequence, so search algorithms work by considering various possible action sequences. The possible action sequences starting at the initial state form a search tree with the initial state at the root; the branches are actions and the nodes correspond to states in the state space of the problem. The root node of the tree corresponds to the initial state. The first step is to test whether this is a goal state. The set of all leaf nodes available for expansion at any given point is called the frontier. The process of expanding nodes on the frontier continues until either a solution is found or there are no more states to expand. 

The general TREE-SEARCH algorithm is shown informally in Figure below

Search algorithms all share this basic structure; they vary primarily according to how they choose which state to expand next—the so-called search strategy.

  

Infrastructure for search algorithms

Search algorithms require a data structure to keep track of the search tree that is being constructed. For each node n of the tree, we have a structure that contains four components:

·         n.STATE: the state in the state space to which the node corresponds;

·         n.PARENT: the node in the search tree that generated this node;

·         n.ACTION: the action that was applied to the parent to generate the node;

·         n.PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state to the node, as indicated by the parent pointers.

Up to now, we have not been very careful to distinguish between nodes and states, but in writing detailed algorithms it’s important to make that distinction. A node is a bookkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world. Thus, nodes are on particular paths, as defined by PARENT pointers, whereas states are not. Furthermore, two different nodes can contain the same world state if that state is generated via two different search paths. Now that we have nodes, we need somewhere to put them. The frontier needs to be stored in such a way that the search algorithm can easily choose the next node to expand according to its preferred strategy. The appropriate data structure for this is a queue. The operations on a queue are as follows:

·         EMPTY?(queue) returns true only if there are no more elements in the queue.

·         POP(queue) removes the first element of the queue and returns it.

·         INSERT(element, queue) inserts an element and returns the resulting queue.

 Queues are characterized by the order in which they store the inserted nodes. Three common variants are the first-in, first-out or FIFO queue, which pops the oldest element of the queue; the last-in, first-out or LIFO queue (also known as a stack), which pops the newest element of the queue; and the priority queue, which pops the element of the queue with the highest priority according to some ordering function.

Measuring problem-solving performance 

Before we get into the design of specific search algorithms, we need to consider the criteria that might be used to choose among them. We can evaluate an algorithm’s performance in four ways:

·         Completeness: Is the algorithm guaranteed to find a solution when there is one?

·         Optimality: Does the strategy find the optimal solution?

·         Time complexity: How long does it take to find a solution?

·         Space complexity: How much memory is needed to perform the search?

Time and space complexity are always considered with respect to some measure of the problem difficulty. In theoretical computer science, the typical measure is the size of the state space graph, |V | + |E|, where V is the set of vertices (nodes) of the graph and E is the set of edges (links). This is appropriate when the graph is an explicit data structure that is input to the search program.

In AI, the graph is often represented implicitly by the initial state, actions, and transition model and is frequently infinite. For these reasons, complexity is expressed in terms of three quantities: b, the branching factor or maximum number of successors of any node; d, the depth of the shallowest goal node (i.e., the number of steps along the path from the root); and m, the maximum length of any path in the state space. Time is often measured in terms of the number of nodes generated during the search, and space in terms of the maximum number of nodes stored in memory. For the most part, we describe time and space complexity for search on a tree; for a graph, the answer depends on how “redundant” the paths in the state space are. To assess the effectiveness of a search algorithm, we can consider just the search cost— which typically depends on the time complexity but can also include a term for memory  usage—or we can use the total cost, which combines the search cost and the path cost of the solution found.

UNINFORMED SEARCH STRATEGIES

 This section covers several search strategies that come under the heading of uninformed search (also called blind search). The term means that the strategies have no additional information about states beyond that provided in the problem definition. All they can do is generate successors and distinguish a goal state from a non-goal state. All search strategies are distinguished by the order in which nodes are expanded. Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies.

We will look into the below mentioned data structures:

1.       Breadth first search

2.       Uniform cost search

3.       Depth first search

4.       Depth limited search

5.       Iterative deepening depth first search

6.     Bidirectional search

1. Breadth-first search

 

Breadth-first search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Breadth-first search is an instance of the general graph-search algorithm in which the shallowest unexpanded node is chosen for expansion. This is achieved very simply

by using a FIFO queue for the frontier. Thus, new nodes (which are always deeper than their parents) go to the back of the queue, and old nodes, which are shallower than the new nodes, get expanded first. There is one slight tweak on the general graph-search algorithm, which is that the goal test is applied to each node when it is generated rather than when it is selected for expansion.

 

There is a best resource to understand in detailed view about the Breadth First search in the video below:

courtesy: MIT opencourseware

2. Uniform-cost search

 When all step costs are equal, breadth-first search is optimal because it always expands the shallowest unexpanded node. By a simple extension, we can find an algorithm that is optimal with any step-cost function. Instead of expanding the shallowest node, uniform-cost search expands the node n with the lowest path cost g(n). This is done by storing the frontier as a priority queue ordered by g.

 In addition to the ordering of the queue by path cost, there are two other significant differences from breadth-first search. The first is that the goal test is applied to a node when it is selected for expansion rather than when it is first generated. The reason is that the first goal node that is generated may be on a suboptimal path. The second difference is that a test is added in case a better path is found to a node currently on the frontier.

Video for the understanding of the Uniform Cost search is as follows:

3. Depth-first search

 

Depth-first search always expands the deepest node in the current frontier of the search tree. The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search “backs up” to the next deepest node that still has unexplored successors.

The depth-first search algorithm is an instance of the graph-search algorithm, breadth-first search uses a FIFO queue, depth-first search uses a LIFO queue. A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent—which, in turn, was the deepest unexpanded node when it was selected. As an alternative to the GRAPH-SEARCH-style implementation, it is common to implement depth-first search with a recursive function that calls itself on each of its children in turn.

Video for Depth First Search:

4. Depth-limited search

 The embarrassing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth limit L. That is, nodes at depth L are treated as if they have no successors. This approach is called depth-limited search. The depth limit solves the infinite-path problem. Unfortunately, it also introduces an additional source of incompleteness if we choose L < d, that is, the shallowest goal is beyond the depth limit. (This is likely when d is unknown.) Depth-limited search will also be nonoptimal if we choose L > d. Its time complexity is O(b^L) and its space complexity is O(bL). Depth-first search can be viewed as a special case of depth-limited search with L=∞.

Video for Depth limited search:

5. Iterative deepening depth-first search

 Iterative deepening search (or iterative deepening depth-first search) is a general strategy, often used in combination with depth-first tree search, that finds the best depth limit. It does this by gradually increasing the limit—first 0, then 1, then 2, and so on—until a goal is found. This will occur when the depth limit reaches d, the depth of the shallowest goal node. Iterative deepening combines the benefits of depth-first and breadth-first search. Like depth-first search, its memory requirements are modest: O(b^d) to be precise. Like breadth-first search, it is complete when the branching factor is finite and optimal when the path cost is a nondecreasing function of the depth of the node.

In general, iterative deepening is the preferred uninformed search method when the search space is large, and the depth of the solution is not known.

Video for Iterative deepening search:

6. Bidirectional search

The idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state and the other backward from the goal—hoping that the two searches meet in the middle. The motivation is that b^d/2 + b^d/2 is much less than b^d, or in the figure, the area of the two small circles is less than the area of one big circle centered on the start and reaching to the goal. Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect; if they do, a solution has been found. (It is important to realize that the first such solution found may not be optimal, even if the two searches are both breadth-first; some additional search is required to make sure there isn’t another short-cut across the gap.)

Video for Bidirectional search:

INFORMED (HEURISTIC) SEARCH STRATEGIES

 

An informed search strategy—one that uses problem-specific knowledge beyond the definition of the problem itself—can find solutions more efficiently than can an uninformed strategy. The purpose of the heuristic function is to guide the search process in the most profitable path among all that are available.

Search algorithms under this category are as follows:

1.       Best first search

2.       Greedy best first search

3.       A* search

4.       Recursive best first search

1. Best first search

 

The general approach we consider is called best-first search. Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH 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. 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.

(Notice that h(n) takes a node as input, but, unlike g(n), it depends only on the state at that node.)

Video for best first search algorithm:

2. Greedy best first search

Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n) = h(n). The change is basically the heuristic function instead of evaluation function. The worst-case time and space complexity for the tree version is O(b^m), where m is the maximum depth of the search space. With a good heuristic function, however, the complexity can be reduced substantially. The amount of the reduction depends on the particular problem and on the quality of the heuristic.

Video for Greedy best first search:

3. A* search

The most widely known form of best-first search is called A∗ search (pronounced “A-star search”). It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:

f(n) = g(n) + h(n).

Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have

f(n) = estimated cost of the cheapest solution through n.

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, A∗ search is both complete and optimal. The algorithm is identical to UNIFORM-COST-SEARCH except that A∗ uses g + h instead of g.

The first condition we require for optimality is that h(n) be an admissible heuristic. An admissible heuristic is one that never overestimates the cost to reach the goal. Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n) + h(n), we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n. Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.

Video for the A* search for reference:

4. Recursive best first search

 Recursive best-first search (RBFS) is a simple recursive algorithm that attempts to mimic the operation of standard best-first search but using only linear space. Its structure is similar to that of a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path. As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value—the best f-value of its children.

The performance of heuristic search algorithms depends on the quality of the heuristic function. One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs for subproblems in a pattern database, or by learning from experience with the problem class.

Further we will see more about the searching algorithms.