EEL5840: ELEMENTS OF MACHINE INTELLIGENCE

Fall 2001

 

LISP PROJECT

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Suman Srinivasan

 

II. Wall Following/Obstacle Avoiding/Obstacle Contouring Robot

 

Statement of the problem

To write a general LISP program to test the Grid-World Robots of Chapters 2,5 of Nilsson.

 

Inputs include:

a.       Size of the grid

b.      Number and location of the boundaries

c.       Sensory input and feature vector set

d.      Production rule set used to simulate robot behavior

 

To generate LISP programs for the following cases:

a.       To generate robot motion for the wall-following system on page 28

b.      The system on page 73

c.       Problem 2 in Exam 1

d.      To do obstacle avoidance with a robot

                                I.      Whose sensor set is {s1, s2, s3, s4, s5, s6, s7, s8}

                             II.      Whose sensors are defective and can only sense {s1, s3, s5, s7}

                           III.      Whose sensors are defective and can only sense {s2, s4, s6, s8}

e.       Same as (d) but with obstacle-countouring

 

Approach

In order to program the robot required for the cases (a) – (e), I first write a general purpose robot program that can perform the basic operations that the robot needs to do, i.e.,

1.      Move a single step north, east, south or west

2.      Move according to conditions specified

 

Then for each case, specific programs are written that provide the robot with the following information (user input as required by the question):

a.         The sensor values

b.         The feature vectors

c.         The production rules

d.         The grid size and boundary location

 

I have followed Nilsson’s approach in most cases:

 

My specific approach to each part is detailed below:

 

Part A:

·        Sensor set {s1, s2, s3, s4, s5, s6, s7, s8}

·        Feature vectors {x1, x2, x3, x4} as follows:

X1 = s2 OR s3

X2 = s4 OR s5

X3 = s6 OR s7

X4 = s8 OR s1

·        Production rules (representing x1 by /x1)

x4 (/x1) ® North

x3 (/x4) ® West

x2 (/x3) ® South

x1 (/x2) ® East

1 ® North

 

Part B:

·        Defective sensor set {s2, s4, s6, s8}

·        Feature vectors {x1, x2, x3, x4} as follows:

w2 = s2

w4 = s4

w6 = s6

w8 = s8

w1 = (old w2 = 1 AND state = east)

w3 = (old w4 = 1 AND state = south)

w5 = (old w6 = 1 AND state = west)

w7 = (old w8 = 1 AND state = north)

·        Production rules

w2 (/w4) ® east

w4 (/x6) ® south

w6 (/w8) ® west

w8 (/w2) ® north

w1 ® north

w3 ® east

w5 ® south

w7 ® west

1 ® North

 

Part C

            This is the same as Part B. So the same sensor and feature vector set can be used.

 

Part D

            Obstacle Avoidance for my robot uses a very simple algorithm:

                        s2 ® South

            s4 ® West

            s6 ® North

                        s8 ® North

            1 ® Wall following

For part (1), the wall following procedure would be as in part (a). For part (3), the wall following procedure would be as in part (b).

 

Part E

Obstacle contouring uses the same procedure as wall following. The only condition would be that the robot would have to start next to the obstacle rather than next to the wall.

For part (1), the procedure would be as in part (a). For part (3), the procedure would be as in part (b).

 

Robot Program

Algorithm

The algorithm of the robot program is as follows:

1.      Set state, counter variables to initial values.

2.      Print out initial location of the robot 

3.      Apply production rules, and move

4.      Print out location of robot

5.      Increment counter

6.      If counter equals the number of iterations,          then STOP

Else Loop

 

Functions

The robot program consists of the following functions:

 

Function Name
Arguments

Returns

What function does

At_xy()

Pos-x, pos-y

0 or 1

Returns the value (0 or 1) at position [pos-x, pos-y] in the grid.

Aor()

O1, o2

0 if both o1 and o2 are 0;

1 otherwise

Arithmetic OR – does a Boolean OR on the inputs (which are binary)

Aand()

A1, a2

1 if both a1 and a2 are 1;

0 otherwise

Arithmetic AND – does a Boolean AND on the inputs

Anot()

N

1 if n=0;

0 if n=1

Arithmetic NOT – binary negation of input

N()

 

 

Moves the robot one step north if possible, otherwise returns an error

S()

 

 

Moves the robot one step north if possible, otherwise returns an error

W()

 

 

Moves the robot one step north if possible, otherwise returns an error

