view release on metacpan or  search on metacpan

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

 ##################################################################
 #
 # 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.


=item *

B<State goal function> (C<_state_goal_p_func> above)

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


=item *

B<State number of successors function> (C<_state_num_successors_func> above)

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


=item *

B<State successors iterator> (C<_state_iterator> above)

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

This function returns a string representation of this node.


=item *

B<State show-progress function> (C<_show_prog_func> above)

This is a callback function for displaying the progress of the search.
It can be an empty callback if you do not need this output.


=item *

B<log string function> (C<log_function> above)

This is an arbitrary string used for logging.    It also gets passed to
the show-progress function above.


=item *

B<str_function> (C<str_function> above)

This function returns a *unique* string representation of this node.
Uniqueness is required for SMA* to work properly.


=item *

B<max states allowed in memory> (C<max_states_in_queue> above)

An integer indicating the maximum number of expanded nodes to hold in
memory at any given time.


=item *

B<maximum cost> (C<MAX_COST> above)

An integer indicating the maximum cost, beyond which nodes will not
be expanded.





=back



=head1 DESCRIPTION


=head2 Overview

Simplified Memory-bounded A* search (or SMA* search) addresses some of the
limitations of conventional A* search, by bounding the amount of space required
to perform a shortest-path search.   This module is an implementation of
SMA*, which was first introduced by Stuart Russell in 1992.   SMA* is a simpler,
more efficient variation of the original MA* search introduced by P. Chakrabarti
et al. in 1989 (see references below).



=head2 Motivation and Comparison to A* Search


=head3 A* search

A* Search is an I<optimal> and I<complete> algorithm for computing a sequence of
operations leading from a system's start-state (node) to a specified goal.
In this context, I<optimal> means that A* search will return the shortest
(or cheapest) possible sequence of operations (path) leading to the goal,
and I<complete> means that A* will always find a path to 
the goal if such a path exists.

In general, A* search works using a calculated cost function on each node along a
path, in addition to an I<admissible> heuristic estimating the distance from 
that node to the goal.  The cost is calculated as:

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

Where:


=over

=item *

I<n> is a state (node) along a path

=item *

I<g(n)> is the total cost of the path leading up to I<n> 

=item *

I<h(n)> is the heuristic function, or estimated cost of the path from I<n>
to the goal node.

=back


For a given admissible heuristic function, it can be shown that A* search
is I<optimally efficient>, meaning that,  in its calculation of the shortest
path, it expands fewer nodes in the search space than any other algorithm.

To be admissible, the heuristic I<h(n)> can never over-estimate the distance
from the node to the goal.   Note that if the heuristic I<h(n)> is set to
zero, A* search reduces to I<Branch and Bound> search.  If the cost-so-far
I<g(n)> is set to zero, A* reduces to I<Greedy Best-first> search (which is
neither complete nor optimal).   If both I<g(n)> and I<h(n)> are set to zero,
the search becomes I<Breadth-first>, which is complete and optimal, but not
optimally efficient.

The space complexity of A* search is bounded by an exponential of the
branching factor of the search-space, by the length of the longest path
examined during the search.   This is can be a problem particularly if the
branching factor is large, because the algorithm may run out of memory.