Let's code a Robot with JavaScript

Olawoyin Temidyo — Sun, 18 Dec 2022 15:18:42 +0000

In this tutorial we are going to build a robot from scratch with JavaScript.
Estimated study time: 1-2hrs
Requirement: Basic knowledge of JavaScript, a text editor of your choosing, the browser or node for running the codes
Goal: To improve your programming and algorithmic skills

Learning is hard but whatever you learn is yours and will make subsequent learning easier
Marijn Haverbeke, Eloquent Javascript

In the village of Meadowfield, there are 11 places with 14 roads between them.

Our robot's objective is to navigate through this village, pick up parcels and deliver them to appropriate addresses.

First, we need a collection of roads, which we are going to store in a roads array like so

const roads = ["Alice's House-Bob's House", "Alice's House-Cabin", "Alice's House-Post Office", "Bob's House-Town Hall", "Daria's House-Ernie's House", "Daria's House-Town Hall", "Ernie's House-Grete's House", "Grete's House-Farm", "Grete's House-Shop", "Marketplace-Farm", "Marketplace-Post Office", "Marketplace-Shop", "Marketplace-Town Hall", "Shop-Town Hall"];

Then we will need to create an object that stores an array of reachable places from each location. Studying the Meadowfield map, you can observe that each location points to one or more location. For example, Alice's House leads(points) to Post Office and Cabin, also Marketplace leads to Farm, Post Office, Town Hall and Shop.

// creating the object
const buildGraph = (road) => {
    let graph = new Map;
    const addEdge  = (from,to) => {
        if(!graph.has(from)) graph.set(from, [to]);
        else graph.get(from).push(to);
    }
    for(let [from, to] of road.map(e => e.split("-"))) {
        addEdge(from, to);
        addEdge(to, from);
    }
    return graph
}

buildGraph(roads)

// After running the code, you should have a result like this
Map(11) {
  "Alice's House" => [ "Bob's House", 'Cabin', 'Post Office' ],
  "Bob's House" => [ "Alice's House", 'Town Hall' ],
  'Cabin' => [ "Alice's House" ],
  'Post Office' => [ "Alice's House", 'Marketplace' ],
  'Town Hall' => [ "Bob's House", "Daria's House", 'Marketplace', 'Shop' ],
  "Daria's House" => [ "Ernie's House", 'Town Hall' ],
  "Ernie's House" => [ "Daria's House", "Grete's House" ],
  "Grete's House" => [ "Ernie's House", 'Farm', 'Shop' ],
  'Farm' => [ "Grete's House", 'Marketplace' ],
  'Shop' => [ "Grete's House", 'Marketplace', 'Town Hall' ],
  'Marketplace' => [ 'Farm', 'Post Office', 'Shop', 'Town Hall' ]
}

What we just created above is a data structure called graph. We used the Map constructor so that we can have an Object with the null prototype, that is, it will not inherit any prototype except the ones we specify.

Moving on to the next part of our program. We will create an object that will represent the state of the village like so

class VillageState {
    constructor(robotLocation, parcels) {
        this.robotLocation = robotLocation;
        this.parcels = parcels
    }
    move(destination) {
        if(!roadGraph.get(this.robotLocation).includes(destination)) return this;
        let parcels = this.parcels.map(p => {
            if(p.place !== this.robotLocation) return p;
            else return {place: destination, address: p.address};
        }).filter(p => p.place !== p.address);
        return new VillageState(destination, parcels)
    }
}

In the code above, we created a VillageState class which stores information about the robot's current location as robotLocation, and the parcels that haven't been delivered yet as parcels as you can see from the constructor function. Next, we have the move() method which describes what happens after the robot has moved. The move method takes in an argument which defines where the robot is moving to. First the method checks if the robot destination(where the robot is moving to) is a valid move. For instance, if robot is currently at Farm and trying to move to Cabin, you can immediately see from the image earlier that it is not a valid move. A robot can only move to places that are reachable from a specific location. In this case farm -> cabin, the move() will simply return the current state, representing the old state before attempting to move. In other words, the robot hasn't moved at all.
Alright, if the move is valid, then we are recreating the parcels based on two conditions

