Building Smarter Delivery Robots: A Journey ThroughAlgorithm Optimization

Exploring algorithm optimization through Eloquent JavaScript's package delivery robot challenge.

Introduction
Chapter 7 of Eloquent JavaScript presents an interesting challenge: building a robot that deliverspackages around a virtual village. What makes this exercise compelling isn't just implementing thesolution—it's exploring how different optimization strategies perform in practice. This article walksthrough building increasingly efficient robots, measuring their performance, and discovering whichapproaches actually deliver results.

The Problem: Package Delivery in a Virtual Village

Imagine a robot that needs to deliver packages around a small village. The village has variouslocations connected by roads, and packages need to be picked up from one location and delivered toanother.

The Village Structure
The village is represented as a graph:

var roads = [
  "Alice's House-Bob's House",
  "Alice's House-Cabin",
  "Alice's House-Post Office",
  "Bob's House-Town Hall",
  // ... more roads
];

function buildGraph(edges) {
  let graph = Object.create(null);
  function addEdge(from, to) {
    if (graph[from] == null) {
      graph[from] = [to];
    } else {
      graph[from].push(to);
    }
  }
  for (let [from, to] of edges.map((r) => r.split("-"))) {
    addEdge(from, to);  // Add edge in both directions
    addEdge(to, from);  // This makes roads bidirectional
  }
  return graph;
}

why bidirectional? Each addEdge call is made twice with swapped parameters so the robot can travel in both directions on any road.

key Concept: Immutable State

The simulation uses an immutable data structure:

class VillageState {
  constructor(place, parcels) {
    this.place = place;
    this.parcels = parcels;
  }

  move(destination) {
    if (!roadGraph[this.place].includes(destination)) {
      return this; // Invalid move, return unchanged state
    }

    let parcels = this.parcels
      .map(p => {
        if (p.place != this.place) return p;
        return { place: destination, address: p.address };
      })
      .f****ilter(p => p.place != p.address);

    return new VillageState(destination, parcels);
  }
} 

The _move _ method doesn't modify the existing state—it creates a new one. This immutability makesdebugging easier and prevents unexpected bugs from state mutations.

Exercise 1: Measuring Robot Performance
Optimization without measurement is guesswork. The book provides three robot strategies:

1. randomRobot: Picks random directions
2. routeRobot: Follows a fixed route visiting all locations
3. goalOrientedRobot: Uses pathfinding to go directly to targets

Building a Comparison Function
Fair comparison requires running each robot multiple times on identical scenarios and averaging theresults:

function compareRobots(robot1, memory1, robot2, memory2) {
  let robot1Total = 0;
  let robot2Total = 0;

  for (let i = 0; i < 100; i++) {
    let task = VillageState.random(); // Same task for both

    robot1Total += countTurns(task, robot1, memory1);
    robot2Total += countTurns(task, robot2, memory2);
  }

  console.log(`Robot 1 average: ${robot1Total / 100}`);
  console.log(`Robot 2 average: ${robot2Total / 100}`);
}

function countTurns(state, robot, memory) {
  for (let turn = 0; ; turn++) {
    if (state.parcels.length == 0) {
      return turn; // Return count instead of logging
    }
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
  }
}

Initial Results

randomRobot:        ~70 turns
routeRobot:         ~16 turns
goalOrientedRobot:  ~15 turns

The goal-oriented approach performs best, but there's room for improvement.

Exercise 2: Building a Smarter Robot
Understanding goalOrientedRobot's Weakness.

function goalOrientedRobot({ place, parcels }, route) {
  if (route.length == 0) {
    let parcel = parcels[0];  // Always picks first parcel!
    if (parcel.place != place) {
      route = findRoute(roadGraph, place, parcel.place);
    } else {
      route = findRoute(roadGraph, place, parcel.address);
    }
  }
  return { direction: route[0], memory: route.slice(1) }
}

The issue: It blindly chooses parcels[0] without considering distance.

Scenario:

• Robot at Post Office
• Parcel 1: At Alice's House (2 steps away)
• Parcel 2: At Marketplace (1 step away)

It heads to Alice's House simply because that parcel is first in the array.

Attempt 1: Choose the Closest Parcel
Strategy: Calculate distance to each parcel and pick the nearest.

function parcelDistance(place, parcel) {
  if (parcel.place != place) {
    return findRoute(roadGraph, place, parcel.place).length;
  } else {
    return findRoute(roadGraph, place, parcel.address).length;
  }
}

function findClosestParcel(place, parcels) {
  let bestParcel = null;
  let shortDistance = Infinity;

  for (let parcel of parcels) {
    let distance = parcelDistance(place, parcel);
    if (distance < shortDistance) {
      shortDistance = distance;
      bestParcel = parcel;
    }
  }
  return bestParcel;
}

function cleverRobot({ place, parcels }, route) {
  if (route.length == 0) {
    let parcel = findClosestParcel(place, parcels);
    if (parcel.place != place) {
      route = findRoute(roadGraph, place, parcel.place);
    } else {
      route = findRoute(roadGraph, place, parcel.address);
    }
  }
  return { direction: route[0], memory: route.slice(1) };
}

Results:

goalOrientedRobot: turnsgoalOrientedRobot: 15.21 turns
cleverRobot: 12.57 turns (17% improvement)

Attempt 2: Consider Total Distance (Pickup + Delivery)
New insight: We should consider the complete journey, not just the next step.

Modified distance calculation:

