Py-Search Package

Base

This module contains the data_structures used in py_search. In particular, it contains the the Problem class, which is used to represent the different search problems, and the AnnotatedProblem class, which wraps around a specific problem and keeps track of the number of core method calls.

At a lower level this module also contains the Node class, which is used to represent a node in the search space.

Finally, the module contains the Fringe class, and its instantiations (FIFOQueue, LIFOQueue, and PrioritySet). A Fringe is used to structure the way a search space is explored.

class py_search.base.AnnotatedProblem(problem)

Bases: py_search.base.Problem

A Problem class that wraps around another Problem and keeps stats on nodes expanded and goal tests performed.

goal_test(node)

A wrapper for the goal_test method that keeps track of the number of goal_tests performed.

node_value(node)

A wraper for the node value method that keeps track of the number of times a node value was calculated.

predecessors(node)

A wrapper for the predecessors method that keeps track of the number of nodes expanded.

random_node()

A wrapper for the random_node method.

random_successor(node)

A wrapper for the random_successor method that keeps track of the number of nodes expanded.

state_goal_test(node, goal)

A wrapper for the state_goal_test method that keeps track of the number of goal_tests performed.

successors(node)

A wrapper for the successor method that keeps track of the number of nodes expanded.

class py_search.base.FIFOQueue

Bases: py_search.base.Fringe

A first-in-first-out queue. Used to get breadth first search behavior.

>>> fifo = FIFOQueue()
>>> fifo.push(0)
>>> fifo.push(1)
>>> fifo.push(2)
>>> print(fifo.pop())
0
>>> print(fifo.pop())
1
>>> print(fifo.pop())
2
pop()
push(node)
remove(node)
class py_search.base.Fringe

Bases: object

A template for a fringe class. Used to control the strategy of different search approaches.

extend(nodes)

Given an iterator (nodes) adds all the nodes to the collection.

pop()

Pops a node off the collection.

push(node)

Adds one node to the collection.

class py_search.base.LIFOQueue

Bases: py_search.base.FIFOQueue

A last-in-first-out queue. Used to get depth first search behavior.

>>> lifo = LIFOQueue()
>>> lifo.push(0)
>>> lifo.push(1)
>>> lifo.push(2)
>>> print(lifo.pop())
2
>>> print(lifo.pop())
1
>>> print(lifo.pop())
0
pop()
class py_search.base.Node(state, parent=None, action=None, node_cost=0, extra=None)

Bases: object

A class to represent a node in the search. This node stores state information, path to the state, cost of the node, depth of the node, and any extra information.

Parameters:
  • state (object for tree search and hashable object for graph search) – the state at this node
  • parent (Node) – the node from which the current node was generated
  • action (typically a string, but can be any object) – the action performed to transition from parent to current.
  • cost (float) – the cost of reaching the current node
  • extra (object) – extra information to store in this node, typically used to store non-hashable information about the state.
cost()

Returns the cost of the current node.

depth()

Returns the depth of the current node. Uses a loop to compute depth (no tail recursion in python).

path()

Returns a path (tuple of actions) from the initial to current node.

class py_search.base.PriorityQueue(node_value=<function <lambda>>, cost_limit=inf, max_length=inf)

Bases: py_search.base.Fringe

A priority queue that sorts elements by their value. Always returns the minimum value item. A PriorityQueue accepts a node_value function, a cost_limit (nodes with a value greater than this limit will not be added) and a max_length parameter. If adding an item ever causes the size to exceed the max_length then the worst nodes are removed until the list is equal to max_length.