If the robot is at the location of any parcel, the robot should pick it up, which makes sense right? Yeah. The call to map does that.
If the robot's location is the same as the address on any picked up parcel, the robot should deliver it. The call to filter does the delivering.

// example
let robot = new VillageState("Post Office", [{place: "Alice's House", address: "Cabin"}]);
console.log(robot) 

// You should have an output like this. 
VillageState {
  robotLocation: 'Post Office',
  parcels: [ { place: "Alice's House", address: 'Cabin' } ]
}

// moving the robot
let move1 = robot.move("Alice's House") // moving to Alice's House
console.log(move1)

// You should have a result like this
VillageState {
  robotLocation: "Alice's House",
  parcels: [ { place: "Alice's House", address: 'Cabin' } ]
}
***Notice that the parcel place is now equivalent to the robotLocation***

// moving the robot once again
let move2 = move1.move("Cabin") // moving to cabin
console.log(move2)

// You should have a result like this
VillageState { robotLocation: 'Cabin', parcels: [] }
***Notice that the parcel array is now empty?*** Parcel delivered.

Alright, we have our robot almost complete. The robot we have at this point is a manual robot, it has no brain, no foresight, it can't think on its own. We have to manually specify where it should move to, which makes it kind of useless. Thus we have our first robot... Welcome the Random Robot. Cheers.

Creating the Random Robot

Description: Random Robot has a central processor that looks at the world and start running around cluelessly, picking up any parcels it comes across and delivering them when it cluelessly reach their delivery address. We can call this dumb right? but it is far better than the manual robot. The robot runs the following code

// the heart of the robot
const robot = (state, robot, memory) => {
    for(let turns = 0;; turns++) {
        if(state.parcels.length == 0) {
            console.log(`Completed in ${turns} turns`)
            break;
        }
        let action = robot(state, memory); 
        state = state.move(action.destination)
        memory = action.memory;
        console.log(`Moved to ${action.destination}`)
    }
}

const random = place => place[Math.floor(Math.random() * place.length)];

const randomRobot = (state) => {
    return {destination:random(roadGraph.get(state.robotLocation))}
}

Simple. That is the code that runs our randomRobot. But before we run our robot, we need a function that will help us generate parcels on the fly and I am attaching a method to the VillageState like so

VillageState.generateParcel = function(parcelCount = 5){
        let parcels = [];
        let places =[...roadGraph.keys()];
        for(let i = 0; i < parcelCount; i++) {
            let place = random(places), address;
            do {
                address = random(places);
            } while(place == address)
            parcels.push({place, address})
        }
        return new VillageState("Post Office", parcels)
    }

Alright, everything set up

// running the robot
robot(VillageState.generateParcel(), randomRobot)

// Your result may vary but mine runs like this
Moved to Marketplace
Moved to Post Office
Moved to Alice's House
Moved to Bob's House
Moved to Alice's House
Moved to Post Office
Moved to Alice's House
Moved to Cabin
Moved to Alice's House
Moved to Cabin
Moved to Alice's House
Moved to Post Office
Moved to Alice's House
Moved to Post Office
Moved to Alice's House
Moved to Post Office
Moved to Alice's House
Moved to Post Office
Moved to Alice's House
Moved to Bob's House
Moved to Alice's House
Moved to Post Office
Moved to Marketplace
Moved to Shop
Moved to Town Hall
Moved to Bob's House
Moved to Town Hall
Moved to Bob's House
Moved to Town Hall
Moved to Daria's House
Moved to Ernie's House
Moved to Grete's House
Moved to Shop
Moved to Grete's House
Moved to Ernie's House
Moved to Grete's House
Moved to Shop
Moved to Town Hall
Moved to Bob's House
Moved to Town Hall
Moved to Shop
Moved to Town Hall
Moved to Daria's House
Moved to Ernie's House
Moved to Daria's House
Moved to Town Hall
Moved to Marketplace
Moved to Post Office
Moved to Alice's House
Completed in 49 turns

// Random robot completed delivering five parcels in 49 moves. Quite much to be honest.

I suppose you are completely lost at this point but I will briefly explain the recent code we wrote.

