view release on metacpan or  search on metacpan

README  view on Meta::CPAN

AI-Pathfinding-SMAstar version 0.07
===================================

NAME

AI::Pathfinding::SMAstar - Memory-bounded A* Search

SYNOPSIS

 use AI::Pathfinding::SMAstar;

EXAMPLE

 ##################################################################
 #
 # This example uses a hypothetical object called FrontierObj, and
 # shows the functions that FrontierObj must feature in order to 
 # perform a path search in a solution-space populated by 
 # FrontierObj objects.
 #
 ##################################################################

 my $smastar = AI::Pathfinding::SMAstar->new(
        # evaluates f(n) = g(n) + h(n), returns a number
        _state_eval_func           => \&FrontierObj::evaluate,

        # when called on a node, returns 1 if it is a goal
        _state_goal_p_func         => \&FrontierObj::goal_test,

        # must return the number of successors of a node
        _state_num_successors_func => \&FrontierObj::get_num_successors,

        # must return *one* successor at a time
        _state_successors_iterator => \&FrontierObj::get_successors_iterator,

        # can be any suitable string representation 
        _state_get_data_func       => \&FrontierObj::string_representation,

        # gets called once per iteration, useful for showing algorithm progress
        _show_prog_func            => \&FrontierObj::progress_callback,      
    );

 # you can start the search from multiple start-states
 # Add the initial states to the smastar object before starting the search.
 foreach my $frontierObj (@start_states){
    $smastar->add_start_state($frontierObj);
 }

 # Start the search.  If successful, frontierGoalObj will contain the 
 # goal node.   The optimal path to the goal node will be encoded in the 
 # ancestry of the goal node.   $frontierGoalObj->antecedent() contains
 # the goal object's parent, and so forth back to the start state.
 my $frontierGoalObj = $smastar->start_search(
    \&log_function,       # returns a string used for logging progress
    \&str_function,       # returns a string used to *uniquely* identify a node 
    $max_states_in_queue, # indicate the maximum states allowed in memory
    $MAX_COST,            # indicate the maximum cost allowed in search
    );

Explanation

In the example above, a hypothetical object, FrontierObj, is used to 
represent a node in your search space. To use SMA* search to find a shortest 
path from a starting node to a goal in your search space, you must define what 
a node is, in your search space (or point, or state).

A common example used for informed search methods, and one that is 
used in Russell's original paper, is a N-puzzle, such as an 8-puzzle or 
15-puzzle. If trying to solve such a puzzle, a node in the search space 
could be defined as a particular configuration of that puzzle.    In the 
/t directory of this module's distribution, SMA* is applied to the problem 
of finding the shortest palindrome that contains a minimum number of letters 
specified, over a given lexicon of words.

Once you have a definition and representation of a node in your search space, SMA* 
search requires the following functions to work:

  ** State evaluation function (_state_eval_func above)

      This function must return the cost of this node in the search space. In all 
forms of A* search, this means the cost paid to arrive at this node along a path, 
plus the estimated cost of going from this node to a goal state. This function 
must be positive and monotonic, meaning that successor nodes mustn't be less 
expensive than their antecedent nodes. Monotonicity is ensured in this implementation 
of SMA*, so even if your function is not monotonic, SMA* will assign the antecedent 
node's cost to a successor if that successor costs less than the antecedent.
  
  * State goal predicate function (_state_goal_p_func above)

      This function must return 1 if the node is a goal node, or 0 otherwise.
    

  * State number of successors function (_state_num_successors_func above)

      This function must return the number of successors of this node, i.e. all 
      nodes that are reachable from this node via a single operation.
    

  * State successors iterator (_state_iterator above)

      This function must return a *handle to a function* that returns next 
      successor of this node, i.e. it must return an iterator that produces 
      the successors of this node *one* at a time. This is 
      necessary to maintain the memory-bounded constraint of SMA* search.
    

  * State get-data function (_state_get_data_func above)

      This function returns a string representation of this node.
    

  * State show-progress function (_show_prog_func above)