;;; -*- Mode: Xbvl;; Syntax: Common-Lisp -*-
; adapté de Paradigms of AI Programming de Peter Norvig

; File gps-srch.lisp: Section 6.4 GPS based on explicit search

(include "gpsfinal")
(include "search")

(de search-gps (start goal beam-width)
  ; cherche une séquence d'opérateurs menant vers le but 'goal'
  (setq beam-width (or beam-width 10))
  (find-all-if
    'action-p
    (beam-search
      (cons '(start) start)
      '(lambda (state) (subsetp goal state))
      'gps-successors
      '(lambda (state)
          (+ (count-if 'action-p state)
             (count-if '(lambda (con)
                           (not (member con state)))
                       goal)))
      beam-width)))

(de gps-successors (state)
  ; retourne une liste d'état atteignables à partir de l'état actuel
  ; en utilisant les ops
  (mymapcar
    '(lambda (op)
        (append
          (remove-if '(lambda (x) 
                         (member x (op-del-list op)))
                     state)
          (op-add-list op)))
    (applicable-ops state)))

(de applicable-ops (state)
  ; retourne la liste de tous les opérateurs applicables actuellement
  (find-all-if
    '(lambda (op)
        (subsetp (op-preconds op) state))
    *ops*))

(de gps-search (START)
  (print '(setq START '((c on a)(a on table)(b on table)(space on c)
		(space on b)(space on table))))
  (print (setq START '((c on a)(a on table)(b on table)(space opn c)
		(space on b)(space on table))))
  (print '(use (make-block-ops '(a b c))))
  (print (use (make-block-ops '(a b c))))
  (print '(search-gps START '((a on b)(b on c))))
  (print (search-gps START '((a on b)(b on c))))
  (print '(search-gps START '((b on c)(a on b))))
  (print (search-gps START '((b on c)(a on b))))
  "c'est tout")