1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
11 # Basic framework for search problems and solver.
13 # The module provides a simple abstract class `SearchProblem[S,A]` to be specialized for a specific problem.
15 # The concrete class `SearchSolver` is used to configure, query, and run a solver for a given problem.
17 # For an example, see the `puzzle.nit` program in the `examples` subdirectory.
23 # Abstract search problem over immutable states (`S`) and actions (`A`).
25 # This class serves to model problems of planing and path-finding.
26 # A state, `S`, is a point in the search problem and fully models a given state of the world.
27 # An action, `A`, is an available mean of transition between two states.
29 # This abstract class is generic made to work with any kind of states and actions.
30 # Therefore, specific subclasses must be developed to implement the required services:
37 # Note that the implemented methods should not temper with the parameters since it is expected
38 # that they remain unmodified.
43 # These tree method are enough to trigger a basic search.
45 # The methods `breadth_first` and `depth_first` return pre-configured solvers for, respectively,
46 # a breadth-first search, a depth-first search.
51 # The `cost` method can be implemented to represent the cost of a single transition.
52 # By default, the cost is 1.
54 # The `heuristic` method can be implemented to represent a lower-bound estimation of the remaining
55 # cost to reach a goal state.
56 # By default, the heuristic is 0.
58 # If one of these (or both) methods are implemented, the `astar` method will return a pre-configured
59 # solver for a A* search.
61 # More configuration and optimization on the search can to be done in the `SearchSolver` class.
62 interface SearchProblem[S
: Object, A
]
63 # The starting state for the problem
64 fun initial_state
: S
is abstract
66 # The available applicable actions for a given state.
67 # While there is a potential large number of distinct states and actions, there should be only
68 # a small number of possible action from a specific state (a small, or at least finite, branching factor).
69 fun actions
(state
: S
): nullable SequenceRead[A
] is abstract
71 # The new state when applying a given action
73 # The returned state can be:
74 # * a completely new state,
75 # * an existing state,
76 # * a new state but equals to an existing state
77 # in this case, ensure that the `==` and `hash` method
78 # are correctly implemented.
80 # Remember, this method should not modify its parameters.
82 # REQUIRE: `actions(state).has(action)`
83 fun apply_action
(state
:S
, action
:A
): S
is abstract
85 # Is the state a goal state?
86 # Once a goal state is found, the solver is automatically stopped.
87 # A problem can have 0, one or more goals if it makes sense
88 # but solver must be used accordingly.
90 fun is_goal
(state
:S
): Bool do return false
92 # The cost for `action` from `old_state` to `new_state`
93 # REQUIRE: `apply_action(old_state, action) == new_state`
95 # Note that having a 0 or negative value can make some search
96 # algorithms fail, or not terminate.
97 fun cost
(state
:S
, action
:A
, state2
: S
): Float do return 1.0
99 # An heuristic of the estimated `cost` going from `state` to a goal state.
101 # Is is expected that the heuristic is *admissible*, it means its is an
102 # optimistic estimation and never an over-estimate, thus is cannot be
103 # higher than the lowest possible remaining cost.
104 # See `SearchSolver::do_revisit` for details.
107 fun heuristic
(state
: S
): Float do return 0.0
109 # return a new breadth-first solver
110 fun breadth_first
: SearchSolver[S
, A
]
112 var todo
= (new Array[SearchNode[S
, A
]]).as_fifo
113 var sol
= new SearchSolver[S
, A
](self, todo
)
117 # return a new depth-first solver
118 fun depth_first
: SearchSolver[S
, A
]
120 var todo
= (new List[SearchNode[S
, A
]]).as_lifo
121 var sol
= new SearchSolver[S
, A
](self, todo
)
125 # return a new best-first solver
128 # * if `heuristic` is not defined, this is basically a Dijkstra search.
129 # * if `cost` in not defined either, this is basically a breadth-first search.
130 fun astar
: SearchSolver[S
, A
]
132 var cpt
= new NodeComparator[S
, A
]
133 var todo
= new MinHeap[SearchNode[S
, A
]](cpt
)
134 var sol
= new SearchSolver[S
, A
](self, todo
)
138 # Create the initial node in the search-tree.
139 # Used internally by the solvers but made public for those who want to replay a plan.
140 fun initial_node
: SearchNode[S
, A
]
142 var res
= new SearchNode[S
,A
](self, initial_state
, null, null, 0.0, 0)
143 res
.compute_heuristic
147 # Negligible quantity for float comparisons
148 # Because of float imprecision, two really near float values should be considered equals.
149 # However, the specific epsilon value could be specific to the problem.
151 # The epsilon value is used for cost comparisons.
154 fun epsilon
: Float do return 0.000000001
156 # Run and evaluate solvers with multiple configuration.
157 # This method can be used to evaluate which configuration to choose by default for a given problem.
159 # `steps` is the maximum number of steps a giver configuration can run.
160 fun run_configs
(steps
: Int)
164 if astar
.run_config
(steps
, c
, "A*") then break
169 # Various Map implementations of memory.
170 # In order to try more configurations with `run_config`, this method
171 # is called to provide alternative implementation.
173 # For instance, a subclass can redefine this method and extends the result with an additional `RBTreeMap`.
174 # Note: because the true nature of the sates `S` is left to the user, some
175 # specific Map implementation could be more efficient than a HashMop.
177 # Default: A `HashMap`
178 fun make_memory
: Array[Map[S
, SearchNode[S
, A
]]]
180 var res
= new Array[Map[S
, SearchNode[S
, A
]]]
181 res
.add
new HashMap[S
, SearchNode[S
, A
]]
186 # A running solver for a given problem, to configure and control.
188 # For a given problem, a lot of variation of search algorithms can be made.
189 # Thus this class permit the user to control the parameters of the search algorithm.
191 # Note that this class is not meant to be specialized, and usually not instantiated directly.
194 # # Basic run and result.
196 # 1. Instantiate it with the method `breadth_first`, `depth_first`, or `astar` from `SearchProblem`.
197 # 2. Apply the method `run`, that will search and return a solution.
198 # 3. Retrieve information from the solution.
201 # var p: SearchProblem = new MyProblem
202 # var res = p.astar.run
203 # if res != null then print "Found plan with {res.depth} actions, that cost {res.cost}: {res.plan.join(", ")}"
207 # # Step-by-step runs and multiple runs
209 # The `run_steps` method (see also `steps`, and `steps_limit`) can be used to run only a maximum number of steps.
210 # This method can be used as a *co-routine* and run them periodically for a small amount of time.
212 # `run` and `run_steps` return the next solution.
213 # A subsequent call to `run` returns the following solution and so on.
215 # When there is no more solutions available, `is_running` become false.
220 # Internally, solvers use a search-tree where nodes are labeled with states, and edges are labeled with actions.
221 # See `SearchNode` for details.
223 # The `run` method return a `SearchNode` that can be used to retrieve a lot of useful information,
224 # like the full `path` or the `plan`.
229 # The solver provide some *knobs* to control how the search-tree is visited.
231 # * `memorize` (see also `memorize_late`)
232 # * `do_revisit` (see also `revisits`)
233 # * `depth_limit` (see also `iterative_deepening` and `depth_limit_reached`)
234 class SearchSolver[S
: Object, A
]
235 # The problem currently solved
236 var problem
: SearchProblem[S
, A
]
238 # The currently open nodes to process.
239 # They are the open nodes.
241 # It is the nature of the queue that control how the solver works.
242 # However, the methods `SearchProblem::breadth_first`, `SearchProblem::depth_first`,
243 # and `SearchProblem::astar` takes care of its correct initialization.
244 private var todo
: Queue[SearchNode[S
, A
]]
246 # Is the solver still running?
247 # A running solver has not yet exhausted all the possible solutions.
248 var is_running
: Bool = true
250 # Does the solver need to memorize visited states?
251 # When activated, there is an increased memory consumption since
252 # all visited states must be kept in memory,
253 # However, there is real a gain, since visited nodes are not
254 # revisited (unless needed by `do_revisit`)
258 # Note: If the graph of states has circuits, then a memory-less search may not terminate.
259 var memorize
: Bool = true is writable
261 # Use memory only on visited (closed) state.
262 # Less memory operations, but two big drawbacks:
263 # * duplicated nodes can fill the `todo` queue (and the memory)
264 # * duplicated nodes require more invocation of `SearchProblem::heuristic`
266 # Note: if `memorize` is false, then this has no effect.
269 var memorize_late
: Bool = false is writable
271 # Storage of nodes when `memorize` is activated
272 # Each state is associated with a node.
274 # * to avoid to revisit visited nodes (see `do_revisit`)
275 # * to avoid to reinvoke `heuristic` on known states (unless `memorize_late` is set)
276 private var memory
: Map[S
, SearchNode[S
, A
]] = new HashMap[S
, SearchNode[S
, A
]]
278 # Total number of time an already memorized node is seen again.
279 # If `memorize_late` is set, then only visited nodes are counted.
280 # Otherwise, nodes in the todo-list are also considered.
283 # Revisit states when a better path to them is found.
284 # Such revisits generally triggers more revisits because they yield
285 # better path to their neighbors.
287 # If `false`, visited states are never revisited.
289 # With astar and an admissible heuristic, no visited node should be revisited.
290 # If the heuristic is not admissible, one may consider set this to `true`.
292 # Obviously, if `memorize` is false, then the value has no specific effect
293 # since all states are considered unvisited.
297 # See also `revisits` and `SearchNode::revisits`.
298 var do_revisit
: Bool = false is writable
300 # Total number of states (potentially) revisited.
302 # It is the number of time that a better path to a visited state is found.
303 # With astar and a really admissible heuristic, this number should stay 0.
304 # So check this value if you are not sure of the heuristic.
306 # Note that states are effectively revisited if `do_revisit` is activated.
309 # The solution found by the last `run`.
311 # ensure `solution != null implies problem.is_goal(solution.state)`
312 var solution
: nullable SearchNode[S
,A
] = null
314 # Nearest solution found (up to date).
315 # The nearest solution is the one with the smallest heuristic value.
316 # The cost is not considered.
317 var nearest_solution
: nullable SearchNode[S
,A
] = null
319 # Limit in the depth search.
321 # States found above this limit are not considered.
323 # Use 0 for no limit.
325 # See also: `iterative_deepening`
326 var depth_limit
: Int = 0 is writable
328 # How much time a `depth_limit` was reached?
330 # This can be used to query if some solutions may have been
331 # ignored because of a `depth_limit`.
333 # This is also used automatically if `iterative_deepening` is activated.
334 var depth_limit_reached
: Int = 0
336 # Increase amount for an iterative deepening search.
337 # It =0, then the iterative deepening search is disabled.
338 # If >0, then `depth_limit` is automatically increased when the todo
339 # queue is empty but the `depth_limit` was reached in the previous iteration.
341 var iterative_deepening
: Int = 0
343 # The total steps executed since the beginning
344 # A step is the visit of a node in the `todo`-list
347 # The total number of nodes created
350 # Limit in the number of steps for a `run`.
352 # One can modify this value then `run` or just call `run_steps`.
354 # Use 0 for no limit.
356 var steps_limit
: Int = 0 is writable
358 # Total number of neighbors considered.
361 # The average number of neighbors by nodes.
362 fun branching_factor
: Float do return neighbors
.to_f
/ steps
.to_f
364 # Update `steps_limit` then just run some additional steps
365 # Return the best solution so far (if any)
366 fun run_steps
(steps
: Int): nullable SearchNode[S
,A
]
369 self.steps_limit
= self.steps
+ steps
373 # Reset the search from the initial state.
374 # Is used at the beginning and with `iterative_deepening`.
378 depth_limit_reached
= 0
379 var initial_node
= problem
.initial_node
380 if memorize
and not memorize_late
then memory
[initial_node
.state
] = initial_node
381 initial_node
.id
= nodes
383 todo
.add initial_node
386 # Run the solver and return the next solution (if any)
387 # Return null is one of these is true:
388 # * `steps_limit` is reached
389 # * the `todo` queue is empty (eg. no reachable solution)
390 fun run
: nullable SearchNode[S
,A
]
392 if steps
== 0 then start
394 var nearest
= nearest_solution
397 if steps_limit
> 0 and steps
>= steps_limit
then break
399 #print "todo={todo.length}"
400 #print " {todo.join("\n ")}"
403 if todo
.is_empty
then
404 # iterative depth search?
405 if depth_limit
<= 0 or iterative_deepening
<= 0 or depth_limit_reached
== 0 then
410 depth_limit
+= iterative_deepening
416 # Because `Queue` has no remove :(
417 if node
.drop
then continue
419 var state
= node
.state
421 if memorize
and memorize_late
then
422 # Is the state already visited?
423 var old
= memory
.get_or_null
(state
)
426 if old
.cost
- node
.cost
< problem
.epsilon
then continue
428 if not do_revisit
then
432 node
.revisits
= old
.revisits
+ 1
438 assert node
.steps
== 0
442 # Keep trace to the nearest
443 if nearest
== null or node
.heuristic
< nearest
.heuristic
then
445 nearest_solution
= node
449 #print "try {node}; todo={todo.length}"
452 if problem
.is_goal
(state
) then
457 # Ignore successors states if the depth limit is reached
458 if depth_limit
> 0 and node
.depth
>= depth_limit
then
459 depth_limit_reached
+= 1
464 var actions
= problem
.actions
(state
)
465 if actions
== null then continue
466 for action
in actions
do
469 # Fast track if no memory or late memory
470 if not memorize
or memorize_late
then
471 var new_node
= node
.apply_action
(action
)
478 # Get the state and the cost. Do not create the node yet.
479 var new_state
= problem
.apply_action
(state
, action
)
480 var new_cost
= node
.cost
+ problem
.cost
(state
, action
, new_state
)
482 # So check if the state was already seen
483 var old
= memory
.get_or_null
(new_state
)
486 # If not better, then skip
487 if old
.cost
- new_cost
< problem
.epsilon
then continue
488 # If visited and do not revisit, then skip
489 if old
.steps
> 0 and not do_revisit
then
494 # Even if `==`, reuse the same state object so
495 # * it may helps the GC
496 # * user-cached things in the previous state can be reused
497 new_state
= old
.state
500 # Finally, create the node
501 var new_node
= new SearchNode[S
, A
](problem
, new_state
, node
, action
, new_cost
, node
.depth
+1)
506 # Compute heuristic and cost
507 new_node
.compute_heuristic
509 # Reuse heuristic and update the cost
510 var h
= old
.heuristic
511 new_node
.heuristic
= h
512 new_node
.score
= new_cost
+ h
514 # Is `old` a visited node?
515 if old
.steps
== 0 then
516 # Old is still in the todo list, so drop it
519 # Old was visited, so revisit it
520 new_node
.revisits
= old
.revisits
+ 1
522 #print "found {old.cost}>{new_cost}:{old.cost>new_cost} d={old.cost-new_cost}\n\t{old}\nthat is worse than\n\t{new_node}"
525 memory
[new_state
] = new_node
533 # The last visited node.
534 # Unless when debugging, the last visited node is not really meaningful.
535 var node
: nullable SearchNode[S
, A
] = null
539 var res
="steps={steps} nodes={nodes} todo={todo.length}"
540 if neighbors
> 0 then res
+= " n={neighbors} (bf={branching_factor})"
541 if revisits
> 0 then res
+= " re={revisits}"
542 if memorized
> 0 then res
+= " mem={memorized}"
548 if n
!= null then res
+= " near={n}"
553 # Run the configuration number `i`, for `steps` number of steps.
554 # The message `msg` suffixed by the name of the configuration is printed followed by the result
556 # This method is used by `SearchProblem::run_configs`
557 fun run_config
(steps
: Int, i
: Int, msg
: String): Bool
567 var mems
= problem
.make_memory
568 memory
= mems
[i
% mems
.length
]
569 msg
+= " {memory.class_name}"
575 memorize_late
= false
592 if i
>= 1 then return true
606 # Used to compare nodes with their score.
607 # Smaller is score, smaller is the node.
608 private class NodeComparator[S
: Object, A
]
610 redef type COMPARED: SearchNode[S
, A
]
611 redef fun compare
(a
,b
) do return a
.score
<=> b
.score
614 # A node in the search-tree visited by a `SearchSolver`.
615 # In search-trees, nodes are labeled with states (`S`), and edges by actions (`A`).
617 # The root node is labeled by the initial state of the problem.
619 # This class is exposed to allow queries on the solution provided by the solver.
620 class SearchNode[S
: Object, A
]
621 # A flag that indicate that `self` is virtually removed from the todo-list.
622 # `self` was added to the todo-list but that a better node for the
623 # same state was found latter.
624 private var drop
= false
626 # The associated problem
627 var problem
: SearchProblem[S
, A
]
629 # The state associated to `self`.
630 # The state labels the node `self`.
633 # Is `self` a root node of the search-tree?
634 # ensure: `result` == `parent == null` and `result`== `action == null`
635 fun is_root
: Bool do return parent
== null
637 # The previous node in the search-tree (if not root).
638 var parent
: nullable SearchNode[S
, A
]
640 # The action used to go from `parent` to `self` (if not root)
641 # The action labels the edge from `parent` to `self`.
642 var action
: nullable A
644 # The past cost (g) from the root node to `self`.
647 # The heuristic from self to the goal (according to `problem.heuristic(state)`
648 # It is the future cost (h)
649 var heuristic
: Float is noinit
651 # The sum of `cost` and `heuristic`
652 # It is the f function.
653 var score
: Float is noinit
655 # Update `heuristic` and `score` according to `problem`.
656 private fun compute_heuristic
658 var h
= problem
.heuristic
(state
)
663 # The depth of `self` in the search tree
664 # It is the number of parents to the root node.
667 # The number of steps needed by the solver to process `self`
668 # It is just a useless generation number, but could be used to evaluate
669 # the behavior of search algorithms.
672 # The rank of creation of nodes by the solver.
673 # It is just a useless generation number, but could be used to evaluate
674 # the behavior of search algorithms.
677 # The number of (potential) revisits of `node`.
678 # This information can be used to debug search algorithms.
679 # And to detect when heuristics are not admissible.
681 # See `SearchSolver::revisits` and `SearchSolver::do_revisit`
683 var revisits
: Int = 0
685 # Create a new child node for the next state, according to `problem`.
686 # Used internally by the solvers but made public for those who want to replay a plan.
688 # ensure `result.parent == self`
689 # ensure `result.action == action`
690 fun apply_action
(action
: A
): SearchNode[S
, A
]
692 var new_state
= problem
.apply_action
(state
, action
)
693 var new_cost
= problem
.cost
(state
, action
, new_state
)
694 var new_node
= new SearchNode[S
, A
](problem
, new_state
, self, action
, cost
+ new_cost
, depth
+1)
695 new_node
.compute_heuristic
699 # Build the sequence of nodes from the initial node to `self`
701 # ensure `result.first.is_root and result.last == self`
702 fun path
: Sequence[SearchNode[S
, A
]]
704 var res
= new List[SearchNode[S
, A
]]
707 while node
!= null do
714 # Build a sequence of actions from the initial state to `self`
715 # See `path` for a more detailed plan.
716 fun plan
: Sequence[A
]
718 var res
= new List[A
]
719 var node
: nullable SearchNode[S
, A
] = self
720 while node
!= null do
722 if a
!= null then res
.unshift
(a
)
728 # Just print a detailed path on the screen
731 print
"result:{state}"
734 if a
!= null then print
" + {a or else ""}"
735 print
" {n.steps}: {n.state} ({n.cost}$)"
739 redef fun to_s
do return "#{steps}/{id} d={depth} f={cost+heuristic} g={cost} h={heuristic}: {state}"
740 #redef fun to_s do return "#{steps} f={(cost+heuristic).to_i} g={cost.to_i} h={heuristic.to_i}"