COMP30024 Artificial Intelligence
Week 4 Problem Sheet
Weekly Topic Review
Last week you dealt with uninformed search methods, which are only able to generate successors and identify goals. This week we will be working with informed search methods, which incorporate domain knowledge to prioritize exploration of more promising nodes.
Copyright By PowCoder代写 加微信 powcoder
Domain knowledge is imparted based on the evaluation function f(σ), which orders nodes in the frontier F based on desirability of expansion: i.e. the search algorithm chooses the next node to expand as σ∗ = argminσ∈F f(σ). In the following let Σ be the set of all possible nodes.
One important component of the evaluation function is the heuristic function h : Σ → R+, an estimate of the cost of the optimal path from the current state to the goal. These are required to be non-negative and have h(goal) = 0 but are otherwise arbitrary, problem-specific functions. As the name implies, designing an effective heuristic function is as much an art as it is a science. Intuitively, good heuristics avoid exploration of non-promising regions of the graph and effectively reduce the branching factor of search. There are two1 properties of heuristics which you should be aware of and will help guide your design of an effective heuristic:
• Admissibility:
h(σ) ≤ min(cost(σ → goal)) = h∗(σ), ∀ σ ∈ Σ
An admissible heuristic defines an optimistic cost estimate; it never overestimates the cost to the goal. Note sacrificing admissibility does not completely void the heuristic function – you lose guarantees of optimality, but non-admissible heuristics may allow your search method to run faster as less nodes in the priority queue need to be expanded – in general there is a tradeoff between speed/optimality.
• Consistency/Monotony:
h(σ) ≤ cost(σ, σ′, A) + h(σ′) ∀ σ ∈ Σ, A(σ) = σ′
This is the triangle inequality applied to costs of graph states.2
1There is a third property, you should know, domination, which is not required here but intuitively states we want admissible h as close to the optimal solution h∗ as possible, provided h(σ) ≤ h∗(σ) ∀ σ ∈ Σ.
2Here cost(σ,σ′,A) denotes the cost to the agent of taking action A in state σ to end up in state σ′. 1
A∗ search is an informed search method which ranks nodes in the frontier by the estimated cost of the optimal path from root to goal passing through each node. i.e. the evaluation function is:
f(σ) = cost(start → σ) + (est.) cost(σ → goal) = g(σ) + h(σ)
This is both complete and (graph) optimal, provided the heuristic is consistent. Note that as nodes are ranked based on f(σ), the search efficiency is highly dependent on the heuristic quality. For a poor heuristic A∗ may completely enumerate the search space and has a time complexity of O(bd).
1. Heuristics [T] Recall in greedy best-first search (GBFS) we expand the node estimated to be
the closest to the goal state, i.e. the evaluation function f(σ) = h(σ).
(a) Suppose that we run a greedy best-first (graph) search algorithm with the heuristic function for node σ set to the negative of the path cost, h(σ) = −g(σ). What sort of search will the greedy search emulate? Hint: simulate this for a few iterations on the graph in Figure 2.
(b) The heuristic path algorithm is a best-first search where the evaluation function contains a relative weighting factor w: f(σ) = (2 − w)g(σ) + wh(σ).
(i) Whatkindofsearchdoesthisperformforw=0,w=1,andw=2?
(ii) For what values is it optimal, assuming that the heuristic h is admissible? Hint:
recall the condition for optimality of A∗.
2. Generation vs. Expansion [T] Recall that state generation refers to the creation of the data structure σ representing the state, whereas state expansion refers to the generation of all children of the present node.
(a) Should informed search algorithms apply the goal test upon state generation or state expansion, in order for the resulting search to be optimal? Does it make a difference from uninformed search algorithms?
(b) Run UCS on the graph in Figure 1, performing the goal test on state expansion. Compare this against performing the goal test on state generation and compare the search paths found.
3. Romanian Road Ramble [T] This year’s COMP30024 class excursion is to sunny Romania. Due to the rising price of gas, Chris has enlisted your help to find the optimal path between stops along the trip. Trace the operation of an A∗ search from Lugoj to Pitesti from the map of Romania in Figure 2. At each stage record the frontier and explored set. Represent each node as: σ = (State, Parent σP , g(σ), h(σ)), and use the following straight-line distance tabulated heuristic function:
Figure 1: Simplified road map of part of Romania. Adapted from Russell and Norvig (2010).
City h(σ)(km)
Timisoara 320
Mehadia 280
Drobeta 240 Craiova 138
What is the final path found by A∗? Is this path optimal?
4. Gridlock [T] n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n
grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that startsin(i,1)mustendupin(n−i+1,n).Oneachtimestep,everyoneofthenvehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.
(a) Find an expression for the size of the state space in terms of n.
(b) Find an expression for the branching factor in terms of n.
(c) Give a (non-trivial) admissible heuristic hi for the number of moves it takes for a single vehicle i starting in (xi, yi) to its goal state, (n − i + 1, n).
(d) Is i hi an admissible heuristic for this problem? How about max{h1, . . . , hn} or min{h1,…,hn}?
References
Stuart Russell and . Artificial Intelligence: A Modern Approach, 3rd Ed. Prentice-Hall, 2010.
Figure 2: Simplified road map of bigger part of Romania. Adapted from Russell and Norvig (2010).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com