Chapter 3: Solving problems by searching (3751)

Chapter 3: Solving problems by searching (3751)

1. introduction

   • one kind of goal-based agent called a problem-solving agent
     • Problem-solvi ng agents use atomic representations
       • states of the world are considered as wholes, withno intemal structure visible to the problemsolving algorithms
   • agents that use more advanced factored or structured representations are usually called planning agents
   • uninformed search algorithms - > Can only identify the problem definition
   • informed search algorithms -> Do well in solving a problem, given some assistance in where to find a solution
   • In this chapter consider asymptotic complexity (that is, 0() notation) and NP-completeness.

2. 3.1 Problem Solving Agents

   • Intelligent agents are supposed to maximize their performance measure.
   • Helps if the agent can adopt a goal and aim at satisfying it
   • Goals help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider.
   • Goal formulation, based on the current situation and the agent's performance measure, is the first step in problem solving.
   • Problem formulation is the process of deciding what actions and states to consider, given a goal.
     • The different states can be granular or larger, depending on the complexity and uncertainty. eg. having a goal to travel to a country, on won't make each state a "step left/right/forward", but rather each state will be a country/city along the way
   • an agent with several immediate options of unknown value can decide what to do by first examining future actions that eventually lead to states of known value.
   • 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.
     • execution phase -> Solution is found and executed
     • we have a simple "formulate, search, execute" design for the agent
       • After formulating a goal and a problem to solve, the agent calls a search procedure to solve it.
       • then uses the solution to guide its actions
   • while the agent is executing the solution sequence it ignores its percepts as it already knows the sequence of actions it will take
     • call this an open-loop system, because ignoring the percepts breaks the loop between agent and environment.
   • 3.1.1 Well-defined problems and solutions
     • A problem can be defined formally by five components:
       • • The initial state that the agent starts in.
         • eg. In(America)
       • • 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. We say that each of these actions is applicable in s. For example, from the state In(Arad), the applicable actions are {Go(Sibiu), Go( Timisoara), Go(Zerind)}.
       • • A description of what each action does
         • the transition model, specified by a function RESULT(s,a) that returns the state that results from doing action a in state s.
         • successor to refer to any state reachable from a given state by a single action
           • RESULT(In(Amd), Go(Zerind)) = In(Zerind)
       • • The goal test
         • determines whether a given state is a goal state
       • • 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
         • cost of a path can be described as the sum of the costs of the individual actions along the path
         • The step cost of taking action a in state s to reach state s' is denoted by c(s, a, s').
         • Solution quality is measured by the path cost function, and an optimal solution has the lowest path cost among all solutions.
     • initial state, actions, and transition model implicitly define the state space of the problem
       • The state space forms a directed network or graph in which the nodes are states and the links between nodes are actions.
       • A path in the state space is a sequence of states connected by a sequence ofactions.
     • A solution to a problem is an action sequence that leads from the initial state to a goal state.
   • 3.1.2 Formulating problems
     • The model which supports the problem of getting to another city is abstracted , and doesn't account for the finer details such as eg. The distance to the next petrol station, since it is irrelevant to finding a road to another city
       • The process of removing detail from a representation is called abstraction.
         • The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world;
       • Both actions and states are abstracted

3. 3.2 Example Problems

   • A toy problem
     • is intended to illustrate or exercise various problem-solving methods
   • A real-world problem
     • tend not to have a single agreed-upon description, but we can give the general flavor oftheir formulations.
   • 3.2.1 Toy problems
     • An incremental formulation -> involves operators that augment the state description, starting with an empty state; for the 8-queens problem, this means that each action adds a queen to the state
     • A complete-state formulation -> starts with all 8 queens on the board and moves them around
     • In this formulation, we have 64 · 63 · · · 57 => 1.8 x 10^14 possible sequences to investigate.

