	Rob Kremer
	Example Solution: Set Based/ Problem CPSC 433: Artifical Intelligence	Computer Science

Model

A: (S,T)

S: 2^F // power set of facts

F: {p: seq city | head p = startCity /\ last p = startCity /\ ∀ c:city • c ∈ p}

T: S x S
T = {(s, s') | ∃ A→B ∈ Ext • A ⊆ s /\ s' = (s-A) ∪ B}

Ext ⊆ {A→B | A,B ⊆ F}
Ext(A) = B where ∃i,j | i>0 /\ j>0 /\ i<|A|-2 /\ j<|A|-2 /\ i≠j • A_i = B_j /\ A_j = B_i /\ ∀k | k≠i /\ k≠j • A_k = B_k // swap

Process P: (A, Env, K)

Env: ({w_ij | w_ij: N∪⊥}, startCity: city) where start ∈ w_ij // The environment is the mapping of the cost of travel from city i to city j and the start city In symmetric problems, w_ij=w_ji.
Env = The set of w_ij Naturals for the particular problem. See Env in the example problem for an example.

K: S x Env → S
K(s,e) = (s-A) ∪ B where

_Wert

_select

_Wert

f_Wert: 2^F x 2^F x Env → Nat
f_Wert(A,B,Env) = // the total path length of B according to Env. (We're going for the smallest f_Wert.)

f_select:2^{2^Fx 2^F}x Env → 2^Fx 2^F
f_select= // choose the best .4 of A and randomly .1 from the remainder. Apply the following f_select operators with a probability of .3, .4, .3 respectively:
1. randomly select 2 facts, f1 and f2 from A. Randomly select a city, x (not the start city). Concatenate the pre-x path of f1, x, and the post-x path of f2 to create a new path f3. If there are cities, m, missing from f3, add them by finding neighbors of m and constructing a re-route between randomly-selected neighbours to include m.
2. randomly select a fact f, from A. If some city, c (other than the start city) that occurs more than once in f. For one of teh occurances of c in A, find the adjacent cities c1, and c2. If these cities have a direct connection in Env, remove their connections to c, and directly connect c1 to c2 in the path.
3. copy

Search Instance

Ins = (s₀, G)
s₀: S
s₀={<A,B,C,D,A>,<A,D,C,B,A>,<A,B,D,C,B,A>} // a randomly selected set of paths

G: s → {yes,no}
G(s) = S // in this problem, every F is a goal state by the definition of F. We are only interested in the smalest f_Wert.

Env = {(w_A,B, 10), (w_A,D, 15), (w_B,C, 7), (w_B,D, 4), (w_C,D, 6), (w_B,A, 10), (w_D,A, 15), (w_C,B, 7), (w_D,B, 4), (w_D,C, 6)} ∪ all others are ⊥.

s_goal ? s \/ no more expansions possible
s_goal= S

Example

s0 = {<A,B,C,D,A>=38,<A,D,C,B,A>=38,<A,B,D,C,B,A>=37}
chose: {<A,D,C,B,A>,<A,B,D,C,B,A>}
op1(<A,D,C,B,A>,<A,B,D,C,B,A>) →_D <A,D,C,B,A> //not very interesting...its the same as the first arg.
op2(<A,B,D,C,B,A>) →_B <A,D,C,B,A> // hmm.. the same as the 2nd s0.
op3(<A,B,D,C,B,A>) → <A,B,D,C,B,A>

s1 = {<A,D,C,B,A>=38, <A,D,C,B,A>=38, <A,B,D,C,B,A>=37}
...

It turns out that <A,B,D,C,B,A> is optimal, and just happened to be in my s0...

CPSC 433: Arficial Intelligence

Last updated 2013-09-01 15:45

Rob Kremer