A general BFS Solver in NetLogo

In this post we will provide an agent based model that solves BFS in a generic way (as generic as it can be done with a standard NetLogo programming style). For that, we will start working with a very basic problem that can be solved as a search in an adequate way and then we will move to solve some other, bigger and more interesting, problems by using the same general solution. You can find a more theoretical point of view of search problems in this post or in this one. BFS is one of the search algorithms that belongs to the group of blind search algorithms that, essentialy, all can do is to distinguish a non-goal state from a goal one.

Let's start presenting the problem to be solved:

Suppose that you want to start from a first number and reach a second one by using only some allowed operations, specifically multiplying by \(3\), adding \(7\), or subtracting \(2\). We would like to know the shortest (or one of the shortest if there are several ones) sequence of operations for this goal.

For example, if we want to reach \(23\) starting from \(5\), one possible solution is:

\[5 - 2 \rightarrow 3 * 3 \rightarrow 9 + 7 \rightarrow 16 + 7 \rightarrow 23\]

In order to solve this problem as a search problem in a state space we need to make some previous work:

1. Defining the state space: in this case is very obvious, our states will be the different numbers that, eventually, we can reach by using the allowed operations. You don't need to be strict with this, only to know what kind of information you will need to represent your problem and being sure that your state space is closed under the transitions (operations) to be defined in the next point, that is, if you take a state in your space and apply any of the valid transitions, you obtain a (probably new) state in your space.
2. Defining the valid transitions: in this case it is easy too, our valid transitions are the three permitted operations of the problem (and they will be represented as: \(*3\), \(+7\), \(-2\)). In our problem the transitions are the same independently of the state where they will be applied to, but sometimes there is a general set of valid transitions and their applicability will depend on the specific state to be applied to.

Although in this basic problem the states and transitions (together, they form the representation of the problem) can be directly obtained from the text of the problem, one can find cases where neither states nor transitions are so clear. In these problems some precautions have to be in mind: states must store all the information that is important for the problem, and transitions have to be realistic in the problem and they must allow to reach the goal from the starting point. Also, it is usual that several representations can be valid for one single problem, choosing correctly between them can be fundamental for the simplicity of the solution and the effectiveness of the search algorithm to be applied.

Essentially, the process that we will implement in this post (known as Breath-First Search, or BFS) will pass through the following steps:

1. Start from the initial condition/state of the problem.
2. Apply all the valid transitions to this state and obtain its children states.
3. Verify if any of the children states satisfies the properties we look for the solution of the problem (have we reached the goal?).
4. If it is the case, stop the search and return the goal (if we are searching) or the sequence of transitions we have applied from the start state to the goal (if we are plannifying).
5. Otherwise, repeat the procedure for every children state.

Of course, some considerations must be done. For example, every time we obtain a new state, we check if the same state had been obtained in a previous step. If this is the case, we will not add it again, because the first time we obtain it ensures a shorter sequence from the start to the goal. With this simple trick we can avoid to search several times over the same state, reducing the computation time (trading it for memory to store the states we have reached previously).

Let's go for the NetLogo solution. Although it is possible to use common data structures for this (as lists), we will make use of agents (turtles) to represent states in our space, and links to represent transitions among them, taking advantage from the extended capabilities that these objects provide.

breed [states state]
states-own
[
  content   ; Stores the content (value) of the state
  explored? ; Tells if the state has been explored (their children has been computed) or not
  path      ; Stores the path to reach this state from the initial state
]

directed-link-breed [transitions transition]
transitions-own
[
  rule   ; Stores the printable version of the transition
]

Now, we will define the procedures that allow to apply transitions on states and obtaining the successors (children) of a specific state. These reports have to be customized in order to solve different problems using the same BFS function. To facilitate the understanding of the general method that will be given bellow, keep in mind the concrete problem we are trying to solve.

Rules are represented by using pairs [ "representation" f ] in such a way that $f$ allows to transform states (it is the transition function) and "representation" is a string to identify the rule. Since in this problem the valid transitions are very short and easy, we will use tasks in order to store the transition functions.

to-report applicable-transitions      ; simply a list of transitions
  report (list
           (list "*3" [ x -> x * 3])
           (list "+7" [ x -> x + 7])
           (list "-2" [ x -> x - 2]))
end

