Search

Input types for searches:

type alias Step state =

state -> List ( state, Bool )

Defines the type of the step function that produces new states from existing ones. This is how the graph over the search space is defined. The step function takes a state and provides a list of other states that can be reached from it. Each of the listed states is paired with a Bool that when true indiciates that a state is considered to be a goal of the search.

type alias Uninformed state =

{ step : Step state

, cost : state -> Float

}

Defines the type of a bundle of operators that need to be supplied to conduct an uninformed (non-heuristic) search.

type alias Informed state =

{ step : Step state

, cost : state -> Float

, heuristic : state -> Float

}

Defines the type of a bundle of operators that need to be supplied to conduct an informed (heuristic) search.

type alias WithUninformed a state =

{ a | step : Step state, cost : state -> Float }

Defines the type of a bundle of operators that need to be supplied to conduct an uninformed (non-heuristic) search. This is an extensible record so that heuristic searches can also have this type since they use the same cost and step functions. This makes it easy to switch from a heuristic to anon-heuristic search.

The search output type:

type SearchResult state

= Complete

| Goal state (() -> SearchResult state)

| Ongoing state (() -> SearchResult state)

Defines the possible outcomes of a search. A search may produce the following results:

Complete. The search space has been exhausted without finding a goal state.
Goal. A goal state has been found. A function to find further results is also returned, in order that the search may be continued to find more goals.
Ongoing. A goal state has not been found yet. The state most recently examined is returned along with a function to continue to the search.

Helper functions for iterating searches to produce results:

next : SearchResult state -> SearchResult state

Steps a search result, to produce the next result.

The result of this function may be an Ongoing search. This will provide the current head search node and a continuation to run the remainder of the search.

nextN : Int -> SearchResult state -> SearchResult state

Continues a search result, to produce the next search goal up to a limited number of iterations.

This function will recursively apply the search until either a Goal state is found or the walk over the search space is Complete, or the iteration count is exhausted in which case an Ongoing search may be returned.

nextGoal : SearchResult state -> SearchResult state

Continues a search result, to produce the next search goal.

The result of this function will never be an Ongoing search. This function will recursively apply the search until either a Goal state is found or the walk over the search space is Complete.
If the search is insufficiently constrained and no goal can ever be found, this function may infnite loop.

Uninformed search strategies:

breadthFirst : WithUninformed a state -> List state -> SearchResult state

Performs an unbounded breadth first search. Breadth first searches store a lot of pending nodes in the buffer, so quickly run out of space.

depthFirst : WithUninformed a state -> List state -> SearchResult state

Performs an unbounded depth first search. Depth first searches can easily fall into infinite loops.

depthBounded : WithUninformed a state -> Int -> List state -> SearchResult state

Implements an uninformed search that is bounded to a specified maximum depth.

costBounded : WithUninformed a state -> Float -> List state -> SearchResult state

Implements a cost bounded search. This search will proceed depth first.

uniformCost : WithUninformed a state -> List state -> SearchResult state

Performs a uniform-cost search. This always follows the search node that has the lowest path cost. It is called a uniform cost search because the boundary of the search will have a roughly uniform cost as the search space is searched by increasing cost.

iterativeDeepening : Int -> WithUninformed a state -> List state -> SearchResult state

Implements an iterative deepening search. This search proceed depth first but repeats at progressively larger depth limits. The iteration number is multiplied by a specified multiple to calculate the maximum depth allowed at a given iteration.

iterativeCostIncreasing : Float -> WithUninformed a state -> List state -> SearchResult state

Implements an iterative cost increasing search. This search proceed depth first but repeats at progressively larger cost limits. The iteration number is multiplied by a specified multiple to calculate the maximum cost allowed at a given iteration.

Informed search strategies:

aStar : Informed state -> List state -> SearchResult state

Performs an A* search. This is one that always follows the search node that has the highest f value (f = heuristic + cost). The seach will only be optimal if the heuristic function is monotonic.

greedy : Informed state -> List state -> SearchResult state

Performs a greedy heuristic search. This is one that always follows the search node that has the highest h value (h = heuristic).

fBounded : Informed state -> Float -> List state -> SearchResult state

Implements an f value (f = heuristic + cost) bounded search. This search will proceed depth first.

iterativeDeepeningAStar : Float -> Informed state -> List state -> SearchResult state

Implements an iterative deepding A-star search. This search proceed depth first but repeats at progressively larger f-limits (f = cost + heuristic). The iteration number is multiplied by a specified multiple to calculate the maximum cost allowed at a given iteration.

Like the A-star search, this search will find the optimal soluation given an admissable heuristic. As this search progresses depth first rather than sleecting the most promising nodes to follow, its memory requirements are lower than A-star.

the-sett/ai-search/4.1.0