AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
examined during the search. This is can be a problem particularly if the
branching factor is large, as the algorithm may run out of memory.
SMA* Search
SMA* search addresses the possibility of running out of memory during search by
pruning the portion of the search-space that is being examined. It relies on the
pathmax, or monotonicity constraint on f(n) to remove the shallowest of the
highest-cost nodes from the search queue when there is no memory left to
expand new nodes. It records the best costs of the pruned nodes within their
antecedent nodes to ensure that crucial information about the search space is not
lost. To facilitate this mechanism, the search queue is best maintained as a
search-tree of search-trees ordered by cost and depth, respectively.
The pruning of the search queue allows SMA* search to utilize all available
memory for search without any danger of overflow. It can, however, make SMA*
search significantly slower than a theoretical unbounded-memory search, due to
the extra bookkeeping it must do, and because nodes may need to be re-expanded
(the overall number of node expansions may increase).
It can be shown that of the memory-bounded variations of A* search, such MA*,
IDA*, Iterative Expansion, etc., SMA* search expands the least number of nodes
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
$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;
$max_states_in_queue = $num_states_in_queue + $max_extra_states_in_queue;
my $max_depth = ($max_states_in_queue - $num_states_in_queue);
my $best; # the best candidate for expansion
if($$priority_queue->is_empty() || !$$priority_queue){
return;
}
else{
my $num_successors = 0;
# 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;
}
elsif($best->{_f_cost} >= $max_cost){
croak "\n\nSearch unsuccessful. max_cost reached (cost: $max_cost).\n";
}
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.
# this way, it gets placed in its rightful place on the queue.
my $fval_before_backup = $best->{_f_cost};
# STEPS:
# 1) remove best and all antecedents from queue, but only if they are
# going to be altered by backing-up fvals. This is because
# removing and re-inserting in queue changes temporal ordering,
# and we don't want to do that unless the node will be
# placed in a new cost-bucket/tree.
# 2) then backup fvals
# 3) then re-insert best and all antecedents back on queue.
# Check if need for backup fvals
$best->check_need_fval_change();
my $cmp_func = sub {
my ($str) = @_;
return sub{
my ($obj) = @_;
my $obj_path_str = $str_function->($obj);
if($obj_path_str eq $str){
return 1;
}
else{
return 0;
}
}
};
my $antecedent = $best->{_antecedent};
my %was_on_queue;
my $i = 0;
# Now remove the offending nodes from queue, if any
if($best->need_fval_change()){
# remove best from the queue
$best = $$priority_queue->deepest_lowest_cost_leaf();
while($antecedent){
my $path_str = $str_function->($antecedent);
if($antecedent->is_on_queue() && $antecedent->need_fval_change()){
$was_on_queue{$i} = 1;
$$priority_queue->remove($antecedent, $cmp_func->($path_str));
}
$antecedent = $antecedent->{_antecedent};
$i++;
}
}
# Backup fvals
if($best->need_fval_change()){
$best->$backup_func();
}
# Put everything back on the queue
if($best->need_fval_change()){
$$priority_queue->insert($best);
my $antecedent = $best->{_antecedent};
my $i = 0;
while($antecedent){
if($was_on_queue{$i} && $antecedent->need_fval_change()){
# the antecedent needed fval change too.
$$priority_queue->insert($antecedent);
}
if($antecedent->need_fval_change()){
# set need_fval_change back to 0, so it will not be automatically seen as
# needing changed in the future. This is important, since we do not want
# to remove an element from the queue *unless* we need to change the fcost.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# and depth) and will not be removed at the right time when searching for
# deepest_lowest_cost_leafs or shallowest_highest_cost_leafs.
$antecedent->{_need_fcost_change} = 0;
}
$antecedent = $antecedent->{_antecedent};
$i++;
}
# Again, set need_fval_change back to 0, so it will not be automatically
# seen as needing changed in the future.
$best->{_need_fcost_change} = 0;
}
}
#
# If best's descendants are all in memory, mark best as completed.
#
if($best->all_in_memory()) {
if(!($best->is_completed())){
$best->is_completed(1);
}
my $cmp_func = sub {
my ($str) = @_;
return sub{
my ($obj) = @_;
my $obj_str = $str_function->($obj);
if($obj_str eq $str){
return 1;
}
else{
return 0;
}
}
};
my $best_str = $str_function->($best);
# If best is not a root node
if($best->{_depth} != 0){
# descendant index is the unique index indicating which descendant
# this node is of its antecedent.
my $descendant_index = $best->{_descendant_index};
my $antecedent = $best->{_antecedent};
$$priority_queue->remove($best, $cmp_func->($best_str));
if($antecedent){
$antecedent->{_descendants_produced}->[$descendant_index] = 0;
}
}
}
# there are no more successors of $best
if(!$succ){
next;
}
my $antecedent;
my @antecedents_that_need_to_be_inserted;
# If the maximum number of states in the queue has been reached,
# we need to remove the shallowest-highest-cost leaf to make room
# for more nodes. That means we have to make sure that the antecedent
# produces this descendant again at some point in the future if needed.
if($num_states_in_queue > $max_states_in_queue){
my $shcl_obj = $$priority_queue->shallowest_highest_cost_leaf($best, $succ, $str_function);
if(!$shcl_obj){
croak "Error while pruning queue: shallowest-highest-cost-leaf was null\n";
}
$antecedent = $shcl_obj->{_antecedent};
if($antecedent){
my $antecedent_successors = \$antecedent->{_descendants_list};
$antecedent->remember_forgotten_nodes_fcost($shcl_obj);
$antecedent->{_forgotten_nodes_num} = $antecedent->{_forgotten_nodes_num} + 1;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# flag the ancestor node as having deleted a descendant
$antecedent->descendants_deleted(1);
# update the number of descendants this node has in memory
$antecedent->{_num_successors_in_mem} = $antecedent->{_num_successors_in_mem} - 1;
# update the total number of nodes in the queue.
$num_states_in_queue--;
}
} # end if (num_states_on_queue > max_states)
# if there is a successor to $best, insert it in the priority queue.
if($succ){
$$priority_queue->insert($succ);
$best->{_num_successors_in_mem} = $best->{_num_successors_in_mem} + 1;
}
else{
croak "Error: no successor to insert\n";
}
}
}
continue {
$iteration++;
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=head3 SMA* Search
Like A* search, SMA* search is an optimal and complete algorithm for finding
a least-cost path. Unlike A*, SMA* will not run out of memory, I<unless the size
of the shortest path exceeds the amount of space in available memory>.
SMA* addresses the possibility of running out of memory
by pruning the portion of the search-space that is being examined. It relies on
the I<pathmax>, or I<monotonicity> constraint on I<f(n)> to remove the shallowest
of the highest-cost nodes from the search queue when there is no memory left to
expand new nodes. It records the best costs of the pruned nodes within their
antecedent nodes to ensure that crucial information about the search space is
not lost. To facilitate this mechanism, the search queue is best maintained
as a search-tree of search-trees ordered by cost and depth, respectively.
=head4 Nothing is for free
The pruning of the search queue allows SMA* search to utilize all available
memory for search without any danger of overflow. It can, however, make
SMA* search significantly slower than a theoretical unbounded-memory search,
due to the extra bookkeeping it must do, and because nodes may need to be
re-expanded (the overall number of node expansions may increase).
In this way there is a trade-off between time and space.
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $phrase_num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word($phrase);
my $ratio = 0;
if($phrase_num_chars){
$ratio = $len_phrase/$phrase_num_chars;
}
#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;
}
}
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
my $cost_key = $obj->$avl_get_key_func();
my $data = $obj->$avl_get_data_func();
return $obj;
}
}
# Return the shallowest, highest-cost leaf
sub shallowest_highest_cost_leaf
{
my ($self, $best, $succ, $str_function) = @_;
my $cost_hash_ref = $self->{_hash_of_trees_ref};
my @cost_keys = (keys %$cost_hash_ref);
my $cost_min_max_tree = $self->{_cost_min_max_tree};
my $obj;
if(!@cost_keys){
return;
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
my $queue = $$avltree->get_queue($least_depth); # get the queue at least_depth
my $queue_keys_iterator = $queue->get_keys_iterator();
my $queue_key = $queue_keys_iterator->(); # burn the first value from the iterator since we're getting first object on next line.
$obj = $$avltree->oldest_at($least_depth); # get the shallowest one that is not at zero depth
my $i = 1;
while($compare_func->($obj, $best) || $compare_func->($obj, $succ) || $obj->has_descendants_in_memory()){
if($queue_key = $queue_keys_iterator->()){
$obj = $queue->lookup_by_key($queue_key);
}
else{
# need a new least_depth. check if there are any more queues with non-zero depth in this tree.
# if not, need a new highest_cost_key.
$obj = undef;
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
$queue = $$avltree->get_queue($least_depth); # get the queue at least_depth
$queue_keys_iterator = $queue->get_keys_iterator();
$queue_key = $queue_keys_iterator->(); # burn the first value from the iterator
$obj = $$avltree->oldest_at($least_depth); # get the shallowest one that is not at zero depth
$i = 1;
next;
}
}
$i++;
} # end while($compare_func->($obj, $best) || $compare_func->($obj, $succ) || $obj->has_descendants_in_memory())
# done loop on last highest_cost_key. if obj is not found, get another highest_cost_key, and loop back again.
if(!$obj){
$least_depth = 0;
$highest_cost_key = next_largest_element(\@cost_keys, $highest_cost_key);
}
else{
last;
}
( run in 0.273 second using v1.01-cache-2.11-cpan-4e96b696675 )