Avoid Heap Exhausting Problems

KIlian42 commented 3 years ago

Dear Mr. Goldman,

hello again. It would be fantastic if you could help me one more time with my thesis. :-)

QUESTION: How can I avoid memory exhausting issues in large problem definitions?

I'm using Emacs with SBCL and Slime, changed the compiler settings to ((DECLAIM (OPTIMIZE (SPEED 3) (SPACE 3)))) and increased the dynamic-space-size for sbcl up to 15GB ram.
I try to get just a single plan (by using :first) and already relaxed my problem definition (as much as possible) but I still get heap exhausting issues when I increase my problem definition.

To describe my problem more specific: My planning domain dispatches n vehicles for transportation regulation in mines (in the following example I use 4 loading points, 2 unloading points and :D 100 vehicles). I'm running a loop method which always call the same operators in the same order (drive truck to loader, (queuing), load truck, drive to unloader, (queuing), unload truck), until a time limit exceeded - I'm using local times for each vehicle. Each round I pick that un/loading point which offers the lowest waiting/cycle time (by using :sort-by) and ship the next truck. The trucks can queue at an un/loading point because un/loading points can be blocked (for that im using time windows which I put in lists in a atom for each un/loader) So it all works fine for lower time limits and less vehicles (e.g. 40). But I would like to diversify my problem and understand why the shop planner needs so much memory - also when it just need to find a single plan (with around 5000 operations). Does Shop saves all world models for each planning step? Or does Shop uses something like a preprocessing grounding technique when seeking a plan?

Many thanks. :)

Yours sincerely

Kilian

KIlian42 commented 3 years ago

This is the world model at the beginning:

And this at the end (at the heap exhausting time point):

Also the amounts of atoms doesn't increase (because I'm always deleting obsolete atoms).

rpgoldman commented 3 years ago

But I would like to diversify my problem and understand why the shop planner needs so much memory

SHOP needs a lot of stack space because it uses the process stack as its search stack. This means that you are left with stack frames anywhere there's a choice point (and probably some others, as well -- I don't believe we manage to prune all the cases where there is only a single choice, or where we are exploring the last choice.

also when it just need to find a single plan (with around 5000 operations).

This is because it is keeping around all the choice points. To find a plan with 5000 operations, you will have k * 5000 stack frames.

