#NQD‑CAL — Open‑Ended Search Calculus

Pattern C.18 · Stable Part C - Kernel Extension Specifications

Status. Calculus specification (CAL). Exports Γ_nqd.* operators for open‑ended, illumination‑style generation. ΔKernel = 0 (no kernel primitives added). Minting note: this CAL does not mint new U‑types; it defines CAL‑records that MAY alias to registered U‑types where present via E.10/UTS.

Depends on. A‑kernel (A.1–A.15), MM‑CHR (C.16) for measurements, KD‑CAL for similarity/corpora, Sys‑CAL for carriers, Decsn‑CAL (objectives; advisory), Compose‑CAL (set aggregation; advisory).

Coordinates with. B.5.2.1 (binding), C.17 Creativity‑CHR (characteristics & scales), C.19 E/E‑LOG (policies: emitter selection, explore/exploit).

Exports (CAL; no U‑type minting here).

• Records: NQD.DescriptorMap (alias of U.DescriptorMap if minted), NQD.NQDArchive (alias of U.NQDArchive), NQD.Niche, NQD.ArchiveCell, NQD.EmissionSeed?, U.EmitterPolicyRef, U.InsertionPolicyRef, U.IlluminationSummary, and NQD.CandidateSet (alias of Set<U.Hypothesis>).

Open‑ended search (NQD) equips FPF with illumination‑style generation and Pareto/portfolio selection in multi‑criteria, partially ordered spaces; it feeds G.5 without scalarising ordinal or mixed‑scale characteristics.

#Keywords

• search
• exploration
• hypothesis generation
• novelty
• quality
• diversity (NQD).

#Relations

#Content

#Problem frame

Open‑ended search (NQD) equips FPF with illumination‑style generation and Pareto/portfolio selection in multi‑criteria, partially ordered spaces; it feeds G.5 without scalarising ordinal or mixed‑scale characteristics.

#Problem

Without a disciplined NQD calculus, contexts (a) conflate illumination telemetry with dominance, (b) lose reproducibility due to undeclared DescriptorMap/DistanceDefRef.editions, and (c) perform illegal aggregations across scales.

#Forces

• Posets vs. scalarisation — selectors must return sets (Pareto/archive) rather than illegal weighted sums across mixed scales. • Exploration vs. exploitation — emitters must adapt while preserving provenance and editioning. • Telemetry metric vs. objective — Illumination (coverage/QD‑score) informs health but is not a dominance characteristic by default. • Reproducibility vs. adaptivity — budgets, ε, K, and InsertionPolicy must be edition‑tracked.

#Solution

Provide Γ_nqd.* operators and U.Types for DescriptorMap, Archive/Niche, policies, and illumination telemetry summaries; bind measurement legality to MM‑CHR and policy control to E/E‑LOG. (Exports/Type notes/Operator specs below are normative parts of this Solution.)

• Operators (Γ):
  • Γ_nqd.generate(seed?, EmitterPolicyRef, Budget, DescriptorMapRef, QualityMeasuresRef, NoveltyMetricRef, CoverageGrid, CellCapacity K=1, EpsilonDominance ε=0, DedupThreshold?, InsertionPolicyRef?) → CandidateSet<U.Hypothesis>
  • Γ_nqd.updateArchive(Archive, CandidateSet, InsertionPolicyRef?) → Archive'
  • Γ_nqd.illuminate(Archive) → IlluminationSummary{coverage, QD-score, occupancyEntropy, filledCells} (report‑only telemetry summary; not a dominance characteristic unless a policy explicitly promotes it).
  • Γ_nqd.selectFront(Archive|CandidateSet, characteristics={Q components, Novelty@context, ΔDiversity_P, …}) → ParetoFront

Type notes.

• U.DescriptorMap (Tech; twin‑labelled Plain) : Hypothesis → ℝ^d (declares encoder, invariances, version, CharacteristicSpaceRef). Publish Tech/Plain per E.10; declare DescriptorMapRef.edition and DistanceDefRef.edition. Dimensionality rule. Require d≥2 only when QD/illumination surfaces are active; for non‑QD contexts d≥1 is lawful.
• NQD.CandidateSet ≡ Set<U.Hypothesis> with attached per‑item vectors {Q_i, N_i, D_i:=ΔDiversity_P, S_i?, provenance_i}.
• U.NQDArchive holds per‑cell elites and genealogy refs; context‑local.
• U.Niche is a region in CharacteristicSpace (grid bucket / CVT centroid / cluster).
• U.EmitterPolicyRef points to a named policy in C.19 E/E‑LOG.
• U.InsertionPolicyRef — named archive‑update policy (e.g., replace_if_better | replace_worst | bounded_age | bounded_regret); versioned.
• U.IlluminationSummary is a telemetry summary over Diversity_P (see C.17), not a dominance characteristic.

Operator specs (normative).

• Γ_nqd.generate(… ) SHALL: (a) respect Budget,
  (b) compute {Q_i} (vector), N_i (Novelty@context), D_i := ΔDiversity_P(h_i | Pool) under the same CharacteristicSpace & TimeWindow as the Pool, and optional S_i (Surprise), (c) deduplicate by DedupThreshold in CharacteristicSpace,
  (d) record DescriptorMapRef.edition, DistanceDefRef.edition, EmitterPolicyRef, ε, K, Seeds, and genealogy references (parent/seed ids) to enable replay and selection auditing.
