nmpuzzle / Search.lhs

Full commit
%include polycode.fmt
%format `on`      = "\operatorname{on}"
%format <$>       = "\, \langle\$\rangle \,"

%format q0        = "q_0"
%format qt        = "q_t"
%format at        = "a_t"
%format nt        = "n_t"

%format expand    = "\delta"
%format nexpanded = "n_{\delta}s"
%format goalp     = "\Phi_F"
\title{AI Tree |Search| Library}
\author{Rhys !}
\date{April 2014}

A Haskell\cite{haskell} module for AI tree search is implemented and commented



This is the |Search| module, for generic AI tree search. Here we export some
constructors and functions for other code to use.

module Search  ( FrontierApp
               , Path
               , SearchResult
               , mkNode, mkRoot
               , stateAt, prevStates
               , actions
               , breadthFirst
               , depthFirst
               , aStar
               , greedyBF
               , search) where

Next, we import a few base Haskell modules that contain some useful
functions.\todo[inline]{Acknowledgments: Data.List.Ordered and

import Control.Applicative ((<$>))
import Data.Function
import Data.List (sortBy)
import Data.List.Ordered (mergeBy)

\section{The |Path| Algebraic Data Type}
All the search algorithms implemented represent the search space as a tree of
states branching from a root node. The |Path| algebraic data type
(ADT)\footnote{Not to be confused with \emph{abstract} data type. Further
details in \cite{adt}.} is used to represent a node on these trees. The type is
parametric over two other types: |a| to record actions or transformations, and
|q|\footnote{From the set of states $Q$ in (non)deterministic finite state
automata (NFA)\cite{nfa}.} to record state.

The type stores a list of actions and states in `reverse chronological order',
ie. with the root state at the end of the list. Since there is no action
associated with the initial state (|q0|), the actions list will always have one
less element than the states list.

data Path a q =  Path  { actions :: [a]
                       , states :: [q] }

Next, a couple of constructor-like functions for |Path| are defined; one to
create a root node and one to create a child node.
mkRoot :: q -> Path a q
mkRoot q0 = Path [] [q0]

mkNode :: Path a q -> a -> q -> Path a q
mkNode (Path as qs) at qt = Path (at:as) (qt:qs)

\section{Search Methods}\todo[inline]{Custom strategies.}
The difference between the search methods implemented is in how they order the
frontier\footnote{The frontier is the list of nodes yet to be examined.}, and
thus the order of node examination. In this implementation, search methods are
defined as a frontier modification function. All methods are guaranteed to be
stable \cite{stable}, ie. the relative order of the nodes provided by the
|expand| function will be preserved in the frontier.

To shorten type signatures, a |FrontierApp| alias is declared. This alias
is polymorphic over the action |a| and state |q| types, like |Path|, and
represents a function that combines the current frontier (hereupon |frontier|)
and a list of new nodes (hereupon |nexpanded|\footnote{From \emph{n}ode,
$\delta$ (see section \ref{search}) and the common Haskell suffix \emph{s} for
lists.}) to create a new frontier.

type FrontierApp a q = [Path a q] -> [Path a q] -> [Path a q]

\subsection{Uninformed Methods}
The two uninformed methods are trivial to define: a breadth first search will
add new nodes to the end of the list, while a depth-first search will add them
to the start of the list.

breadthFirst, depthFirst :: FrontierApp a q
breadthFirst = (++)
depthFirst = flip (++)

\subsection{Informed Methods}
The two informed methods are slightly more complex, since they take additional
factors into account.

Firstly, greedy breadth first search (GBFS). GBFS takes only one additional
factor into account, namely an estimated distance to the a goal node, typically
designated $h(n)$ where $n$ represents the current node. |greedyBF| takes a
heuristic function of type |q -> Integer|, and returns a |FrontierApp| that
sorts the frontier using that function.

greedyBF :: (Ord m, Num m) => (q -> m) -> FrontierApp a q
greedyBF h frontier nexpanded = mergeUSOn h' nexpanded frontier where
  h' = h . stateAt

A* search takes both $h(n)$ and a known path cost $g(n)$ into account. |g|
accepts the action type |a| instead of the state |q| to allow for simple state
sharing, if the caller desires\footnote{Obviously, the function could be
broadened to |q -> a -> Integer| if required in a later version.}.

-- TODO: presorted version
aStar :: (Ord m, Num m) => (a -> m) -> (q -> m) -> FrontierApp a q
aStar g h frontier nexpanded = mergeUSOn f nexpanded frontier where
    f (Path (at:_) (qt:_)) = h qt + g at

\section{Running a Search}\label{search}
Using the above definitions, the |search| function is fairly trivial, simply
expanding the head of the frontier until a goal state is reached or the frontier
is emptied.

|search| takes a |FrontierApp| value |app|, expansion function
|expand|\footnote{\label{delta}In reference to the transition functions of
NFA.}, a goal predicate |goalp|\footnote{From set-builder notation
$\Phi$\cite{set-notation} and the NFA goal set $F$\cite{nfa}.} and an initial
state |q0|\footnote{ibid.}. The function returns a |Maybe| value because the
goal state may not be achievable.

type SearchResult a q = (Int, Maybe (Path a q))

search :: (Eq q) =>
    FrontierApp a q ->
    (Path a q -> [Path a q]) ->
    (q -> Bool) ->
    q ->
    SearchResult a q

The root of the search tree is defined as |q0| and the recursive function |go|
is called with the root-populated frontier.\todo[inline]{Note counter.}

search app expand goalp q0 = go 0 [mkRoot q0] where
      go procCount (nt@(Path as (qt:qs)):ns)

For each head of the frontier, |nt|, |go|:

    \item Makes a goal check and returns |nt| if |goalp| is satisfied
          | goalp qt      = (1 + procCount + length ns, Just nt)
    \item Checks if |nt| is a duplicate state and ignores it if so
          | qt `elem` qs  = go (procCount + 1) ns
    \item Expands the node with |expand| and adds the resulting nodes to the
          frontier using |app|.
          | otherwise     = go (procCount + 1) (app ns (expand nt))

If the frontier has been emptied, there is no solution and |Nothing| is

      go procCount [] = (procCount, Nothing)

\section{Utility Definitions}
% The following code is hidden from the TeX output, since it's just for testing.
%if False
    \item A |Show| instance so |Path| values can be pretty-printed.
instance (Show a, Show q) => Show (Path a q) where
    show (Path as qs) = showl as qs where
      showl  []       (q0:[])  =  show q0
      showl  (at:as)  (qt:qs)  =  showl as qs ++ " " ++
                                  show at ++ " -> " ++ show qt
    \item Sorting and merging ordered lists on a transform. The underlying
          |sortBy| and |mergeBy| functions are stable, and thus are all the
          functions below.\todo[inline]{Check sort performance.}
sortOn :: (Ord b) => (a -> b) -> [a] -> [a]
sortOn f = sortBy (compare `on` f)

mergeOn :: (Ord b) => (a -> b) -> [a] -> [a] -> [a]
mergeOn f = mergeBy (compare `on` f)

mergeUSOn :: (Ord b) => (a -> b) -> [a] -> [a] -> [a]
mergeUSOn f uxs = mergeOn f (sortOn f uxs)

  \item |stateAt| returns the state value of a node and |prevStates| returns all
        previous states from the current node to the root node.
stateAt :: Path a q -> q
stateAt = head . states

prevStates :: Path a q -> [q]
prevStates = tail . states


  `The Haskell Programming Language'

  `Algebraic data type'

  `Set-builder notation'

  Almeida M, Moreira N, Reis R,
  `On the performance of automata minimization algorithms',
  p. 3

  `Sorting algorithm',
  section `Stability'