AI-Pathfinding-SMAstar

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

  * log string function (log_function above)

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

  * str_function (str_function above)

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

  * max states allowed in memory (max_states_in_queue above)

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

  * maximum cost (MAX_COST above)

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



DESCRIPTION

Overview

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 more efficient variation of the 
original MA* search introduced by Chakrabarti et al. in 1989. See references below.

Motivation and Comparison to A* Search

A* search

A* Search is an optimal and complete algorithm for computing a sequence of 
operations leading from a system's start-state (node) to a specified goal. In 

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

{
    my ($self, $state) = @_;


    my $state_eval_func = $self->{_state_eval_func};
    my $state_goal_p_func = $self->{_state_goal_p_func};
    my $state_num_successors_func = $self->{_state_num_successors_func},
    my $state_successors_iterator = $self->{_state_successors_iterator},
    my $state_get_data_func = $self->{_state_get_data_func};
    
    # make sure required functions have been defined
    if(!defined($state_eval_func)){
	croak "SMAstar:  evaluation function is not defined\n";
    }
    if(!defined($state_goal_p_func)){
	croak "SMAstar:  goal function is not defined\n";
    }
    if(!defined($state_num_successors_func)){
	croak "SMAstar:  num successors function is not defined\n";
    }
   if(!defined($state_successors_iterator)){

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

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.

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

=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