AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
# 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
This function returns a string representation of this node.
* State show-progress function (_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.
* 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)
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.
state_goal_p_func()
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
}
###################################################################
#
# 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,
$self->{_show_prog_func},
$max_states_in_queue,
$max_cost,
);
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
#
#################################################################
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;
my $num_states_in_queue = $$priority_queue->size();
my $max_extra_states_in_queue = $max_states_in_queue;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# loop over the elements in the priority queue
while(!$$priority_queue->is_empty()){
# determine the current size of the queue
my $num_states_in_queue = $$priority_queue->{_size};
# get the best candidate for expansion from the queue
$best = $$priority_queue->deepest_lowest_cost_leaf_dont_remove();
#------------------------------------------------------
if(!$DEBUG){
my $str = $log_function->($best);
$show_prog_func->($iteration, $num_states_in_queue, $str);
}
else{
my $str = $log_function->($best);
print "best is: " . $str_function->($best) . ", cost: " . $best->{_f_cost} . "\n";
}
#------------------------------------------------------
if($best->$goal_p()) {
# goal achieved! iteration: $iteration, number of
# states in queue: $num_states_in_queue.
return $best;
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
#
# 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
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=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.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=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
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);
lib/AI/Pathfinding/SMAstar/AVLQueue.pm view on Meta::CPAN
#
# Queue.pm
#
# Implementation of a queue based on a binary tree
# A tree structure is used rather than a heap to allow
# infrequent, but necessary, arbitrary access to elements
# in the middle of the queue in log(n) time
#
# This is primarily necessary to facilitat the SMAstar
# path-finding algorithm.
#
#
# Author: matthias beebe
# Date : June 2008
#
#
package AI::Pathfinding::SMAstar::AVLQueue;
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
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();
}
diag("ran SMA search: palindrome is '$palindrome'");
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
###########################################################################
#
# Auxiliary functions
#
###########################################################################
#----------------------------------------------------------------------------
sub log_function
{
my ($path_obj) = @_;
if(!$path_obj){
my ($pkg, $filename, $line) = caller();
print "$pkg, $filename, $line\n";
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
$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;
}
#----------------------------------------------------------------------------
sub str_function
{
my ($path_obj) = @_;
( run in 1.990 second using v1.01-cache-2.11-cpan-49f99fa48dc )