AI-Pathfinding-SMAstar version 0.07
===================================

NAME

AI::Pathfinding::SMAstar - Memory-bounded A* Search

SYNOPSIS

use AI::Pathfinding::SMAstar;

EXAMPLE

##################################################################
#
# This example uses a hypothetical object called FrontierObj, and
# shows the functions that FrontierObj must feature in order to
# perform a path search in a solution-space populated by
# FrontierObj objects.
#
##################################################################

my $smastar = AI::Pathfinding::SMAstar->new(
       # evaluates f(n) = g(n) + h(n), returns a number
       _state_eval_func           => \&FrontierObj::evaluate,

       # when called on a node, returns 1 if it is a goal
       _state_goal_p_func         => \&FrontierObj::goal_test,

       # must return the number of successors of a node
       _state_num_successors_func => \&FrontierObj::get_num_successors,

       # must return *one* successor at a time
       _state_successors_iterator => \&FrontierObj::get_successors_iterator,

       # can be any suitable string representation
       _state_get_data_func       => \&FrontierObj::string_representation,

       # gets called once per iteration, useful for showing algorithm progress
       _show_prog_func            => \&FrontierObj::progress_callback,
   );

# you can start the search from multiple start-states
# 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
a node is, in your search space (or point, or state).

A common example used for informed search methods, and one that is
used in Russell's original paper, is a N-puzzle, such as an 8-puzzle or
15-puzzle. If trying to solve such a puzzle, a node in the search space
could be defined as a particular configuration of that puzzle.    In the
/t directory of this module's distribution, SMA* is applied to the problem
of finding the shortest palindrome that contains a minimum number of letters
specified, over a given lexicon of words.

Once you have a definition and representation of a node in your search space, SMA*
search requires the following functions to work:

 ** State evaluation function (_state_eval_func above)

     This function must return the cost of this node in the search space. In all
forms of A* search, this means the cost paid to arrive at this node along a path,
plus the estimated cost of going from this node to a goal state. This function
must be positive and monotonic, meaning that successor nodes mustn't be less
expensive than their antecedent nodes. Monotonicity is ensured in this implementation
of SMA*, so even if your function is not monotonic, SMA* will assign the antecedent
node's cost to a successor if that successor costs less than the antecedent.

 * State goal predicate function (_state_goal_p_func above)

     This function must return 1 if the node is a goal node, or 0 otherwise.


 * State number of successors function (_state_num_successors_func above)

     This function must return the number of successors of this node, i.e. all
     nodes that are reachable from this node via a single operation.


 * State successors iterator (_state_iterator above)

     This function must return a *handle to a function* that returns next
     successor of this node, i.e. it must return an iterator that produces
     the successors of this node *one* at a time. This is
     necessary to maintain the memory-bounded constraint of SMA* search.


 * State get-data function (_state_get_data_func above)

     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)

     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
introduced by Stuart Russell in 1992. SMA* is a more efficient variation of the
original MA* search introduced by Chakrabarti et al. in 1989. See references below.

Motivation and Comparison to A* Search

A* search

A* Search is an optimal and complete algorithm for computing a sequence of
operations leading from a system's start-state (node) to a specified goal. In
this context, optimal means that A* search will return the shortest possible
sequence of operations (path) leading to the goal, and 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 admissible heuristic estimating the distance
from that node to the goal. The cost is calculated as:

f(n) = g(n) + h(n)

Where:



  * n is a state (node) along a path


  * g(n) is the total cost of the path leading up to n


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



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
0 otherwise.

state_num_successors_func()

Sets/gets the function that returns the number of successors of
this node.

state_successors_iterator()

Sets/gets the function that returns the next successor of
this node.

state_get_data_func()

Sets/gets the function that returns a string representation
of this node.

show_prog_func()

sets/gets the callback function for displaying the progress of the
search. It can be an empty callback if you do not need this output.

EXPORT

None by default.

SEE ALSO

Russell, Stuart. (1992) "Efficient Memory-bounded Search Methods" Proceedings
of the 10th European conference on Artificial intelligence, pp. 1-5

Chakrabarti, P. P., Ghose, S., Acharya, A., and de Sarkar, S. C. (1989) "Heuristic
search in restricted memory" Artificial Intelligence Journal, 41, pp. 197-221.

AUTHOR

Matthias Beebe, <[email protected]>


INSTALLATION

To install this module type the following:

  perl Makefile.PL
  make
  make test
  make install

DEPENDENCIES

This module requires these other modules and libraries:

 Tree::AVL
 Test::More

COPYRIGHT AND LICENCE

Copyright (C) 2010 by Matthias Beebe

This library is free software; you can redistribute it and/or modify it
under the same terms as Perl itself, either Perl version 5.10.0 or, at
your option, any later version of Perl 5 you may have available.

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.