explorateur 1.2.0

State space search

Explorateur

Explorateur is a Python library to conduct State-Space-Search (SSS), a powerful framework for solving problems that require search over a collection of states.

Explorateur performs generic state-space-search over problem-specific states and moves. The user defines the BaseState and BaseMove and the library drives the search for solutions.

Given an initial user state, Explorateur performs iterative search moves until a stopping condition is reached:

• A termination state is found
• The search space is exhausted
• Reached max iterations, runtime limit, max depth
• Optionally, given a goal state, a goal state is encountered.

The behavior of the overall algorithm is controlled by the Search Strategy and the Exploration Strategy.

Search Strategy

• TreeSearch over open states
• GraphSearch over open states while also storing the closed states to avoid visiting duplicates.

Exploration Strategy

• BreadthFirst in uninformed fashion
• DepthFirst in uninformed fashion
• BestFirst in informed fashion assuming an objective function evaluates the solution quality of a state.

Quick Start

To use Explorateur, you need to define BaseState and BaseMove as in the template below.

from explorateur import Explorateur, BaseMove, BaseState, ExplorationType, SearchType


# TODO Implement your own Search Moves
class MyMove(BaseMove):

    def __init__(self):
        # TODO Your move object
        pass

    def __str__(self) -> str:
        # TODO Your move string, also used for node labels in DOT graph
        pass


# TODO Implement your own Search State 
class MyState(BaseState):

    def __init__(self):
        # TODO Your problem specific state representation
        super().__init__() # Make sure to initialize the base state!

    def get_moves(self) -> List[MyMove]:
        # TODO Your branching decisions as a list of moves
        pass

    def is_terminate(self, goal_state=None) -> bool:
        # TODO Is the current state a solution/termination?
        pass

    def execute(self, move: MyMove) -> bool:
        # TODO Execute the move on the state and return success flag
        pass

    def __str__(self) -> str:
        # TODO Your state string, also used for node labels in DOT graph
        pass

# Explarateur
explorer = Explorateur()

# Initial state
initial_state = MyState()

# Search for solutions
if explorer.search(initial_state,
                   goal_state=None,  # Optional goal state
                   exploration_type=ExplorationType.DepthFirst(),
                   search_type=SearchType.TreeSearch(),
                   is_solution_path=True,
                   dot_filename="tree_search_dfs.dot"):
    
    # Retrieve the solution state and the solution path
    # Dot graph file is also available for visualizing the search 
    print("Solution:", explorer.solution_state)
    print("Solution Path:", *explorer.solution_path, sep="\n<-")
else:
    print("No solution found!")

# Search statistics
print("Total Decisions:", explorer.num_decisions)
print("Total Failures:", explorer.num_failed_decisions)
print("Total Time:", explorer.total_time)

Concrete Example

Here is a concrete implementation to solve a toy Constraint Satisfaction Problem using backtracking tree search, with the corresponding search dot graph and search visualization.

Install from PyPI

Explorateur can be installed from PyPI using pip install explorateur

Install from Source

Alternatively, you can build a wheel package on your platform from scratch using the source code:

git clone https://github.com/skadio/explorateur.git
cd explorateur
pip install setuptools wheel # if wheel is not installed
python setup.py sdist bdist_wheel
pip install dist/explorateur-X.X.X-py3-none-any.whl

Test your setup

To confirm that cloning was successful, run the tests included in the project. All tests should pass.

git clone https://github.com/skadio/explorateur.git
cd explorateur
python -m unittest discover tests

To run a specific test from a given test file:

$ python -m unittest -v tests.<file_name>.<class_name>.<function_name>

For example:

$ python -m unittest -v tests.test_usage_example.UsageExampleTest.test_usage_example

To confirm that installation was successful, try importing Explorateur after pip install explorateur

import explorateur
print(explorateur.__version__)

Support

Please submit bug reports and feature requests as Issues.

License

Explorateur is licensed under the Apache License 2.0.