AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
##################################################################
#
# 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,
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)
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.
state_goal_p_func()
Sets/gets the function that returns 1 if the node is a goal node, or
0 otherwise.
state_num_successors_func()
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
##################################################
# SMAstar constructor
##################################################
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_priority_queue => AI::Pathfinding::SMAstar::PriorityQueue->new(),
_state_eval_func => undef,
_state_goal_p_func => undef,
_state_num_successors_func => undef,
_state_successors_iterator => undef,
_show_prog_func => undef,
_state_get_data_func => undef,
@_, # attribute override
};
return bless $self, $class;
}
sub state_eval_func {
my $self = shift;
if (@_) { $self->{_state_eval_func} = shift }
return $self->{_state_eval_func};
}
sub state_goal_p_func {
my $self = shift;
if (@_) { $self->{_state_goal_p_func} = shift }
return $self->{_state_goal_p_func};
}
sub state_num_successors_func {
my $self = shift;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
#
# 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};
# 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)){
croak "SMAstar: successor iterator is not defined\n";
}
# create a path object from this state
my $state_obj = AI::Pathfinding::SMAstar::Path->new(
_state => $state,
_eval_func => $state_eval_func,
_goal_p_func => $state_goal_p_func,
_num_successors_func => $state_num_successors_func,
_successors_iterator => $state_successors_iterator,
_get_data_func => $state_get_data_func,
);
my $fcost = AI::Pathfinding::SMAstar::Path::fcost($state_obj);
# check if the fcost of this node looks OK (is numeric)
unless(Scalar::Util::looks_like_number($fcost)){
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# Memory-bounded A* search
#
#
#################################################################
sub sma_star_tree_search
{
my ($priority_queue,
$goal_p,
$successors_func,
$eval_func,
$backup_func,
$log_function, # debug string func; represent state object as a string.
$str_function,
$prog_function,
$show_prog_func,
$max_states_in_queue,
$max_cost,
) = @_;
my $iteration = 0;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
else{
my $successors_iterator = $best->$successors_func();
my $succ = $successors_iterator->();
if($succ){
# if succ is at max depth and is not a goal node, set succ->fcost to infinity
if($succ->depth() >= $max_depth && !$succ->$goal_p() ){
$succ->{_f_cost} = $max_cost;
}
else{
# calling eval for comparison, and maintaining pathmax property
$succ->{_f_cost} = max($eval_func->($succ), $eval_func->($best));
my $descendant_index = $succ->{_descendant_index};
$best->{_descendant_fcosts}->[$descendant_index] = $succ->{_f_cost};
}
}
# determine if $best is completed, and if so backup values
if($best->is_completed()){
# remove from queue first, back up fvals, then insert back on queue.
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,
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
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.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
);
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
maximum number of expanded states to store in the queue, and a maximum cost
value (beyond which the search will cease).
=head2 state_eval_func()
$smastar->state_eval_func(\&FrontierObj::evaluate);
Set or get the handle to the function that returns the cost of the object
argument (node) in the search space.
=head2 state_goal_p_func()
$smastar->state_goal_p_func(\&FrontierObj::goal_test);
Set/get the handle to the goal predicate function. This is a function
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
sub compare
{
my ($min_letters) = @_;
return sub{
my ($self, $arg_obj) = @_;
my $self_eval_func = evaluate($min_letters);
my $argobj_eval_func = evaluate($min_letters);
my $self_eval = $self->$self_eval_func;
my $arg_obj_eval = $arg_obj->$argobj_eval_func;
return $self_eval - $arg_obj_eval;
}
}
sub compare_by_depth
{
my ($self, $arg_obj) = @_;
my $self_depth = $self->{_depth};
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
elsif($arg_phrase_plus_word eq $phrase_plus_word){
return 0;
}
return 1;
}
#----------------------------------------------------------------------------
# evaluation function f(n) = g(n) + h(n) where
#
# g(n) = cost of path through this node
# h(n) = distance from this node to goal (optimistic)
#
# used for A* search.
#
sub evaluate
{
my ($min_num_letters) = @_;
return sub{
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)){
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
#my $total_cost = $cost_so_far + $cost;
my $total_cost = $cost_so_far + $cost + $ratio;
#my $total_cost = 0; # greedy search (best-first search)
#my $distance_from_goal = 0; # branch and bound search. optimistic/admissible.
my $distance_from_goal = $min_num_letters - ($num_chars_so_far + $num_new_chars); #1 optimistic/admissible
my $evaluation = $total_cost + $distance_from_goal;
$self->{_f_cost} = $evaluation;
return $evaluation;
}
}
#-----------------------------------------------------------------------------
sub phrase_is_palindrome_min_num_chars
{
my ($min_num_chars) = @_;
return sub{
my ($self) = @_;
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
##################################################
# Path constructor
##################################################
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_state => undef, # node in the search space
_eval_func => undef,
_goal_p_func => undef,
_num_successors_func => undef,
_successors_iterator => undef,
_get_data_func => undef,
###########################################
#
# path stuff
#
###########################################
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
return;
}
#----------------------------------------------------------------------------
# evaluation function f(n) = g(n) + h(n) where
#
# g(n) = cost of path through this node
# h(n) = distance from this node to goal (optimistic)
#
# used for A* search.
#
sub fcost
{
my ($self) = @_;
my $fcost = $self->{_f_cost};
if(defined($fcost)){
return $fcost;
}
my $eval_func = $self->{_eval_func};
my $result = $eval_func->($self->{_state});
$self->{_f_cost} = $result;
return $result;
}
sub is_goal
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
my $descendants_deleted = 0;
my $descendants_found = 0;
# loop over nodes returned by iterator
while(my $next_state = $iterator->()){
$next_descendant = AI::Pathfinding::SMAstar::Path->new(
_state => $next_state,
_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};
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
fget_key => \&AI::Pathfinding::SMAstar::Examples::WordObj::word,
fget_data => \&AI::Pathfinding::SMAstar::Examples::WordObj::word,
);
print STDERR "-" x 80 . "\n";
print STDERR "-" x 80 . "\n";
diag("reading dictionary '$dictionary_file'");
eval{
($num_words, @words) = AI::Pathfinding::SMAstar::Examples::PalUtils::read_dictionary_filter_by_density($dictionary_file, $sparsity);
};
is( $@, '', '$@ is not set after object insert' );
diag("loaded words: '$num_words'");
isnt( $num_words, undef, 'num_words is $num_words');
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
$avltree_rev_height = $avltree_rev->get_height();
diag("AVL trees loaded. Heights are $avltree_height, $avltree_rev_height\n\n");
my @phrase_obj_list;
my $smastar;
ok(
$smastar = AI::Pathfinding::SMAstar->new(
_state_eval_func => AI::Pathfinding::SMAstar::Examples::Phrase::evaluate($min_letters),
_state_goal_p_func => AI::Pathfinding::SMAstar::Examples::Phrase::phrase_is_palindrome_min_num_chars($min_letters),
_state_num_successors_func => \&AI::Pathfinding::SMAstar::Examples::Phrase::get_num_successors,
_state_successors_iterator => \&AI::Pathfinding::SMAstar::Examples::Phrase::get_descendants_iterator,
_state_get_data_func => \&AI::Pathfinding::SMAstar::Examples::Phrase::roll_up_phrase,
_show_prog_func => sub{ },
#_show_prog_func => \&AI::Pathfinding::SMAstar::Examples::PalUtils::show_progress_so_far,
),
'created smastar');
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
my $str = "";
# $cand is the parent's word (the candidate that generated this phrase)
my $cand = "";
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);
$depth = $path_obj->{_depth};
$num_chars_so_far = sprintf("%02d", $num_chars_so_far);
$num_new_chars = sprintf("%02d", $num_new_chars);
$cost = sprintf("%02d", $cost);
$cost_so_far = sprintf("%02d", $cost_so_far);
$depth = sprintf("%02d", $depth);
my $specifier = "%" . $max_word_length . "s";
$str = sprintf($specifier, $str);
$evaluation = sprintf("%04f", $evaluation);
$letters_seen_str = sprintf("%26s", $letters_seen_str);
my $log_str = "";
$log_str = $log_str . "depth: $depth, ";
$log_str = $log_str . "eval: $evaluation, ";
$log_str = $log_str . "letters: '$letters_seen_str', ";
$log_str = $log_str . "'$str', ";
$log_str = $log_str . "'$phrase', ";
$log_str = $log_str . "cand: $cand";
return $log_str;
}
( run in 1.799 second using v1.01-cache-2.11-cpan-98e64b0badf )