AI1/AI&ML – Informed Search
Dr Leonardo of the Session
This session aims to help you:
§ Describe the difference between uninformed and informed search § Understand the concept of a heuristic function in informed search
Copyright By PowCoder代写 加微信 powcoder
§ Analyse the performance of A* and apply the algorithm to solve search problems
§ Recap – Uninformed Search § Informed Search
§ A* Search
Searching for Solutions
§ A solution is an action sequence from an initial state to a goal state
§ Possible action sequences form a search tree with initial state at the
root; actions are the branches and nodes correspond to the state space
§ The idea is to expand the current state by applying each possible action: this generates a new set of states
Searching for Solutions
§ Let us consider the example from before
§ If S1 is the initial state and {S7, S8} is the set of goal states, the
corresponding search tree after expanding the initial state is:
S2 S4S5 S6
Searching for Solutions
§ Each of the three nodes resulting from the first expansion is a leaf node § The set of all leaf nodes available for expansion at any given time is
called the frontier (also sometimes called the open list)
§ The path from S1 to S1 is a loopy path and in general is not considered
S2 S4S5 S6
Uninformed Search Strategies
§ Uninformed search (also called blind search) means that the strategies have no additional information about states beyond that provided in the problem definition
§ Uninformed search strategies can only generate successors and distinguish a goal state from a non-goal state
§ The key difference between two uninformed search strategies is the order in which nodes are expanded
Breadth-First Search vs Depth-First Search
§ BFS would expand the shallowest node, namely S3 § DFS would expend the deepest node, namely S6
S2 S4S5 S6
§ Recap – Uninformed Search § Informed Search
§ A* Search
Informed Search Strategies
§ Informed search strategies use problem-specific knowledge beyond the definition of the problem itself
§ Informed search strategies can find solutions more efficiently compared to uninformed search
Informed Search Strategies
§ The general approach, called best-first search, is to determine which node to expand based on an evaluation function
𝑓 𝑛 : 𝑛𝑜𝑑𝑒 → 𝑐𝑜𝑠𝑡 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒
§ This function acts as a cost estimate: the node with the lowest cost is the one that is expanded next
S3 f(S3)=7
Informed Search Strategies – Heuristics
§ The evaluation function 𝑓(𝑛) for most best-first algorithms includes a heuristic function as a component:
h 𝑛 = estimated cost of the cheapest path from node 𝑛 to a goal node
§ Heuristic functions are the most common form in which new knowledge is given to the search algorithm. If 𝑛 is a goal node, then h(𝑛) = 0
§ A heuristic can be a rule of thumb, common knowledge; it is quick to compute, but not guaranteed to work (nor to yield optimal solutions)
Informed Search Strategies – Heuristics
§ Consider the problem to find the shortest path to Bucharest in Romania
§ We can use the straight-line distance heuristic, denoted by h!”#
§ This is a useful heuristic as it is correlated with actual road distances
Informed Search Strategies – Heuristics
§ Consider the problem to find the shortest path to Bucharest in Romania
§ The straight-line distances h!”# are shown in the table above § For example, the SLD from Sibiu would be 253
Informed Search Strategies – Heuristics
§ Consider the problem to find the shortest path to Bucharest in Romania
§ If we use 𝑓 𝑛 = h!”#(𝑛), then from Sibiu we expand Fagaras § This is because Fagaras has SLD 176, while 193
Informed Search Strategies – Heuristics
§ Consider the problem to find the shortest path to Bucharest in Romania
§ When 𝑓 𝑛 = h(𝑛), we call this strategy Greedy Best-First Search
§ Recap – Uninformed Search § Informed Search
§ A* Search
§ The most widely known informed search strategy is A*
§ This search strategy evaluates nodes using the following cost function
where 𝑔 𝑛 is the cost to reach the node and h 𝑛 is the heuristic from the
node to the goal
§ This is equivalent to the cost of the cheapest solution through node 𝑛
A* Search – Example
§ Consider the problem to find the shortest path to Bucharest in Romania
§ Let us consider Sibiu as the initial state. Calculate 𝑓(𝑛) to choose which node to expand, starting with Fagaras
𝑓 𝐹𝑎𝑔𝑎𝑟𝑎𝑠 = 𝑔 𝐹𝑎𝑔𝑎𝑟𝑎𝑠 + h(𝐹𝑎𝑔𝑎𝑟𝑎𝑠)
A* Search – Example
§ Consider the problem to find the shortest path to Bucharest in Romania
§ Let us consider Sibiu as the initial state. Calculate 𝑓(𝑛) to choose which node to expand, starting with Fagaras
𝑓 𝐹𝑎𝑔𝑎𝑟𝑎𝑠 =99+176=275
A* Search – Example
§ Consider the problem to find the shortest path to Bucharest in Romania
§ Repeat the calculation for all the children, i.e., for 𝑓 𝑅𝑖𝑚𝑛𝑖𝑐𝑢 𝑉𝑖𝑙𝑐𝑒𝑎 = 80 + 193 = 273
A* Search – Algorithm
§ A* search algorithm:
• Expandthenodeinthefrontierwithsmallestcost𝑓 𝑛 =𝑔 𝑛 +h 𝑛
• Do not add children in the frontier if the node is already in the frontier or in the list of visited nodes (to avoid loopy paths)
• If the state of a given child is in the frontier
• If the frontier node has a larger 𝑔 𝑛 , place the child into the frontier and remove the node
with larger 𝑔 𝑛 from the frontier • Stop when a goal node is visited
A* Search – Completeness and Optimality
§ The A* search is complete and optimal if h 𝑛 is consistent
A* Search – Completeness and Optimality
§ The A* search is complete and optimal if h 𝑛 is consistent
§ A heuristic is said to be consistent (or monotone), if the estimate is always no greater than the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour
h𝑛 ≤𝑐𝑜𝑠𝑡𝑛,𝑛′ +h𝑛′
A* Search – Time and Space Complexity
§ The number of states for the A* search is exponential in the length of the solution, namely for constant step costs: 𝑂(𝑏&’)
§ When h∗ is the actual cost from root node to goal node, 𝜖 = )∗*) is the relative error )∗
A* Search – Time and Space Complexity
§ The number of states for the A* search is exponential in the length of the solution, namely for constant step costs: 𝑂(𝑏&’)
§ When h∗ is the actual cost from root node to goal node, 𝜖 = )∗*) is the relative error )∗
§ Space is the main issue with A*, as it keeps all generated nodes in memory, therefore A* is not suitable for many large-scale problems
A* Search – Summary
Let us summarise the performance of the A* search algorithm
§ Completeness: if the heuristic h(𝑛) is consistent, then the A* algorithm
is complete
§ Optimality: if the heuristic h(𝑛) is consistent, A* is optimal
A* Search – Summary
Let us summarise the performance of the A* search algorithm
§ Completeness: if the heuristic h(𝑛) is consistent, then the A* algorithm
is complete
§ Optimality: if the heuristic h(𝑛) is consistent, A* is optimal
§ Time complexity: 𝑂(𝑏&’), where 𝜖 is the relative error of the heuristic
A* Search – Summary
Let us summarise the performance of the A* search algorithm
§ Completeness: if the heuristic h(𝑛) is consistent, then the A* algorithm
is complete
§ Optimality: if the heuristic h(𝑛) is consistent, A* is optimal
§ Time complexity: 𝑂(𝑏&’), where 𝜖 is the relative error of the heuristic
§ Space complexity: 𝑂(𝑏’), since we keep in memory all expanded nodes and all nodes in the frontier
A* – Applications
§ A* has a large number of applications
§ In practice, the most common ones are in games and in robotics
§ A* is complete and optimal, given a consistent heuristic
§ However, A* has typically high time/space complexity, regardless of the
heuristic chosen
§ Heuristics have a considerable impact on the performance of informed search algorithms, and they can drastically reduce the time and space complexity in comparison to uninformed search algorithms
Aims of the Session
You should now be able to:
§ Describe the difference between uninformed and informed search § Understand the concept of a heuristic function in informed search
§ Analyse the performance of A* and apply the algorithm to solve search problems
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com