ribs 0.6.3

A bare-bones Python library for quality diversity optimization.

pyribs

Website	Source	Docs	Paper	Twitter
pyribs.org	GitHub	docs.pyribs.org	pyribs.org/paper

PyPI	Conda	CI/CD	Docs Status

A bare-bones Python library for quality diversity (QD) optimization. Pyribs implements the highly modular Rapid Illumination of Behavior Space (RIBS) framework for QD optimization. Pyribs is also the official implementation of Covariance Matrix Adaptation MAP-Elites (CMA-ME), Covariance Matrix Adaptation MAP-Elites via a Gradient Arborescence (CMA-MEGA), Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), and scalable variants of CMA-MAE.

Overview

Quality diversity (QD) optimization is a subfield of optimization where solutions generated cover every point in a measure space while simultaneously maximizing (or minimizing) a single objective. QD algorithms within the MAP-Elites family of QD algorithms produce heatmaps (archives) as output where each cell contains the best discovered representative of a region in measure space.

In the QD literature, measure function outputs have also been referred to as "behavioral characteristics," "behavior descriptors," or "feature descriptors."

Recent years have seen the development of a large number of QD algorithms. To represent these and future algorithms, we have developed the highly modular RIBS framework. RIBS divides a QD algorithm into three components:

• An archive, which saves generated solutions within measure space.
• One or more emitters, where each emitter is an algorithm which generates new candidate solutions and responds to feedback about how the solutions were evaluated and how they were inserted into the archive.
• A scheduler which controls the interaction of the archive and emitters. The scheduler also provides an interface for requesting new candidate solutions and telling the algorithm how candidates performed.

By interchanging these components, a user can compose a large number of QD algorithms.

Pyribs is an implementation of the RIBS framework designed to support a wide range of users, from beginners entering the field to experienced researchers seeking to develop new algorithms. Pyribs achieves these goals by embodying three principles:

• Simple: Centered only on components that are absolutely necessary to run a QD algorithm, allowing users to combine the framework with other software frameworks.
• Flexible: Capable of representing a wide range of current and future QD algorithms, allowing users to easily create or modify components.
• Accessible: Easy to install and learn, particularly for beginners with limited computational resources.

In contrast to other QD libraries, pyribs is "bare-bones." For example, like pycma, pyribs focuses solely on optimizing fixed-dimensional continuous domains. Focusing on this one commonly-occurring problem allows us to optimize the library for performance as well as ease of use. Refer to the list of additional QD libraries below if you need greater performance or have additional use cases.

Following the RIBS framework (shown in the figure below), a standard algorithm in pyribs operates as follows:

1. The user calls the ask() method on the scheduler. The scheduler requests solutions from each emitter by calling the emitter's ask() method.
2. The user evaluates solutions to obtain the objective and measure values.
3. The user passes the evaluations to the scheduler's tell() method. The scheduler adds the solutions into the archive and receives feedback. The scheduler passes this feedback along with the evaluated solutions to each emitter's tell() method, and each emitter then updates its internal state.

Paper

Two years after the initial release of pyribs, we released a paper that elaborates on the RIBS framework and the design decisions behind pyribs! For more information on this paper, see here.

Citation

If you use pyribs in your research, please consider citing our GECCO 2023 paper as follows. Also consider citing any algorithms you use as shown below.

