AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
- original version; created by h2xs 1.23 with options
-XAn AI::Pathfinding::SMAstar
0.02 Fri Feb 25 11:17:01 2010
- updated pod documentation
0.03 Sun Feb 28 12:26:58 2010
- updated pod documentation
0.04 Tue Mar 2 13:17:53 2010
- updated error handling in add_start_state method
- perldoc edits
0.05 Thu Mar 4 11:06:10 2010
- fixed an issue where search did not terminate when max_cost
is reached.
0.06 Thu Mar 4 11:06:10 2010
- fixed an issue with successor iterator in Path class.
# 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.
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
this context, optimal means that A* search will return the shortest possible
sequence of operations (path) leading to the goal, and 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 admissible heuristic estimating the distance
from that node to the goal. The cost is calculated as:
f(n) = g(n) + h(n)
probability of producing a sub-optimal solution.
METHODS
new()
Creates a new SMA* search object.
start_search()
Initiates a memory-bounded search. You must pass a log_function for recording
current status, a function that returns a *unique* string representing a node in
the search-space, a maximum number of expanded states to store in the queue, and a
maximum cost value, beyond which the search will cease.
state_eval_func()
Sets/gets the function that returns the cost of this node in the
search space.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
my $self = shift;
if (@_) { $self->{_show_prog_func} = shift }
return $self->{_show_prog_func};
}
###################################################################
#
# Add a state from which to begin the search. There can
# be multiple start-states.
#
###################################################################
sub add_start_state
{
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};
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
}
# add this node to the queue
$self->{_priority_queue}->insert($state_obj);
}
###################################################################
#
# start the SMAstar search process
#
###################################################################
sub start_search
{
my ($self,
$log_function,
$str_function,
$max_states_in_queue,
$max_cost,
) = @_;
if(!defined($str_function)){
croak "SMAstar start_search: str_function is not defined.\n";
}
sma_star_tree_search(\($self->{_priority_queue}),
\&AI::Pathfinding::SMAstar::Path::is_goal,
\&AI::Pathfinding::SMAstar::Path::get_descendants_iterator_smastar,
\&AI::Pathfinding::SMAstar::Path::fcost,
\&AI::Pathfinding::SMAstar::Path::backup_fvals,
$log_function,
$str_function,
\&AI::Pathfinding::SMAstar::Path::progress,
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# 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
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
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)>
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=head1 METHODS
=head2 new()
my $smastar = AI::Pathfinding::SMAstar->new();
Creates a new SMA* search object.
=head2 start_search()
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
);
Initiates a memory-bounded search. When calling this function, pass a handle to
a function for recording current status( C<log_function> above- this can be
an empty subroutine if you don't care), a function that returns a *unique* string
representing a node in the search-space (this *cannot* be an empty subroutine), a
lib/AI/Pathfinding/SMAstar/AVLQueue.pm view on Meta::CPAN
my $size = $avltree->get_size();
return $size;
}
sub print{
my ($self, $delim) = @_;
my @tree_elts = $self->{_avltree}->get_list();
foreach my $obj (@tree_elts){
print $obj->{_start_word} . ", " . $obj->{_phrase} . ", " . $obj->{_queue_counter} . "\n";
}
print "\n\nobj_counts_tree:\n";
$self->{_obj_counts_tree}->print("*");
my $iterator = $self->{_obj_counts_tree}->get_keys_iterator();
print "\n\niterator keys:\n";
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
## the Phrase constructor
##################################################
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_word_list => undef,
_words_w_cands_list => undef,
_dictionary => undef,
_dictionary_rev => undef,
_start_word => undef, # remainder on cand for antecedent of this obj
_word => undef,
_cand => undef, # cand found for the antecedent of this obj
_predecessor => undef,
_dir => 0,
_repeated_pal_hash_ref => {},
_match_remainder_left => undef,
_match_remainder_right => undef,
_letters_seen => undef, # letters seen, up to/including antecedent
_cost => undef, # cost used for heuristic search
_cost_so_far => undef,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
##############################################
## methods to access per-object data
##
## With args, they set the value. Without
## any, they only retrieve it/them.
##############################################
sub start_word {
my $self = shift;
if (@_) { $self->{_start_word} = shift }
return $self->{_start_word};
}
sub word {
my $self = shift;
if (@_) { $self->{_word} = shift }
return $self->{_word};
}
sub cand {
my $self = shift;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my ($self) = @_;
# if fcost has already been calculated (or reassigned during a backup)
# then return it. otherwise calculate it
my $fcost = $self->{_f_cost};
if(defined($fcost)){
return $fcost;
}
my $word = $self->{_start_word};
my $cost = $self->{_cost};
my $cost_so_far = $self->{_cost_so_far};
my $num_new_chars = $self->{_num_new_chars};
my $num_chars_so_far = $self->{_num_chars_so_far};
my $phrase = defined($self->{_phrase}) ? $self->{_phrase} : "";
my $len_phrase = length($phrase);
my $phrase_num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word($phrase);
my $ratio = 0;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $dictionary = $phrase_obj->{_dictionary};
my $dictionary_rev = $phrase_obj->{_dictionary_rev};
my $repeated_pal_hash_ref = $phrase_obj->{_repeated_pal_hash_ref};
my $letters_seen = $phrase_obj->{_letters_seen};
my $cost = $phrase_obj->{_cost};
my $cost_so_far = $phrase_obj->{_cost_so_far};
my $num_chars_so_far = $phrase_obj->{_num_chars_so_far};
my $no_match_remainder = $phrase_obj->{_no_match_remainder};
my $depth = $phrase_obj->{_depth};
my $direction = $phrase_obj->{_dir};
my $word = $phrase_obj->{_start_word};
my $whole_word = $phrase_obj->{_cand};
my $len_whole_word = defined($whole_word) ? length($whole_word) : 0;
my $rev_word = reverse($word);
my $len_word = length($word);
my @cands;
my @descendants;
if($direction == 0){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($word, $dictionary, $dictionary_rev);
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $newcost = $collisions_per_length + $len_w;
my $new_cost_so_far = $cost + $cost_so_far;
#---------------------------------------------------------------------------
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
#_words_w_cands_list => \@words_to_make_phrases,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
_start_word => $w,
_cand => $stored_c,
_word => $w,
_predecessor => $phrase_obj,
_dir => 0,
_repeated_pal_hash_ref => $repeated_pal_hash_ref,
_letters_seen => \@sorted_letters_seen,
_cost => $newcost,
_cost_so_far => $new_cost_so_far,
_num_chars_so_far => $new_num_chars_so_far,
_num_new_chars => $num_new_chars,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
$new_cost_so_far = $cost + $cost_so_far;
}
#---------------------------------------------------------------------------
if($match_remainder){ # there is a length difference between the candidate and this word.
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
_start_word => $match_remainder,
_cand => $c,
_word => $whole_word,
_predecessor => $phrase_obj,
_dir => $new_direction,
_repeated_pal_hash_ref => $repeated_pal_hash_ref,
_letters_seen => \@sorted_letters_seen,
_cost => $newcost,
_cost_so_far => $new_cost_so_far,
_num_chars_so_far => $new_num_chars_so_far,
_num_new_chars => $num_new_chars,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
#my $newcost = $collisions_per_length + $sparsity;
my $newcost = $collisions_per_length + $len_w;
my $new_cost_so_far = $cost + $cost_so_far;
#---------------------------------------------------------------------------
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
_start_word => $w,
_cand => $c,
_word => $w,
_predecessor => $phrase_obj,
_dir => 0,
_repeated_pal_hash_ref => $repeated_pal_hash_ref,
_letters_seen => \@sorted_letters_seen,
_cost => $newcost,
_cost_so_far => $new_cost_so_far,
_num_chars_so_far => $new_num_chars_so_far,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $dictionary_rev = $phrase_obj->{_dictionary_rev};
my $repeated_pal_hash_ref = $phrase_obj->{_repeated_pal_hash_ref};
my $letters_seen = $phrase_obj->{_letters_seen};
my $cost = $phrase_obj->{_cost};
my $cost_so_far = $phrase_obj->{_cost_so_far};
my $num_chars_so_far = $phrase_obj->{_num_chars_so_far};
my $no_match_remainder = $phrase_obj->{_no_match_remainder};
my $depth = $phrase_obj->{_depth};
my $direction = $phrase_obj->{_dir};
my $word = $phrase_obj->{_start_word};
my $whole_word = $phrase_obj->{_cand};
my $len_word = length($word);
my @cands;
my @descendants;
if($direction == 0){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($word, $dictionary, $dictionary_rev);
}
elsif($direction == 1){
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $dictionary_rev = $phrase_obj->{_dictionary_rev};
my $repeated_pal_hash_ref = $phrase_obj->{_repeated_pal_hash_ref};
my $letters_seen = $phrase_obj->{_letters_seen};
my $cost = $phrase_obj->{_cost};
my $cost_so_far = $phrase_obj->{_cost_so_far};
my $num_chars_so_far = $phrase_obj->{_num_chars_so_far};
my $no_match_remainder = $phrase_obj->{_no_match_remainder};
my $depth = $phrase_obj->{_depth};
my $direction = $phrase_obj->{_dir};
my $word = $phrase_obj->{_start_word};
my $whole_word = $phrase_obj->{_cand};
my $len_word = length($word);
my @cands;
my @descendants;
if($direction == 0){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($word, $dictionary, $dictionary_rev);
}
elsif($direction == 1){
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
#-----------------------------------------------------------------------------
# traverse from candidate phrase-object back up to start word, building up the
# phrase string. iterative version.
#-----------------------------------------------------------------------------
sub roll_up_phrase
{
my ($pobj, $phrase, $depth) = @_; # depth == depth of recursion
if(!$depth){
$depth = 0;
}
while($pobj){
if(!$pobj->{_cand} && $depth == 0){
# top-level call to roll_up_phrase is called on a root node.
return $pobj->{_start_word};
}
else{
# if depth is 0, that means this is a top-level call.
# otherwise this is the nth iteration within this while loop.
# if this is a top-level call and _phrase is already defined,
# just return _phrase.
if(defined($pobj->{_phrase}) && !$depth){
return $pobj->{_phrase};
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
if($antecedent){
$antecedent_predecessor = $antecedent->{_predecessor};
$ant_direction = $antecedent->{_dir};
$ant_cand = $antecedent->{_cand};
}
my $word = defined($pobj->{_word}) ? $pobj->{_word} : "";
my $startword = defined($pobj->{_start_word}) ? $pobj->{_start_word} : "";
my $cand = defined($pobj->{_cand}) ? $pobj->{_cand} : "";
if(!$phrase){
if($direction == 0){
$phrase = $cand;
}
elsif($direction == 1){
$phrase = $cand;
}
}
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
sub roll_up_phrase_plus_word
{
my ($self) = @_;
my $phrase = $self->{_phrase};
my $word = $self->{_start_word};
my $phrase_plus_cand = $phrase . ": " . $word;
return $phrase_plus_cand;
}
sub DESTROY
{
my ($self) = @_;
my $antecedent;
my $ant_phrase;
my ($pkg, $filename, $line_num) = caller();
if($self->{_predecessor}){
$antecedent = $self->{_predecessor};
$ant_phrase = $antecedent->{_phrase} ? $antecedent->{_phrase} : $antecedent->{_start_word};
}
else{
$antecedent->{_phrase} = "none";
}
# print " $line_num, destroying phrase object $self, '" . $self->{_start_word} . ", " . $self->{_phrase} .
# "', parent is $antecedent: '" . $ant_phrase . "' \n";
# if($line_num != 0){ # if not final sweep at program exit
# print " caller is: $pkg, $filename, $line_num\n";
# }
if($line_num == 0){ # line_num is zero
$d++;
# print "\$d : $d\n";
}
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
_eval_func => $self->{_eval_func},
_goal_p_func => $self->{_goal_p_func},
_get_data_func => $self->{_get_data_func},
_num_successors_func => $self->{_num_successors_func},
_successors_iterator => $self->{_successors_iterator},
_antecedent => $self,
_depth => $depth + 1,
);
my $start_word = $next_descendant->{_state}->{_start_word};
my $phrase = $next_descendant->{_state}->{_phrase};
my $already_produced_p = $self->{_descendants_produced}->[$i] || ($self->{_descendant_fcosts}->[$i] != -1);
if($already_produced_p){
# have already produced this descendant
$descendants_found++;
# found descendant in tree\n";
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
$avltree->insert($word_objs[$i]);
$avltree_rev->insert($rev_word_objs[$i]);
}
show_progress(1);
print STDERR "\n";
#
# Build the words-with-candidates list. This will be used for phrases that are
# palindromes with a space in the middle position. The descendants of these
# types of palindromes are found by sort-of starting all over again... any word becomes
# a candidate for the extension of the palindrome- any word that has candidates,
# that is. By building a list of only the words that have candidates,
# the search time is greatly reduced.
#
my $i = 0;
diag("building words_w_cands_list.");
foreach my $w (@words){
show_progress($i/$num_words);
my @candidates = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($w, $avltree, $avltree_rev);
if(@candidates){
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
foreach my $word (@words_w_cands){
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity($word);
my $len_word = length($word);
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word($word);
my $cost = $sparsity + $len_word;
my $phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => \@words,
_words_w_cands_list => \@words_w_cands,
_dictionary => $avltree,
_dictionary_rev => $avltree_rev,
_start_word => $word,
_word => $word,
_cost => $cost,
_letters_seen => [],
_cost_so_far => 0,
_num_chars_so_far => 0,
_num_new_chars => $num_chars,
);
diag("inserting word $word");
$smastar->add_start_state($phrase);
}
# diag("starting SMA* search...");
my $palindorme_phr_obj;
$palindrome_phr_obj = $smastar->start_search(
\&log_function,
\&str_function,
$max_states_in_queue,
$MAX_COST,
);
my $palindrome;
if($palindrome_phr_obj){
$palindrome = $palindrome_phr_obj->{_state}->roll_up_phrase();
}
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
my $cost = "";
my $cost_so_far = "";
my $num_new_chars = "";
my $num_chars_so_far = "";
my $letters_seen = [];
my $letters_seen_str = join("", @$letters_seen);
my $phrase = "";
my $evaluation = -1;
my $depth = 0;
$str = $path_obj->{_state}->{_start_word};
# $cand is the parent's word (the candidate that generated this phrase)
$cand = defined($path_obj->{_state}->{_cand}) ? $path_obj->{_state}->{_cand} : "";
$cost = $path_obj->{_state}->{_cost};
$cost_so_far = $path_obj->{_state}->{_cost_so_far};
$num_new_chars = $path_obj->{_state}->{_num_new_chars};
$num_chars_so_far = $path_obj->{_state}->{_num_chars_so_far};
$letters_seen = $path_obj->{_state}->{_letters_seen};
$letters_seen_str = join("", @$letters_seen);
$phrase = defined($path_obj->{_state}->{_phrase}) ? $path_obj->{_state}->{_phrase} : "";
$evaluation = AI::Pathfinding::SMAstar::Path::fcost($path_obj);
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
}
#----------------------------------------------------------------------------
sub str_function
{
my ($path_obj) = @_;
my $sw = defined($path_obj->{_state}->{_start_word}) ? $path_obj->{_state}->{_start_word} : "";
my $phrase = defined($path_obj->{_state}->{_phrase}) ? $path_obj->{_state}->{_phrase} : "";
my $str = "$sw, $phrase";
return $str;
}
( run in 0.492 second using v1.01-cache-2.11-cpan-0d8aa00de5b )