AI-Pathfinding-SMAstar

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

    

  * 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)

      An integer indicating the maximum number of expanded nodes to 
      hold in memory at any given time.
    

  * maximum cost (MAX_COST above)

      An integer indicating the maximum cost, beyond which nodes will not be 
      expanded.



DESCRIPTION

Overview

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 

README  view on Meta::CPAN

    

   * h(n) is the heuristic function, or estimated cost of the path from n 
      to the goal node.

The to be admissible, the heuristic must never over-estimate the distance 
from the node to the goal. If the heuristic is set to zero, A* search reduces 
to Branch and Bound search.

For a given heuristic function, it can be shown that A* search is optimally 
efficient, meaning that, in its calculation of the shortest path, it expands 
fewer nodes in the search space than any other algorithm.

The space complexity of A* search is bounded by an exponential of the 
branching factor of the search-space and the length of the longest path 
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 
on average. However, for certain classes of problems, guaranteeing optimality 
can be costly. This is particularly true in solution spaces where:

    * the branching factor of the search space is large
    * there are multiple equivalent optimal solutions (or shortest paths)

For solution spaces with these characteristics, stochastic methods or 
approximation algorithms such as Simulated Annealing can provide a massive 
reduction in time and space requirements, while introducing a tunable 
probability of producing a sub-optimal solution.

README  view on Meta::CPAN

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()

Sets/gets the function that returns 1 if the node is a goal node, or 

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

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.


=item *

B<max states allowed in memory> (C<max_states_in_queue> above)

An integer indicating the maximum number of expanded nodes to hold in
memory at any given time.


=item *

B<maximum cost> (C<MAX_COST> above)

An integer indicating the maximum cost, beyond which nodes will not
be expanded.





=back



=head1 DESCRIPTION

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

=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

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.

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

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

    \&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);

Set or get the handle to the function that returns the cost of the object 
argument (node) in the search space.