Introduction

Imagine teaching a robot to walk by giving it a score for distance traveled. Simple enough — except that, on many terrains, the highest-scoring intermediate postures are dead ends. The robot learns to hold a stable crouch that scores well but never leads to actual walking. It is stuck in a deceptive local optimum: a plateau where every small step seems to make things worse.

Novelty Search (Lehman & Stanley, 2011) attacks this problem with a radical idea: stop rewarding fitness entirely. Instead, reward an agent for doing something behaviorally different from everything that has been tried before. The novelty score of a candidate is its average distance to its kk nearest behavioral neighbors in an ever-growing archive of past behaviors.

The result is surprising. By never explicitly chasing the goal, novelty search often finds the goal — and finds it faster than a fitness-driven search on problems where the fitness landscape is deceptive. It is a counterintuitive lesson about non-convex optimization: sometimes the best way to reach a peak is to stop staring at it.

Try It

The maze below has a deceptive trap: the direct path toward the exit is blocked by a wall, so agents that follow the fitness gradient (get closer to the exit) pile up in a dead end. Novelty search, which rewards going somewhere new, wanders around the trap and eventually stumbles out.

<!-- Main two-panel layout — maze canvas on left, novelty archive on right -->
<div id="app">
  <div id="left-panel">
    <div class="panel-label">Maze</div>
    <canvas id="maze-canvas" width="220" height="220"></canvas>
    <div class="legend">
      <span class="dot fitness-dot"></span> Fitness agents
      <span class="dot novelty-dot"></span> Novelty agents
      <span class="dot exit-dot"></span> Exit
    </div>
    <div id="status" class="status">Choose a search mode to begin.</div>
    <div class="btns">
      <button id="btn-fitness" type="button">Run Fitness Search</button>
      <button id="btn-novelty" type="button">Run Novelty Search</button>
      <button id="btn-reset" type="button" class="ghost">Reset</button>
    </div>
  </div>
  <div id="right-panel">
    <div class="panel-label">Novelty archive</div>
    <div id="archive-list"></div>
  </div>
</div>

