Solution for:


http://www.cs.iastate.edu/~cs572/assignments/assignment2.pdf

TA ,Jie Bao
Dept of Computer Science
Iowa State University
baojie@cs.iastate.ed
http://www.cs.iastate.edu/~baojie
Oct 24, 2002

Question 1
a)Proof: assume h is admissible, we also know that every arc is of unit cost. Since As adds at most b child nodes( b: branching factor) to the front of the list of nodes like DFS until it reaches the shallowest goal node( which is at depth d) O(bd) memory is needed.
b)As we know
- arcs are unit cost
- depth of cutoff (c) is increased by 1 at a time starting from 1
- h is admissible
Assume Ad terminated with a suboptimal goal g2 (i.e. f(g2)>f*(s))
But since Ad would have previously examined all nodes n where f(n)<f(g2), and f(n) never decreases along any path from the root to any node, then an optimal goal g1 would have already been expanded by Ad (because f(g1)<f(g2)) Thus Ad is admissible

Question 2
Your aim is to visit all nodes with as low total distance (cost) as possible.
Two ways to define your state space
1) Define nodes as status with both starting and goal node "dorm" 2) Define the visited path list as status, for example . ¡°A¡±, ¡°A->B->C¡±, ¡°A->E->C->B->F->G->A¡± Then you should define your h function. For Example, for 1)
H(n) = max {dist(n,x)} + min {dist (x,dorm)}
Where you x belongs to{unvisited nodes}

A rank on this h function may be:
g) Bidirectional A* search
c) A* search
d) Branch-and bound search with dynamic programming
e) Bidirectional best first (greedy) search
a) Best first search
b) Hillclimbing search
f) Bidirectional Hillclimbing search

For 2), you can use distance as path cost g and a optimistic h where always underestimate future path cost.
A possible rank is:
c) A* search
d) Branch-and bound search with dynamic programming
a) Best first search
b) Hillclimbing search
g) Bidirectional A* search
e) Bidirectional best first (greedy) search
f) Bidirectional Hillclimbing search

Bidirectional search works bad for such status space because all nodes at the bottom of the tree is goal nodes, which includes whole path information by it self, it’s trivial to use bidirectional search.
Rank may be different when you use different h and g function.

Question 3
Using contradiction

Monotone there implies consistent. If n2 is a successor of n1, then
h(n1) ?h(n2)<= k(n1,n2) (**)
where k(n1,n2) is the cost to go from n1 to n2

( You can see the proof in Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley )
Judea Pearl’s homepage http://bayes.cs.ucla.edu/jp_home.html

notice that k(s,n) = g*(n)
a) suppose the path found by A* with g(n)> g*(n), i.e. it’s not the cheapest path to n, we try to find a contradiction to the admissibility of A*
h(s)-h(n )<= k(s,n) = g*(n)
but g(n) > g*(n)
so h(s) ?h(n) < g(n)
now f(n) = g(n) + h(n)
g(n) > h(s) ?h(n)
=> f(n) > h(s) –h(n)+h(n) = h(s)
=> f(n) > h(s) + 0 = h(s) + g(s) = f(s)
=> f(n) > f(s) >= f*(s)
if n is a goal node A* would terminate and return a path of cost f(n)>f*(s). This is a contradiction to the admissibility of A*.
So if (s...n) is selected for extension, g(n) = g*(n)

b) Suppose there is a decreasing sequence, we try to find contradiction between triangular inequality and (**)
Assume the f-value of partial paths extended by A* do not form a non-decreasing sequence
Let p1 = (s...n1) , p2 = (s...n2)
P1 is extended before P2 but f(n1)>f(n2)
Obviously P2 could not have been on L when P1 was expanded because A* expends the lowest f value path.
Without the loss of generality, assume that n2 is a descendent of n1
f(n2) < f(n1)
=> g(n2) + h(n2) < g(n1) + h(n1)
=> h(n1) ?h(n2) > g(n2) ?g(n1)
by triangle inequality, g(n2) ?g(n1) >= k(n1,n2)
so h(n1) ?h(n2) > k(n1,n2)
which is contradict to (**)
Therefore, f-value of partial paths extended form a non-decreasing sequence.

Question 4
a) "without this check" means don't set infinity value when the memory is used up and the node is not a goal node.
if the memory is not enough, it's easy to find a loop by example. Set memory capacity to 2 and use the example tree on the text and see what will happens:



b) two steps

Lemma 1 for any node n, f(n) increases when n is completed
Proof: Induction on the depth of n. Any node not yet completed has finite f-cost. If depth (n) = MAX -1 and n is not completed, then when n is chosen for expansion, it is greater than some constant d, and consider node n with depth(n) = d. For any successor s in S(n), if f(s) = f(n) when s is generated, then s will be the deepest least-f-cost node in OPEN and n will not be expeande until either s is pruned or f(s) increases.
If s is pruned immediately after being generated, then since it is both the shallowest and deepest leaf with the highest and lowest f-cost, it is the only leaf in the search tree. But then the search tree is merely a path from start to s so d(s) = MAX and the result followings from the base case. If s is not pruned immediately, then it is chosen for expansion and will not be pruned until it is completed since MAX is large enough to hold the path from start to s and the only nodes generated while s is not completed are descendants of s.
By the induction hypothesis, when s is completed, f(s) will increase, so f(s) increases before the next successor of n is generated. Therefore, for every s in S(n), f(s)>f(n) when n is completed, and after BACKUP(n) is called, f(n) = min f(s) (on s ) increases.