4. 3.2.2 Real-world problems

   • Touring problems are closely related to route-finding problems
   • The traveling salesperson problem (TSP) is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour.
   • A VLSI layout problem requires positioning millions of components and connections on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield.
   • Robot navigation is a generalization of the route-finding problem described earlier
   • Automatic assembly sequencing of complex objects by a robot

5. 3.3 Searching for solutions

   • 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 t.he problem.
   • We do this by expanding the current state; that is, applying each legal action to the current state, thereby generating a new set of states
     • we add three branches from the parent node ln(Arad) leading to three new child nodes: ln(Sibiu), ln(Timisoara), and ln(Zerind)
   • leaf node, that is, a node with no children in the tree.
   • The set of all leaf nodes available for expansion at any given point is called the frontier
   • The process of expanding nodes onthe frontiercontinues until either a solution is fotmd or there are no more states to expand
   • Loopy paths are a special case of the more general concept of redundant paths, which exist wheneverthere is more thanone way to get from one state to another.
     • Redundant paths can be excluded in searches when one action costs more than the other, in some cases
     • Routing and reversible actions (travel, sliding puzzle) have redundant paths not avoidable
   • algorithms that forget their history are doomed to repeat it.
     • a data structure called the explored set (also known as the closed list), which remembers every expanded node
       • The new algorithm, called GRAPH-SEARCH (remembers the nodes visited)
         • the frontier separates the state-space graph into the explored region and the unexplored region
     • TREE-SEARCH algorithms have redundant paths
   • 3.3.1 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:
     • 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.
     • The frontier needs to be stored in such a way that the search algo can easily choose the next node to expand according to its preferred strategy.
       • The appropriate data structure for this is a queue
         • FIFO
         • LIFO (Stack)
         • Priority queue
   • 3.3.2 Measuring problem-solving performance
     • We can evaluate an algorithm's performance in four ways:
     • Time and Space complexity's typical measure is the size of the state space graph, lVI + lEI, where V is the set of vertices (nodes) of the graph and E is the set of edges (links).
     • 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.
     • 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.

6. 3.4 Uninformed Search Strategies

   • also called blind search
   • strategies have no additional inf01mation 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.
   • Strategies that know whether one non-goal state is"more promising" than another are called informed search or heuristic search strategies
   • 3.4.1 Breadth-first search
     • root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on
     • all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded
     • Breadth-first search is an instance of the general graph-search algorithm
       • a FIFO queue for the frontier
       • new nodes (which are always deeper than their parents) go to the back ofthe queue, and old nodes, which are shallower than the new nodes, get expanded first.
       • the goal test is applied to each node when it is generated rather than when it is selected for expansion.
       • b+ b^2 + b^3 + . . . + b^d = O(b^d) .
     • the space complexity is always within a factor of b of the time complexity.
     • space complexity is O(b^d)
     • First, the memory requirements are a bigger problemfor breadth-first search than is the execution time.
     • In general, exponential-complexity search problems cannot be solved by uninformed methods for any but the smallest instances.
   • 3.4.2 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
     • two other significant differences from breadth-first search
       • the goal test is applied to a node when it is selectedfor expansion
       • The second difference is that a test is added in case a better path is found to a node currently on the frontier.
       • It is easy to see that uniform-cost search is optimal in general.
     • uniform-cost search expands nodes in order oftheir optimal path cost.
     • does not care about the number of steps a path has, but only about their total cost.
     • Uniform-cost search does strictly more work (than breadth first) by expanding nodes at depth d unnecessarily. (In search of more optimal path)
   • 3.4.3 Depth-first search
     • expands the deepest node in the current frontier of the search tree
     • whereas breadth-first-search uses a FIFO queue, depth-first search uses aLIFOqueue. A LIFO queue means that the most recently generated node is chosen for expansion
     • it is common to implement depth-first search with a recursive function that calls itself on each of its children in turn.
     • The graph-search version, which avoids repeated states and redundant paths, is complete in finite state spaces because it will eventually expand every node. TI1e tree-search version, on the other hand, is not complete-for example, in Figure 3.6 the algorithm will follow the Arad-Sibiu-Arad-Sibiu loop forever
       • both versions fail if an infinite non-goal path is encountered.
     • a depth-first tree search needs to store only a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path
     • depth-first tree search as the basic workhorse of many areas of AI
     • For a state space with branching factor b and maximum depth m, depth-first search requires storage of only O(bm) nodes
       • Exponentially less than for breadth first
     • A variant of depth-first search called backtracking search uses still less memory
       • only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next. In this way, only O(m) memory is needed rather than O(bm)
   • 3.4.4 Depth-limited search
     • supplying depth-first search with a predetermined depth limit £. That is, nodes at depth £ are treated as if they have no successors.
     • Sometimes, depth limits can be based on knowledge ofthe problem. For example, on the map of Romania there are 20 cities. Therefore, we know that if there is a solution, it must be of length 19 at the longest, so f. = 19 is a possible choice
     • The number, known as the diameter of the state space, gives us a better depth limit, which leads to a more efficient depth-limited search. eg. If we know that a solution exists at depth 9, then we can set the limit to this.
   • 3.4.5 Iterative deepening depth-first search
     • 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
     • Iterative deepening combines the benefits of depth-first and breadth-first search.
     • In general, iterative deepening is the preferred uninformed search methodwhen the search space is large and the depth ofthe solution is not known.
   • 3.4.6 Bidirectional search
     • run two simultaneous searches--one forward from the initial state and the other backward from the goal, oping that the two searches meet in the middle
     • 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.
   • 3.4.7 Comparing uninformed search strategies
     • This comparison is for tree-search versions

