21a349df1104873ca1cd4ba2e4c2a5473f304608
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)
166 if astar
.run_config
(steps
, c
, "A*") then break
171 # Various Map implementations of memory.
172 # In order to try more configurations with `run_config`, this method
173 # is called to provide alternative implementation.
175 # For instance, a subclass can redefine this method and extends the result with an additional `RBTreeMap`.
176 # Note: because the true nature of the sates `S` is left to the user, some
177 # specific Map implementation could be more efficient than a HashMop.
179 # Default: A `HashMap`
180 fun make_memory
: Array[Map[S
, SearchNode[S
, A
]]]
182 var res
= new Array[Map[S
, SearchNode[S
, A
]]]
183 res
.add
new HashMap[S
, SearchNode[S
, A
]]
188 # A running solver for a given problem, to configure and control.
190 # For a given problem, a lot of variation of search algorithms can be made.
191 # Thus this class permit the user to control the parameters of the search algorithm.
193 # Note that this class is not meant to be specialized, and usually not instantiated directly.
196 # # Basic run and result.
198 # 1. Instantiate it with the method `breadth_first`, `depth_first`, or `astar` from `SearchProblem`.
199 # 2. Apply the method `run`, that will search and return a solution.
200 # 3. Retrieve information from the solution.
203 # var p: SearchProblem = new MyProblem
204 # var res = p.astar.run
205 # if res != null then print "Found plan with {res.depth} actions, that cost {res.cost}: {res.plan.join(", ")}"
209 # # Step-by-step runs and multiple runs
211 # The `run_steps` method (see also `steps`, and `steps_limit`) can be used to run only a maximum number of steps.
212 # This method can be used as a *co-routine* and run them periodically for a small amount of time.
214 # `run` and `run_steps` return the next solution.
215 # A subsequent call to `run` returns the following solution and so on.
217 # When there is no more solutions available, `is_running` become false.
222 # Internally, solvers use a search-tree where nodes are labeled with states, and edges are labeled with actions.
223 # See `SearchNode` for details.
225 # The `run` method return a `SearchNode` that can be used to retrieve a lot of useful information,
226 # like the full `path` or the `plan`.
231 # The solver provide some *knobs* to control how the search-tree is visited.
233 # * `memorize` (see also `memorize_late`)
234 # * `do_revisit` (see also `revisits`)
235 # * `depth_limit` (see also `iterative_deepening` and `depth_limit_reached`)
236 class SearchSolver[S
: Object, A
]
237 # The problem currently solved
238 var problem
: SearchProblem[S
, A
]
240 # The currently open nodes to process.
241 # They are the open nodes.
243 # It is the nature of the queue that control how the solver works.
244 # However, the methods `SearchProblem::breadth_first`, `SearchProblem::depth_first`,
245 # and `SearchProblem::astar` takes care of its correct initialization.
246 private var todo
: Queue[SearchNode[S
, A
]]
248 # Is the solver still running?
249 # A running solver has not yet exhausted all the possible solutions.
250 var is_running
: Bool = true
252 # Does the solver need to memorize visited states?
253 # When activated, there is an increased memory consumption since
254 # all visited states must be kept in memory,
255 # However, there is real a gain, since visited nodes are not
256 # revisited (unless needed by `do_revisit`)
260 # Note: If the graph of states has circuits, then a memory-less search may not terminate.
261 var memorize
: Bool = true is writable
263 # Use memory only on visited (closed) state.
264 # Less memory operations, but two big drawbacks:
265 # * duplicated nodes can fill the `todo` queue (and the memory)
266 # * duplicated nodes require more invocation of `SearchProblem::heuristic`
268 # Note: if `memorize` is false, then this has no effect.
271 var memorize_late
: Bool = false is writable
273 # Storage of nodes when `memorize` is activated
274 # Each state is associated with a node.
276 # * to avoid to revisit visited nodes (see `do_revisit`)
277 # * to avoid to reinvoke `heuristic` on known states (unless `memorize_late` is set)
278 private var memory
: Map[S
, SearchNode[S
, A
]] = new HashMap[S
, SearchNode[S
, A
]]
280 # Total number of time an already memorized node is seen again.
281 # If `memorize_late` is set, then only visited nodes are counted.
282 # Otherwise, nodes in the todo-list are also considered.
285 # Revisit states when a better path to them is found.
286 # Such revisits generally triggers more revisits because they yield
287 # better path to their neighbors.
289 # If `false`, visited states are never revisited.
291 # With astar and an admissible heuristic, no visited node should be revisited.
292 # If the heuristic is not admissible, one may consider set this to `true`.
294 # Obviously, if `memorize` is false, then the value has no specific effect
295 # since all states are considered unvisited.
299 # See also `revisits` and `SearchNode::revisits`.
300 var do_revisit
: Bool = false is writable
302 # Total number of states (potentially) revisited.
304 # It is the number of time that a better path to a visited state is found.
305 # With astar and a really admissible heuristic, this number should stay 0.
306 # So check this value if you are not sure of the heuristic.
308 # Note that states are effectively revisited if `do_revisit` is activated.
311 # The solution found by the last `run`.
313 # ensure `solution != null implies problem.is_goal(solution.state)`
314 var solution
: nullable SearchNode[S
,A
] = null
316 # Nearest solution found (up to date).
317 # The nearest solution is the one with the smallest heuristic value.
318 # The cost is not considered.
319 var nearest_solution
: nullable SearchNode[S
,A
] = null
321 # Limit in the depth search.
323 # States found above this limit are not considered.
325 # Use 0 for no limit.
327 # See also: `iterative_deepening`
328 var depth_limit
: Int = 0 is writable
330 # How much time a `depth_limit` was reached?
332 # This can be used to query if some solutions may have been
333 # ignored because of a `depth_limit`.
335 # This is also used automatically if `iterative_deepening` is activated.
336 var depth_limit_reached
: Int = 0
338 # Increase amount for an iterative deepening search.
339 # It =0, then the iterative deepening search is disabled.
340 # If >0, then `depth_limit` is automatically increased when the todo
341 # queue is empty but the `depth_limit` was reached in the previous iteration.
343 var iterative_deepening
: Int = 0
345 # The total steps executed since the beginning
346 # A step is the visit of a node in the `todo`-list
349 # The total number of nodes created
352 # Limit in the number of steps for a `run`.
354 # One can modify this value then `run` or just call `run_steps`.
356 # Use 0 for no limit.
358 var steps_limit
: Int = 0 is writable
360 # Total number of neighbors considered.
363 # The average number of neighbors by nodes.
364 fun branching_factor
: Float do return neighbors
.to_f
/ steps
.to_f
366 # Update `steps_limit` then just run some additional steps
367 # Return the best solution so far (if any)
368 fun run_steps
(steps
: Int): nullable SearchNode[S
,A
]
371 self.steps_limit
= self.steps
+ steps
375 # Reset the search from the initial state.
376 # Is used at the beginning and with `iterative_deepening`.
380 depth_limit_reached
= 0
381 var initial_node
= problem
.initial_node
382 if memorize
and not memorize_late
then memory
[initial_node
.state
] = initial_node
383 initial_node
.id
= nodes
385 todo
.add initial_node
388 # Run the solver and return the next solution (if any)
389 # Return null is one of these is true:
390 # * `steps_limit` is reached
391 # * the `todo` queue is empty (eg. no reachable solution)
392 fun run
: nullable SearchNode[S
,A
]
394 if steps
== 0 then start
396 var nearest
= nearest_solution
399 if steps_limit
> 0 and steps
>= steps_limit
then break
401 #print "todo={todo.length}"
402 #print " {todo.join("\n ")}"
405 if todo
.is_empty
then
406 # iterative depth search?
407 if depth_limit
<= 0 or iterative_deepening
<= 0 or depth_limit_reached
== 0 then
412 depth_limit
+= iterative_deepening
418 # Because `Queue` has no remove :(
419 if node
.drop
then continue
421 var state
= node
.state
423 if memorize
and memorize_late
then
424 # Is the state already visited?
425 var old
= memory
.get_or_null
(state
)
428 if old
.cost
- node
.cost
< problem
.epsilon
then continue
430 if not do_revisit
then
434 node
.revisits
= old
.revisits
+ 1
440 assert node
.steps
== 0
444 # Keep trace to the nearest
445 if nearest
== null or node
.heuristic
< nearest
.heuristic
then
447 nearest_solution
= node
451 #print "try {node}; todo={todo.length}"
454 if problem
.is_goal
(state
) then
459 # Ignore successors states if the depth limit is reached
460 if depth_limit
> 0 and node
.depth
>= depth_limit
then
461 depth_limit_reached
+= 1
466 var actions
= problem
.actions
(state
)
467 if actions
== null then continue
468 for action
in actions
do
471 # Fast track if no memory or late memory
472 if not memorize
or memorize_late
then
473 var new_node
= node
.apply_action
(action
)
480 # Get the state and the cost. Do not create the node yet.
481 var new_state
= problem
.apply_action
(state
, action
)
482 var new_cost
= node
.cost
+ problem
.cost
(state
, action
, new_state
)
484 # So check if the state was already seen
485 var old
= memory
.get_or_null
(new_state
)
488 # If not better, then skip
489 if old
.cost
- new_cost
< problem
.epsilon
then continue
490 # If visited and do not revisit, then skip
491 if old
.steps
> 0 and not do_revisit
then
496 # Even if `==`, reuse the same state object so
497 # * it may helps the GC
498 # * user-cached things in the previous state can be reused
499 new_state
= old
.state
502 # Finally, create the node
503 var new_node
= new SearchNode[S
, A
](problem
, new_state
, node
, action
, new_cost
, node
.depth
+1)
508 # Compute heuristic and cost
509 new_node
.compute_heuristic
511 # Reuse heuristic and update the cost
512 var h
= old
.heuristic
513 new_node
.heuristic
= h
514 new_node
.score
= new_cost
+ h
516 # Is `old` a visited node?
517 if old
.steps
== 0 then
518 # Old is still in the todo list, so drop it
521 # Old was visited, so revisit it
522 new_node
.revisits
= old
.revisits
+ 1
524 #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}"
527 memory
[new_state
] = new_node
535 # The last visited node.
536 # Unless when debugging, the last visited node is not really meaningful.
537 var node
: nullable SearchNode[S
, A
] = null
541 var res
="steps={steps} nodes={nodes} todo={todo.length}"
542 if neighbors
> 0 then res
+= " n={neighbors} (bf={branching_factor})"
543 if revisits
> 0 then res
+= " re={revisits}"
544 if memorized
> 0 then res
+= " mem={memorized}"
550 if n
!= null then res
+= " near={n}"
555 # Run the configuration number `i`, for `steps` number of steps.
556 # The message `msg` suffixed by the name of the configuration is printed followed by the result
558 # This method is used by `SearchProblem::run_configs`
559 fun run_config
(steps
: Int, i
: Int, msg
: String): Bool
569 var mems
= problem
.make_memory
570 memory
= mems
[i
% mems
.length
]
571 msg
+= " {memory.class_name}"
577 memorize_late
= false
594 if i
>= 1 then return true
600 var res
= run_steps
(steps
)
608 # Used to compare nodes with their score.
609 # Smaller is score, smaller is the node.
610 private class NodeComparator[S
: Object, A
]
612 redef type COMPARED: SearchNode[S
, A
]
613 redef fun compare
(a
,b
) do return a
.score
<=> b
.score
616 # A node in the search-tree visited by a `SearchSolver`.
617 # In search-trees, nodes are labeled with states (`S`), and edges by actions (`A`).
619 # The root node is labeled by the initial state of the problem.
621 # This class is exposed to allow queries on the solution provided by the solver.
622 class SearchNode[S
: Object, A
]
623 # A flag that indicate that `self` is virtually removed from the todo-list.
624 # `self` was added to the todo-list but that a better node for the
625 # same state was found latter.
626 private var drop
= false
628 # The associated problem
629 var problem
: SearchProblem[S
, A
]
631 # The state associated to `self`.
632 # The state labels the node `self`.
635 # Is `self` a root node of the search-tree?
636 # ensure: `result` == `parent == null` and `result`== `action == null`
637 fun is_root
: Bool do return parent
== null
639 # The previous node in the search-tree (if not root).
640 var parent
: nullable SearchNode[S
, A
]
642 # The action used to go from `parent` to `self` (if not root)
643 # The action labels the edge from `parent` to `self`.
644 var action
: nullable A
646 # The past cost (g) from the root node to `self`.
649 # The heuristic from self to the goal (according to `problem.heuristic(state)`
650 # It is the future cost (h)
651 var heuristic
: Float is noinit
653 # The sum of `cost` and `heuristic`
654 # It is the f function.
655 var score
: Float is noinit
657 # Update `heuristic` and `score` according to `problem`.
658 private fun compute_heuristic
660 var h
= problem
.heuristic
(state
)
665 # The depth of `self` in the search tree
666 # It is the number of parents to the root node.
669 # The number of steps needed by the solver to process `self`
670 # It is just a useless generation number, but could be used to evaluate
671 # the behavior of search algorithms.
674 # The rank of creation of nodes by the solver.
675 # It is just a useless generation number, but could be used to evaluate
676 # the behavior of search algorithms.
679 # The number of (potential) revisits of `node`.
680 # This information can be used to debug search algorithms.
681 # And to detect when heuristics are not admissible.
683 # See `SearchSolver::revisits` and `SearchSolver::do_revisit`
685 var revisits
: Int = 0
687 # Create a new child node for the next state, according to `problem`.
688 # Used internally by the solvers but made public for those who want to replay a plan.
690 # ensure `result.parent == self`
691 # ensure `result.action == action`
692 fun apply_action
(action
: A
): SearchNode[S
, A
]
694 var new_state
= problem
.apply_action
(state
, action
)
695 var new_cost
= problem
.cost
(state
, action
, new_state
)
696 var new_node
= new SearchNode[S
, A
](problem
, new_state
, self, action
, cost
+ new_cost
, depth
+1)
697 new_node
.compute_heuristic
701 # Build the sequence of nodes from the initial node to `self`
703 # ensure `result.first.is_root and result.last == self`
704 fun path
: Sequence[SearchNode[S
, A
]]
706 var res
= new List[SearchNode[S
, A
]]
709 while node
!= null do
716 # Build a sequence of actions from the initial state to `self`
717 # See `path` for a more detailed plan.
718 fun plan
: Sequence[A
]
720 var res
= new List[A
]
721 var node
: nullable SearchNode[S
, A
] = self
722 while node
!= null do
724 if a
!= null then res
.unshift
(a
)
730 # Just print a detailed path on the screen
733 print
"result:{state}"
736 if a
!= null then print
" + {a or else ""}"
737 print
" {n.steps}: {n.state} ({n.cost}$)"
741 redef fun to_s
do return "#{steps}/{id} d={depth} f={cost+heuristic} g={cost} h={heuristic}: {state}"
742 #redef fun to_s do return "#{steps} f={(cost+heuristic).to_i} g={cost.to_i} h={heuristic.to_i}"