Lisp - modify A* to check for best cost, receive list of goal nodes

Question

I am trying to modify an existing Hill-climb function, which takes two node names (such as A and E), and has an optional parameter which is used recursively (a queue). I'm trying to define a function 'cheaper' that evaluates if one path is cheaper than another. Also, instead of one goal node, I'm trying to pass a list of goal nodes, which the function, upon reaching one of those nodes, stops evaluating.

The problem is my function won't return anything except the start node I've input and an empty list.

Here is my network/graph and associated costs:

(setf (get 's 'coordinates) '(0 3)
      (get 'a 'coordinates) '(4 6)
      (get 'b 'coordinates) '(7 6)
      (get 'c 'coordinates) '(11 9)
      (get 'd 'coordinates) '(2 0)
      (get 'e 'coordinates) '(9 2)
      (get 'f 'coordinates) '(11 3))


(setf (get 's 'cost) 0
      (get 'a 'cost) 16
      (get 'b 'cost) 4
      (get 'c 'cost) 10
      (get 'd 'cost) 5
      (get 'e 'cost) 12
      (get 'f 'cost) 14)

And here is my modified Hill-climb function:

(defun hill-climb (start finish &optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'(lambda (p1 p2)
                                                      (cheaper p1 p2 
                                                               finish)))
                                            (rest queue))))))

Finally, here are the 'cost' and 'cheaper' functions:

(defun cost (path)
  (apply '+ (mapcar #'(lambda (x) (get x 'cost)) path)))


(defun cheaper (p1 p2)
  (< (cost p1)
     (cost p2)))

EDIT: Sorry, and here's 'extend':

(defun extend (path)
  (print (reverse path))
  (mapcar #'(lambda (new-node) (cons new-node path))
          (remove-if #'(lambda (neighbor) (member neighbor path))
                     (get (first path) 'neighbors))))

Where's `extend`? Note that you pass the wrong number of arguments to `cheaper`. Also, using single linked lists as queues is probably not the best idea. — danlei, Oct 11 '11 at 03:11
Sorry, added extend. Noticed the cheaper thing, before was using a function that took 3 arguments. The queue setup is sort of dictated by the assignment. So I know here the issue is that, because I'm using a list of possible goal nodes instead of a single one, when I'm calling the function recursively, I'm not sure how it'll work out in terms of what I pass back to it from the 'finish' list. Perhaps if I just modify 'cheaper' it'll work out better... — Sean Glover, Oct 11 '11 at 03:28
Now, where does the `neighbors` property come from? Did you plan to add that property in a separate step? I don't know your specifications, but I would except a neighbor to be +/-1 for each coordinate(?). Also, since this is homework, please tag it as such. — danlei, Oct 11 '11 at 04:12

danlei · Accepted Answer · 2011-10-11T21:37:50.843

I'm not really sure, what the problem is here. In your expand, a neighbor property is used which is not given in your question. If this property is defined for every node, your code works.

Assuming every node that is next to another without another in between (which is the only option that seems to make sense for your data, since the alternative, namely to make only tangent nodes (i.e. nodes which are +/-1 for one or both coordinates) neighbors, would yield no neighbors at all in your example):

(setf (get 's 'neighbors) '(a d)
      (get 'a 'neighbors) '(s b d)
      (get 'b 'neighbors) '(a c e)
      (get 'c 'neighbors) '(b)
      (get 'd 'neighbors) '(s a e)
      (get 'e 'neighbors) '(b d f)
      (get 'f 'neighbors) '(e))

(defun hill-climb (start finish &optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'cheaper)
                                            (rest queue))))))

(Missing parts stay the same as in your post. Only minor adjustments, like dropping the lambda around, and the extra argument to, cheaper.)

Will give the correct results:

CL-USER> (hill-climb 's '(b))

(S) 
(S D) 
(S D E) 
(S D E B)
CL-USER> (hill-climb 's '(b d))

(S) 
(S D)

If you may not introduce the new property, you will have to check for neighbors in your expand function (which would also mean that you'd have to pass a list of nodes).

Lisp - modify A* to check for best cost, receive list of goal nodes

1 Answers1