function parcelDistance(place, parcel) {
  if (parcel.place != place) {
    // Distance to pickup + distance from pickup to delivery
    return findRoute(roadGraph, place, parcel.place).length +
           findRoute(roadGraph, parcel.place, parcel.address).length;
  } else {
    return findRoute(roadGraph, place, parcel.address).length;
  }
}

Results:

goalOrientedRobot: 15.82 turns
cleverRobot:       15.28 turns (minimal improvement)

Analysis:
This approach sometimes ignores parcels at the current location. A parcel at our currentposition should almost always be picked up immediately (0-step pickup cost), but the total distancecalculation doesn't prioritize this.

Attempt 3: Prioritize Local Parcels
Strategy:
Always grab parcels at our current location first.

function findClosestParcel(place, parcels) {
  let bestParcel = null;
  let shortDistance = Infinity;

  // First pass: look for parcels at current location
  for (let parcel of parcels) {
    if (parcel.place == place) {
      let distance = findRoute(roadGraph, place, parcel.address).length;
      if (distance < shortDistance) {
        shortDistance = distance;
        bestParcel = parcel;
      }
    }
  }

  if (bestParcel != null) return bestParcel; // Found one here!

  // Second pass: find best parcel elsewhere
  for (let parcel of parcels) {
    let distance = parcelDistance(place, parcel);
    if (distance < shortDistance) {
      shortDistance = distance;
      bestParcel = parcel;
    }
  }

  return bestParcel;
}

Results:

goalOrientedRobot: 15.88 turns
cleverRobot:       16.07 turns (regression)

Analysis:
Always prioritizing local parcels creates a greedy algorithm that can commit to inefficientlong-distance deliveries.

The Breakthrough: Multi-Parcel Thinking
different approach emerges from observing real delivery services. Delivery drivers don't:

• Pick up one package
• Deliver it
• Return for the next one

They:

• Pick up multiple packages along their route
• Deliver them opportunistically as they pass by destinations

This requires a different question: instead of "which parcel should I complete next?", ask "what's thenearest useful destination?"

The Efficient Robot Algorithm

function categorizeParcels(place, parcels) {
  let toPickup = [];
  let toDeliver = [];

  for (let parcel of parcels) {
    if (parcel.place != place) {
      toPickup.push(parcel);
    } else {
      toDeliver.push(parcel);
    }
  }

  return { toPickup, toDeliver };
}

function getAllDestinations(place, parcels) {
  let { toPickup, toDeliver } = categorizeParcels(place, parcels);
  let destinations = [];

  // Add all pickup locations
  for (let parcel of toPickup) {
    if (!destinations.includes(parcel.place)) {
      destinations.push(parcel.place);
    }
  }

  // Add all delivery addresses
  for (let parcel of toDeliver) {
    if (!destinations.includes(parcel.address)) {
      destinations.push(parcel.address);
    }
  }

  return destinations;
}

function findClosestDestination(place, destinations) {
  let bestDestination = null;
  let shortestDistance = Infinity;

  for (let dest of destinations) {
    let route = findRoute(roadGraph, place, dest);
    if (route.length < shortestDistance) {
      shortestDistance = route.length;
      bestDestination = dest;
    }
  }

  return bestDestination;
}

function efficientRobot({ place, parcels }, route) {
  if (route.length > 0) {
    return { direction: route[0], memory: route.slice(1) };
  }

  let destinations = getAllDestinations(place, parcels);
  let target = findClosestDestination(place, destinations);
  let newRoute = findRoute(roadGraph, place, target);

  return { direction: newRoute[0], memory: newRoute.slice(1) };
}

How it works:

1. Identify all useful destinations (places with parcels to pick up or deliver)
2. Find the closest destination
3. Move toward it
4. As the robot moves, VillageState.move() automatically handles pickups and deliveries

Final Results

goalOrientedRobot: 15.37 turns
cleverRobot:       15.40 turns
efficientRobot:    12.15 turns (20% improvement)

Key Takeaways

1.Greedy Algorithms Can Be Deceiving
Optimizing for the immediate next step (closest parcel) worked better than trying to plan too far ahead(total distance). Sometimes simpler heuristics win.

1. Over-optimization Can Backfire
   The "prioritize local parcels" strategy seemed logical but decreased performance. Measurement revealstruth.

2. Problem Framing Matters
   The breakthrough came from reframing the question:

• ❌ "Which parcel should I complete next?"
• ✅ "What's the nearest useful thing I can do?"

1. Reframing Drives Innovation
   The most effective solution came from changing the fundamental question being asked.

2. Incremental Improvement Through Testing
   Each iteration taught us something:

• Attempt 1: Proximity matters (17% improvement)
• Attempt 2: Too much planning hurts (regression)
• Attempt 3: Greedy local priority fails (regression)
• Final: Dynamic re-evaluation wins (20% improvement)

Further Optimizations
The efficient robot could be improved further with:

• Traveling Salesman Problem algorithms for optimal multi-stop routes
• Lookahead planning (considering 2-3 moves ahead)
• Clustering nearby parcels for batch pickups/deliveries

But these add significant complexity for diminishing returns in a small village.

Conclusion
Algorithm optimization is rarely straightforward. Logical improvements can decrease performance, andbreakthrough solutions often require reframing the problem entirely.

The path from 15.37 turns to 12.15 turns demonstrates that understanding comes from building,measuring, and iterating. Sometimes the best insights emerge not from theory, but from observing whatactually works.

Explored different approaches to this problem? Found other optimizations? The discussion is open in the comments.