Matthias Beebe > AI-Pathfinding-SMAstar-0.07 > AI::Pathfinding::SMAstar

Download:
AI-Pathfinding-SMAstar-0.07.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.07   Source  

NAME ^

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

SYNOPSIS ^

 use AI::Pathfinding::SMAstar;

EXAMPLE

 ##################################################################
 #
 # This example uses a hypothetical object called FrontierObj, and
 # shows the functions that the FrontierObj class 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, $frontierGoalPath will contain the
 # goal path.   The optimal path to the goal node will be encoded in the
 # ancestry of the goal path.   $frontierGoalPath->antecedent() contains
 # the goal path's parent path, and so forth back to the start path, which
 # contains only the start state.
 #
 # $frontierGoalPath->state() contains the goal FrontierObj itself.
 #
 my $frontierGoalPath = $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
    );

In the example above, a hypothetical object, FrontierObj, is used to represent a state, or 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 optimal puzzle solving, such as solving an 8 or 15-tile puzzle in the least number of moves. If trying to solve such a puzzle, a node in the search space could be defined as a configuration of that puzzle (a paricular ordering of the tiles).

There is an example provided in the /t directory of this module's distribution, where SMA* is applied to the problem of finding the shortest palindrome that contains a minimum number of letters specified, over a given list of words.

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

DESCRIPTION ^

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

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 (or cheapest) 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:

For a given admissible 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.

To be admissible, the heuristic h(n) can never over-estimate the distance from the node to the goal. Note that if the heuristic h(n) is set to zero, A* search reduces to Branch and Bound search. If the cost-so-far g(n) is set to zero, A* reduces to Greedy Best-first search (which is neither complete nor optimal). If both g(n) and h(n) are set to zero, the search becomes 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.

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

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:

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

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

Creates a new SMA* search object.

start_search()

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

Initiates a memory-bounded search. When calling this function, pass a handle to a function for recording current status( 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).

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.

state_goal_p_func()

 $smastar->state_goal_p_func(\&FrontierObj::goal_test);

Set/get the handle to the goal predicate function. This is a function that returns 1 if the argument object is a goal node, or 0 otherwise.

state_num_successors_func()

 $smastar->state_num_successors_func(\&FrontierObj::get_num_successors);

Set/get the handle to the function that returns the number of successors of this the object argument (node).

state_successors_iterator()

 $smastar->state_successors_iterator(\&FrontierObj::get_successors_iterator);

Set/get the handle to the function that returns iterator that produces the next successor of this node.

state_get_data_func()

 $smastar->state_get_data_func(\&FrontierObj::string_representation);

Set/get the handle to the function that returns a string representation of this node.

show_prog_func()

 $smatar->show_prog_func(\&FrontierObj::progress_callback);

Sets/gets the callback function for displaying the progress of the search. It can be an empty callback (sub{}) if you do not need this output.

DEPENDENCIES

 Tree::AVL
 Test::More

INCLUDED MODULES

 AI::Pathfinding::SMAstar
 AI::Pathfinding::SMAstar::Path
 AI::Pathfinding::SMAstar::PriorityQueue
 AI::Pathfinding::SMAstar::TreeOfQueues

EXPORT

None by default.

SEE ALSO ^

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

[2] 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, <matthiasbeebe@gmail.com>

COPYRIGHT AND LICENSE ^

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.

syntax highlighting: