Planning in NetLogo: the wolf, the goat, and the cabbage again

In my Goals in NetLogo tutorial and the Wolf, Goat, and Cabbage follow-up, I discussed the use in NetLogo of lists of agent goals. We will now see how a simple planner can be used to generate such goal lists.

For the planner, we represent possible system states (not including the boat being in transit) with a list of the form [ w g c m ], where the items are 1 if loose on the right bank, -1 if loose on the left bank, and 0 if being carried by the man. The initial state is therefore [ 0 0 0 1 ].

The state representing success has everybody on the left (possibly being carried):

to-report acceptable [ state ] ;; everybody is on the left (possibly being carried)
  report ((item 0 state <= 0) and (item 1 state <= 0) and
          (item 2 state <= 0) and (item 3 state = -1))
end

On the other hand, a state is bad if the wolf and goat (or goat and cabbage) are loose on the same side of the river:

to-report bad [ state ] ;; wolf and goat loose together, or goat and cabbage loose together
  report ((item 0 state = -1 and item 1 state = -1) or
          (item 0 state = 1 and item 1 state = 1) or
          (item 1 state = -1 and item 2 state = -1) or
          (item 1 state = 1 and item 2 state = 1))
end

Our simple planner will keep track of the best goal list so far, with the empty list meaning “not yet.” The best out of two alternatives is therefore the shortest, excluding the case of the empty list:

to-report best-of [ x y ] ;; find the best of two solutions
  if-else (length x < length y and x != [])
    [ report x ]
    [ report y]
end

Checking if the man can legally cross the river requires counting zeros (which represent carried items):

to-report count-zeros [ x y z ] ;; count-zeros is used to count how much the man is carrying
  let n 0
  if (x = 0) [ set n (n + 1) ]
  if (y = 0) [ set n (n + 1) ]
  if (z = 0) [ set n (n + 1) ]
  report n
end

The main planning function takes a state, a history of past states, a partial solution, and the best solution so far. If the state is illegal, or we are going back to it (i.e. we are looping), or if we cannot compete with the best solution so far, we report the best solution so far. If the state we have reached is an acceptable solution, we report the best of two solutions:

to-report planner [ state history partial-solution best-so-far ] ;; the planner itself
  if-else ((bad state) or (member? state history) or
           (length best-so-far <= length partial-solution and best-so-far != []))
    [ report best-so-far ]

    [ if-else (acceptable state)
        [ report best-of best-so-far partial-solution ]

Otherwise, we explore all legal moves from the current state, including all the possible item drops. In each case we calculate a new state and a new partial solution, and update the best solution so far via a recursive call:

        [ let h (lput state history)
          let b best-so-far
          let w (item 0 state)
          let g (item 1 state)
          let c (item 2 state)
          let m (item 3 state)

          ;; Can drop carried items on the current bank
          ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
          if (item 0 state = 0)
            [ let s (list m g c m)
              let new-partial (sentence partial-solution (list "drop" wolf))
              set b (planner s h new-partial b) ]
          if (item 1 state = 0)
            [ let s (list w m c m)
              let new-partial (sentence partial-solution (list "drop" goat))
              set b (planner s h new-partial b) ]
          if (item 2 state = 0)
            [ let s (list w g m m)
              let new-partial (sentence partial-solution (list "drop" cabbage))
              set b (planner s h new-partial b) ]

We also explore all legal pickups and all legal moves left or right. The final value (b) of the best solution so far is reported as the best plan:

          ;; Can pick up items on the current bank
          ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
          if (item 0 state = m)
            [ let s (list 0 g c m)
              let new-partial (sentence partial-solution (list "pickup" wolf))
              set b (planner s h new-partial b) ]
          if (item 1 state = m)
            [ let s (list w 0 c m)
              let new-partial (sentence partial-solution (list "pickup" goat))
              set b (planner s h new-partial b) ]
          if (item 2 state = m)
            [ let s (list w g 0 m)
              let new-partial (sentence partial-solution (list "pickup" cabbage))
              set b (planner s h new-partial b) ]

          ;; Can go left or right if at most one item is being carried
          ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
          if ((m = 1) and (count-zeros w g c <= 1))
            [ let s (list w g c -1)
              let new-partial (sentence partial-solution [ "go-left" ])
              set b (planner s h new-partial b) ]
          if ((m = -1) and (count-zeros w g c <= 1))
            [ let s (list w g c 1)
              let new-partial (sentence partial-solution [ "go-right" ])
              set b (planner s h new-partial b) ]

          report b
        ]
    ]
end

A wrapper function calls this planning function with the initial state, and adds some goals to tell the wolf and goat to stop eating after the final solution has been obtained (this ensures termination, with all goals being satisfied).

to-report wgc-plan ;; top-level reporter to return the full plan
  let init-state [0 0 0 1]
  let p (planner init-state [] [] [])
  
  set p (sentence p (list "instruct" wolf [] "instruct" goat []))
  show (fput "THE PLAN IS:" p)
  report p
end

The final program is available at Modeling Commons. See also here for a video. The diagram below shows the system states explored by the planner, starting at the blue state and ending at the green one (the final “L” or “R” in state names marks the position of the man, lowercase “l” or “r” marks the position of loose items, and uppercase “W,” “G,” or “C” marks carried items). For more complex planning activities, it may be appropriate to interface NetLogo to external Java-based planning software, such as JavaFF.