• Γ_nqd.updateArchive SHALL apply local competition per cell (keep up to K elites), preserve genealogy, and enact the declared InsertionPolicyRef; default is replace_if_better with deterministic tie‑breakers.
• Γ_nqd.illuminate SHALL return coverage and QD‑score computed against the declared grid and archive edition.
• Γ_nqd.selectFront SHALL compute the (ε‑)Pareto front over the declared characteristics; Illumination is excluded by default (report‑only).

Pipeline: apply Eligibility (ConstraintFit=pass) → Dominance (default set from C.19; by default {Q components} only) → Tie‑breakers (Novelty@context, ΔDiversity_P, Surprise; Illumination telemetry metric). Pure academic QD-mode: Contexts MAY elect a pure‑QD mode (dominance on Q only; N/ΔD used via archive occupancy and tie‑breakers). Any deviation SHALL be declared by policy id and recorded in provenance.

Reproducibility & editions. Each call SHALL emit provenance sufficient for replay: {DHCMethodRef.edition, DescriptorMapRef.edition, EmitterPolicyRef (params), **InsertionPolicyRef**, DedupThreshold?, ε, K, Seeds, TimeWindow}. Telemetry hook: whenever IlluminationSummary increases (Δcoverage>0 or ΔQD‑score>0), the Context SHALL emit a Telemetry(PathSlice) record that cites {EmitterPolicyRef, DescriptorMapRef.edition, DistanceDefRef.edition, InsertionPolicyRef?, TimeWindow}. (Aligns with G.6/G.7/G.11 portfolio/edition constraints.)

Measurement alignment. Novelty@context, Use‑Value (ValueGain), Surprise, Diversity_P SHALL be measured per C.17 (MM‑CHR templates). IlluminationSummary is a telemetry summary over Diversity_P (coverage/QD‑score); when CharacteristicSpace includes domain‑family cells, publish grid id and FamilyCoverage, plus DescriptorMapRef.edition/DistanceDefRef.edition. .

#Conformance Checklist

• C18‑1 Declare DescriptorMap (encoder, invariances, corpus edition) before generation.
• C18‑1b When used in F/G triads, DescriptorMap SHALL declare a domain‑family coordinate (grid/cells) and reference an F1‑Card::DistanceDefRef & δ_family.
• C18‑1c When a domain‑family coordinate is declared, the Context SHALL compute and publish AliasRisk for each front/portfolio emission, together with the dSig collision rule and the policy id. AliasRisk is computed against U.DomainDiversitySignature (dSig); the DescriptorMap SHALL publish: (i) collisionRuleId (near‑duplicate threshold, e.g. “≥3 characteristics equal”), (ii) dSigSource pointers used for coding the five characteristics. The collision rule and formula MUST be part of DescriptorMap provenance (see Creativity‑CHR, Heterogeneity Characterisation).
• C18‑2 Record EmitterPolicyRef (policy id from C.19) and parameter set.
• C18‑3 Compute D = ΔDiversity_P(h | Pool) under the same DescriptorMap & TimeWindow as the Pool (see C.17).
• C18‑4 Exclude Illumination from dominance unless policy explicitly promotes it.
• C18‑5 Keep Use‑Value separate from assurance scores; do not alter F/G/R semantics (see B.3, C.17 §Use‑Value).
• C18‑6 Emit full provenance; thinning after front computation MUST be recorded.
• C18‑7 Before computing any front, apply ConstraintFit = pass as a hard eligibility filter.

Defaults. Normative defaults live in C.19 (EmitterPolicy) and are not restated here. Minimum provenance remains: DescriptorMapRef.edition and DistanceDefRef.edition, DHCMethodRef.edition, EmitterPolicyRef, InsertionPolicyRef, TimeWindow, Seeds, DedupThreshold?; also record FamilyCoverage/MinInterFamilyDistance.

Didactic quickstart (Context).

1. Pick 2–4 Quality coordinates and a simple DescriptorMap (2–4 dims).
2. Set defaults: K=1, ε=0, a conservative EmitterPolicy.
3. Run Γ_nqd.generate to fixed Budget; inspect the front; log coverage (IlluminationSummary).
4. Apply abductive plausibility filters; promote prime hypothesis to L0.

#Archetypal Grounding

System. Legged‑robot gait exploration: Q = forward speed & energy efficiency (ratio), D = morphology/coordination descriptors (ℝ^d); Archive = CVT grid; Illumination reports coverage without entering dominance. "Episteme. SoTA palette synthesis: Q = Use‑Value proxies per C.17 (ratio/interval as legal), D = method‑family niches; publish DescriptorMapRef.edition and DistanceDefRef.edition for reproducible fronts.

#Bias‑Annotation

Lexical firewall and notation independence apply; no vendor/tool tokens; ordinal characteristics never averaged; illumination treated as report‑only telemetry unless a policy promotes it. (E.5.1, E.5.2, C.16)

#Consequences

• Portfolio honesty (no forced scalarisation). • Reproducibility (editioned maps/policies). • Healthy diversity signals via telemetry metrics.

#Rationale

Post‑2015 Quality‑Diversity (MAP‑Elites & successors) demonstrates illumination efficacy; NQD‑CAL captures these ideas while preserving MM‑CHR legality and LOG governance.

#Relations

Builds on: C.16, C.2. Coordinates with: B.5.2.1 (binding), C.17, C.19, G.5, G.6, G.11.

#C.18:End