explorateur 1.0.0

State space search

Explorateur

Explorateur is a library written in Python to solve problems that require searching over a collection of states. The main search loop begins with an initial state, and then, performs search moves until a termination state is found, search space is exhausted, or a stopping criteria, such as the number of iterations, runtime limit, or maximum depth, has been reached. Optionally, a goal state can also be provided as input.

Explorateur provides a generic state space search based on problem-specific BaseMove and BaseState representations. The search strategy can be TreeSearch or GraphSearch. The exploration strategy can be BestFirst, BreadthFirst, or DepthFirst.

Quick Start:

Here is the template BaseMove and BaseState example, ready for problem specific implementations. When the search is complete, the solution and the solution path can be retrieved as well as the dot graph for visualization of the search.

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 mvoe 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
        pass

    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

# Explorateur
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_file_path="tree_search_dfs.dot"):
    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 small Constraint Satisfaction Problem with the corresponding DOT Graph 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

This command will run all the tests.

$  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_exploration_type.ExplorationTypeTests.test_bfs_1

Changelog

Date	Notes
15 May, 2024	Initial release

Support

Please submit bug reports and feature requests as Issues.

License

Explorateur is licensed under the Apache License 2.0.