/* Base styles — layout, canvas, legend, buttons, archive list */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; font-size: 14px; }
#app { display: flex; gap: 12px; padding: 8px; }
#left-panel { flex: 0 0 auto; }
#right-panel { flex: 1 1 auto; min-width: 0; }
.panel-label { font-size: .75rem; font-weight: 700; text-transform: uppercase;
               letter-spacing: .06em; color: #5a7088; margin-bottom: 4px; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 6px; }
.legend { display: flex; align-items: center; gap: 8px; margin-top: 5px;
          font-size: .78rem; color: #555; flex-wrap: wrap; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.fitness-dot { background: #e63946; }
.novelty-dot { background: #2a9d8f; }
.exit-dot { background: #f4a261; border: 2px solid #e76f51; }
.status { font-size: .92rem; font-weight: 600; min-height: 1.4em;
          margin: 6px 0; color: #1d3557; }
.btns { display: flex; gap: 6px; flex-wrap: wrap; margin-top: 4px; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .75rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
#archive-list { display: flex; flex-direction: column; gap: 4px;
                max-height: 210px; overflow-y: auto; }
.arch-item { font-size: .78rem; padding: 3px 7px; background: #e8f4f1;
             border-radius: 5px; color: #1a6b5e; }
.arch-item.exit { background: #fde8d8; color: #b84c1a; font-weight: 700; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Maze demo: fitness search vs novelty search on a deceptive maze.
// Grid layout: 0 = open corridor, 1 = wall.
// 0 = open, 1 = wall. The maze is 11x11 cells (including border walls).
const MAZE = [
  [1,1,1,1,1,1,1,1,1,1,1],
  [1,0,0,0,0,0,1,0,0,0,1],
  [1,0,1,1,1,0,1,0,1,0,1],
  [1,0,1,0,0,0,1,0,1,0,1],
  [1,0,1,0,1,1,1,0,1,0,1],
  [1,0,0,0,1,0,0,0,1,0,1],
  [1,1,1,0,1,0,1,1,1,0,1],
  [1,0,0,0,1,0,0,0,0,0,1],
  [1,0,1,1,1,1,1,1,1,0,1],
  [1,0,0,0,0,0,0,0,0,0,1],
  [1,1,1,1,1,1,1,1,1,1,1]
];
const ROWS = MAZE.length, COLS = MAZE[0].length;
// Start (top-left) and Exit (bottom-right) positions.
const START = { r: 1, c: 1 };
const EXIT  = { r: 9, c: 9 };
// Deceptive trap: greedy fitness search piles up at the dead end near (7,3).
// The direct path toward EXIT passes through a dead end at (5,4)-(7,1).
// Fitness search (minimize Euclidean distance to EXIT) piles up at (7,3).

const CELL = 20; // pixel size of each maze cell
const canvas = document.getElementById('maze-canvas');
const ctx = canvas.getContext('2d');

// Draw walls and corridors, then overlay agent dots.
function drawMaze(dots, color) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      ctx.fillStyle = MAZE[r][c] ? '#2c3e50' : '#f0f4f8';
      ctx.fillRect(c * CELL, r * CELL, CELL, CELL);
    }
  }
  // Draw the exit marker (orange square).
  ctx.fillStyle = '#f4a261';
  ctx.fillRect(EXIT.c * CELL + 3, EXIT.r * CELL + 3, CELL - 6, CELL - 6);
  ctx.strokeStyle = '#e76f51'; ctx.lineWidth = 1.5;
  ctx.strokeRect(EXIT.c * CELL + 3, EXIT.r * CELL + 3, CELL - 6, CELL - 6);
  // Draw the start marker (blue circle).
  ctx.fillStyle = '#457b9d';
  ctx.beginPath();
  ctx.arc(START.c * CELL + CELL / 2, START.r * CELL + CELL / 2, 4, 0, Math.PI * 2);
  ctx.fill();
  if (dots) {
    ctx.fillStyle = color || '#e63946';
    for (const { r, c } of dots) {
      ctx.beginPath();
      ctx.arc(c * CELL + CELL / 2, r * CELL + CELL / 2, 3.5, 0, Math.PI * 2);
      ctx.fill();
    }
  }
}

// Return passable neighbors of cell (r, c).
function neighbors(r, c) {
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  return dirs.map(([dr, dc]) => ({ r: r + dr, c: c + dc }))
             .filter(p => p.r >= 0 && p.r < ROWS && p.c >= 0 && p.c < COLS && !MAZE[p.r][p.c]);
}

// BFS from (sr, sc) returning cells in visit order.
function bfsSteps(sr, sc) {
  const dist = Array.from({ length: ROWS }, () => Array(COLS).fill(Infinity));
  dist[sr][sc] = 0;
  const q = [{ r: sr, c: sc }];
  const path = [{ r: sr, c: sc }];
  while (q.length) {
    const cur = q.shift();
    for (const nb of neighbors(cur.r, cur.c)) {
      if (dist[nb.r][nb.c] === Infinity) {
        dist[nb.r][nb.c] = dist[cur.r][cur.c] + 1;
        q.push(nb); path.push(nb);
      }
    }
  }
  return path;
}

// Fitness search: greedy — always step toward EXIT.
// Fitness search: at each step, move to the open neighbor closest to EXIT (greedy).
function runFitnessSearch() {
  const pop = [];
  const AGENTS = 12;
  for (let i = 0; i < AGENTS; i++) {
    let r = START.r, c = START.c;
    const visited = [{ r, c }];
    for (let step = 0; step < 40; step++) {
      const nbs = neighbors(r, c);
      if (!nbs.length) break;
      // Sort neighbors by Euclidean distance to EXIT (closest first).
      nbs.sort((a, b) => dist2(a, EXIT) - dist2(b, EXIT));
      const next = nbs[0];
      r = next.r; c = next.c;
      visited.push({ r, c });
      if (r === EXIT.r && c === EXIT.c) break;
    }
    pop.push({ r, c });
  }
  return pop;
}

function dist2(a, b) { return (a.r - b.r) ** 2 + (a.c - b.c) ** 2; }

// Novelty search: archive endpoints, score by avg distance to k nearest.
// Novelty search: archive of endpoints; score = avg dist to k=3 nearest archived endpoints.
const K = 3;
const archive = [];
let archiveDots = [];

function noveltyScore(pt) {
  if (!archive.length) return 9999;
  const dists = archive.map(a => Math.sqrt(dist2(pt, a))).sort((a, b) => a - b);
  const k = Math.min(K, dists.length);
  return dists.slice(0, k).reduce((s, d) => s + d, 0) / k;
}

// One novelty step: sample 8 random walks, pick the endpoint with highest novelty.
// One novelty-search step: sample 8 random walks, pick the one with highest novelty.
function noveltyStep(r, c) {
  const SAMPLES = 8;
  let best = null, bestScore = -1;
  for (let i = 0; i < SAMPLES; i++) {
    let cr = r, cc = c;
    // Take a random walk of up to 20 steps from the current position.
    for (let s = 0; s < 20; s++) {
      const nbs = neighbors(cr, cc);
      if (!nbs.length) break;
      const pick = nbs[Math.floor(Math.random() * nbs.length)];
      cr = pick.r; cc = pick.c;
    }
    const score = noveltyScore({ r: cr, c: cc });
    if (score > bestScore) { bestScore = score; best = { r: cr, c: cc }; }
  }
  return best || { r, c };
}

function runNoveltySearch(iterations) {
  const AGENTS = 12;
  const pop = [];
  archive.push({ r: START.r, c: START.c });
  for (let it = 0; it < iterations; it++) {
    for (let i = 0; i < AGENTS; i++) {
      const prev = archive[archive.length - 1];
      const next = noveltyStep(prev.r, prev.c);
      const score = noveltyScore(next);
      // Add to archive only if novelty score exceeds threshold.
      if (score > 1.5) archive.push(next);
      pop.push(next);
    }
  }
  return pop;
}

let running = false;

function setButtons(on) {
  document.getElementById('btn-fitness').disabled = !on;
  document.getElementById('btn-novelty').disabled = !on;
  document.getElementById('btn-reset').disabled = !on;
}

function setStatus(msg) {
  document.getElementById('status').textContent = msg;
}

function updateArchiveUI() {
  const list = document.getElementById('archive-list');
  list.innerHTML = '';
  const unique = [];
  const seen = new Set();
  for (const p of archive) {
    const key = p.r + ',' + p.c;
    if (!seen.has(key)) { seen.add(key); unique.push(p); }
  }
  for (const p of unique.slice(-20).reverse()) {
    const div = document.createElement('div');
    const isExit = p.r === EXIT.r && p.c === EXIT.c;
    div.className = 'arch-item' + (isExit ? ' exit' : '');
    div.textContent = isExit
      ? i18nFmt('EXIT found at (%r%, %c%)', { r: p.r, c: p.c })
      : i18nFmt('(%r%, %c%)', { r: p.r, c: p.c });
    list.appendChild(div);
  }
}

document.getElementById('btn-fitness').addEventListener('click', () => {
  if (running) return;
  running = true; setButtons(false);
  setStatus('Running fitness search…');
  setTimeout(() => {
    const pop = runFitnessSearch();
    drawMaze(pop, '#e63946');
    const trapped = pop.every(p => p.r !== EXIT.r || p.c !== EXIT.c);
    setStatus(trapped ? 'Fitness search is trapped in the dead end — it never reaches the exit.' : 'Fitness search found the exit.');
    running = false; setButtons(true);
  }, 50);
});

document.getElementById('btn-novelty').addEventListener('click', () => {
  if (running) return;
  running = true; setButtons(false);
  setStatus('Running novelty search…');
  let iter = 0;
  const TOTAL = 10;
  function step() {
    const pop = runNoveltySearch(1);
    archiveDots = [...archive];
    drawMaze(pop, '#2a9d8f');
    updateArchiveUI();
    iter++;
    const found = archive.some(p => p.r === EXIT.r && p.c === EXIT.c);
    if (found) {
      setStatus(i18nFmt('Novelty search found the exit after %iter% iteration(s)!', { iter: iter }));
      running = false; setButtons(true);
    } else if (iter < TOTAL) {
      setTimeout(step, 120);
    } else {
      setStatus('Novelty search is still exploring — run again to continue.');
      running = false; setButtons(true);
    }
  }
  step();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  if (running) return;
  archive.length = 0; archiveDots = [];
  document.getElementById('archive-list').innerHTML = '';
  drawMaze(null);
  setStatus('Choose a search mode to begin.');
});

drawMaze(null);
setStatus('Choose a search mode to begin.');
Result
Console

Press Run Fitness Search to watch the fitness-driven population converge on the dead end. Then press Run Novelty Search to see how rewarding behavioral novelty disperses the population and finds the exit. The archive panel on the right records every distinct endpoint novelty search has visited — the exit appears there once it is reached.

The Real Complexity

Novelty Search sounds almost magical, but it carries real costs and hard limits.

  • No convergence guarantee. Because novelty search ignores the objective, it can explore forever without ever solving the task. It works well on deceptive problems; on straightforward fitness landscapes it is often worse than plain hill-climbing.
  • Growing archive. Every behavior that passes a novelty threshold is added to the archive. The archive can grow without bound, and the novelty score of every new candidate must be computed against all archived behaviors — O(k⋅∣archive∣)O(k \cdot |\text{archive}|) per evaluation, which slows as the archive balloons.
  • Behavior characterization is manual. Someone must decide what counts as a "behavior." For a maze robot the natural choice is the xyxy-endpoint; for a legged robot it might be the joint-angle sequence. Wrong characterizations break novelty search just as badly as a deceptive fitness function.
  • Hybrid approaches exist. Pure novelty search is rarely used in production. Practical systems blend novelty with fitness — for instance Quality-Diversity algorithms like MAP-Elites maintain a grid of diverse high-quality solutions simultaneously, combining novelty's coverage with fitness's directedness.

The deep insight is that deceptive fitness landscapes are common in evolutionary computation: any time a high-scoring intermediate behavior is a dead end, standard genetic algorithms can get stuck. Novelty search proves that an explicit diversity pressure can break those traps — even if the pressure has nothing to do with the final goal.

Where It Matters

Wherever a fitness function has deceptive local optima, novelty (or diversity) pressure helps:

  • Robot locomotion. The classic Lehman & Stanley experiments evolved walking gaits in simulated creatures. Fitness search converged on passive balancing; novelty search found genuine locomotion by exploring a wide variety of body-movement signatures.
  • Open-ended evolution. Artificial-life systems like Picbreeder and Endlessforms use novelty-like objectives to keep a population innovating indefinitely rather than converging on a single good form.
  • Game-level generation. Procedural content generators use behavioral novelty to ensure generated levels feel distinct, preventing repetitive designs that score equally on a crude quality metric.
  • Quality-Diversity (QD) algorithms. MAP-Elites, CMA-ME, and related algorithms are the current state of the art. They maintain a map of behaviors indexed by hand-chosen feature dimensions and fill each cell with the best individual found so far — combining novelty's diversity with fitness's quality.
  • Neural architecture search. Some NAS systems add novelty bonuses to prevent all candidate networks from collapsing to the same architecture.

Novelty Search also changed how researchers think about evolutionary computation: it showed that what you optimize matters as much as how you optimize it, and that sometimes the right answer is to stop optimizing the thing you actually care about.

Conclusion

Novelty Search is a provocation as much as an algorithm: it asks whether the goal you defined is actually the right thing to optimize. On problems where the fitness landscape is deceptive — where higher scores lead systematically away from the solution — abandoning the objective altogether can be the shortest path to it.

The lesson carries beyond evolutionary computation. Whenever you design a reward signal, a loss function, or a metric, ask whether the highest-scoring intermediate state is a dead end. If it is, some form of diversity pressure — novelty search, Quality-Diversity, curiosity-driven exploration in reinforcement learning — may be what breaks the trap.

Chasing non-convex optimization peaks by staring at them is sometimes the worst strategy. Novelty Search is the algorithm that proved it.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/novelty-search/Content licensed under CC BY-NC 4.0.