20a502c978dbbc2b3ab3c6db77a70c4990833710
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.
21 # Abstract search problem over immutable states (`S`) and actions (`A`).
23 # This class serves to model problems of planing and path-finding.
24 # A state, `S`, is a point in the search problem and fully models a given state of the world.
25 # An action, `A`, is an available mean of transition between two states.
27 # This abstract class is generic made to work with any kind of states and actions.
28 # Therefore, specific subclasses must be developed to implement the required services:
35 # Note that the implemented methods should not temper with the parameters since it is expected
36 # that they remain unmodified.
41 # These tree method are enough to trigger a basic search.
43 # The methods `breadth_first` and `depth_first` return pre-configured solvers for, respectively,
44 # a breadth-first search, a depth-first search.
49 # The `cost` method can be implemented to represent the cost of a single transition.
50 # By default, the cost is 1.
52 # The `heuristic` method can be implemented to represent a lower-bound estimation of the remaining
53 # cost to reach a goal state.
54 # By default, the heuristic is 0.
56 # If one of these (or both) methods are implemented, the `astar` method will return a pre-configured
57 # solver for a A* search.
59 # More configuration and optimization on the search can to be done in the `SearchSolver` class.
60 interface SearchProblem[S
: Object, A
]
61 # The starting state for the problem
62 fun initial_state
: S
is abstract
64 # The available applicable actions for a given state.
65 # While there is a potential large number of distinct states and actions, there should be only
66 # a small number of possible action from a specific state (a small, or at least finite, branching factor).
67 fun actions
(state
: S
): nullable SequenceRead[A
] is abstract
69 # The new state when applying a given action
71 # The returned state can be:
72 # * a completely new state,
73 # * an existing state,
74 # * a new state but equals to an existing state
75 # in this case, ensure that the `==` and `hash` method
76 # are correctly implemented.
78 # Remember, this method should not modify its parameters.
80 # REQUIRE: `actions(state).has(action)`
81 fun apply_action
(state
:S
, action
:A
): S
is abstract
83 # Is the state a goal state?
84 # Once a goal state is found, the solver is automatically stopped.
85 # A problem can have 0, one or more goals if it makes sense
86 # but solver must be used accordingly.
88 fun is_goal
(state
:S
): Bool do return false
90 # The cost for `action` from `old_state` to `new_state`
91 # REQUIRE: `apply_action(old_state, action) == new_state`
93 # Note that having a 0 or negative value can make some search
94 # algorithms fail, or not terminate.
95 fun cost
(state
:S
, action
:A
, state2
: S
): Float do return 1.0
97 # An heuristic of the estimated `cost` going from `state` to a goal state.
99 # Is is expected that the heuristic is *admissible*, it means its is an
100 # optimistic estimation that never an over-estimate, thus is cannot be#
101 # higher than the lowest possible remaining cost.
102 # See `SearchSolver::do_revisit` for details.
105 fun heuristic
(state
: S
): Float do return 0.0
107 # return a new breadth-first solver
108 fun breadth_first
: SearchSolver[S
, A
]
110 var todo
= (new Array[SearchNode[S
, A
]]).as_fifo
111 var sol
= new SearchSolver[S
, A
](self, todo
)
115 # return a new depth-first solver
116 fun depth_first
: SearchSolver[S
, A
]
118 var todo
= (new List[SearchNode[S
, A
]]).as_lifo
119 var sol
= new SearchSolver[S
, A
](self, todo
)
123 # return a new best-first solver
126 # * if `heuristic` is not defined, this is basically a Dijkstra search.
127 # * if `cost` in not defined either, this is basically a breadth-first search.
128 fun astar
: SearchSolver[S
, A
]
130 var cpt
= new NodeComparator[S
, A
]
131 var todo
= new MinHeap[SearchNode[S
, A
]](cpt
)
132 var sol
= new SearchSolver[S
, A
](self, todo
)
136 # Create the initial node in the search-tree.
137 # Used internally by the solvers but made public for those who want to replay a plan.
138 fun initial_node
: SearchNode[S
, A
]
140 var res
= new SearchNode[S
,A
](self, initial_state
, null, null, 0.0, 0)
141 res
.compute_heuristic
145 # Negligible quantity for float comparisons
146 # Because of float imprecision, two really near float values should be considered equals.
147 # However, the specific epsilon value could be specific to the problem.
149 # The epsilon value is used for cost comparisons.
152 fun epsilon
: Float do return 0.000000001
154 # Run and evaluate solvers with multiple configuration.
155 # This method can be used to evaluate which configuration to choose by default for a given problem.
157 # `steps` is the maximum number of steps a giver configuration can run.
158 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
598 var res
= run_steps
(steps
)
606 # Used to compare nodes with their score.
607 # Smaller is score, smaller is the node.
608 private class NodeComparator[S
: Object, A
]
609 super Comparator[SearchNode[S
, A
]]
610 redef fun compare
(a
,b
) do return a
.score
<=> b
.score
613 # A node in the search-tree visited by a `SearchSolver`.
614 # In search-trees, nodes are labeled with states (`S`), and edges by actions (`A`).
616 # The root node is labeled by the initial state of the problem.
618 # This class is exposed to allow queries on the solution provided by the solver.
619 class SearchNode[S
: Object, A
]
620 # A flag that indicate that `self` is virtually removed from the todo-list.
621 # `self` was added to the todo-list but that a better node for the
622 # same state was found latter.
623 private var drop
= false
625 # The associated problem
626 var problem
: SearchProblem[S
, A
]
628 # The state associated to `self`.
629 # The state labels the node `self`.
632 # Is `self` a root node of the search-tree?
633 # ensure: `result` == `parent == null` and `result`== `action == null`
634 fun is_root
: Bool do return parent
== null
636 # The previous node in the search-tree (if not root).
637 var parent
: nullable SearchNode[S
, A
]
639 # The action used to go from `parent` to `self` (if not root)
640 # The action labels the edge from `parent` to `self`.
641 var action
: nullable A
643 # The past cost (g) from the root node to `self`.
646 # The heuristic from self to the goal (according to `problem.heuristic(state)`
647 # It is the future cost (h)
648 var heuristic
: Float is noinit
650 # The sum of `cost` and `heuristic`
651 # It is the f function.
652 var score
: Float is noinit
654 # Update `heuristic` and `score` according to `problem`.
655 private fun compute_heuristic
657 var h
= problem
.heuristic
(state
)
662 # The depth of `self` in the search tree
663 # It is the number of parents to the root node.
666 # The number of steps needed by the solver to process `self`
667 # It is just a useless generation number, but could be used to evaluate
668 # the behavior of search algorithms.
671 # The rank of creation of nodes by the solver.
672 # It is just a useless generation number, but could be used to evaluate
673 # the behavior of search algorithms.
676 # The number of (potential) revisits of `node`.
677 # This information can be used to debug search algorithms.
678 # And to detect when heuristics are not admissible.
680 # See `SearchSolver::revisits` and `SearchSolver::do_revisit`
682 var revisits
: Int = 0
684 # Create a new child node for the next state, according to `problem`.
685 # Used internally by the solvers but made public for those who want to replay a plan.
687 # ensure `result.parent == self`
688 # ensure `result.action == action`
689 fun apply_action
(action
: A
): SearchNode[S
, A
]
691 var new_state
= problem
.apply_action
(state
, action
)
692 var new_cost
= problem
.cost
(state
, action
, new_state
)
693 var new_node
= new SearchNode[S
, A
](problem
, new_state
, self, action
, cost
+ new_cost
, depth
+1)
694 new_node
.compute_heuristic
698 # Build the sequence of nodes from the initial node to `self`
700 # ensure `result.first.is_root and result.last == self`
701 fun path
: Sequence[SearchNode[S
, A
]]
703 var res
= new List[SearchNode[S
, A
]]
706 while node
!= null do
713 # Build a sequence of actions from the initial state to `self`
714 # See `path` for a more detailed plan.
715 fun plan
: Sequence[A
]
717 var res
= new List[A
]
718 var node
: nullable SearchNode[S
, A
] = self
719 while node
!= null do
721 if a
!= null then res
.unshift
(a
)
727 # Just print a detailed path on the screen
730 print
"result:{state}"
733 if a
!= null then print
" + {a or else ""}"
734 print
" {n.steps}: {n.state} ({n.cost}$)"
738 redef fun to_s
do return "#{steps}/{id} d={depth} f={cost+heuristic} g={cost} h={heuristic}: {state}"
739 #redef fun to_s do return "#{steps} f={(cost+heuristic).to_i} g={cost.to_i} h={heuristic.to_i}"