CSW 4701- Artificial Intelligence Search Programs in LISP (Comment Here we detail the bidirectional search procedure for state spaces that are trees: (loop (print "Please tell me the starting position:") (setf state (read)) (setf SI (list state nil)) (print "Please tell me the goal state you wish to find:") (setf goal (read)) (setf SQ goal) (bidirect SI SQ 'successor-function-forward 'successor-function-backward ) (comment Ok, now the implementation code follows.) (defun bidirect (si sg succsf succsb) (let ( ( openf (list (list si nil nil) ) ) ;note the inner list is a node ( openb (list (list sg nil nil) ) ) ;note the inner list is a node ;note for trees, we don't need a closed list ( nf nil ) ( nb nil ) ( daughtersf nil ) ( daughtersb nil ) ( jointpath nil )) (loop (cond ((or (null openf) (null openb)) ;Have we exhausted the search space? (print "Sorry, the problem posed is insoluable") (return nil))) (setf nf (pop openf)) ;Ok, remove the first node and update open ;we don't need a closed list for trees (cond ((setf jointpath (member (state nf) openb ) ) ;have we found our node in the backward frontier? (print "Great. I found a solution. Here it is:") (return (success jointpath)) )) (setf daughtersf (apply succsf nf)) ;here we generate new derived states (setf openf (append openf daughtersf)) ;open is used as a QUEUE, thus its bfs. (setf nb (pop openb)) ;Ok, remove the first node and update open (cond ((setf jointpath (member (state nb) openf ) ) ;have we found our state in the forward fronteir? (print "Great. I found a solution. Here it is:") (return (success jointpath)) )) (setf daughtersb (apply succsb nb)) ;here we generate new derived states (setf openb (append openb daughtersb)) ;open is used as a QUEUE, thus its bfs. ) ;closes loop ) ;closes let ) ;closes defun ) ;closes main loop