mod archive

module archive

Quality-diversity archive: tessellation, curiosity, novelty. Quality-diversity archive primitives.

The occupancy catalog keeps one best structure per packing family and draws new starts from it, which is MAP-Elites with a learned descriptor in place of a designed one. Three pieces of that literature are missing here and are supplied below, each as arithmetic over descriptors so nothing in this module needs a search, a socket, or a potential.

Why a tessellation

Families are discovered by leader clustering, so their number is whatever the data produced: a campaign reported twenty-two families across twenty-four replicas, which is nearly one cell per replica and not an archive at all. Worse, a saturation statistic over a support that grows as it samples is answering a moving question. Tessellating the descriptor space instead makes the cell count a parameter and the cells equal by construction, which is what centroidal Voronoi tessellations are for in this setting.

The tessellation needs a descriptor of fixed width. A DECAF class histogram grows a column whenever the codebook grows one, so it is the wrong input; the fixed-width cloud mean is the right one. That constraint is real and is the reason this is a separate space from the family key rather than a replacement for it.

Functions

fn novelty(descriptor: &[f64], seen: &[Vec<f64>], k: usize) -> f64

Novelty of a descriptor: mean distance to its k nearest neighbours among those already seen.

On a deceptive landscape the objective’s gradient points into the trap, and this is the quantity a search follows instead. An empty neighbourhood is maximally novel and answers infinity, which is the honest value: nothing has been seen to compare against.

Structs and Unions

struct Archive

An archive of descriptor cells with an annealed radius.

Cells are not a grid and not discovered at a fixed radius. A structure joins the nearest cell within Dcut and opens a new one beyond it, and Dcut anneals from half the mean pairwise distance down to a floor over the run, which is conformational space annealing’s rule and crate::diversity::DiversityAnnealer is already the schedule for it. Early on the archive is coarse and the search is asked only to be different; late on it is fine and the search is asked to be better. That is the simulated-annealing half of CSA applied to diversity rather than to acceptance.

Selection is the exploration half, and the reference is not the physics literature. Hard-exploration Atari was solved by keeping an archive of visited cells, returning to a promising one, and exploring from there: first return, then explore. A Leave is that return, and the cell it returns to is chosen the same way, by weighting a cell’s demonstrated success against how little it has been tried.

Implementations

impl Archive

Functions

fn anneal(&mut self, progress: f64) -> f64

Advance the radius to where progress through the run puts it.

fn assign(&self, descriptor: &[f64]) -> Option<usize>

Cell this descriptor belongs to without opening one.

fn cells(&self) -> usize

Cells opened so far.

fn coverage<'a, I>(&self, descriptors: I) -> f64
where
    I: IntoIterator<Item = &'a [f64]>

Fraction of open cells that any of descriptors occupies.

The denominator is the cells opened so far and it grows as the radius anneals down, so this is a diagnostic and not a stopping criterion: a run can drive it down by discovering structure rather than by failing to. Anything that stops on it stops on the shape of the schedule.

fn nearest(&self, descriptor: &[f64]) -> Option<usize>

Nearest cell to this descriptor, however far away it is.

For classifying, not for opening. Every descriptor an open archive is asked about gets an answer in the archive’s own numbering, which matters because the alternative namespace, the leader-clustered packing families, uses the same integers for unrelated things. Falling back from one to the other credits occupancy and reward to whatever cell happens to share the number.

fn new(initial: f64, floor_fraction: f64) -> Self

An archive whose radius starts at initial and anneals to floor_fraction of it.

fn observe(&mut self, descriptor: &[f64]) -> Option<usize>

Cell this descriptor belongs to, opening one if it is further than the radius from every cell already open.

fn penalise(&mut self, cell: usize)

A start drawn from this cell produced nothing.

fn radius(&self) -> f64

Current radius.

fn reward(&mut self, cell: usize)

A start drawn from this cell produced something the catalog kept.

fn score(&self, cell: usize) -> f64

Posterior mean success rate of a cell.

fn select<R: Rng + ?Sized>(&self, allowed: &[usize], rng: &mut R) -> Option<usize>

Return to a cell: a Thompson draw on what the cell has produced, discounted by how heavily it has already been visited.

The posterior is the exploit term and the count is the explore term, which is the shape of the cell-selection rule that made return-then-explore work: a cell nothing has visited is worth returning to even with no evidence, and a cell visited a hundred times has to keep earning it.

fn visits(&self, cell: usize) -> u64

Times a structure landed in a cell.

struct Curiosity

Per-cell Beta-Bernoulli bandit over the archive.

Choosing which cell to draw a start from is a bandit problem and deserves to be treated as one. The reward is binary, the catalog kept what came back or it did not, so the conjugate model is Beta over a Bernoulli rate and the selection rule is Thompson sampling: draw a rate from each cell’s posterior and take the highest.

That is better than the reward-and-decay heuristic it replaces on three counts. It has no constants to pick, where the heuristic had a decay and a floor chosen by hand. Its exploration is automatic: a cell tried twice has a wide posterior and still wins draws, while a cell tried two hundred times does not, so effort moves off a cell only once there is evidence to move it. And it cannot write a cell off, because a Beta posterior never reaches zero, which matters because a descriptor can be wrong where a cell is right.

The allocator over move kernels in crate::allocate is the same idea over a Gaussian reward; this is the Bernoulli case.

Implementations

impl Curiosity

Functions

fn draws(&self, cell: usize) -> f64

Times this cell has been drawn from.

fn ensure(&mut self, cells: usize)

Grow the table so cells are armed, new ones uniform.

Cells are discovered as the search runs, so the table cannot be sized once. Growing never disturbs a posterior already earned.

fn new(cells: usize) -> Self

A bandit over cells, each with a uniform prior.

fn penalise(&mut self, cell: usize)

A start drawn from this cell produced nothing.

fn reward(&mut self, cell: usize)

A start drawn from this cell produced something the catalog kept.

fn score(&self, cell: usize) -> f64

Posterior mean success rate of a cell, or the uniform prior for one the table has not armed.

fn select<R: Rng + ?Sized>(&self, allowed: &[usize], rng: &mut R) -> Option<usize>

Thompson draw: sample a rate from each allowed cell’s posterior and take the highest.