A JS program that replicates the mark scheme solution to the Uniform Cost Search question on ECS629 Artificial Intelligence past exam from 2015

README.md

If you run agendaSearch.js you should get the same output as output.txt

I reverse-engineered the optimisations made in the mark scheme solution. They were:

1. If a cheaper path exists to a node in the agenda already, don't add the more expensive path to the agenda. If you find a cheaper path to a node than you already have in the agenda, remove the more expensive path.
2. Don't expand nodes which were already expanded, even if you reach them through a different path. In UCS, the path to every node expanded so far should already be optimal.

The algorithm works even without those two optimisations, but the agenda size gets quite big - not an issue for a computer on such a small problem, possibly a problem for a computer on a much larger problem, definitely a problem for someone doing this in an exam.

To turn off the simplifying assumptions:

• To turn off (1), comment out the following:

    // Reduces agenda size by not adding nodes to which there is a cheaper path.
    // This works by picking the first encountered state for a particular node,
    // which because the agenda is sorted will be the cheapest path to that node.
    const nodeToAgendaItem = new Map();
    for (const item of agenda) {
      if (!nodeToAgendaItem.has(item.node)) {
        nodeToAgendaItem.set(item.node, item);
      }
    }
    // We have to re-sort the agenda here because the Map() implementation might have hashed
    // the entries in a different order to what was on the agenda before
    agenda = [...nodeToAgendaItem.values()].sort(byCost);

• To turn off (2), replace const visitedNodeSet = new Set(globalVisitedNodes); with const visitedNodeSet = new Set();

Observe how the agenda changes (but the chosen path and cost remains the same).

agendaSearch.js

// Node prototype:
/* {
  name: 'X',
  children: [{ node: { name: 'Y' }, cost: 10 }],
} */

E = makeNode('E');
C = makeNode('C');
makeBidiEdge(E, C, 80);
A = makeNode('A');
makeBidiEdge(C, A, 120);
F = makeNode('F');
makeBidiEdge(C, F, 110);
D = makeNode('D');
makeBidiEdge(C, D, 120);
B = makeNode('B');
makeBidiEdge(C, B, 150);
makeBidiEdge(A, B, 110);
makeBidiEdge(B, D, 100);
G = makeNode('G');
makeBidiEdge(B, G, 200);
makeBidiEdge(D, G, 90);
makeBidiEdge(F, G, 170);

console.info(formatPathAndCost(ucs(G, node => node === E)));

function makeNode(name, children = []) {
  return { name, children };
}

function makeBidiEdge(nodeA, nodeB, cost) {
  nodeA.children.push(makeEdge(nodeB, cost));
  nodeB.children.push(makeEdge(nodeA, cost));
}

function makeEdge(node, cost) {
  return { node, cost };
}

function ucs(startNode, isGoal) {
  // Keeps track of which nodes we already expanded at some point
  const globalVisitedNodes = [];
  let agenda = [{node: startNode, cost: 0, path: []}];
  do {
    if (!agenda.length) return null;
    if (isGoal(agenda[0].node)) {
      console.log(`Expanded ${agenda[0].node.name}; Goal reached`);
      return {
        path: [...agenda[0].path, agenda[0].node],
        cost: agenda[0].cost
      };
    }
    
    const state = agenda[0];
    agenda = [
      ...agenda.slice(1),
      ...expand(state),
    ].sort(byCost);
    
    // Reduces agenda size by keeping the cheapest path to each node.
    // This works by picking the first encountered state for a particular node,
    // which because the agenda is sorted will be the cheapest path to that node.
    const nodeToAgendaItem = new Map();
    for (const item of agenda) {
      if (!nodeToAgendaItem.has(item.node)) {
        nodeToAgendaItem.set(item.node, item);
      }
    }
    // We have to re-sort the agenda here because the Map() implementation might have hashed
    // the entries in a different order to what was on the agenda before
    agenda = [...nodeToAgendaItem.values()].sort(byCost);
    console.log(`Expanded ${state.node.name}; Agenda = ${formatAgenda(agenda)}`);
  } while (true);
  
  function expand(state) {
    if (!state.node.children.length) return [];
    globalVisitedNodes.push(state.node);
    const visitedNodeSet = new Set(globalVisitedNodes);
    // Only add nodes to the agenda which we have not already expanded elsewhere.
    // If they were already expanded, we have optimal paths to them.
    return state.node.children.filter(edge => !visitedNodeSet.has(edge.node)).map(edge => ({
      node: edge.node,
      cost: state.cost + edge.cost,
      path: [...state.path, state.node],
    }));
  }
  
  function byCost(stateA, stateB) {
    return stateA.cost - stateB.cost;
  }
}

function formatAgenda(agenda) {
  const agendaStr = agenda.map(state => `(${state.node.name}, ${state.cost})`).join(', ');
  return `[${agendaStr}]`;
}

function formatPathAndCost({ path, cost }) {
  const pathStr = path.map(node => node.name).join(' -> ');
  return `Path: ${pathStr}, Cost: ${cost}`;
}

output.txt

Expanded G; Agenda = [(D, 90), (F, 170), (B, 200)]
Expanded D; Agenda = [(F, 170), (B, 190), (C, 210)]
Expanded F; Agenda = [(B, 190), (C, 210)]
Expanded B; Agenda = [(C, 210), (A, 300)]
Expanded C; Agenda = [(E, 290), (A, 300)]
Expanded E; Goal reached
Path: G -> D -> C -> E, Cost: 290