## Friday, April 9, 2010

### Improved Canonical Search

Here is an improved search. This the simplest version of the “canonical” graph search given in many A.I. textbooks.

I decided to code it using mostly sequences. There was no overriding technical reason for this, I simply wanted some practice using sequences in F#.

The code is split into three sections: a generic search function, a specific implementation and adapter using a simple node type, and a test.

The test graph is the same as that used in Patrick Henry Winston’s Artificial Intelligence (3rd edition, p.64ff). I added a disconnected node, H, so that I could test search failures. For convenience, here is a copy of it:

This test shows depth- and breadth-first searches. A* will come next, but will require some modification to the canonical search.

The code is below. There may be a bug or two, or a bad practice. I did test it using Winston’s examples, and it passed.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)
open System.Collections.Generic

//// Generic search.

type Path<'n> = int*'n*('n list)

// Search for a path.
let rec search<'n>
(isGoal:'n->bool)
(expand:'n->seq<'n*int>)
(merge:seq<Path<'n>>->seq<Path<'n>>->seq<Path<'n>>)
(paths:seq<Path<'n>>) =
match Seq.isEmpty paths with
| true -> Seq.empty
| false ->
match isGoal n with
| true -> paths
| false ->
search
isGoal
expand
merge
(merge
(Seq.skip 1 paths)
(Seq.map
(fun (n0,c0)->(c+c0,n0,n::nl))
(expand n)))

// Merge functions determine search behavior.
let breadthFirst s0 s1 = Seq.append s0 s1
let depthFirst s0 s1 = Seq.append s1 s0

//// Non-generic parts.

// A simple node.
type Node = {
id:string

// Base node for initialization.
let node = { id=""; links=[] }

let searchNodes =

// Prevents looping.
let hashLoop = new HashSet<string>()

// Goal test.
let testNode (g:Node) (n:Node) = g.id=n.id

// Expand a path.
let expandNode (n:Node) =
| false -> Seq.empty

(merge:seq<Path<Node>>->seq<Path<Node>>->seq<Path<Node>>)
(start:Node)
(goal:Node) =
hashLoop.Clear()
let sr =
search
(testNode goal)
expandNode
merge
(seq { yield (0,start,[]) })
match Seq.isEmpty sr with
| true -> None

// Define a graph.

let s = { node with id="s" }
let a = { node with id="a" }
let b = { node with id="b" }
let c = { node with id="c" }
let d = { node with id="d" }
let e = { node with id="e" }
let f = { node with id="f" }
let g = { node with id="g" }
let h = { node with id="h" }

// Print a path.
let printo (po:Path<Node> option) =
let rec printo0 (l:Node list) =
match l with
| [] -> printfn ""
| h::t ->
printf "%s " h.id
printo0 t
match po with
| None -> printfn "Search Failed"
| Some((c,n,nl)) -> printo0 (n::nl)

// Test some searches.

printo (searchNodes depthFirst s d)
printo (searchNodes depthFirst s g)
printo (searchNodes depthFirst s h)