AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
$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;
$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.
# This is because when we remove it from the queue and re-insert it, it
# loses its seniority in the queue (it becomes the newest node at its cost
# 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;
my $descendant_index = $shcl_obj->{_descendant_index};
# record the index of this descendant in the forgotten_nodes list
$antecedent->{_forgotten_nodes_offsets}->{$descendant_index} = 1;
# flag the antecedent as not having this descendant in the queue
$antecedent->{_descendants_produced}->[$descendant_index] = 0;
$antecedent->{_descendant_fcosts}->[$descendant_index] = -1;
# 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++;
}
print "\n\nreturning unsuccessfully. iteration: $iteration\n";
return;
}
}
sub max
{
my ($n1, $n2) = @_;
return ($n1 > $n2 ? $n1 : $n2);
}
sub fp_compare {
my ($a, $b, $dp) = @_;
my $a_seq = sprintf("%.${dp}g", $a);
my $b_seq = sprintf("%.${dp}g", $b);
if($a_seq eq $b_seq){
return 0;
}
elsif($a_seq lt $b_seq){
return -1;
}
else{
return 1;
}
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=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
=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)>
Where:
=over
=item *
I<n> is a state (node) along a path
=item *
I<g(n)> is the total cost of the path leading up to I<n>
=item *
I<h(n)> is the heuristic function, or estimated cost of the path from I<n>
to the goal node.
=back
For a given admissible heuristic function, it can be shown that A* search
is I<optimally efficient>, meaning that, in its calculation of the shortest
path, it expands fewer nodes in the search space than any other algorithm.
To be admissible, the heuristic I<h(n)> can never over-estimate the distance
from the node to the goal. Note that if the heuristic I<h(n)> is set to
zero, A* search reduces to I<Branch and Bound> search. If the cost-so-far
I<g(n)> is set to zero, A* reduces to I<Greedy Best-first> search (which is
neither complete nor optimal). If both I<g(n)> and I<h(n)> are set to zero,
the search becomes I<Breadth-first>, which is complete and optimal, but not
optimally efficient.
The space complexity of A* search is bounded by an exponential of the
branching factor of the search-space, by the length of the longest path
examined during the search. This is can be a problem particularly if the
branching factor is large, because the algorithm may run out of memory.
=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.
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 on average.
However, for certain classes of problems, guaranteeing optimality can be costly.
This is particularly true in solution spaces where:
=over
=item *
the branching factor of the search space is large
=item *
there are many equivalent optimal solutions (or shortest paths)
=back
For solution spaces with these characteristics, stochastic methods or
approximation algorithms such as I<Simulated Annealing> can provide a
massive reduction in time and space requirements, while introducing a
tunable probability of producing a sub-optimal solution.
=head1 METHODS
( run in 0.372 second using v1.01-cache-2.11-cpan-cdf2f3d4e48 )