You can make things somewhat more efficient by using find-plans-stack instead of find-plans. This mode is somewhat experimental (e.g., it doesn't support :which :all yet), but should work for your problem.

I'm intrigued that you get a heap exhausted error instead of blowing the stack.

Does Shop saves all world models for each planning step?

No. SHOP has only a single world state, in a difference style representation (so changes are popped off on backtracking). That should not be the cause of your problem.

Or does Shop uses something like a preprocessing grounding technique when seeking a plan?

SHOP is a lifted planner, and operators are not grounded until they are inserted into the plan.

I'll have a look at your domain and problem and see what might be causing this.

KIlian42 commented 3 years ago

Here is my planning domain:

planner.txt

(defun delete_old_blockations (time l)
  (setq new (list ))
  (loop for x in l do
    (if (or (and (= (nth 0 x) -1) (= (nth 1 x) 0)) (< time (+ (nth 0 x) (nth 1 x))))
    (setq new (append new (list x)))))
  (sort new #'< :key #'car)
  new
)

(defun get_ore (p l) ;p = payload of truck; l = lists of blocks at shovel -> list-item: (rock-type amount)
  (defparameter b (car l)) ;extract next block 
  (if (<= (nth 1 b) p) 
      ;block <= payload -> return block as payload
      (if (> (length (cdr l)) 0)
      ; and further blocks at shovel left
      (append (list b) (list (cdr l)))
      ; without further blocks at shovel left
      (list b))
      ;block > payload -> return payload and reduced block at shovel
      (if (> (length (cdr l)) 0)
          ; with reduced block and further blocks at shovel left
      (progn (defparameter new_block_value (- (nth 1 b) p))
                 (defparameter new_block (append (list (nth 0 b)) (list new_block_value)))
         (defparameter new_l (append (list new_block) (cdr l)))
         (defparameter new_payload (list (car b) p))
         (append (list new_payload) (list new_l)))
      ; with only reduced block at shovel left
      (progn (defparameter new_block_value (- (nth 1 b) p))
                 (defparameter new_block (append (list (nth 0 b)) (list new_block_value)))
         (defparameter new_payload (list (car b) p))
         (append (list new_payload) (list (list new_block)))))))

(defun get_start_time (s d l)
  (loop for x in l do
    (setq e (+ s d))
    (setq start (car x))
    (setq end (+ (car x) (nth 1 x)))
    (if (> end s)
    (if (and (= start s) (= end e))
        (setq s (+ (car x) (car (cdr x))))
        (if (and (and (> end s) (<= end e)) (and (>= start s) (< start e)))
        (setq s (+ (car x) (car (cdr x))))
        (if (and (<= start s) (<= e end))
            (setq s (+ (car x) (car (cdr x))))
            (if (and (> end s) (<= end e))
                (setq s (+ (car x) (car (cdr x))))
            (if (and (>= start s) (< start e))
                (setq s (+ (car x) (car (cdr x))))
                (return-from get_start_time s))))))))
  s)

(Defdomain Mine (
;---------------- AXIOMS ----------------
;(:- (global-time ?global-time) ((bagof ?time (time ?truck ?time) ?list) (assign ?global-time (maximum '?list))))
;(:- (empty ?source) ((ore-at ?source ?blocks) (eval (not (if '?blocks 1)))))
;(:- (goal-reached) ((forall (?source) (source ?source) (empty ?source))))
;(:- (goal-reached) ((ore-at g1 100)))
;---------------- AXIOMS ----------------

;---------------- OPERATORS ----------------    
    (:op (!drive-to ?truck ?old-loc ?loc ?start ?duration)
     :delete ((truck ?truck ?start ?old-loc ?payload ?payload-max)
          (distance ?old-distance))
     :add ((truck ?truck ?end ?loc ?payload ?payload-max)
           (distance ?new-distance))
     :precond ((truck ?truck ?start ?old-loc ?payload ?payload-max)
           (assign ?end (eval (+ ?start ?duration)))
           (route ?route ?old-loc ?loc ?duration ?distance)
           (distance ?old-distance)
           (assign ?new-distance (+ ?old-distance ?distance)))
     :cost 0
    )

    (:op (!queueing ?truck ?loc ?start ?duration)
     :delete ((truck ?truck ?start ?loc ?payload ?payload-max)
          (queue ?old-queuetime))
     :add ((truck ?truck ?end ?loc ?payload ?payload-max)
           (queue ?new-queuetime))
     :precond ((truck ?truck ?start ?loc ?payload ?payload-max)
           (assign ?end (eval (+ ?start ?duration)))
           (queue ?old-queuetime)
           (assign ?new-queuetime (+ ?old-queuetime ?duration)))
     :cost 0
    )

    (:op (!load ?truck ?source ?start ?duration)
     :delete ((truck ?truck ?start ?source ?payload ?payload-max)
          (ore-at ?source ?stack)
          (idle ?source ?idle)
          (utilization ?source ?old-n ?old-utilization)
          (blocked ?source ?old-list))
     :add ((truck ?truck ?end ?source ?new-payload ?payload-max)
           (ore-at ?source ?new-stack)
           (idle ?source ?end)
           (utilization ?source ?new-n ?new-utilization)
           (blocked ?source ?new-list))
     :precond ((truck ?truck ?start ?source ?payload ?payload-max)
           (ore-at ?source ?stack)
           (assign ?ore-trans (get_ore ?payload-max '?stack))
           (assign ?new-stack (nth 1 '?ore-trans))
           (assign ?new-payload (nth 1(car '?ore-trans)))
           (assign ?end (+ ?start ?duration))
           (idle ?source ?idle)
           (utilization ?source ?old-n ?old-utilization)
           (assign ?new-n (+ ?old-n 1))
           (assign ?new-utilization (+ ?old-utilization ?duration))
           (blocked ?source ?old-list)
           (assign ?blockation (append (list '?start) (list '?duration)))
           (assign ?new-list (append '?old-list (list '?blockation))))
     :cost 0
    )

    (:op (!unload ?truck ?goal ?start ?duration)
     :delete ((truck ?truck ?start ?goal ?payload ?payload-max)
          (ore-at ?goal ?amount)
          (blocked ?goal ?old-list))
     :add ((truck ?truck ?end ?goal 0 ?payload-max)
           (ore-at ?goal ?new-amount)
           (blocked ?goal ?new-list))
     :precond ((truck ?truck ?start ?goal ?payload ?payload-max)
           (ore-at ?goal ?amount)
           (assign ?new-amount (+ ?amount ?payload))
           (assign ?end (+ ?start ?duration))
           (blocked ?goal ?old-list)
           (assign ?blockation (append (list '?start) (list '?duration)))
           (assign ?new-list (append '?old-list (list '?blockation))))
     :cost 0
    )

    (:op (!!clear-blocking ?time)
     :delete ((blocked s1 ?l1)
          (blocked s2 ?l2)
          (blocked s3 ?l3)
          (blocked s4 ?l4)
          (blocked g1 ?l5)
          (blocked g2 ?l6))
     :add ((blocked s1 ?new1)
           (blocked s2 ?new2)
           (blocked s3 ?new3)
           (blocked s4 ?new4)
           (blocked g1 ?new5)
           (blocked g2 ?new6))
     :precond ((blocked s1 ?l1) (assign ?new1 (delete_old_blockations '?time '?l1))
           (blocked s2 ?l2) (assign ?new2 (delete_old_blockations '?time '?l2))
           (blocked s3 ?l3) (assign ?new3 (delete_old_blockations '?time '?l3))
           (blocked s4 ?l4) (assign ?new4 (delete_old_blockations '?time '?l4))
           (blocked g1 ?l5) (assign ?new5 (delete_old_blockations '?time '?l5))
           (blocked g2 ?l6) (assign ?new6 (delete_old_blockations '?time '?l6)))
     :cost 0
    )      
;---------------- OPERATORS END ----------------

;------------- METHODS -------------

;--------------- SOME DEBUGGING HELPER METHODS ---------------
(:method (print-current-state) ((eval (print-current-state))) ())
(:method (print-current-tasks) ((eval (print-current-tasks))) ())
(:method (print-current-plan) ((eval (print-current-plan))) ())
;--------------- SOME DEBUGGING HELPER METHODS END ---------------

;--------------- METHOD 1 ---------------
    (:method (haulage-loop)

    goal-not-reached-and-pick-next-truck
    (:sort-by ?time ((truck ?truck ?time ?position ?payload ?payload-max)
             (time-limit ?time-limit)
             (eval (<= ?time ?time-limit))
             (not (goal-reached))
             (heuristic ?heuristic)))
    (:ordered (!!clear-blocking ?time)
          (print-current-state)
          (?heuristic ?truck)
          (haulage-loop))

    goal-reached-and-end-loop-do-nothing
    ()
    ()

    )
;--------------- METHOD 1 END ---------------

;--------------- METHOD 2 ---------------
    (:method (dispatch-cycle ?truck)

    haulage
    (:sort-by ?cycle-time  ((source ?any-source)
                    (truck ?truck ?time ?position ?payload ?payload-max)
                (route ?route1 ?position ?any-source ?drive-time1 ?length1)
                (assign ?arrival-time1 (+ ?time ?drive-time1))
                (blocked ?any-source ?list1)
                (assign ?starting-time1 (get_start_time ?arrival-time1 5 '?list1))
                (assign ?waiting-time1 (- ?starting-time1 ?arrival-time1))
                (assign ?leaving-time (+ ?starting-time1 5))
                (goal ?any-goal)
                (route ?route2 ?any-source ?any-goal ?drive-time2 ?length2)
                (assign ?arrival-time2 (+ ?leaving-time ?drive-time2))
                (blocked ?any-goal ?list2)
                (assign ?starting-time2 (get_start_time ?arrival-time2 2 '?list2))
                (assign ?waiting-time2 (- ?starting-time2 ?arrival-time2))
                (assign ?cycle-time (+ ?starting-time2 ?waiting-time2 2))))
    (:ordered (!drive-to ?truck ?position ?any-source ?time ?drive-time1)
          (queueing ?truck ?any-source ?arrival-time1 ?waiting-time1)
          (!load ?truck ?any-source ?starting-time1 5)
          (!drive-to ?truck ?any-source ?any-goal ?leaving-time ?drive-time2)
          (queueing ?truck ?any-goal ?arrival-time2 ?waiting-time2)
          (!unload ?truck ?any-goal ?starting-time2 2)) 

    )
;--------------- METHOD 2 END ---------------

;--------------- METHOD 3 ---------------
    (:method (queueing ?truck ?loc ?arrival ?wait)

    queue
    ((eval (> ?wait 0)))
    ((!queueing ?truck ?loc ?arrival ?wait))

    not-queue
    ((eval (<= ?wait 0)))
    ()

    )
;--------------- METHOD 3 END ---------------

))

(defproblem problem Mine
    ((time-limit 720)
    (heuristic dispatch-cycle)
    (source s1)
    (source s2)
    (source s3)
    (source s4)
    (idle s1 0)
    (idle s2 0)
    (idle s3 0)
    (idle s4 0)
    (utilization s1 0 0)
    (utilization s2 0 0)
    (utilization s3 0 0)
    (utilization s4 0 0)
    (queue 0)
    (distance 0)
    (goal g1)
    (goal g2)
    (blocked s1 ((-1 0)))
    (blocked s2 ((-1 0)))
    (blocked s3 ((-1 0)))
    (blocked s4 ((-1 0)))
    (blocked g1 ((-1 0)))
    (blocked g2 ((-1 0)))
    (ore-at s1 ((1 1000000)))
    (ore-at s2 ((1 1000000)))
    (ore-at s3 ((1 1000000)))
    (ore-at s4 ((1 1000000)))
    (ore-at g1 0)
    (ore-at g2 0)
    (route r1 s1 g1 9 1.5)
    (route r1 g1 s1 6 1.5)
    (route r2 s2 g1 9 1.5)
    (route r2 g1 s2 6 1.5)
    (route r3 s3 g1 9 1.5)
    (route r3 g1 s3 6 1.5)
    (route r4 s4 g1 9 1.5)
    (route r4 g1 s4 6 1.5)
    (route r5 s1 g2 9 1.5)
    (route r5 g2 s1 6 1.5)
    (route r6 s2 g2 9 1.5)
    (route r6 g2 s2 6 1.5)
    (route r7 s3 g2 9 1.5)
    (route r7 g2 s3 6 1.5)
    (route r8 s4 g2 9 1.5)
    (route r8 g2 s4 6 1.5)
    (truck truck1 0 g1 0 50)
    (truck truck2 0 g1 0 50)
    (truck truck3 0 g1 0 50)
    (truck truck4 0 g1 0 50)
    (truck truck5 0 g1 0 50)
    (truck truck6 0 g1 0 50)
    (truck truck7 0 g1 0 50)
    (truck truck8 0 g1 0 50)
    (truck truck9 0 g1 0 50)
    (truck truck10 0 g1 0 50)
    (truck truck11 0 g1 0 50)
    (truck truck12 0 g1 0 50)
    (truck truck13 0 g1 0 50)
    (truck truck14 0 g1 0 50)
    (truck truck15 0 g1 0 50)
    (truck truck16 0 g1 0 50)
    (truck truck17 0 g1 0 50)
    (truck truck18 0 g1 0 50)
    (truck truck19 0 g1 0 50)
    (truck truck20 0 g1 0 50)
    (truck truck21 0 g1 0 50)
    (truck truck22 0 g1 0 50)
    (truck truck23 0 g1 0 50)
    (truck truck24 0 g1 0 50)
    (truck truck25 0 g1 0 50)
    (truck truck26 0 g1 0 50)
    (truck truck27 0 g1 0 50)
    (truck truck28 0 g1 0 50)
    (truck truck29 0 g1 0 50)
    (truck truck30 0 g1 0 50)
    (truck truck31 0 g1 0 50)
    (truck truck32 0 g1 0 50)
    (truck truck33 0 g1 0 50)
    (truck truck34 0 g1 0 50)
    (truck truck35 0 g1 0 50)
    (truck truck36 0 g1 0 50)
    (truck truck37 0 g1 0 50)
    (truck truck38 0 g1 0 50)
    (truck truck39 0 g1 0 50)
    (truck truck40 0 g1 0 50)
    (truck truck41 0 g1 0 50)
    (truck truck42 0 g1 0 50)
    (truck truck43 0 g1 0 50)
    (truck truck44 0 g1 0 50)
    (truck truck45 0 g1 0 50)
    (truck truck46 0 g1 0 50)
    (truck truck47 0 g1 0 50)
    (truck truck48 0 g1 0 50)
    (truck truck49 0 g1 0 50)
    (truck truck50 0 g1 0 50)
    (truck truck51 0 g1 0 50)
    (truck truck52 0 g1 0 50)
    (truck truck53 0 g1 0 50)
    (truck truck54 0 g1 0 50)
    (truck truck55 0 g1 0 50)
    (truck truck56 0 g1 0 50)
    (truck truck57 0 g1 0 50)
    (truck truck58 0 g1 0 50)
    (truck truck59 0 g1 0 50)
    (truck truck60 0 g1 0 50)
    (truck truck61 0 g1 0 50)
    (truck truck62 0 g1 0 50)
    (truck truck63 0 g1 0 50)
    (truck truck64 0 g1 0 50)
    (truck truck65 0 g1 0 50)
    (truck truck66 0 g1 0 50)
    (truck truck67 0 g1 0 50)
    (truck truck68 0 g1 0 50)
    (truck truck69 0 g1 0 50)
    (truck truck70 0 g1 0 50)
    (truck truck71 0 g1 0 50)
    (truck truck72 0 g1 0 50)
    (truck truck73 0 g1 0 50)
    (truck truck74 0 g1 0 50)
    (truck truck75 0 g1 0 50)
    (truck truck76 0 g1 0 50)
    (truck truck77 0 g1 0 50)
    (truck truck78 0 g1 0 50)
    (truck truck79 0 g1 0 50)
    (truck truck80 0 g1 0 50)
    (truck truck81 0 g1 0 50)
    (truck truck82 0 g1 0 50)
    (truck truck83 0 g1 0 50)
    (truck truck84 0 g1 0 50)
    (truck truck85 0 g1 0 50)
    (truck truck86 0 g1 0 50)
    (truck truck87 0 g1 0 50)
    (truck truck88 0 g1 0 50)
    (truck truck89 0 g1 0 50)
    (truck truck90 0 g1 0 50)
    (truck truck91 0 g1 0 50)
    (truck truck92 0 g1 0 50)
    (truck truck93 0 g1 0 50)
    (truck truck94 0 g1 0 50)
    (truck truck95 0 g1 0 50)
    (truck truck96 0 g1 0 50)
    (truck truck97 0 g1 0 50)
    (truck truck98 0 g1 0 50)
    (truck truck99 0 g1 0 50)
    (truck truck100 0 g1 0 50)
    )
    (:ordered (haulage-loop))
)

(find-plans 'problem :which :first :verbose :plans :time-limit 720)

#|
(asdf:load-system "shop3")
(in-package :SHOP-USER)
(load "/Users/kiliankramer/Desktop/planner2")
|#

rpgoldman commented 3 years ago

There is an absolutely enormous unifier when I interrupt the program -- about 22,000 elements. I'm not sure why that is happening, but it's not healthy.

rpgoldman commented 3 years ago

I did a little clean-up (see #49), but am a little confused about the three lisp functions up top.

Note that you have been using dynamically scoped variables in a number of places -- I replaced with lexical variables. But that should not have caused the issue you see.

KIlian42 commented 3 years ago

Thank You so much for the quick response. As soon as I’m home again I will check it.

rpgoldman commented 3 years ago

find-plans-stack works for me. Your report, by the way, I think shows a problem in how SHOP maintains its stack, where it can make excessive copies.

KIlian42 commented 3 years ago

Thank you very much for your time and help! :)

There is an absolutely enormous unifier when I interrupt the program -- about 22,000 elements. I'm not sure why that is happening, but it's not healthy.

How do you display this - with (shop-trace : ...) ? :) Do you think this might be the reason for my heap exhausting? If yes I'm helpless what to do :D - I'm not using forall - but I use sort-by and setof/bagof in my domain. What else could cause that - too many unbound variables?... e.g. for binding (truck ?truck ...) 100 possibilities in each step

I did a little clean-up (see #49), but am a little confused about the three lisp functions up top.

Note that you have been using dynamically scoped variables in a number of places -- I replaced with lexical variables. But that should not have caused the issue you see.

Thanks for tidying up my code! - I'm still a beginner in Lisp...

find-plans-stack works for me. Your report, by the way, I think shows a problem in how SHOP maintains its stack, where it can make excessive copies.

So can you run the domain and find the plan without any problems? -- if yes it should also somehow work on my computer (MacOS) too -- Unfornatly I got also a heap exhausting with find-plans-stack after a while ...

KIlian42 commented 3 years ago

This is because it is keeping around all the choice points. To find a plan with 5000 operations, you will have k * 5000 stack frames.

Hi, I found a way to avoid my memory problem. So I did use Shops :sort-by function in every method. Instead of using :sort-by, I'm using Lisps sort function now ... and I'm getting 2-3 times bigger plans. Since I'm only interested in the first element of the :sort-by list and Shops saving all the choice points and stack frames...I think this was the reason for my problem

...e.g. I try to plan 100 vehicles at the same time by sorting their local time - for that I did use :sort-by ?time ((truck ?truckxy ?time)). So apparently Shop saved in each loop step 100 choice points...and I did use :sort-by in almost every method so I had a lot of choice points and stack frames. If you like please close that issue. Have a good day. :)

rpgoldman commented 3 years ago

If you are not worried about missing solutions, you can also use the just-one qualifier to avoid leaving behind too many stack entries.

But use with care!

shop-planner / shop3

Avoid Heap Exhausting Problems #47