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.

The behavior of the search is controlled by the built-in Search Strategy and the Exploration Strategy and user-defined moves. Given an initial user state, Explorateur performs search moves iteratively until a stopping condition is reached.

Search Strategy

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

Exploration Strategy

• BreadthFirst in an uninformed fashion,
• DepthFirst in an uninformed fashion,
• BestFirst in an informed fashion with an objective function that evaluates the quality of a state. By default, the best first search is set to minimize. To maximize, multiply your objective function by -1.

Stopping Conditions

• A termination state is found,
• The search space is exhausted,
• A stopping criterion such as max iterations, runtime limit, or max depth has been reached,
• (Optionally) The given goal state is encountered.

Quick Start

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

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


# Implement your 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


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

Examples

• Backtracking Tree-Search: A toy Constraint Satisfaction Problem to find a solution via backtracking tree search as depicted in search visualization.
• Graph Search: The classical Romanian Graph Problem solved with a goal state as depicted in search visualization. Note the use of __eq__ and __hash__ to enable graph-based search to handle state comparison and hashing.
• A* Search: The classical A* Search between an initial and goal state using an admissible heuristic solved with best-first search to minimize the total cost as depicted in search visualization. Note the use of get_objective function for optimization.

Installation

Explorateur can be installed from PyPI using pip install explorateur

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

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

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

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

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.