Lemma 2: If a node n is pruned, it is not regenerated until the f-cost of some ancestor of n increases.
Proof. Let start-s1-...-sm-n be the path from start n and let si be the deepest ancestor of n that is pruned between the time n is pruned and regenerated. Then since SMA* cycles through all successors when expanding si, si+1 will not be regenerated until si is completed, at which time f(si) increases, by Lemma 1

Theorem: SMA* terminates.
Proof. If SMA* never generates MAX nodes, then no nodes are ever pruned, so SMA* behaves identically to A*, which terminates. Assume MAX nodes have been generated, so at every iteration exactly one node is generated and one node is pruned. Since only MAX nodes can be in the search tree at the start of an iteration, there are finitely many distinct trees (defined by the nodes in memory, their current f-costs, and the nest successor to be generated for each node in OPEN) that can be generated. Therefore, if SMA* does not terminate, it must enter a loop in which some search tree T is repeatedly generated. However, to generate T, any node n that is pruned from T must be regenerated, in which case by Lemma 2, the f-cost of some ancestor of n increases, so T cannot be regenerated. If only newly generated nodes are pruned, then each generated node is immediately pruned, so the same node in T will be expanded until it is completed, at which time its f-cost increases, and again T cannot be regenerated. Since a tree is never regenerated, SMA* does not enter an infinite loop and therefore terminates.

Question 5.


a) and b) actually are a same question.
You need to try to find all possible cased for junctions on polyhedra, for example



, along with all possible T, L, fork and arrow conjunctions in the textbook but eliminate those with "-" edges.

For five-conjunction or even higher planar conjunction, the possible configuration is similar to four-conjunction.

Discussion:
1)What happens for two objects touching at their peaks?
(Provided by Becca)


2) Is there T conjunctions?
If there is only one solid object with no concave edges, there will be no T conjunctions.
If there are more than one objects in the world, there are may be “T?conjunction when all objects have no concave edges. See the example below: (from [Prof. Ben-Avi] Natural Constraints. http://www.ee.cooper.edu/ courses/course_pages/past_courses/EE459/AIHO5/ )



Since the problem haven¡¯t specified if there is only object in that world or not, both claims for the validity or invalidity of T conjunction are accepted.

Question 6
Realizable examples:

possible labeling:


Unrealizable examples

Some more interesting and more complex examples:




Question 7
notice that Waltz¡¯s study is based a very simplified case
1- Every vertex is trihedral
2- Surface do not contain 0-width cracks
3- No shadows
4- The scene is views from a general viewing position.
So it can only handle with very restricted case not general scene interpretation problem. So the two assertions are not contradicted.

Question 8
Give examples that use those algorithms
- Hill climbing: when the domain is continuous and has only one maximum.
- Random search: If you have no good heuristic for the problem or the domain is discrete and not ordered with some
heuristic function. Eg. find the oldest student in ISU by randomly interview students in campus.
- Stochastic parallel hill climbing (like GA): if your evaluation function has many local maxima. Eg. find maximal point
on a 2-dimensional complex multi-peak function.
- Stochastic hill climbing: when it¡¯s not clear that your heuristic function returns the best choice and the solution is
not sensitive to the start point.
- Simulated annealing: when the evaluation function has many local maxima, but the ¡°depth¡± of local maxima is relatively
more sallow than the global maxima peak. (Then it makes sense to at noise on search direction)

Question 9
- You need to find a goal node (h(x)=0) in a AND-OR tree using A*. Give first 4 steps in your search

Setp0

Setp1

Setp2

Setp3

Setp4

 

Question 10
You need to formally define that status space and your constraints:
3-tuple (Z,C,D):
Z = {Q1,Q2,A3,Q4} where Qi represents the column into which the queen is placed.
D = {Di| i belongs {1,2,3,4} ^ Di = {1,2,3,4} }
C: (i <>j) => (Qi <> Qj) (No two queens can share the same row)
(i <> j) => (|Qi - Qj| <> |i-j|) (No two queens are on the same diagonal)
To show constraint propagation, you can write either in diagram (shown below, not complete) or in text (see study guide
Chapter 4, page 9 for example of constraint propagation in text)


Question 11
Based on your experience. Be sure to formally define Z: set of variables, C: set of constraints, and D: the domain of variables.

Some good examples:
- Cross puzzle
- Map coloring
- Airport plan scheduling
- Task assigning problem
- Unit-length job scheduling
- Assemly line Scheduling



[Return to Jie Bao's Homepage]