Complete Program in LISP

You will recall the lecture discussions of the Blocks World, State-Space Search, and Rule-Based Systems (RBSs). In this project, we will build a Blocks World RBS planner that will take a Blocks World rule-set, a starting state and a goal state and construct a sequence of gripper operations that will convert the starting state into the goal state. It will also employ a reasonable heuristic function to avoid expanding too many nodes in the search. We will take the rule-set from Rules 4-7 Luger, section 8.4. We will assume we've upgraded to the "Smart Gripper", which can move to the correctly named block (eg, via sensory input). Thus, we have the 4 Blocks World Rules in our Rule Base System (RBS). Each rule represents a set of potential operations on an RBS state in a State-Space Search for a goal state. One sample Start State (SS) is from Luger Fig 2.3, page 67. Another sample SS is from Luger Fig 8.18, age 315. As a heuristic function, we will use an (unordered) Hamming distance of WMEM assertions vs grounded rule pre-condition expressions (exprs). One sample goal state (GS) will be to get the blocks into an alphabetic tower with A on top, B next down, etc. Another sample GS is to get the blocks in a tower in reverse alphabetic order, with A on the bottom, B next up, etc. What we particularly want, however, is a plan that is, a list of the states on a path from SS to GS, or more particularly, a list of the grounded rules (which are gripper "move" operations) connecting one state to the next. Moreover, during processing, a log will be printed for each state "expanded" indicating the mom state (by name is sufficient), the grounded-rules (to be discussed in lecture) generated along with their unifiers, the child state generated from each grounded-rule, and its Hamming distance to the GS, and the updated RBS search state of the Open and Closed lists. A sample lispified set of rules will be provided and discussed along with a few infrastructure functions to help out.

Heuristic Function, F(N) = G(N) + H(N)

We will use an unordered Hamming distance between two lists of exprs. The distance value increments by one for each expr in the first list that is not in the second, and also by one for distance between to lists of exprs. The distance value increments by one for each expr in the second list that is not in the first. For example: this Hamming distance between the groups

((r b c) (r c d) (s b) (p e))

and

((r c b) (r c d) (s b) (p a) (p e))

is 5 because these 5 exprs are not common to both groups:

(r b c) (p e) (r c b) (r c d) (p a).

Goal Completion

Once your search reaches the goal state, it should stop.