State space search
Project description
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.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for explorateur-1.0.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8ea60c98e270004e75bb9562b3016d883ad6cd7838c44bc4b75a95d7c5843361 |
|
MD5 | 05ed91bc15e312be09ad1f202ef48cd7 |
|
BLAKE2b-256 | a99cdc552f13271021fbabdf12b22a589dc1a963a0dc0bfe8fab35a6a36f3d68 |