Although it is not necessary, we can add some extra reports to restrict, for example, the valid states and/or the valid transitions. Here, valid? is a boolean report to say when the states are valid, for example if the content is positive:

to-report valid? [x]
  report (x > 0)
end

The previous reports are auxiliary procedures. Next, we define a mandatory report that will be used by the general BFS search procedure: children-states is an agent report that returns the children (successors by transition applications) for the current state. For this, it must return a list of pairs [ns tran], where ns is the content of the children-state, and tran is the applicable transition to get it.

To get it easily in NetLogo, you only have to map the applicable transitions on the current content, and then to filter the valid states.

to-report children-states
  report filter [ ns -> valid? (first ns)]
                (map [ r -> (list (run-result (last r) content) r)]
                     applicable-transitions)
end

One more mandatory report is needed, final-state?, an agent report that identifies the final states for the problem. It usually will depend on a property of the content of the state (for example, if it is equal to an specific final state), and in general it allows the use of parameters because maybe the verification of reaching the goal depends on some extra information from the problem (for example, the final state to compare with).

to-report final-state? [params]
  report ( content = params)
end

Note that, if you want to apply this algorithm to a different problem, all you need is to adapt the previous procedures to fit the representation of your problem. It is supposed that you will not need to change anything else unless you want some extra features that goes beyond the scope of this general solution. Anyway, it must be easy to make the modifications in (almost) all the cases.

As we noted before, essentially the algorithm computes the children states for not explored states and link them by using the applied transition. It iterates until the goal is reached (using final-state? report), and use two reports about representation:

• children-states : reports the children states of the current state.
• final-state? : reports if the current state is a final one.

The general BFS procedure to achieve this task is given, and commented in the following lines. It receives two parameters, the initial state to start with, and the final state for the most common case where the goal is reached when some specific state is generated. If the goal of your problem must be verified with some other property you can extend the final-state? report in order to satisfy your necessities.

Note: this is a simpler version than the one you can find in the github repository, but essentially the same.

