view release on metacpan or  search on metacpan

lib/AI/Pathfinding/SMAstar.pm  view on Meta::CPAN

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


=head2 new()

  my $smastar = AI::Pathfinding::SMAstar->new();