We started with the robot function, which we set up to run infinitely until the robot completes its action(delivering every parcels) which is evident as the for loop conditionals is omitted(A very nice way to set up an infinite loop).
We then moved on to store the action of the robot in the action binding, which returns an object like so {destination: "Alice's Place"}(for example), and then updated the state with the next line. And this action continues until all the parcels are delivered.

The randomRobot function is actually the randomRobot's mind, where it chooses where to go next. It returns an object with the destination property which has a value of where to go next.

Alright, I introduce to you our next Robot: Route Robot

Creating the routeRobot

Description: The routeRobot works by following a specified route in stored in its memory. The route starts at any location and follows a path that reaches every part of the map. And that's the extra parameter of the robot function earlier.

export const routeRobot = (state, memory = []) => {
    let route = ["Alice's House", "Cabin", "Alice's House", "Bob's House", "Town Hall", "Daria's House", "Ernie's House", "Grete's House", "Shop", "Marketplace", "Farm", "Marketplace", "Post Office", "Alice's House"];
    if(memory.length == 0) memory = route;
    return {destination: memory[0], memory:memory.slice(1)}
}

// running the robot
robot(VillageState.generateParcel(), routeRobot)

// You should have a result like this one
Moved to Alice's House
Moved to Cabin
Moved to Alice's House
Moved to Bob's House
Moved to Town Hall
Moved to Daria's House
Moved to Ernie's House
Moved to Grete's House
Moved to Shop
Moved to Marketplace
Moved to Farm
Moved to Marketplace
Moved to Post Office
Moved to Alice's House
Completed in 14 turns
// the routeRobot completed delivering 5 parcels in 14 turns.

Of course, we can see that the routeRobot is quite efficient than the randomRobot, but following a blind route can't be called intelligent behavior, so we bring to you the goalOrientedRobot

Creating the goalOrientedRobot

Description: The goalOrientedRobot works by looking at the world, takes the first parcel in its memory, plot a route towards it, pick it up, then plot another graph towards its delivery address. We can call this an intelligent behavior. It thinks, which makes it my favorite robot. But before we continue, we need to set a findRoute algorithm that the robot will use in calculating routes.

function findRoute(graph, from, to) {
    let work = [{at: from, route:[]}]; // the route array stores information about the road
    for(let i = 0; i < work.length; i++) {
        let {at, route} = work[i];
        for(let place of graph.get(at)) {
            if(place == to) return route.concat(place);
            if(!work.some(e => e.at == place)) {
                work.push({at:place, route: route.concat(place)})
            }
        }
    }
}

// definininhg the goalOrientedRobot

function goalOrientedRobot({robotLocation, parcels}, route = []) {
    if(route.length == 0) {
        let p = parcels[0];
        if(robotLocation !== p.place) {
            route = findRoute(roadGraph, robotLocation, p.place) // pick it one after the other
        } else {
            route = findRoute(roadGraph, p.place, p.address) // once robot picks up a parcel, it plots a graph towards the destination address
        }
    }
    return {destination: route[0], memory: route.slice(1)};
}

// running the robot
robot(VillageState.generateParcels(), goalOrientedRobot)

// Your result should look like this.
Moved to Marketplace
Moved to Town Hall
Moved to Daria's House
Moved to Ernie's House
Moved to Grete's House
Moved to Farm
Moved to Marketplace
Moved to Post Office
Moved to Alice's House
Moved to Cabin
Moved to Alice's House
Moved to Bob's House
Moved to Town Hall
Moved to Marketplace
Moved to Town Hall
Moved to Daria's House
Completed in 16 turns
// this is slightly better than the route Robot

Alright, that's the end of this tutorial. Hope you've learnt something. This tutorial is long and may be difficult to grasp all the concept if you are new to javascript or programming in general. This tutorial is one of the five projects in Eloquent Javascript by Marijn Haverbeke. The book is great to get started in the world of programming.

And all the code to this tutorial can be found here. You can clone the repo, play around with the code, modify, practice, practice and practice. Because only through practicing can you become a master of something. Thank you. Have a lovely day.

Forem: Olawoyin Temidyo

Let's code a Robot with JavaScript

Creating the Random Robot

Creating the routeRobot

Creating the goalOrientedRobot