to BFS [#initial-state #final-state]
  ca
  show-output   ; Auxiliary procedure to print the conditions of the search problem to be solved
	        ; Maybe, you want to customize it too. Find it at the end of this code
  ; Create the agent associated to the initial state
  create-states 1
  [
    set shape "circle"
    set color green
    set content #initial-state
    set label content
    set path (list self)
    set explored? false
  ]
  ; While there are not-explored states (the verification about the goal is made inside the loop)
  while [any? states with [not explored?]]
  [
    ask states with [not explored?]
    [
      ; Compute the children states by applying every rule to the current state,
      ; and for each new of them we creat a new agent state 
      foreach children-states
      [
        s -> 
        ; We separate the contents and transitions from each children
        let new-state first s
        let applied-rule last s
        ; We consider only new states (states that have not been visited previously)
        if not any? states with [content = new-state]
        [
          ; Clone one new agent for each new state
          hatch-states 1
          [
            set content new-state
            set label content
            set explored? false
            create-transition-from myself [  ; and link it with its father using a transition link
              set rule applied-rule
              set label first applied-rule
            ]
            set color blue
	    ; Update the path for the new state (remember that the clone is a copy of the father, 
	    ; so we only need to add the new state to the father's path)
            set path lput self path
        ] ]
	; Update the layout in order to show in a clear way the search in the space state
        if layout? [layout]
      ]
      ; When all its children have been computed, we mark the current state as explored
      set explored? true
    ]
    ; After a new level is totally generated for the current state,
    ; we check if the goal has been reached
    if any? states with [final-state? #final-state]
     [
       ; If it is the case, we highlight the goal and the path from the initial state (we use 
       ;   reduce with an appropriate function). 
       ; It could be that we find several final states in the same level, 
       ;   so we choose only one of them.
       output-print ""
       output-print "The Solution is:"
       output-print "----------------"
       output-print (word "From " initial_state)
       ask one-of states with [final-state? #final-state]
       [
         set color red
         let a reduce highlight path
       ]
       ; Print the number of explored states, and stop de procedure
       output-print ""
       output-print (word count turtles " explored states" )
       stop
  ] ]
end

That's all. The three basic procedures to solve the search problem via BFS have been shown. In the next lines you will find auxiliary procedures that act as utility functions for this objective and the interface.

Highlight report is used as a parameter function for reduce over the path connecting start and goal states. Given two connected states (that are connected directly through a link/transition) it will highlight the link and returns the second state. As a secondary effect, it will print the textual sequence of transitions to be applied.

to-report highlight [x y]
  ask transition [who] of x [who] of y [
    set color red
    set thickness .3
    output-print (word (first rule) " -> " [content] of y)]
  report y
end

In case you only want to show the path of links connecting the starting state to the goal, you can use the clean procedure, that erases all the states out of the solution path (in red). Use it after highlight.

to clean
  ask states with [not any? my-links with [color = red]] [die]
  repeat 10000 [
    layout-spring states transitions 1 5 1
  ]
end

To provide a clear representation of the state space, we use a radial layout for the tree of generated states.

to layout
  layout-radial states transitions state 0
end

And finally, we have a procedure to print some information about the search problem to be solved.

to show-output
  output-print (word "Go from " Initial_State " to " Final_State)
  output-print (word "using the transitions:")
  foreach applicable-transitions
  [
    r -> output-print (first r)
  ]
end

By using the model that you can find here you can test how the algorithm works and how the different procedures and reports play their roles in it. You can find also a model that runs the same algorithm but in an ordered way (in the order the agents are created) and can be time-stepped to see the creation process by children or by complete levels.

You can test a web (reduced) version of this model in the following link. Please, keep mind that there are small differences between the web version and the normal one, mainly because NetLogo Web is still in development stage and some features and commands are not available:

BFS Web Model

How can we solve more problems with this pattern?

Jugs Problem

Let's use the same pattern to solve some different search problems. We will start with the renowned problem of the two jugs:

You have two jugs, the first one has a \(3\) litres capacity, the second one \(4\) litres. You also have an unlimited source of water. Measure exactly \(2\) litres of water in the second jug. The allowed operations on the jugs are:

• empty a jug,
• refill a jug,
• pour the content of one jug in the other.

The first step is not about programming, but about giving an abstract representation of the problem. In this case, we will use pairs as states, \([j_1 j_2]\), where \(j_1\) is the water in the first jug, and \(j_2\) is the water in the second jug. Hence, one initial state could be \([0 0]\) (both jugs are empty) and any final state is of the form \([x 2]\) (the second jug has \(2\) litres).

The rules will be represented in a similar way as the previous problem, using tasks to obtain the application of the transition:

to-report applicable-transitions
  report (list
           (list "Empty 1" [x -> (list 0 (last x))])
           (list "Empty 2" [x -> (list (first x) 0)])
           (list "Pour 1 to 2" [x -> pour1-2 (first x) (last x)])
           (list "Pour 2 to 1" [x -> pour2-1 (first x) (last x)])
           (list "Fill 1" [x -> (list 3 (last x))])
           (list "Fill 2" [x -> (list (first x) 4)])
		  )
end

In order to facilitate the expressions of these transitions we have designed some auxiliary reports that pours the content of one jug in the other (note that we could make a more general report containing both cases simultaneously, but our goal now is to understand problem solving with BFS, not to make the most reduced code):

to-report pour1-2 [x1 x2]
  let dif 4 - x2
  ifelse dif <= x1
  [report (list (x1 - dif) 4)]
  [report (list 0 (x2 + x1))]
end

to-report pour2-1 [x1 x2]
  let dif 3 - x1
  ifelse dif <= x2
  [report (list 3 (x2 - dif))]
  [report (list (x2 + x1) 0)]
end

valid? is a boolean report telling which states are valid.

to-report valid? [x]
  report ((first x <= 3) and (last x <= 4))
end

Thanks to the definition of the transitions and states, children-states report doesn't need any modification (in some cases you may want to change it, but it is not the case now).

to-report children-states
  report filter [ns -> valid? (first ns)]
                (map [r -> (list (run-result (last r) content) r)]
                     applicable-transitions)
end

Finally, the final-state? report identifies the final states for the problem with the property they must verify. In this case, the water in the second jug must be 2 litres.

to-report final-state? [params]
  report ( last content = 2)
end

That's all, here (URL) you can find the model with this modifications and test the different paths you obtain modifying the conditions of the problem. Remember that now the Final_State input box is not necessary, because we defined final-state? in a different way, but our BFS procedure is still using it as input parameter.

Towers of Hanoi

As a last example, we will solve the Towers of Hanoi problem, where by moving one disc at a time between towers (and with the restriction of allowing only to put a smaller disc over a bigger one) we must move all the discs from one tower to a different one. The most common version of this problem contains \(3\) towers and \(3\) discs initially in the first one, and the goal is to get the three discs (in the same order) in the last tower. A general case will have \(N\) discs and \(M\) towers.

The representation of the states that we will use is based in lists of numbers. The different discs will be represented by numbers from \(1 < 2 < 3 < ... < N\), and the content of a tower will be given by the list of discs it contains \([d_1 ... d_k]\), where \(d_1 < d_2 < ... < d_k\) (disc \(1\) is over disc \(2\), that is over disc \(3\),...). Finally, a specific state of the problem will be the list of the \(M\) towers we have, \([ [T_1] [T_2] [T_3] ... [T_M] ]\). For example, the usual initial state is [ [1 2 3] [ ] [ ] ], the final state is [ [ ] [ ] [1 2 3] ], and one intermediate possible state could be [ [2 3] [1] [ ] ].

We will make use of the same general representation for transitions as pairs, [ "representation" f ], but in this case f will be given by a pair of the form form f=[i j] indicating that we will move top disc from the \(tower_i\) to the top of the \(tower_j\), not for a task. The general expression of the transitions will be:

[ "i->j" [i j] ]

Note that this is the general form of all the possible transitions, but not all of them are applicable on any state, it depends on the specific content of the state (for example, in the initial state the transition [2 1] is not applicable because there are no dics on the tower \(2\) that can be moved to tower \(1\)). For this reason, this agent report returns the applicable transitions for the content (it depends on the current state).

to-report applicable-transitions [c]
  let t-a []
  let lista (range (length c))
  foreach lista [
    i ->
    foreach lista [
      j ->
      let t (list (word i "->" j) (list i j))
      if valid-transition? t c [set t-a lput t t-a]
  ] ]
  report t-a
end

Where valid-transition? reports if a given transition, t, is applicable to a given state, s:

to-report valid-transition? [t s]
  let i first last t
  let j last last t
  if empty? (item i s) [report false]
  if empty? (item j s) [report true]
  let top-disc-i first (item i s)
  let top-disc-j first (item j s)
  report top-disc-i < top-disc-j
end

We build a report, apply-transition, that returns the result of applying a transition t to a state s. It is used directly by the map application of mandatory children-states report.

to-report apply-transition [t s]
  let i first last t
  let j last last t
  let disco first (item i s)
  set s replace-item i s (bf (item i s))
  set s replace-item j s (fput disco (item j s))
  report (list s t)
end

Since in this case we have restricted the applicability of the transitions for every state, we can be sure that all the generated states are valid, so we have the report:

to-report children-states
  report (map [t -> apply-transition t content] (applicable-transitions content))
end

Finally, final-state? is looking for a specific state (as in the first problem we presented):

to-report final-state? [params]
  report ( content = params)
end

As we noted before, we will customize also the show-output procedure:

to show-output
  output-print (word "Go from " Initial_State)
  output-print (word "     to " Final_State)
  output-print (word "using the transitions:")
  output-print " Move the top discs"
  output-print " between towers"
end

Note that the initial state will determine the number of discs and towers of the game, and it is not restricted in any way. Here you can get the model and test the results it provides.

Some final considerations

From a computational point of view, BFS algorithm is complete (if there is a solution, that is, a path from the starting state to a goal, it will eventually find it), but as the solution is far away from the initial state, the resources to get it (in time steps and memory space) grows exponentially.

It is easy to modify the BFS procedure to obtain a DFS one. A Depth-First Search is technically similar to the BFS, but in every step we don't create all the children states of a given one, but only the first (in some order) child and, if it is not the goal, we compute its children before to compute its "brothers". In this way, the tree is generated going deeper instead of filling a complete level. If you are lucky, you will find the goal in a more faster way, but the possibilities to get lost in the deep world of the search tree are higher. Consequently, DFS is not complete (maybe there is a short solution using the next unexplored child, but it gets lost forever in a bad useless branch), but sometimes it could use much lower resources.

In a later post we will present some efficient algorithms to deal with the same kind of problems, trying to avoid the exponential grow by using some extra information from the problem and the data structures it uses. But note that, once the methodology of BFS is presented and functional, "all" you need to solve a search problem is to find a convenient representation of your problem in a State Space (don't forget the transitions).