>>> pq = PriorityQueue(node_value=lambda x: x, max_length=3)
>>> pq.push(6)
>>> pq.push(0)
>>> pq.push(2)
>>> pq.push(6)
>>> pq.push(7)
>>> print(len(pq))
3
>>> print(pq.pop())
0
>>> print(pq.pop())
2
>>> print(pq.pop())
6
Parameters:
  • node_value (a function with one parameter for node) – The node evaluation function (defaults to lambda x: x.cost())
  • cost_limit (float) – the maximum value for elements in the set, if an item exceeds this limit then it will not be added (defaults to float('inf'))
  • max_length (int or float('inf')) – The maximum length of the list (defaults to float('inf')
clear()

Empties the list.

peek()

Returns the best node.

peek_value()

Returns the value of the best node.

pop()

Pop the best value from the priority queue.

push(node)

Push a node into the priority queue. If the node exceeds the cost limit then it is not added. If the max_length is exceeded by adding the node, then the worst node is discarded from the set.

update_cost_limit(cost_limit)

Updates the cost limit and removes any nodes that violate the new limit.

class py_search.base.Problem(initial, goal=None, initial_cost=0, extra=None)

Bases: object

The basic problem to solve. The main functions that must be defined include successors and goal_test. Some search techniques also require the random_successor and predecessors methods to be implemented.

goal_test(node)

Returns true if a goal state is found. This is typically used not used by the local search / optimization techniques. By default, this checks if the state equals the goal.

node_value(node)

Returns the the value of the current node. This is the value being minimized by the search. By default the cost is used, but this function can be overloaded to include a heuristic.

predecessors(node)

An iterator that yields all of the predecessors of the current goal.

random_node()

This method returns a random node in the search space. This is used by some of the local search / optimization techniques to randomly restart search.

random_successor(node)

This method should return a single successor node. This is used by some of the search techniques. By default, this just computes all of the successors and randomly samples one. This default approach is not very efficient, but this funciton can be overridden to generate a single successor more efficiently.

state_goal_test(node, goal)

Returns true if the given node and goal match. This is used primarily in bidirecitonal search, which compares nodes in the fringes.

successors(node)

An iterator that yields all of the successors of the current node.

Uninformed Search

This module includes the core search methods tree_search() and graph_search and the primary uninformed search techniques: depth_first_search(), breadth_first_search(), and iterative_deepening_search().

A uninformed technique that searchs simultaneously in both the forward and backward directions.

A simple implementation of depth-first search using a FIFO queue.

Parameters:
  • problem (Problem) – The problem to solve.
  • search (graph_search() or :func`tree_search`) – A search algorithm to use (defaults to graph_search).
  • depth_limit (int or float('inf')) – A limit for the depth of the search tree. If set to float(‘inf’), then depth is unlimited.

A simple implementation of depth-first search using a LIFO queue.

Parameters:
  • problem (Problem) – The problem to solve.
  • search (graph_search() or :func`tree_search`) – A search algorithm to use (defaults to graph_search).
  • depth_limit (int or float('inf')) – A limit for the depth of the search tree. If set to float(‘inf’), then depth is unlimited.

Perform graph search (i.e., no duplicate states) using the given fringe class. Returns an iterator to the solutions, so more than one solution can be found.

Note that the closed list will allow re-expansion of nodes with a lower cost.

Parameters:
  • problem (Problem) – The problem to solve.
  • fringe (fringe) – The fringe class to use.
  • depth_limit (int or float('inf')) – A limit for the depth of the search tree. If set to float(‘inf’), then depth is unlimited.

An implementation of iterative deepening search. This search is basically depth-limited depth first up to the depth limit. If no solution is found at the current depth limit then the depth limit is increased by depth_inc and the depth-limited depth first search is restarted.

Parameters:
  • problem (Problem) – The problem to solve.
  • search (graph_search() or :func`tree_search`) – A search algorithm to use (defaults to graph_search).
  • initial_depth_limit (int or float('inf')) – The initial depth limit for the search.
  • depth_inc (int) – The amount to increase the depth limit after failure.
  • max_depth_limit (int or float('inf')) – The maximum depth limit (default value of float(‘inf’))
py_search.uninformed.iterative_sampling(problem, num_samples=inf, depth_limit=inf)

A non-systematic alternative to depth-first search. This samples paths through the tree until a dead end or until the depth limit is reached. It has much lower memory requirements than depth-first or breadth-first search, but requires the user to specify num_samples and depth_limit parameters. The search will return non-optimal paths (it does not evaluate node values) and sometimes it may fail to find solutions if the number of samples or depth limit is too low.

A full description of the algorithm and the mathematics that support it can be found here:

Langley, P. (1992, May). Systematic and nonsystematic search strategies. In Artificial Intelligence Planning Systems: Proceedings of the First International Conference (pp. 145-152).

This technique is included with the other uninformed methods because it is uninformed when random_successor uniform randomly generates successors. However, this technique could be converted into an informed technique if random_successor is implemented with an approach that samples successors according to their node_value.

Parameters:
  • problem (Problem) – The problem to solve.
  • search (graph_search() or :func`tree_search`) – A search algorithm to use (defaults to graph_search).
  • num_samples (int or float('inf') (default of float('inf'))) – The number of samples through the search tree. If no solution is found after collecting this many samples, then the search fails.
  • max_depth_limit (int or float('inf') (default of float('inf'))) – The maximum depth limit (default value of float(‘inf’))

Perform tree search (i.e., search where states might be duplicated) using the given fringe class.Returns an iterators to the solutions, so more than one solution can be found.

Parameters:
  • problem (Problem) – The problem to solve.
  • fringe (fringe) – The fringe class to use.
  • depth_limit (int or float('inf')) – A limit for the depth of the search tree. If set to float(‘inf’), then depth is unlimited.

Informed Search

This module includes the informed search techniques: best_first_search() (i.e., A*), iterative_deepening_best_first_search() (i.e., IDA*), beam_search(), and widening_beam_search().

A variant of breadth-first search where all nodes in the fringe are expanded, but the resulting new fringe is limited to have length beam_width, where the nodes with the worst value are dropped. The default beam width is 1, which yields greedy best-first search (i.e., hill climbing).

There are different ways to implement beam search, namely best-first beam search and breadth-first beam search. According to:

Wilt, C. M., Thayer, J. T., & Ruml, W. (2010). A comparison of greedy search algorithms. In Third Annual Symposium on Combinatorial Search.

breadth-first beam search almost always performs better. They find that allowing the search to re-expand duplicate nodes if they have a lower cost improves search performance. Thus, our implementation is a breadth-first beam search that re-expand duplicate nodes with lower cost.

Parameters:
  • problem (Problem) – The problem to solve.
  • beam_width (int) – The size of the beam (defaults to 1).
  • graph_search (boolean) – whether to use graph or tree search.

Cost limited best-first search. By default the cost limit is set to float(‘inf’), so it is identical to traditional best-first search. This implementation uses a priority set (i.e., a sorted list without duplicates) to maintain the fringe.

If the problem.node_value is the cost to reach the node plus an admissible heuristic estimate of the distance from the node to the goal, then this is the A* algorithm.

Parameters:
  • problem (Problem) – The problem to solve.
  • search (graph_search() or :func`tree_search`) – A search algorithm to use (defaults to graph_search).
  • cost_limit (float) – The cost limit for the search (default = float(‘inf’))

A variant of iterative deepening that uses cost to determine the limit for expansion. When search fails, the cost limit is increased according to cost_inc. If the heuristic is admissible, then this is guranteed to find the best solution (similar to best first serach), but uses less memory.

If the problem.node_value is the cost to reach the node plus an admissible heuristic estimate of the distance from the node to the goal, then this is the IDA* algorithm.

Parameters:
  • problem (Problem) – The problem to solve.
  • search (graph_search() or :func`tree_search`) – A search algorithm to use (defaults to graph_search).
  • initial_cost_limit (float) – The initial cost limit for the search.
  • cost_inc (float) – The amount to increase the cost limit after failure.
  • max_cost_limit (float) – The maximum cost limit (default value of float(‘inf’))

A variant of beam search that successively increase the beam width when search fails. This ensures that if a solution exists, and you’re using graph search, and the solution space is finite, then that beam search will find it.

However, if you are looking for multiple solutions, then it might return duplicates as the width is increased. As the beam width increase, behavior is closer and closer to breadth-first search.

Parameters:
  • problem (Problem) – The problem to solve.
  • initial_beam_width (int) – The initial size of the beam (defaults to 1).
  • max_beam_width (int) – The maximum size of the beam (defaults to 1000).

Optimization / Local Search

This module contains the local search / optimization techniques. Instead of trying to find a goal state, these algorithms try to find the lowest cost state.

py_search.optimization.branch_and_bound(problem, graph_search=True, depth_limit=inf)

An exhaustive optimization technique that is guranteed to give the best solution. In general the algorithm starts with some (potentially non-optimal) solution. Then it uses the cost of the current best solution to prune branches of the search that do not have any chance of being better than this solution (i.e., that have a node_value > current best cost).

In this implementation, node_value should provide an admissible lower bound on the cost of solutions reachable from the provided node. If node_value is inadmissible, then optimality guarantees are lost.

Also, if the search space is infinite and/or the node_value function provides too little guidance (e.g., node_value = float(‘-inf’)), then the search might never terminate. To counter this, a depth_limit can be provided that stops expanding nodes after the provided depth. This will ensure the search is finite and guaranteed to terminate.

Finally, the problem.goal_test function can be used to terminate search early if a good enough solution has been found. If goal_test(node) return True, then search is immediately terminated and the node is returned.

Note, the current implementation uses best-first search via a priority queue data structure.

Parameters:
  • problem (py_search.base.Problem) – The problem to solve.
  • graph_search (Boolean) – Whether to use graph search (no duplicates) or tree search (duplicates)
py_search.optimization.hill_climbing(problem, random_restarts=0, max_sideways=0, graph_search=True)

Probably the simplest optimization approach. It expands the list of neighbors and chooses the best neighbor (steepest descent hill climbing).

Default configuration should yield similar behavior to local_beam_search() when it has a width of 1, but doesn’t need to maintain alternatives, so might use slightly less memory (just stores the best node instead of limited length priority queue).

If graph_search is true (the default), then a closed list is maintained. This is imporant for search spaces with platues because it keeps the algorithm from reexpanding neighbors with the same value and getting stuck in a loop.

If random_restarts > 0, then search is restarted multiple times. This can be useful for getting out of local minimums.

The problem.goal_test function can be used to terminate search early if a good enough solution has been found. If goal_test(node) return True, then search is immediately terminated and the node is returned.

Parameters:
  • problem (py_search.base.Problem) – The problem to solve.
  • random_restarts (int) – The number of times to restart search. The initial state is used for the first search and subsequent starts begin at a random state.
  • max_sideways (int) – Specifies the max number of contiguous sideways moves.
  • graph_search (Boolean) – Whether to use graph search (no duplicates) or tree search (duplicates)

A variant of py_search.informed_search.beam_search() that can be applied to local search problems. When the beam width of 1 this approach yields behavior similar to hill_climbing().

The problem.goal_test function can be used to terminate search early if a good enough solution has been found. If goal_test(node) return True, then search is immediately terminated and the node is returned.

Parameters:
  • problem (py_search.base.Problem) – The problem to solve.
  • beam_width (int) – The size of the search beam.
  • max_sideways (int) – Specifies the max number of contiguous sideways moves.
  • graph_search (Boolean) – Whether to use graph search (no duplicates) or tree search (duplicates)
py_search.optimization.random() → x in the interval [0, 1).
py_search.optimization.simulated_annealing(problem, temp_factor=0.95, temp_length=None, initial_temp=None, init_prob=0.4, min_accept=0.02, min_change=1e-06, limit=inf)

A more complicated optimization technique. At each iteration a random successor is expanded if it is better than the current node. If the random successor is not better than the current node, then it is expanded with some probability based on the temperature.

Used the formulation of simulated annealing found in:
Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1989). Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Operations research, 37(6), 865-892.

Also, the problem.goal_test function can be used to terminate search early if a good enough solution has been found. If goal_test(node) return True, then search is immediately terminated and the node is returned.

Parameters:
  • problem (py_search.base.Problem) – The problem to solve.
  • temp_factor (float) – The factor for geometric cooling, a value between 0 and 1, but usually very close to 1.
  • temp_length (int) – The number of nodes to expand at each temperature. If set to None (the default) then it is automatically chosen to be equal to the length of the successors list.
  • initial_temp (float or None) – The initial temperature for the annealing. The number is objective function specific. If set to None (the default), then a semi-random walk is used to select an initial temperature that will yield approx. init_prob acceptance rate for worse states.
  • min_accept (float between 0 and 1) – The fraction of states that must be accepted in temp_length iterations (taken from a single temperature) to not be frozen. Every time this is not exceeded, the frozen counter is incremented until it hits 5. If a better state is found, then the frozen counter is reset to 0.
  • min_change (float) – The amount of change that must be achieved in temp_length iterations (taken from a single temperature) to not be frozen. Everytime this is not exceeded, the frozen counter is incremented until it hits 5. If a better state is found, then the frozen counter is reset to 0.
  • limit (float) – The maximum number of iterations (random neighbors) to expand before stopping.