E()

 

 

Moves the robot one step north if possible, otherwise returns an error

Move()

 

 

Moves the robot as many times as requested by user input; also displays [x, y] coordinates of the robot.

 

User Input Programs

 

Functions

Each of the user input program consists of the following functions:

 

Function Name
Arguments

Returns

What function does

Sensor input functions – si()

 

 

Returns the value of the grid at the particular cell around the robot

The feature vector set – xi() or wi()

 

 

Logical function of sensor values or older feature vectors

Rules()

 

 

Production rules specifying the robot motion

 

Variables

All variables are global and are used across both the robot function and user input.

Varible Name
Used for

X

x coordinate of the robot location

Y

y coordinate of the robot location

State

Direction the robot is currently moving (Values: north, south, east, west)

I

Counter variable

 

Size

Grid size with coordinates starting from 0

 

 

Grid-size

Actual grid size

Grid

2-dimensional list containing the location of boundaries (in binary)

 

LISP Programs

ROBOT.LSP

; Returns the object (0 or 1) present at co-ordinates

(defun at_xy (pos-x pos-y) (nth pos-x (nth pos-y grid)))

 

; Arithmetic OR – needed to combine 0s and 1s

(defun aor (o1 o2) (cond

  ( (eq (+ o1 o2) 0)      0 )

  ( t                     1 )

))

 

; Arithmetic AND

(defun aand (a1 a2) (* a1 a2))

 

; Arithmetic NOT

(defun anot (n) (cond

  ( (eq n 0)     1 )

  ( (eq n 1)     0 )

))

 

; Move north

(defun n() (prog()

  (if (< y 2)      'cannot_move_north

                   (setf y (1- y)) )

  (setf state 'north)

))

 

; Move south

(defun s() (prog()

  (if (> y (- size 2))      'cannot_move_south

                            (setf y (1+ y)) )

  (setf state 'south)

))

 

; Move west

(defun w() (prog()

  (if (< x 2)      'cannot_move_west

                   (setf x (1- x)) )

  (setf state 'west)

))

 

; Move east

(defun e() (prog()

  (if (> x (- size 2))      'cannot_move_east

                            (setf x (1+ x)) )

  (setf state 'east)

))

 

; The runtime function – applies the rules and prints

; the position the robot is at.

(defun move() (prog (i)

     ; Sets size to 1 – grid_size: so that coordinates start at 0

     (setf size (1- grid-size))

     ; Set state to 0

     (setf state 0)

     (setf i 0)

     ; Print initial location

     (print (list x y))

LOOP

     ; Apply production rules

     (rules)

     ; Print current location

     (print (list x y))

     (setf i (1+ i))

     ; If iterations are complete, return T…

     (if (> i iterations) (return t))

     ; … else continue

     (go LOOP)

))    

 

 

 


For parts (a), (b) and (c): the cells, starting position and robot’s motion, according to my input would be:

 
 
 

 

 

 

 

 

 

 

 

 

 

 

Cells the robot cannot occupy
 

 

 
R

 

 

 

 

 

 

 

 

 

 

 

R             The robot’s starting position
 

 

 

 

 

 

 

 

Motion of the robot
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(a)

PART-A.LSP

; The set s – points around the robot

(defun s1() (at_xy (1- x) (1- y)))

(defun s2() (at_xy     x  (1- y)))

(defun s3() (at_xy (1+ x) (1- y)))

(defun s4() (at_xy (1+ x)     y ))

(defun s5() (at_xy (1+ x) (1+ y)))

(defun s6() (at_xy     x  (1+ y)))

(defun s7() (at_xy (1- x) (1+ y)))

(defun s8() (at_xy (1- x)     y ))

 

; The feature vector x

(defun x1() (aor (s2) (s3)))

(defun x2() (aor (s4) (s5)))

(defun x3() (aor (s6) (s7)))

(defun x4() (aor (s8) (s1)))

 

; Rules that the robot follows

(defun rules() (cond

     ( (eq (aand (x4) (anot (x1))) 1)           (n) )

     ( (eq (aand (x3) (anot (x4))) 1)           (w) )

     ( (eq (aand (x2) (anot (x3))) 1)           (s) )

     ( (eq (aand (x1) (anot (x2))) 1)           (e) )

     ( t                                        (n) )                  

))

 

; User variables

(setf grid-size 8)

(setf iterations 25)

(setf grid '((1 1 1 1 1 1 1 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 1 1 1 1 1 1 1)

))

(setf x '2 y '2)

 

OUTPUT

> (load "robot.lsp")

; loading robot.lsp

T

> (load "part-a.lsp")

; loading part-a.lsp

T

> (move)

 

(2 2)

(2 3)

(3 3)

(4 3)

(5 3)

(5 2)

(5 1)

(6 1)

(6 2)

(6 3)

(6 4)

(6 5)

(6 6)

(5 6)

(5 5)

(4 5)

(3 5)

(2 5)

(2 6)

(1 6)

(1 5)

(1 4)

(1 3)

(1 2)

(1 1)

(2 1)

(2 2)

T

 

(b)

PART-B.LSP

; Variables for memory operations

(setf o_w2 '0 o_w4 '0 o_w6 '0 o_w8 '0 o_state '0)

 

; The robot’s sensor values

(defun s2() (at_xy     x  (1- y)))

(defun s4() (at_xy (1+ x)     y ))

(defun s6() (at_xy     x  (1+ y)))

(defun s8() (at_xy (1- x)     y ))

 

; Rules the robot follows

(defun rules() (prog()

  ; w2, w4, w6, w8 – Current sensor values

  (setf w2 (s2))

  (setf w4 (s4))

  (setf w6 (s6))

  (setf w8 (s8))

  ; w1, w3, w5, w7 – Memory based values

  (setf w1 (and (eq o_w2 1) (eq o_state 'east)))

  (setf w3 (and (eq o_w4 1) (eq o_state 'south)))

  (setf w5 (and (eq o_w6 1) (eq o_state 'west)))

  (setf w7 (and (eq o_w8 1) (eq o_state 'north)))

  (cond

     ( (eq (aand w2 (anot w4)) 1)           (e) )

     ( (eq (aand w4 (anot w6)) 1)           (s) )

     ( (eq (aand w6 (anot w8)) 1)           (w) )

     ( (eq (aand w8 (anot w2)) 1)           (n) )

     ( w1                                   (n) )

     ( w3                                   (e) )

     ( w5                                   (s) )

     ( w7                                   (w) )

     ( t                                    (n) )                   

  )

  ; Used to remember current state

  (setf o_w2 w2)

  (setf o_w4 w4)

  (setf o_w6 w6)

  (setf o_w8 w8)

  (setf o_state state)

))

 

; User variables

(setf grid-size 8)

(setf iterations 25)

(setf grid '((1 1 1 1 1 1 1 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 1 1 1 1 1 1 1)

))

(setf x '2 y '2)

 

OUTPUT

> (load "robot.lsp")

; loading robot.lsp

T

> (load "part-b.lsp")

; loading part-b.lsp

T

> (move)

 

(2 2)

(2 3)

(3 3)

(4 3)

(5 3)

(5 2)

(5 1)

(6 1)

(6 2)

(6 3)

(6 4)

(6 5)

(6 6)

(5 6)

(5 5)

(4 5)

(3 5)

(2 5)

(2 6)

(1 6)

(1 5)

(1 4)

(1 3)

(1 2)

(1 1)

(2 1)

(2 2)

T

 

 


(c)

The solution for Problem 2 in Exam 1 is the same as the solution for Part B, i.e., the robot that can only sense {s2, s4, s6, s8}.

 

 

 


(d) Obstacle avoidance

For part (d) (1, 2, 3): the cells, starting position and robot’s motion, according to my input would be (as mentioned before, the robot does extremely simple obstacle avoidance! That is why it keeps cycling in the indicated place):

 
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cells the robot cannot occupy
 

 

 
 

 

 

 

 

 

 

 

 

 

 

 

R             The robot’s starting position
 

 

 

 

 

 

R

 

Motion of the robot
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(1)

PART-D1.LSP

(defun s1() (at_xy (1- x) (1- y)))

(defun s2() (at_xy     x  (1- y)))

(defun s3() (at_xy (1+ x) (1- y)))

(defun s4() (at_xy (1+ x)     y ))

(defun s5() (at_xy (1+ x) (1+ y)))

(defun s6() (at_xy     x  (1+ y)))

(defun s7() (at_xy (1- x) (1+ y)))

(defun s8() (at_xy (1- x)     y ))

 

(defun x1() (aor (s2) (s3)))

(defun x2() (aor (s4) (s5)))

(defun x3() (aor (s6) (s7)))

(defun x4() (aor (s8) (s1)))

(defun rules() (cond

     ( (eq (s2) 1)                              (s) )

     ( (eq (s8) 1)                              (e) )

     ( (eq (s6) 1)                              (n) )

     ( (eq (s4) 1)                              (w) )

     ( (eq (aand (x4) (anot (x1))) 1)           (n) )

     ( (eq (aand (x3) (anot (x4))) 1)           (w) )

     ( (eq (aand (x2) (anot (x3))) 1)           (s) )

     ( (eq (aand (x1) (anot (x2))) 1)           (e) )

     ( t                                        (n) )

  )

  (setf o_state state)

)

 

(setf grid-size 8)

(setf iterations 20)

(setf grid '((1 1 1 1 1 1 1 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 1 1 1 1 1 1 1)

))

(setf x '5 y '4)

 

OUTPUT

> (load "robot.lsp")

; loading robot.lsp

T

> (load "part-d1.lsp")

; loading part-d1.lsp

T

> (move)

 

(5 4)

(5 3)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

T

 

(2)

A robot that can sense only {s1, s3, s5, s7} cannot do obstacle avoidance since it cannot see the cells directly in front of it, i.e., the cells it needs to move to.

 

(3)

PART-D3.LSP

(setf o_w2 '0 o_w4 '0 o_w6 '0 o_w8 '0 o_state '0)

 

(defun s2() (at_xy     x  (1- y)))

(defun s4() (at_xy (1+ x)     y ))

(defun s6() (at_xy     x  (1+ y)))

(defun s8() (at_xy (1- x)     y ))

 

(defun rules() (prog()

  (setf w2 (s2))

  (setf w4 (s4))

  (setf w6 (s6))

  (setf w8 (s8))

  (setf w1 (and (eq o_w2 1) (eq o_state 'east)))

  (setf w3 (and (eq o_w4 1) (eq o_state 'south)))

  (setf w5 (and (eq o_w6 1) (eq o_state 'west)))

  (setf w7 (and (eq o_w8 1) (eq o_state 'north)))

  (cond

     ( (eq (s2) 1)                          (s) )

     ( (eq (s8) 1)                          (e) )

     ( (eq (s6) 1)                          (n) )

     ( (eq (s4) 1)                          (w) )

     ( (eq (aand w2 (anot w4)) 1)           (e) )

     ( (eq (aand w4 (anot w6)) 1)           (s) )

     ( (eq (aand w6 (anot w8)) 1)           (w) )

     ( (eq (aand w8 (anot w2)) 1)           (n) )

     ( w1                                   (n) )

     ( w3                                   (e) )

     ( w5                                   (s) )

     ( w7                                   (w) )

     ( t                                    (n) )                  

  )

  (setf o_w2 w2)

  (setf o_w4 w4)

  (setf o_w6 w6)

  (setf o_w8 w8)

  (setf o_state state)

))

 

; USER INPUT

(setf grid-size 8)

(setf iterations 25)

(setf grid '((1 1 1 1 1 1 1 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 1)

             (1 0 0 1 1 0 0 1)

             (1 1 1 1 1 1 1 1)

))

(setf x '5 y '4)

 

OUTPUT

> (load "robot.lsp")

; loading robot.lsp

T

> (load "part-d3.lsp")

; loading part-d3.lsp

T

> (move)

 

(5 4)

(5 3)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

(5 2)

(6 2)

T

 

 

 

 


(e) Obstacle contouring

 

For part (e) (1, 2, 3): the cells, starting position and robot’s motion, according to my input would be:

 
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cells the robot cannot occupy
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R             The robot’s starting position
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Motion of the robot
 

 

 

 

 

R

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(1)

PART-E1.LSP

(defun s1() (at_xy (1- x) (1- y)))

(defun s2() (at_xy     x  (1- y)))

(defun s3() (at_xy (1+ x) (1- y)))

(defun s4() (at_xy (1+ x)     y ))

(defun s5() (at_xy (1+ x) (1+ y)))

(defun s6() (at_xy     x  (1+ y)))

(defun s7() (at_xy (1- x) (1+ y)))

(defun s8() (at_xy (1- x)     y ))

 

(defun x1() (aor (s2) (s3)))

(defun x2() (aor (s4) (s5)))

(defun x3() (aor (s6) (s7)))

(defun x4() (aor (s8) (s1)))

(defun rules() (cond

     ( (eq (aand (x4) (anot (x1))) 1)           (n) )

     ( (eq (aand (x3) (anot (x4))) 1)           (w) )

     ( (eq (aand (x2) (anot (x3))) 1)           (s) )

     ( (eq (aand (x1) (anot (x2))) 1)           (e) )

     ( t                                        (n) )                  

))

 

(setf grid-size 9)

(setf iterations 25)

(setf grid '((1 1 1 1 1 1 1 1 1)

             (1 0 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 0 1)

             (1 0 0 1 1 1 0 0 1)

             (1 0 0 1 1 1 0 0 1)

             (1 0 0 1 1 1 0 0 1)

             (1 0 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 0 1)

             (1 1 1 1 1 1 1 1 1)

))

(setf x '5 y '6)

 

OUTPUT

> (load "robot.lsp")

; loading robot.lsp

T

> (load "part-e1.lsp")

; loading part-e1.lsp

T

> (move)

 

(5 6)

(6 6)

(6 5)

(6 4)

(6 3)

(6 2)

(5 2)

(4 2)

(3 2)

(2 2)

(2 3)

(2 4)

(2 5)

(2 6)

(3 6)

(4 6)

(5 6)

(6 6)

(6 5)

(6 4)

(6 3)

(6 2)

(5 2)

(4 2)

(3 2)

(2 2)

(2 3)

T

 

(2)

As explained in (d) (2), a robot that can only sense {s1, s3, s5, s7} cannot be used for obstacle contouring since it is unable to see the cells that it had to move to.

 

(3)

PART-E3.LSP

(setf o_w2 '0 o_w4 '0 o_w6 '0 o_w8 '0 o_state '0)

 

(defun s2() (at_xy     x  (1- y)))

(defun s4() (at_xy (1+ x)     y ))

(defun s6() (at_xy     x  (1+ y)))

(defun s8() (at_xy (1- x)     y ))

 

(defun rules() (prog()

  (setf w2 (s2))

  (setf w4 (s4))

  (setf w6 (s6))

  (setf w8 (s8))

  (setf w1 (and (eq o_w2 1) (eq o_state 'east)))

  (setf w3 (and (eq o_w4 1) (eq o_state 'south)))

  (setf w5 (and (eq o_w6 1) (eq o_state 'west)))

  (setf w7 (and (eq o_w8 1) (eq o_state 'north)))

  (cond

     ( (eq (aand w2 (anot w4)) 1)           (e) )

     ( (eq (aand w4 (anot w6)) 1)           (s) )

     ( (eq (aand w6 (anot w8)) 1)           (w) )

     ( (eq (aand w8 (anot w2)) 1)           (n) )

     ( w1                                   (n) )

     ( w3                                   (e) )

     ( w5                                   (s) )

     ( w7                                   (w) )

     ( t                                    (n) )                  

  )

  (setf o_w2 w2)

  (setf o_w4 w4)

  (setf o_w6 w6)

  (setf o_w8 w8)

  (setf o_state state)

))

 

; USER INPUT

(setf grid-size 9)

(setf iterations 25)

(setf grid '((1 1 1 1 1 1 1 1 1)

             (1 0 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 0 1)

             (1 0 0 1 1 1 0 0 1)

             (1 0 0 1 1 1 0 0 1)

             (1 0 0 1 1 1 0 0 1)

             (1 0 0 0 0 0 0 0 1)

             (1 0 0 0 0 0 0 0 1)

             (1 1 1 1 1 1 1 1 1)

))

(setf x '5 y '6)

 

OUTPUT

> (load "part-e3.lsp")

; loading part-e3.lsp

T

> (move)

 

(5 6)

(6 6)

(6 5)

(6 4)

(6 3)

(6 2)

(5 2)

(4 2)

(3 2)

(2 2)

(2 3)

(2 4)

(2 5)

(2 6)

(3 6)

(4 6)

(5 6)

(6 6)

(6 5)

(6 4)

(6 3)

(6 2)

(5 2)

(4 2)

(3 2)

(2 2)

(2 3)

T

II. A* Search

 

I made an attempt to program the A* search for the 8 puzzle and 15 puzzle in LISP. Unfortunately, as I ran out of time towards the end of the semester, I was unable to complete the program. I have included my algorithm and what I have managed to complete.

Statement of the problem

To write a general LISP program to implement A* search, where both the heuristic function h(n) and fixed cost function g(n) are specified by the user.

a)      To test the program with the 8 puzzles used in class

b)      Specify a heuristic function and use it to solve a given 8 puzzle

c)      Specify a heuristic function and use it to solve a given 15 puzzle

 

Approach:

The representation of the puzzle would be as shown in the example:

            ((2 8 3) (0 1 4) (5 6 7)) would be the start node’s puzzle representation

 

I would use what I call a “representation list”, which would contain the required fields needed to store all the required data associated with the puzzle as follows:

            (<puzzle> <id> <pointer> <depth> <f(n)>)

where

 

Tag
Used for

puzzle

The 2-dimensional list containing the puzzle

id

A unique ID to identify the node (to be used to backtrack from goal node)

pointer

Points to the ID of the parent node

depth

Indicates depth of the node in the tree. Would be used to calculate g(n)

f(n)

The cost function f(n) of the node

 

E.g.: ( ((2 8 3) (0 1 4) (5 6 7)) 1 0 0 8 ) would be the start node’s representation.

 

Thus, CLOSED and OPEN would be lists consisting of the representation lists of the puzzles.

E.g.:     CLOSED:        (  ( ((2 8 3) (0 1 4) (5 6 7)) 1 0 0 8 )

                     ( ((0 8 3) (2 1 4) (5 6 7)) 2 1 1 9 ) )

 

Algorithm

 

The algorithm for a-star() :

1.      Initialize start and goal nodes, and construct the start node’s representation list.

2.      Set OPEN = list of representation list of start node, CLOSED = empty list

3.      If OPEN = nil, exit with failure

4.      Move the first list in OPEN to CLOSED

5.      If first list in CLOSED is the goal node, then print the path to the goal node.

6.      Generate successors of the first list in CLOSED, calculate their id, pointer, depth and f(n), and add them to OPEN.

7.      Sort OPEN according to increasing f(n) values.

8.      Go to step (3).

 

The program for a-star() :

(setf start '((2 8 3) (0 1 4) (5 6 7)))

(setf goal '((1 2 3) (4 5 6) (7 8 0)))

(setf OPEN (list (append (list start) (1 0 0 0))))

(setf CLOSED nil)

 

(defun a-star () (prog()

LOOP

   ; If OPEN = nil, exit with failure

   (if (null OPEN) (return nil))

 

   ; Move first of OPEN to CLOSED

   (setf CLOSED (first OPEN))

   (setf OPEN (rest OPEN))

 

   ; If the first list in CLOSED is the goal…

   ; …print the path to the goal  

   (if (eq (first (first CLOSED)) goal)

((print_success) (return T)))

 

   ; Generate successors

   (generate_successors)

 

   ; Sort the list OPEN

   (sort_open)

   (goto LOOP)

))

 

The algorithm for print_success() :

1.      Set ‘ptr’ to pointer of goal node

2.      Set a temporary list to puzzle configuration of the goal node

3.      Search CLOSED for parent of the node.

4.      If the parent is the start node:

a.       Reverse the temporary list.

b.      Print it out

else,

a.         Append the parent to the temporary list.

b.         Set ‘ptr’ to the pointer of this node

c.         Goto step (3).

 

The program for print_success() :

      (defun print_success () (prog (lis)

   ; Set the pointer to parent of goal node

   (setf ptr (third (first CLOSED)))

 

   ; Add the puzzle arrangement of the goal node to lis

   (setf lis (first (first CLOSED)))

   (setf l (length CLOSED))

L1

   ; If start node is found, reverse lis, and print the nodes

   (if (eq ptr 0) (prog (true_lis)

       (setf true_lis (reverse lis))

       (dolist element true_lis i

            (print element))

       (return T)

   ))

 

   ; If the parent is found, add it to lis, and continue search

   (if (eq (second(nth CLOSED i)) ptr) (

       (setf lis (append lis (first (nth CLOSED i))))

       (setf ptr (third (nth CLOSED i)))

       (setf i 1)

       (goto L1)

   )

   (   (setf i (1+ i))

       (goto L1)

   )

))

 

 

The algorithm for generate_successors() :

1.      Get the puzzle arrangement, ID, and depth of the node

2.      Locate the blank in the arrangement, and move it left, right, up and down (if these are possible)

3.      Calculate the ID, pointer, depth and f(n) for these arrangements, and create a list SUCCESSOR containing the representation list of the successors.

4.      Check if each element of the SUCCESSOR list is a member of either OPEN or CLOSED. If it not, then add it to OPEN.