@inproceedings{10.1145/3583131.3590374,
  author = {Tjanaka, Bryon and Fontaine, Matthew C and Lee, David H and Zhang, Yulun and Balam, Nivedit Reddy and Dennler, Nathaniel and Garlanka, Sujay S and Klapsis, Nikitas Dimitri and Nikolaidis, Stefanos},
  title = {Pyribs: A Bare-Bones Python Library for Quality Diversity Optimization},
  year = {2023},
  isbn = {9798400701191},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3583131.3590374},
  doi = {10.1145/3583131.3590374},
  abstract = {Recent years have seen a rise in the popularity of quality diversity (QD) optimization, a branch of optimization that seeks to find a collection of diverse, high-performing solutions to a given problem. To grow further, we believe the QD community faces two challenges: developing a framework to represent the field's growing array of algorithms, and implementing that framework in software that supports a range of researchers and practitioners. To address these challenges, we have developed pyribs, a library built on a highly modular conceptual QD framework. By replacing components in the conceptual framework, and hence in pyribs, users can compose algorithms from across the QD literature; equally important, they can identify unexplored algorithm variations. Furthermore, pyribs makes this framework simple, flexible, and accessible, with a user-friendly API supported by extensive documentation and tutorials. This paper overviews the creation of pyribs, focusing on the conceptual framework that it implements and the design principles that have guided the library's development. Pyribs is available at https://pyribs.org},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
  pages = {220–229},
  numpages = {10},
  keywords = {framework, quality diversity, software library},
  location = {Lisbon, Portugal},
  series = {GECCO '23}
}

Usage

Here we show an example application of CMA-ME in pyribs. To initialize the algorithm, we first create:

• A 2D GridArchive where each dimension contains 20 cells across the range [-1, 1].
• Three instances of EvolutionStrategyEmitter, all of which start from the search point 0 in 10-dimensional space and a Gaussian sampling distribution with standard deviation 0.1.
• A Scheduler that combines the archive and emitters together.

After initializing the components, we optimize (pyribs maximizes) the negative 10-D Sphere function for 1000 iterations. Users of pycma will be familiar with the ask-tell interface (which pyribs adopted). First, the user must ask the scheduler for new candidate solutions. After evaluating the solution, they tell the scheduler the objectives and measures of each candidate solution. The algorithm then populates the archive and makes decisions on where to sample solutions next. Our toy example uses the first two parameters of the search space as measures.

import numpy as np

from ribs.archives import GridArchive
from ribs.emitters import EvolutionStrategyEmitter
from ribs.schedulers import Scheduler

archive = GridArchive(
    solution_dim=10,
    dims=[20, 20],
    ranges=[(-1, 1), (-1, 1)],
)
emitters = [
    EvolutionStrategyEmitter(
        archive,
        x0=[0.0] * 10,
        sigma0=0.1,
    ) for _ in range(3)
]
scheduler = Scheduler(archive, emitters)

for itr in range(1000):
    solutions = scheduler.ask()

    # Optimize the 10D negative Sphere function.
    objective_batch = -np.sum(np.square(solutions), axis=1)

    # Measures: first 2 coordinates of each 10D solution.
    measures_batch = solutions[:, :2]

    scheduler.tell(objective_batch, measures_batch)

To visualize this archive with Matplotlib, we then use the grid_archive_heatmap function from ribs.visualize.

import matplotlib.pyplot as plt
from ribs.visualize import grid_archive_heatmap

grid_archive_heatmap(archive)
plt.show()

For more information, refer to the documentation.

Installation

pyribs supports Python 3.8 and above. Earlier Python versions may work but are not officially supported. To find the installation command for your system (including for installing from source), visit the installation selector on our website.

To test your installation, import pyribs and print the version with this command:

python -c "import ribs; print(ribs.__version__)"

You should see a version number in the output.

Documentation

See here for the documentation: https://docs.pyribs.org

To serve the documentation locally, clone the repo and install the development requirements with

pip install -e .[dev]

Then run

make servedocs

This will open a window in your browser with the documentation automatically loaded. Furthermore, every time you make changes to the documentation, the preview will also reload.

Contributors

pyribs is developed and maintained by the ICAROS Lab at USC. For information on contributing to the repo, see CONTRIBUTING.

• Bryon Tjanaka
• Matthew C. Fontaine
• David H. Lee
• Yulun Zhang
• Nivedit Reddy Balam
• Nathan Dennler
• Sujay S. Garlanka
• Nikitas Klapsis
• Robby Costales
• Sam Sommerer
• Vincent Vu
• Stefanos Nikolaidis

We thank Amy K. Hoover and Julian Togelius for their contributions deriving the CMA-ME algorithm.

Users

pyribs users include:

• Adam Gaier (Autodesk Research)
• Adaptive & Intelligent Robotics Lab (Imperial College London)
• Chair of Statistical Learning and Data Science (LMU Munich)
• Game Innovation Lab (New York University)
• Giovanni Iacca (University of Trento)
• HUAWEI Noah's Ark Lab
• ICAROS Lab (University of Southern California)
• Jacob Schrum (Southwestern University)
• Lenia Research
• Paul Kent (The University of Warwick)
• Various researchers at the University of Tsukuba

Publications

For the list of publications which use pyribs, refer to our Google Scholar entry.

Software

See the GitHub dependency graph for the public GitHub repositories which depend on pyribs.

Citing Algorithms in pyribs

If you use the following algorithms, please also cite their relevant papers:

• CMA-ME: Fontaine 2020

  @inproceedings{10.1145/3377930.3390232,
    author = {Fontaine, Matthew C. and Togelius, Julian and Nikolaidis, Stefanos and Hoover, Amy K.},
    title = {Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space},
    year = {2020},
    isbn = {9781450371285},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3377930.3390232},
    doi = {10.1145/3377930.3390232},
    booktitle = {Proceedings of the 2020 Genetic and Evolutionary Computation Conference},
    pages = {94–102},
    numpages = {9},
    location = {Canc\'{u}n, Mexico},
    series = {GECCO '20}
  }
  

• CMA-MEGA: Fontaine 2021

  @inproceedings{NEURIPS2021_532923f1,
   author = {Fontaine, Matthew and Nikolaidis, Stefanos},
   booktitle = {Advances in Neural Information Processing Systems},
   editor = {M. Ranzato and A. Beygelzimer and Y. Dauphin and P.S. Liang and J. Wortman Vaughan},
   pages = {10040--10052},
   publisher = {Curran Associates, Inc.},
   title = {Differentiable Quality Diversity},
   url = {https://proceedings.neurips.cc/paper/2021/file/532923f11ac97d3e7cb0130315b067dc-Paper.pdf},
   volume = {34},
   year = {2021}
  }
  

• CMA-MAE: Fontaine 2022

  @misc{cmamae,
    doi = {10.48550/ARXIV.2205.10752},
    url = {https://arxiv.org/abs/2205.10752},
    author = {Fontaine, Matthew C. and Nikolaidis, Stefanos},
    keywords = {Machine Learning (cs.LG), Artificial Intelligence (cs.AI), FOS: Computer and information sciences, FOS: Computer and information sciences},
    title = {Covariance Matrix Adaptation MAP-Annealing},
    publisher = {arXiv},
    year = {2022},
    copyright = {arXiv.org perpetual, non-exclusive license}
  }
  

• Scalable CMA-MAE: Tjanaka 2022

  @misc{scalablecmamae,
        title={Training Diverse High-Dimensional Controllers by Scaling Covariance Matrix Adaptation MAP-Annealing},
        author={Bryon Tjanaka and Matthew C. Fontaine and Aniruddha Kalkar and Stefanos Nikolaidis},
        year={2022},
        eprint={2210.02622},
        archivePrefix={arXiv},
        primaryClass={cs.RO}
  }
  

Additional QD Libraries

• QDax: Implementations of QD algorithms in JAX. QDax is suitable if you want to run entire QD algorithms on hardware accelerators in a matter of minutes, and it is particularly useful if you need to interface with Brax environments.
• qdpy: Python implementations of a wide variety of QD algorithms.
• sferes: Contains C++ implementations of QD algorithms; can also handle discrete domains.

License

pyribs is released under the MIT License.

Credits

The pyribs package was initially created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.

History

0.6.3

Small patch release due to deprecation issues.

Changelog

Improvements

• Replace np.product with np.prod due to deprecation ({pr}385)

0.6.2

Small patch release due to installation issues in our tutorials.

Changelog

API

• Import ribs[visualize] in tutorials that need it ({pr}379)

Improvements

• Switch to a branch-based release model ({pr}382)

0.6.1

(This release was removed)

0.6.0

Changelog

API

• Drop Python 3.7 support and upgrade dependencies ({pr}350)
• Add visualization of QDax repertoires ({pr}353)
• Improve cvt_archive_heatmap flexibility ({pr}354)
• Clip Voronoi regions in cvt_archive_heatmap ({pr}356)
• Backwards-incompatible: Allow using kwargs for colorbar in parallel_axes_plot ({pr}358)
  • Removes cbar_orientaton and cbar_pad args for parallel_axes_plot
• Add rasterized arg for heatmaps ({pr}359)
• Support 1D cvt_archive_heatmap ({pr}362)
• Add 3D plots for CVTArchive ({pr}371)
• Add visualization of 3D QDax repertoires ({pr}373)
• Enable plotting custom data in visualizations ({pr}374)

Documentation

• Use dask instead of multiprocessing for lunar lander tutorial ({pr}346)
• pip install swig before gymnasium[box2d] in lunar lander tutorial ({pr}346)
• Fix lunar lander dependency issues ({pr}366, {pr}367)
• Simplify DQD tutorial imports ({pr}369)
• Improve visualization docs examples ({pr}372)

Improvements

• Improve developer workflow with pre-commit ({pr}351, {pr}363)
• Speed up 2D cvt_archive_heatmap by order of magnitude ({pr}355)
• Refactor visualize module into multiple files ({pr}357)
• Refactor visualize tests into multiple files ({pr}370)
• Add GitHub link roles in documentation ({pr}361)
• Refactor argument validation utilities ({pr}365)
• Use Conda envs in all CI jobs ({pr}368)
• Split tutorial CI into multiple jobs ({pr}375)

0.5.2

This release contains miscellaneous edits to our documentation from v0.5.1. Furthermore, the library is updated to support Python 3.11, removed deprecated options, and strengthened with more robust checks and error messages in the schedulers.

Changelog

API

• Support Python 3.11 ({pr}342)
• Check that emitters passed in are lists/iterables in scheduler ({pr}341)
• Fix Matplotlib get_cmap deprecation ({pr}340)
• Backwards-incompatible: Default plot_centroids to False when plotting ({pr}339)
• Raise error messages when ask is called without ask_dqd ({pr}338)

Documentation

• Add BibTex citation for GECCO 2023 ({pr}337)

Improvements

• Update distribution dependencies ({pr}344)

0.5.1

This release contains miscellaneous edits to our documentation from v0.5.0. There were no changes to library functionality in this release.

0.5.0

To learn about this release, see our page on What's New in v0.5.0: https://docs.pyribs.org/en/stable/whats-new.html

Changelog

API

• Schedulers warn if no solutions are inserted into archive ({pr}320)
• Implement BanditScheduler ({pr}299)
• Backwards-incompatible: Implement Scalable CMA-ES Optimizers ({pr}274, {pr}288)
• Make ribs.emitters.opt public ({pr}281)
• Add normalized QD score to ArchiveStats ({pr}276)
• Backwards-incompatible: Make ArchiveStats a dataclass ({pr}275)
• Backwards-incompatible: Add shape checks to tell() and tell_dqd() methods ({pr}269)
• Add method for computing CQD score in archives ({pr}252)
• Backwards-incompatible: Deprecate positional arguments in constructors ({pr}261)
• Backwards-incompatible: Allow custom initialization in Gaussian and IsoLine emitters ({pr}259, {pr}265)
• Implement CMA-MAE archive thresholds ({pr}256, {pr}260, {pr}314)
  • Revive the old implementation of add_single removed in ({pr}221)
  • Add separate tests for add_single and add with single solution
• Fix all examples and tutorials ({pr}253)
• Add restart timer to EvolutionStrategyEmitter and GradientArborescenceEmitter({pr}255)
• Rename fields and update documentation ({pr}249, {pr}250)
  • Backwards-incompatible: rename Optimizer to Scheduler
  • Backwards-incompatible: rename objective_value to objective
  • Backwards-incompatible: rename behavior_value/bcs to measures
  • Backwards-incompatible: behavior_dim in archives is now measure_dim
  • Rename n_solutions to batch_size in Scheduler.
• Add GradientArborescenceEmitter, which is used to implement CMA-MEGA ({pr}240, {pr}263, {pr}264, {pr}282, {pr}321)
• Update emitter tell() docstrings to no longer say "Inserts entries into archive" ({pr}247)
• Expose emitter.restarts as a property ({pr}248)
• Specify that x0 is 1D for all emitters ({pr}244)
• Add best_elite property for archives ({pr}237)
• Rename methods in ArchiveDataFrame and rename as_pandas behavior columns ({pr}236)
• Re-run CVTArchive benchmarks and update CVTArchive ({pr}235, {pr}329)
  • Backwards-incompatible: use_kd_tree now defaults to True since the k-D tree is always faster than brute force in benchmarks.
• Allow adding solutions one at a time in optimizer ({pr}233)
• Minimize numba usage ({pr}232)
• Backwards-incompatible: Implement batch addition in archives ({pr}221, {pr}242)
  • add now adds a batch of solutions to the archive
  • add_single adds a single solution
• emitter.tell now takes in status_batch and value_batch ({pr}227)
• Make epsilon configurable in archives ({pr}226)
• Backwards-incompatible: Remove ribs.factory ({pr}225, {pr}228)
• Backwards-incompatible: Replaced ImprovementEmitter, RandomDirectionEmitter, and OptimizingEmitter with EvolutionStrategyEmitter ({pr}220, {pr}223, {pr}278)
• Raise ValueError for incorrect array shapes in archive methods ({pr}219)
• Introduced the Ranker object, which is responsible for ranking the solutions based on different objectives ({pr}209, {pr}222, {pr}245)
• Add index_of_single method for getting index of measures for one solution ({pr}214)
• Backwards-incompatible: Replace elite_with_behavior with retrieve and retrieve_single in archives ({pr}213, {pr}215, {pr}295)
• Backwards-incompatible: Replace get_index with batched index_of method in archives ({pr}208)
  • Also added grid_to_int_index and int_to_grid_index methods for GridArchive and SlidingBoundariesArchive
• Backwards-incompatible: Made it such that each archive is initialized fully in its constructor instead of needing a separate .initialize(solution_dim) call ({pr}200)
• Backwards-incompatible: Add sigma, sigma0 options to gaussian_emitter and iso_line_emitter ({pr}199)
  • gaussian_emitter constructor requires sigma; sigma0 is optional.
  • iso_line_emitter constructor takes in optional parameter sigma0.
• Backwards-incompatible: Add cbar, aspect options for cvt_archive_heatmap ({pr}197)
• Backwards-incompatible: Add aspect option to grid_archive_heatmap + support for 1D heatmaps ({pr}196)
  • square option no longer works
• Backwards-incompatible: Add cbar option to grid_archive_heatmap ({pr}193)
• Backwards-incompatible: Replace get_random_elite() with batched sample_elites() method ({pr}192)
• Backwards-incompatible: Add EliteBatch and rename fields in Elite ({pr}191)
• Backwards-incompatible: Rename bins to cells for consistency with literature ({pr}189)
  • Archive constructors now take in cells argument instead of bins
  • Archive now have a cells property rather than a bins property
• Backwards-incompatible: Only use integer indices in archives ({pr}185)
  • ArchiveBase
    • Replaced storage_dims (tuple of int) with storage_dim (int)
    • _occupied_indices is now a fixed-size array with _num_occupied indicating its current usage, and _occupied_indices_cols has been removed
    • index_of must now return an integer

Bugs

• Fix boundary lines in sliding boundaries archive heatmap ({pr}271)
• Fix negative eigenvalue in CMA-ES covariance matrix ({pr}285)

Documentation

• Speed up lunar lander tutorial ({pr}319)
• Add DQDTutorial ({pr}267)
• Remove examples extra in favor of individual example deps ({pr}306)
• Facilitate linking to latest version of documentation ({pr}300)
• Update lunar lander tutorial with v0.5.0 features ({pr}292)
• Improve tutorial and example overviews ({pr}291)
• Move tutorials out of examples folder ({pr}290)
• Update lunar lander to use Gymnasium ({pr}289)
• Add CMA-MAE tutorial ({pr}273, {pr}284)
• Update README ({pr}279)
• Add sphinx-codeautolink to docs ({pr}206, {pr}280)
• Fix documentation rendering issues on ReadTheDocs ({pr}205)
• Fix typos and formatting in docstrings of ribs/visualize.py ({pr}203)
• Add in-comment type hint rich linking ({pr}204)
• Upgrade Sphinx dependencies ({pr}202)

Improvements

• Move threadpoolctl from optimizer to CMA-ES ({pr}241)
• Remove unnecessary emitter benchmarks ({pr}231)
• Build docs during CI/CD workflow ({pr}211)
• Drop Python 3.6 and add Python 3.10 support ({pr}181)
• Add procedure for updating changelog ({pr}182)
• Add 'visualize' extra ({pr}183, {pr}184, {pr}302)

0.4.0 (2021-07-19)

To learn about this release, see our blog post: https://pyribs.org/blog/0-4-0

Changelog

API

• Add ribs.visualize.parallel_axes_plot for analyzing archives with high-dimensional BCs ({pr}92)
• Backwards-incompatible: Reduce attributes and parameters in EmitterBase to make it easier to extend ({pr}101)
• In Optimizer, support emitters that return any number of solutions in ask() ({pr}101)
• Backwards-incompatible: Store metadata in archives as described in {pr}87 ({pr}103, {pr}114, {pr}115, {pr}119)
• Backwards-incompatible: Rename "index" to "index_0" in CVTArchive.as_pandas for API consistency ({pr}113)
• Backwards-incompatible: Make index_of() public in archives to emphasize each index's meaning ({pr}128)
• Backwards-incompatible: Add index to get_random_elite() and elite_with_behavior() in archives ({pr}129)
• Add clear() method to archive ({pr}140, {pr}146)
• Represent archive elites with an Elite namedtuple ({pr}142)
• Add len and iter methods to archives ({pr}151, {pr}152)
• Add statistics to archives ({pr}100, {pr}157)
• Improve manipulation of elites by modifying as_pandas ({pr}123, {pr}149, {pr}153, {pr}158, {pr}168)
• Add checks for optimizer array and list shapes ({pr}166)

Documentation

• Add bibtex citations for tutorials ({pr}122)
• Remove network training from Fooling MNIST tutorial ({pr}161)
• Fix video display for lunar lander in Colab ({pr}163)
• Fix Colab links in stable docs ({pr}164)

Improvements

• Add support for Python 3.9 ({pr}84)
• Test with pinned versions ({pr}110)
• Increase minimum required versions for scipy and numba ({pr}110)
• Refactor as_pandas tests ({pr}114)
• Expand CI/CD to test examples and tutorials ({pr}117)
• Tidy up existing tests ({pr}120, {pr}127)
• Fix vocab in various areas ({pr}138)
• Fix dependency issues in tests ({pr}139)
• Remove tox from CI ({pr}143)
• Replace "entry" with "elite" in tests ({pr}144)
• Use new archive API in ribs.visualize implementation ({pr}155)

0.3.1 (2021-03-05)

This release features various bug fixes and improvements. In particular, we have added tests for SlidingBoundariesArchive and believe it is ready for more rigorous use.

Changelog

• Move SlidingBoundariesArchive out of experimental by adding tests and fixing bugs ({pr}93)
• Added nicer figures to the Sphere example with grid_archive_heatmap ({pr}86)
• Added testing for Windows and MacOS ({pr}83)
• Fixed package metadata e.g. description

0.3.0 (2021-02-05)

pyribs is now in beta. Since our alpha release (0.2.0), we have polished the library and added new tutorials and examples to our documentation.

Changelog

• Added a Lunar Lander example that extends the lunar lander tutorial ({pr}70)
• Added New Tutorial: Illuminating the Latent Space of an MNIST GAN ({pr}78)
• GridArchive: Added a boundaries attribute with the upper and lower bounds of each dimension's bins ({pr}76)
• Fixed a bug where CMA-ME emitters do not work with float32 archives ({pr}74)
• Fixed a bug where Optimizer is able to take in non-unique emitter instances ({pr}75)
• Fixed a bug where GridArchive failed for float32 due to a small epsilon ({pr}81)
• Fix issues with bounds in the SlidingBoundaryArchive ({pr}77)
• Added clearer error messages for archives ({pr}82)
• Modified the Python requirements to allow any version above 3.6.0 ({pr}68)
• The wheel is now fixed so that it only supports py3 rather than py2 and py3 ({pr}68)
• Miscellaneous documentation fixes ({pr}71)

0.2.0 (2021-01-29)

• Alpha release

0.2.1 (2021-01-29)

• Package metadata fixes (author, email, url)
• Miscellaneous documentation improvements

0.1.1 (2021-01-29)

• Test release (now removed)

0.1.0 (2020-09-11)

• Test release (now removed)

0.0.0 (2020-09-11)

• pyribs begins