7. 3.5 Informed (Heuristic) search strategies

   • one that uses problem-specific knowledge beyond the definition ofthe problem itself-can find solutions more efficiently than can an uninfonned strategy.
   • 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.
     • implementation of best-first graph search is identical to that for uniform-cost search (Figure 3.14), except for the use off instead of g to order the priority queue.
     • include as a component of a heuristic function, denoted h(n) where h( n) = estimated cost of the cheapest path from the state at node n to a goal state
   • 3.5.1 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
     • it evaluates nodes by using just the heuristic function; that is, f(n) = h(n).
     • Straight line heuristic used for path to Bucharest. Knowledge outside of the problem definition is known
     • "greedy"-at each step it tries to get as close to the goal as it can
   • 3.5.2 A* search: Minimizing the total estimated solution cost
     • It evaluates nodes by combining g(n), the cost tor each the node, and h(n), the cost to get from the node to the goal: f(n) = g(n) + h(n)
     • f(n) = estimated cost of the cheapest solution through n .
     • A* search is both complete and optimal.
     • The algorithm is identical to UNIFORM-COST-SEARCH except that A* uses g + h instead of g.
     • Conditions for optimality: Admissibility and consistency
       • we require for optimality that h(n) be an admissible heuristic.
         • never overestimates the cost to reach the goal
         • 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.
         • by nature optimistic because they think the cost of solving the problem is less than it actually is
         • Notice in particular that Bucharest first appears on the frontier at step (e), but it is not selected for expansion because its f-cost (450) is higher than that of Pitesti (417).
       • consistency (or sometimes monotonicity) is required only for applications of A* to graph search.
     • Optimality of A*
       • A* has the following properties: the tree-search version of A* is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent.
       • if h(n) is consistent, then the values of f(n) along any path are nondecreasing.
     • THIS SECTION IS INCOMPLETE
   • 3.5.3 Memory-bounded heuristic search
   • 3.5.4 Learning to search better

8. 3.6 Heuristic Function

   • 3.6.1 The effect ofheuristic accuracy on performance
   • 3.6.2 Generating admissible heuristics from relaxed problems
   • 3.6.3 Generating admissible heuristics from subproblems: Pattern databases
   • 3.6.4 Learning heuristics from experience

Images and files in the map