lib/ai/backtrack.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # This file is free software, which comes along with NIT.  This software is
   4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   5 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   6 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   7 # is kept unaltered, and a notification of the changes is added.
   8 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
   9 # another product.
  10
  11 # Basic framework for active backtrack solver
  12 #
  13 # This module provides a simple abstract class `BacktrackProblem[S,A]` to be specialized for a specific problem.
  14 #
  15 # The concrete class `BacktrackSolver` is used to configure, query, and run a solver for a given problem.
  16 #
  17 # For an example, see the `queens.nit` program in the `examples` subdirectory.
  18 module backtrack
  19
  20 # Abstract backtrack problem of states (`S`) and actions (`A`).
  21 #
  22 # This class serves to model search problems using a backtracking approach.
  23 # A state, `S`, is a point in the search problem and fully model a given state of the world.
  24 # An action, `A`, is an available mean of transition between two states.
  25 # While there is a potential large number of distinct states and actions, there should be only
  26 # a small number of possible actions from a specific state (thus, a small, or at least finite, branching factor).
  27 #
  28 # The point this class is that the state is a mutable object, the roles of the actions is to modify
  29 # the state.
  30 #
  31 # This abstract class is generic and made to work with any kind of states and actions.
  32 # Therefore, specific subclasses must be developed to implements the required services:
  33 #
  34 # * `initial_state`
  35 # * `actions`
  36 # * `apply_action`
  37 # * `backtrack`
  38 # * `is_goal`
  39 #
  40 # # Basic search
  41 #
  42 # The method `solve` returns a new solver for a backtrack search.
  43 abstract class BacktrackProblem[S: Object,A]
  44         # The starting state of the problem.
  45         # It is this object that will be modified by `apply_action` and `backtrack`.
  46         fun initial_state: S is abstract
  47
  48         # The available and applicable actions for a given state
  49         # Because of `backtracking`, actions must also be reversible (see `backtrack`).
  50         #
  51         # If there is no available actions, null (or an empty collection) must be returned.
  52         #
  53         # In order to optimise the search time, it is sensible to return `null`
  54         # (or an empty collection) as early as possible.
  55         #
  56         # Node: to help some specific implementations, the current node is also available.
  57         # See `BacktrackNode` for details.
  58         fun actions(state: S, node: BacktrackNode[A]): nullable Collection[A] is abstract
  59
  60         # Modify `state` by applying `action`
  61         # The `action` comes from an earlier invocation of `actions`.
  62         fun apply_action(state: S, action: A) is abstract
  63
  64         # Modify `state` by undoing `action`
  65         # Because of this method, it is important that any action can be undone
  66         # knowing only the post-state and the action.
  67         fun backtrack(state: S, action: A) is abstract
  68
  69         # Is the state a goal state?
  70         # Once a goal state is found, the solver is automatically stopped.
  71         # See `BacktrackSolver.run`.
  72         fun is_goal(state: S): Bool is abstract
  73
  74         # Return a new solver
  75         fun solve: BacktrackSolver[S,A] do
  76                 return new BacktrackSolver[S,A](self, initial_state)
  77         end
  78 end
  79
  80 # A running solver for a given problem, that can be configured and controlled.
  81 #
  82 #
  83 # # Basic run and results.
  84 #
  85 # 1. Instantiate it with the method `solve` from `BacktrackProblem`.
  86 # 2. Apply the method `run`, that will search and return a solution.
  87 # 3. Retrieve information from the solution.
  88 #
  89 # ~~~~nitish
  90 # var p: BacktrackProblem = new MyProblem
  91 # var solver = p.solve
  92 # var res = solver.run
  93 # if res != null then
  94 #   print "Found solution in {res.depth} actions: {res.plan.join(", ")}"
  95 #   print "The state of the solution is: {solver.state}"
  96 # end
  97 # ~~~~
  98 #
  99 #
 100 # # Step-by-step runs and multiple runs
 101 #
 102 # The `run_steps` method (see also `steps`, and `steps_limit`) can be used to run only a maximum number of steps.
 103 # Thus, this method can be used as a *co-routine* and be run periodically for a small amount of time.
 104 #
 105 # `run` and `run_steps` return the next solution.
 106 # A subsequent call to `run` returns the following solution and so on.
 107 #
 108 # When there is no more solutions available, `null` is returned and `is_running` become false.
 109 #
 110 # Between run, the state of the current search can be read.
 111 #
 112 #
 113 # # Search-trees
 114 #
 115 # Internally, solvers use a zipper on the virtual search-tree where nodes are elements in the apply/backtrack graph.
 116 # See the class `BacktrackNode` for details
 117 #
 118 # The `run` and `node` methods return a `BacktrackNode` that can be used to retrieve a lot of useful information,
 119 # like the full `path` or the `plan`.
 120 # If only the solved state is required, the `state` method from the solver gives it.
 121 class BacktrackSolver[S: Object, A]
 122         # The problem currently solved
 123         var problem: BacktrackProblem[S,A]
 124
 125         # The current state.
 126         # Do not modify it directly: the solver will do that by its own use of
 127         # `problem.apply_action` and `problem.backtrack`.
 128         var state: S
 129
 130         # The current `node` in the backtrack-zipper.
 131         var node: nullable BacktrackNode[A] = null
 132
 133         # Is the solver still running?
 134         # A running solver has not yet exhausted all the possible solutions.
 135         var is_running = true
 136
 137         # Initialize `node`
 138         private fun start: BacktrackNode[A]
 139         do
 140                 assert node == null
 141                 var node = new BacktrackNode[A](null, null, 0, 0)
 142                 self.node = node
 143                 return node
 144         end
 145
 146
 147         # The total steps executed since the beginning.
 148         var steps = 0
 149
 150         # Limit in the number of steps for a `run`.
 151         #
 152         # One can modify this value then `run` or just call `run_steps`.
 153         #
 154         # Use 0 for no limit.
 155         # Default: 0
 156         var steps_limit = 0 is writable
 157
 158         # Update `steps_limit` then just run some additional steps.
 159         # Return the `node` corresponding to the found solution, or `null` if no solution is found.
 160         fun run_steps(steps: Int): nullable BacktrackNode[A]
 161         do
 162                 steps_limit = self.steps + steps
 163                 return run
 164         end
 165
 166         # Run the solver and return the next solution found (if any).
 167         # Return null is one of these is true:
 168         # * `steps_limit` is reached
 169         # * no more reachable solution, in this case `is_running` become false.
 170         fun run: nullable BacktrackNode[A]
 171         do
 172                 var node = self.node
 173                 # Not yet started, of finished?
 174                 if node == null then
 175                         if steps > 0 then return null
 176                         node = start
 177                         var res = problem.is_goal(state)
 178                         if res then return node
 179                 end
 180
 181                 loop
 182                         if steps_limit > 0 and steps > steps_limit then break
 183                         steps += 1
 184
 185                         var totry = node.totry
 186
 187                         # It is the first visit in this state?
 188                         if totry == null then
 189                                 var actions = problem.actions(state, node)
 190                                 if actions != null and not actions.is_empty then
 191                                         totry = actions.to_a
 192                                         node.totry = totry
 193                                 end
 194                         end
 195
 196                         #print state
 197                         #print node
 198
 199                         # No remaining actions?
 200                         if totry == null or totry.is_empty then
 201                                 #print "Backtrack"
 202                                 var a = node.action
 203                                 if a == null then
 204                                         #print "no more action"
 205                                         is_running = false
 206                                         self.node = null
 207                                         return null
 208                                 end
 209
 210                                 problem.backtrack(state, a)
 211                                 node = node.parent
 212                                 assert node != null
 213                                 continue
 214                         end
 215
 216                         var a = totry.pop
 217                         problem.apply_action(state, a)
 218                         #print "Play {a or else ""}"
 219                         node = new BacktrackNode[A](node, a, node.depth+1, steps)
 220
 221                         var res = problem.is_goal(state)
 222                         if res then
 223                                 self.node = node
 224                                 return node
 225                         end
 226                 end
 227                 self.node = node
 228                 return null
 229         end
 230
 231         redef fun to_s do return "{node or else "#0"}"
 232 end
 233
 234 # A node in the backtrack-zipper visited by a `BacktrackSolver`.
 235 #
 236 # The solver visits the virtual search tree with a zipper.
 237 #
 238 # A node is the zipper (this class) is associated to:
 239 # * a state of the problem (indirectly),
 240 # * the actions not yet explored from the state (see `totry`)
 241 # * the action that yields to the state (see `action`), used to backtrack.
 242 # * and the parent node in the zipper (see `parent`).
 243 #
 244 # There is no direct link between a node and a state; it is unneeded
 245 # since the same state is used, and mutated, during the whole execution of the solver.
 246 #
 247 # This class is exposed to allow queries on the solution provided by the solver.
 248 class BacktrackNode[A]
 249         # The previous node in the backtrack-zipper
 250         var parent: nullable BacktrackNode[A]
 251
 252         # The last action executed
 253         var action: nullable A
 254
 255         # The remaining actions to try from this node
 256         var totry: nullable Array[A] = null
 257
 258         # The depth of `self` in the search-tree.
 259         var depth: Int
 260
 261         # The number of steps needed by the solver to process `self`.
 262         # This is just a useless generation number, but could be used to evaluate
 263         # the behavior of search algorithms.
 264         var steps: Int
 265
 266         # Build a sequence of nodes from the initial node to `self`
 267         # ensure `result.first.parent == null and result.last == self`
 268         fun path: Sequence[BacktrackNode[A]]
 269         do
 270                 var res = new List[BacktrackNode[A]]
 271                 res.add(self)
 272                 var node = parent
 273                 while node != null do
 274                         res.unshift(node)
 275                         node = node.parent
 276                 end
 277                 return res
 278         end
 279
 280         # Build a sequence of actions from the initial state to `self`
 281         # See `path` for a more detailed plan.
 282         fun plan: Sequence[A]
 283         do
 284                 var res = new List[A]
 285                 var node: nullable BacktrackNode[A] = self
 286                 while node != null do
 287                         var a = node.action
 288                         if a != null then res.unshift(a)
 289                         node = node.parent
 290                 end
 291                 return res
 292         end
 293
 294         redef fun to_s do
 295                 var res = "#{steps} d={depth}"
 296                 var tt = totry
 297                 if tt != null then res += " tt={tt.join(" ")}"
 298                 return res
 299         end
 300 end