view release on metacpan or  search on metacpan

lib/AI/Pathfinding/SMAstar.pm  view on Meta::CPAN

1;
__END__
# Below is stub documentation for your module. You'd better edit it!

=head1 NAME

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


=head1 SYNOPSIS

 use AI::Pathfinding::SMAstar;
  

=head2 EXAMPLE

 ##################################################################
 #
 # This example uses a hypothetical object called FrontierObj, and
 # shows the functions that the FrontierObj class 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, $frontierGoalPath will contain the
 # goal path.   The optimal path to the goal node will be encoded in the
 # ancestry of the goal path.   $frontierGoalPath->antecedent() contains
 # the goal path's parent path, and so forth back to the start path, which
 # contains only the start state.
 #
 # $frontierGoalPath->state() contains the goal FrontierObj itself.
 #
 my $frontierGoalPath = $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
    );



In the example above, a hypothetical object, C<FrontierObj>, is used to
represent a state, or I<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 I<node> is, in your search space (or I<point>, or I<state>).

A common example used for informed search methods, and one that is used in Russell's
original paper, is optimal puzzle solving, such as solving an 8 or 15-tile puzzle
in the least number of moves.   If trying to solve such a puzzle, a I<node> in the
search space could be defined as a  configuration of that puzzle (a paricular
ordering of the tiles).

There is an example provided in the /t directory of this module's distribution,
where SMA* is applied to the problem of finding the shortest palindrome that
contains a minimum number of letters specified, over a given list of words.

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


=over


=item *

B<State evaluation function> (C<_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:

I<f(x) = g(n) + h(n)>

This function must be I<positive> and I<monotonic>, meaning that the path to a
successor node must be at least as expensive overall when compared to the path
to that node's antecedent.   So if the nodes along a particular path are
labeled:  1 -> 2 -> 3, it must be at least as expensive to arrive at node 3 as
it is to arrive at node 2.   This amounts to the evaluation of the following
assignment B<[1]> when calculating the cost of a successor of node I<x>:

I<f(successor) = max(f(x), g(successor) + h(successor))>  

NOTE: Monotonicity is ensured in this implementation of SMA*, so even if your
function is not monotonic (which is possible, even given an admissible 
heuristic), SMA* will assign the antecedent node's cost to a successor if
that successor's I<g+h> amounts to less than the antecedent's f-cost.