Ch03: Solving Problems by Searching

<style> .r { color: rgb(224, 60, 46); font-weight: bold; } .b { color: rgb(45, 123, 238); font-weight: bold; } .g { color: rgb(33, 147, 66); font-weight: bold; } .y { color: rgb(247, 191, 25); font-weight: bold; } </style> # Solving Problems by Searching ## Problem-solving Agents - A kind of goal-based agent - Use **atomic** representations with no internal structure visible to the problem solving algorithms - First Step: goal formulation - Based on current situation and the agent's performance measure - A goal is considered as a set of world states - By given a goal, the problem formulation is - The process of deciding what actions and states to consider > Assuming the environment is observable, discrete known, and deterministic, then *the solution to any problem is a fixed sequence of actions* - The process of looking for a sequence of actions that reaches the goal is called search - Carry out the solution is called the execution phase - The design of an agent can be considered as a simple "**formulate**, **search**, **execute**" ### Example: Romania - On holiday in Romania; currently in Arad - Flight leaves tomorrow from Bucharest - Formulate goal: - Be in Bucharest - Formulate prolem - States: various cities - Actions: drive between cities - Find solution: - Sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest ![](https://hackmd.io/_uploads/H1v5Oeae6.png =600x) ### Problem types - **Deterministic, full observable** $\rightarrow$ single-state problem - Agent knows exactly which state it will be in; solution is a sequence - **Non-observable** $\rightarrow$ conformant (一致的) problem - Agent may have no idea where it is; solution (if any) is a sequence - **Nondeterministic and/or partially observable** $\rightarrow$ contingency (意外事件) problem - Percepts provide new information about current state - Solution is a contingent plan or a policy - Often interleave (交錯) search, execution - **Unknown state space** $\rightarrow$ exploratotion problem ("online") ### Well-defined Problems and Solutions A search problem can be defined formally as follows: - A set of possible states that the environment can be in. (Called state space) - Initial state that the agent starts in, such as *Arad* - A set of one or more goal states - The actions available to the agent - Given a particular state $s, Action(s)$ returns the finite set of actions that can be executed in $s$. - Ex. $Action(Arad) = \{ToSibiu, ToTimisoara, ToZerind\}$ - A transition model, which describes what each action does. $Result(s, a)$ returns the state that results from doing action a in state s. - e.g. $Result(Arad, ToZerind) = Zerind$ - An action cost function, denoted by Action-Cost(`s`, `a`, `s'`) that gives the numeric cost of applying action `a` in state `s` to reach state `s'`. - A problem solving agent should use a cost function that reflects its own performance measure - e.g. for route-finding agents, the cost of an action might be the length in miles, or it might be the time it takes to complete the action. ## Formulating Problems - Abstraction 抽象 - The process of removing detail from a representation - The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world - The abstraction is useful if carrying out each of the actions in the solutions is easier than the original problem ## Example Problems - Standardized problems and real-world problems - Standardized problem: intended to illustrate or exercise various problem-solving methods (旨在說明或練習各種解決問題的方法) - Real-world problem: people actually care about their solutions ## Standardized Problems ### Vaccum world - **States**: 2 $\times$ 2^2^ = 8 possible states - **Initial state**: any state can be designed as the initial state - **Actions**: *Left, Right, Suck, NoOP* - **Transition model**: see the figure below - **Goal test**: checks whether all squares are clean - **Path cost**: each step costs 1, so the path cost is the number of steps in the path ![image.png](https://hackmd.io/_uploads/Byz-lv97T.png =600x) ### 8-puzzle - **States**: integer locations of tiles - **Initial state**: any state can be designed as the initial state - **Actions**: move blank *left, right, up, down* - **Transition model**: given a state and action, this returns the resulting state - **Goal test**: = goal state - **Path cost**: 1 per move ![image.png](https://hackmd.io/_uploads/HJMwbwcXT.png =300x) ### 8-queens - Two kinds of formulation: *incremental* and *complete-state* formulation - Incremental formulation - **States**: any arrangement of 0 to 8 queens on the board - **Initial state**: no queens on the board - **Actions**: add a queen to any empty square - **Transition model**: returns the board with a queen added to the specified square - **Goal test**: 8 queens are on the board, none attacked - **Path cost**: don't care - A better formulation that reduces # of states (from 1.8 * 10^14^ to 2057) - **States**: all possible arrangements of n queens (0 $\le$ n $\le$ 8), one per column in leftmost n columns, with no queen attacking another - **Actions**: add a queen to any square in the leftmost empty column such that it is not attacked by any other queen ![image.png](https://hackmd.io/_uploads/r1yhWPqXT.png =200x) ## Real-world Problems ### Route-finding Problem - Airline travel problem - **States**: each state includes a location, current time, other extra information about historical aspects, such as previous segments of flight, fare bases, status as domestic or international - **Initial state**: specified by user's query - **Actions**: take any flight from current location, in any seat class, leaving after current time, leaving enough time for within-airport transfer if needed - **Transition model**: flight's destination as the current location and arrival time as the current time - **Goal test**: are we at the final destination specified by the user - **Path cost**: depends on monetary cost, waiting time, flight time, customs and immigration procedures, seat quality, and so on ### Other Real-world Problems - Touring problems - Closely related to route-finding problems - State space is quite different. Each state must include not only the current location but also the set of cities the agent has visited - Goal state, for example, check the agent is in Bucharest and all 20 cities have been visited - Traveling Saleperson Problem (TSP) - a touring problem in which each city must be visited exactly once - The aim is to find the *shortest* tour - NP-hard problem - VLSI layout - Positioning, millions of components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield - Robot navigation - A generalization of the routing-finding problem - A robot can move in a continuous space with an infinte set of possible actions and states - Automatic assembly sequencing - Find an order in which to assemble the parts of some object ## Searching for Solutions - Search Tree - Root as the initial state - Branches as actions - Nodes correspond to states in the state space - Search by expanding the current state - Generate a new set of states by applying each legal action to the current state ![image.png](https://hackmd.io/_uploads/H1RgPw9QT.png =500x) ### Informal Description of Tree-search and Graph Search: ![](https://hackmd.io/_uploads/S1vsfyaea.png) > Frontier: The set of all leaf nodes available for expansion at any given point is called the frontier ### Loopy Path and Redundant Path  - Loopy path: A repeated state in the search tree. - Ex. A -> B -> A - Can be easily avoid, since the **path costs are additive** and step costs are **nonnegative**. - A loopy path to any given state is never better than the same path with the loop removed. - Redundant Path: There is more than one way to get from one state to another. - **Loopy paths are special case of redundant path**. - Ex. Arad->Sibiu (140 km) vs Arad-Zerind-Oradea-Sibiu (297 km) - The second path is redundant - In other cases, redundant paths are **unavoidable**. - To avoid exploring redundant paths is to **remember** where one has been. (See graph search in the previous slide) - 要列出所有可能的答案時要保留 redundant path. ### Node and State - A node is a **data structure** constituting part of a search tree including parent, children, depth, path cost g(x). - A state is a (representation of) a **physical configuration**. - States do not have parents, children, depth, or path cost! ### Concepts used to implement search algorithms - **Queue**: FIFO (First In First Out) - **Stack**: LIFO (Last In First Out) - **Priority queue**: pops the element of the queue with **highest priority**. - **Hash table**: allow efficient checking for repeated states. ### Measuring Problem-solving Performance - A strategy is defined by picking the order of node expansion - Strategies are evaluated along the following dimensions: - **Completeness** - Does it always find a solution if one **exits**? - **Optimality** - Does the strategy find the **least-cost (optimal) solution**? - **Time Complexity** - Number of nodes **generated/expanded**. - **Space Complexity** - Maximum number of nodes **in memory**. - Time and space complexity are measured in terms of - $b$ – **maximum branching factor** of the search tree - $d$ – **depth of the least-cost solution** - $m$ – **maximum depth** of the state space (may be $\infty$) ## Uninformed Search Strategies 不知情的搜索策略 Uninformed strategies use only the information available in the problem definition. Also called **blind search**. - Breadth-first search - Uniform-cost search - Depth-first search - Depth-limited search - Iterative deepening depth-first search - Bidirectional search ### Breadth-first search on a graph ![](https://hackmd.io/_uploads/S125OJ6e6.png) - Expand shallowest unexpanded node - Implementation - fringe is a FIFO queue, i.e., new successors go at end ![image.png](https://hackmd.io/_uploads/r15St_qXa.png =300x) #### Properties of Breadth-first Search - Complete - Yes, if $b$ is finite. - Time - $1 + b + b^2 + b^3 + \cdots + b^d = O(b^d)$ - Space - $O(b^d)$ (keeps every node in memory) - Optimal - Yes (if **cost = 1 per step**); not optimal in general. - **Space** is the big problem; can easily generate nodes at 100MB/s, so 24hrs = 8640GB ### Uniform-cost Search ![](https://hackmd.io/_uploads/HyRP-eplT.png) - Expand least-cost unexpanded node, denoted by lowest path cost $g(n)$ - Two significant difference from breadth-first search - Goal test is applied to a node when it is selected for expansion (rather than it is first generated) - A test is added in case a better path is found to a node currently on the frontier - Implementation: - fringe = queue ordered by path cost, lowest first - Equivalent to breadth-first if step costs all equal - Complete - Yes, if step cost >= $\varepsilon$ - Time - \# of nodes with g <= cost of optimal solution, $O(b^{1 + [C^*/\varepsilon]})$ - Where $C^*$ is the cost of the optimal solution - Space - \# of nodes with g <= cost of optimal solution, $O(b^{1 + [C^*/\varepsilon]})$ - Optimal - Yes, nodes expanded in increasing order of $g(n)$ #### Why not goal-test when generating child nodes ![](https://hackmd.io/_uploads/rJIo-gTgT.png) - Goal: From Sibiu to Bucharest - Successors of Sibiu: Rimnicu Vilcea and Fagaras (cost 80 and 99) - Least-cost node will be Rimnicu Vilcea, and is expanded next, adding Pitesti with cost 80+97=177. - Least-cost node will be Fagaras, and is expanded, adding Bucharest with cost 99+211 =310. - Now a goal node has been generated, but uniform-cost search keeps going, choosing Pitesti for expansion and adding a second path to Bucharest with cost 80 + 97 + 101 = 278. - Now the algorithm checks to see **if this new path is better than the old one**; it is, so the old one is discarded. Bucharest, now with cost 278 is selected for expansion and the solution is returned. ### Depth-first Search - Complete - No, fails in infinite-depth spaces, spaces with loops - Modify to avoid repeated states along path -> complete in finite spaces - Time - $O(b^m)$: terrible if $m$ is much larger than $d$ - But if solutions are **dense**, may be much faster than breadth-first - Space - $O(bm)$, i.e., linear space! - Optimal - No ### Depth-limited Search - = depth-first search with depth limit $l$, - i.e., nodes at depth $l$ have no successors - Recursive implementation ![](https://hackmd.io/_uploads/r1Y8Qe6e6.png) ### Iterative Deepening Search ![](https://hackmd.io/_uploads/HJIc7l6xT.png) - $l$ = 0 ![](https://hackmd.io/_uploads/HksV4g6xT.png =400x) - $l$ = 1 ![](https://hackmd.io/_uploads/Bk28VxagT.png) - $l$ = 2 ![](https://hackmd.io/_uploads/ryTvVgplT.png) - $l$ = 3 ![](https://hackmd.io/_uploads/H1xYEgaep.png) #### Properties of Iterative Deepening Search - Complete - Yes - Time - $db^1 + (d - 1)b^2 + \cdots + b^d = O(b^d)$ - Space - $O(b^d)$  ### Bidirectional Search - Run two simultaneous searches and hope that the two searches meet in the middle - One **forward** from the initial state, the other **backward** from the goal. - Motivated by $b^{d/2} + b^{d/2}$ is much less then $b^d$ - Goal test is replaced by checking whether the frontiers of the two searches intersect - However, this **may not be the optimal solution**. - Bidirectional search requires a method for **computing predecessors**. - 8-puzzle and find a route in Romania, backward search is very much like the forward search - 8-queen, “no queen attacks another queen” - it is hard to find such a function for backward search ### Comparison of Uninformed Search Strategies ![](https://hackmd.io/_uploads/ryS0Be6l6.png) - $b$ is the branching factor - $d$ is the depth of the shallowest solution - $m$ is the maximum depth of the search tree - $l$ is the depth limit ## Informed (Heuristic) Search Strategies - Best-first search - Instance of the general tree-search or graph-search algorithm - A node is selected for expansion based on an **evaluation function**, $f(n)$ - Node with the lowest evaluation is expanded first. - Implementation is identical to that for uniform-cost search, except for the use of $f$ instead of $g$ to order the priority queue. - Special cases: - Greedy search - A* search ### Heuristic Functions - Most best-first algorithms include as a component of $f$ a heuristic function, denoted $h(n)$: - $h(n)$ = estimated cost of the cheapest path from the state at node $n$ to a goal state. - $h(n)$ takes a node as input, $g(n)$ depends only on the state at that node. ### Greedy Best-first Search - Greedy search expands the node that appears to be closest to goal - It evaluates nodes by using just the heuristic function, i.e. $f(n) = h(n)$ - In Romania example, **straight-line distance** heuristic is used, as $h_{SLD}$. ![](https://hackmd.io/_uploads/B1ZWOl6e6.png) Value of $h_{SLD}$: ![](https://hackmd.io/_uploads/H13f_eTgp.png) #### Properties of Greedy Search - Complete - No, can get stuck in loops - Ex. From Iasi to Fagaras - Iasi -> Neamt -> Iasi -> Neamt -> - Complete in finite space with repeated-state checking - Time - $O(b^m)$, but a good heuristic can give b dramatic improvement - Space - O(b^m) keeps all nodes in memory - Optimal - No ### A* Search - Idea: avoid expanding paths that are **already expensive** - Evaluation function: $f(n) = g(n) + h(n)$ - $g(n)$: cost so far to reach the node $n$ - $h(n)$: estimated cost to goal from $n$ - $f(n)$ = estimated total cost of path through $n$ to goal - A* search uses an admissible heuristic - i.e., $h(n) \le h^*(n)$ where $h^*(n)$ is the true cost from $n$. - (Also require $h(n) \ge 0$, so $h(G) = 0$ for any goal $G$.) - E.g., $h_{SLD}(n)$ never overestimates the actual road distance - Provided that the heuristic function satisfied certain **conditions**, A* search is both complete and optimal ![](https://hackmd.io/_uploads/ryIfql6g6.png) ![](https://hackmd.io/_uploads/BkI79eTep.png) --- - Conditions for optimality: **Admissibility** and **consistency** - $h(n)$ be an admissible heuristic - Admissible heuristic is one that **never overestimates** the cost to reach the goal. - e.g. the straight-line distance in Romania example - Consistency or monotonicity - A $h(n)$ is consistent if, for every node $n$ and every successor $n'$ of $n$ generated by any action $a$, the estimated cost of reaching the goal from $n$ is no greater than the step cost of getting to $n'$ plus the estimated cost of reaching the goal from $n'$ - $h(n) <= c(n, a, n') + h(n')$ - A form of the general **triangle inequality** ![](https://hackmd.io/_uploads/H1QOslaea.png) #### Optimality of A* - Suppose some suboptimal goal $G_2$ has been generated and is in the queue. - Let $n$ be an unexpanded node on a shortest path to an optimal goal $G_1$. - $$f(G2) = g(G2) since h(G2) = 0 $$  #### Properties of A* - Complete - Yes, unless there are infinitely many nodes with f <= f(G) - Time - Exponential in [relative error in h * length of soln.] - Space - Keeps all nodes in memory - Optimal - Yes, cannot expand $f_{i+1}$ until $f_i$ is finished #### Proof of Lemma: Consistency  #### A* Search - Main drawback - It keeps all generated nodes in memory - Iterative-deepening A\* (IDA*) algorithm - The simplest way to reduce memory requirements for A* - The cutoff is the f-cost (g+h) - At each iteration, the cutoff value is the smallest f-cost of any node that exceeded the cutoff on the previous iteration ### Memory-bounded Heuristic Search - RBFS (Recursive best-first search) - A simple recursive algorithm - Attempts to mimic the operation of standard best-first search - Using only linear space #### RBFS ![](https://hackmd.io/_uploads/HyAkg-Tl6.png) - It uses the $f\_limit$ variable to keep track of the f-value of the best alternative path available from an ancestor of the current node - If the current node exceeds this limit, the recursion unwinds back to the alternative path - Back-up value - The best f-value of its children - Decide whether it’s worth reexpanding the subtree at some later time ![](https://hackmd.io/_uploads/HJTsgZpgT.png) ![](https://hackmd.io/_uploads/SJT2l-pep.png) - More efficient than IDA* - Excessive node re-generation - Each mind change corresponds to an iteration of IDA* and could require many reexpansions of forgotten nodes to recreate the best path and extend it one more node. --- - It is optimal - If the heuristic function is admissible - Space complexity - It is linear in the depth of the deepest optimal solution - Time complexity - Depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded. --- - MA\* (Memory-bounded A*) - SMA\* (Simplified MA*) - It expands the best leaf until memory is full - Always drops the worst leaf node – the one with the highest f-value - Backs up the value of the forgotten node to its parent ### Heuristic Functions - The 8-puzzle was one of the earliest heuristic search problems. - The average solution cost is about 22 steps - The branching factor is about 3 ![](https://hackmd.io/_uploads/BySjz-6xT.png) #### Two Commonly Used Heuristics - h1 = the number of misplace tiles - An admissible heuristic - 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. (i.e., total Manhattan distance) - An admissible heuristic - 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** - h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18 #### Dominance - If $h_2(n) \ge h_1(n)$ for all $n$ (both admissible) - Then $h_2$ dominates $h_1$ and is better for search - Typical search costs - d = 14 IDS = 3,473,941 nodes - A*($h_1$) = 539 nodes - A*($h_2$) = 113 nodes - d = 24 IDS ~= 54,000,000,000 nodes - A*($h_1$) = 39,135 nodes - A*($h_2$) = 1,641 nodes - Given any admissible heuristics $h_a, h_b$ - $h(n) = max(h_a(n), h_b(n))$ - Is also admissible and dominates $h_a, h_b$ - Comparison of the search costs and effective branching factors for the iterative deepening search and A* algorithms with $h_1, h_2$ ![](https://hackmd.io/_uploads/rkcnvW6lT.png) #### The effect of heuristic accuracy on performance #### Relaxed Problems - Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem - If the rules of the 8-puzzle are relaxed so that a tile can move **anywhere**, then $h_1(n)$ gives the shortest solution - If the rules are relaxed so that a tile can move to **any adjacent square**, then $h_2(n)$ gives the shortest solution - Key point: the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem --- - Well-known example: travelling salesperson problem (TSP) - Find the shortest tour visiting all cities exactly once - Minimum spanning tree can be computed in $O(n^2)$, and is a lower bound on the shortest (open) tour [後面的演算法相關筆記](https://fu-sheng-wang.blogspot.com/search/label/AI?updated-max=2017-02-12T01:12:00-08:00&max-results=20&start=33&by-date=false)