ai :: SearchProblem :: defaultinit
# Abstract search problem over immutable states (`S`) and actions (`A`).
#
# This class serves to model problems of planing and path-finding.
# A state, `S`, is a point in the search problem and fully models a given state of the world.
# An action, `A`, is an available mean of transition between two states.
#
# This abstract class is generic made to work with any kind of states and actions.
# Therefore, specific subclasses must be developed to implement the required services:
#
# * `initial_state`
# * `actions`
# * `apply_action`
# * `is_goal`
#
# Note that the implemented methods should not temper with the parameters since it is expected
# that they remain unmodified.
#
#
# # Basic search
#
# These tree method are enough to trigger a basic search.
#
# The methods `breadth_first` and `depth_first` return pre-configured solvers for, respectively,
# a breadth-first search, a depth-first search.
#
#
# # Advanced search
#
# The `cost` method can be implemented to represent the cost of a single transition.
# By default, the cost is 1.
#
# The `heuristic` method can be implemented to represent a lower-bound estimation of the remaining
# cost to reach a goal state.
# By default, the heuristic is 0.
#
# If one of these (or both) methods are implemented, the `astar` method will return a pre-configured
# solver for a A* search.
#
# More configuration and optimization on the search can to be done in the `SearchSolver` class.
interface SearchProblem[S: Object, A]
# The starting state for the problem
fun initial_state: S is abstract
# The available applicable actions for a given state.
# While there is a potential large number of distinct states and actions, there should be only
# a small number of possible action from a specific state (a small, or at least finite, branching factor).
fun actions(state: S): nullable SequenceRead[A] is abstract
# The new state when applying a given action
#
# The returned state can be:
# * a completely new state,
# * an existing state,
# * a new state but equals to an existing state
# in this case, ensure that the `==` and `hash` method
# are correctly implemented.
#
# Remember, this method should not modify its parameters.
#
# REQUIRE: `actions(state).has(action)`
fun apply_action(state:S, action:A): S is abstract
# Is the state a goal state?
# Once a goal state is found, the solver is automatically stopped.
# A problem can have 0, one or more goals if it makes sense
# but solver must be used accordingly.
# Default: no goals
fun is_goal(state:S): Bool do return false
# The cost for `action` from `old_state` to `new_state`
# REQUIRE: `apply_action(old_state, action) == new_state`
# Default: `1`.
# Note that having a 0 or negative value can make some search
# algorithms fail, or not terminate.
fun cost(state:S, action:A, state2: S): Float do return 1.0
# An heuristic of the estimated `cost` going from `state` to a goal state.
#
# Is is expected that the heuristic is *admissible*, it means its is an
# optimistic estimation and never an over-estimate, thus is cannot be
# higher than the lowest possible remaining cost.
# See `SearchSolver::do_revisit` for details.
#
# Default: `0`.
fun heuristic(state: S): Float do return 0.0
# return a new breadth-first solver
fun breadth_first: SearchSolver[S, A]
do
var todo = (new Array[SearchNode[S, A]]).as_fifo
var sol = new SearchSolver[S, A](self, todo)
return sol
end
# return a new depth-first solver
fun depth_first: SearchSolver[S, A]
do
var todo = (new List[SearchNode[S, A]]).as_lifo
var sol = new SearchSolver[S, A](self, todo)
return sol
end
# return a new best-first solver
#
# notes:
# * if `heuristic` is not defined, this is basically a Dijkstra search.
# * if `cost` in not defined either, this is basically a breadth-first search.
fun astar: SearchSolver[S, A]
do
var cpt = new NodeComparator[S, A]
var todo = new MinHeap[SearchNode[S, A]](cpt)
var sol = new SearchSolver[S, A](self, todo)
return sol
end
# Create the initial node in the search-tree.
# Used internally by the solvers but made public for those who want to replay a plan.
fun initial_node: SearchNode[S, A]
do
var res = new SearchNode[S,A](self, initial_state, null, null, 0.0, 0)
res.compute_heuristic
return res
end
# Negligible quantity for float comparisons
# Because of float imprecision, two really near float values should be considered equals.
# However, the specific epsilon value could be specific to the problem.
#
# The epsilon value is used for cost comparisons.
#
# Default: 1E-9
fun epsilon: Float do return 0.000000001
# Run and evaluate solvers with multiple configuration.
# This method can be used to evaluate which configuration to choose by default for a given problem.
#
# `steps` is the maximum number of steps a giver configuration can run.
fun run_configs(steps: Int)
do
var c = 0
loop
if astar.run_config(steps, c, "A*") then break
c += 1
end
end
# Various Map implementations of memory.
# In order to try more configurations with `run_config`, this method
# is called to provide alternative implementation.
#
# For instance, a subclass can redefine this method and extends the result with an additional `RBTreeMap`.
# Note: because the true nature of the sates `S` is left to the user, some
# specific Map implementation could be more efficient than a HashMop.
#
# Default: A `HashMap`
fun make_memory: Array[Map[S, SearchNode[S, A]]]
do
var res = new Array[Map[S, SearchNode[S, A]]]
res.add new HashMap[S, SearchNode[S, A]]
return res
end
end
lib/ai/search.nit:23,1--184,3