Projeto: Um Robô

A questão de saber se Máquinas Podem Pensar [...] é tão relevante quanto a questão de saber se Submarinos Podem Nadar.

Nos capítulos de “projeto”, vou parar de bombardear você com teoria nova por um momento e, em vez disso, vamos trabalhar juntos em um programa. A teoria é necessária para aprender a programar, mas ler e entender programas reais é igualmente importante.

Nosso projeto neste capítulo é construir um autômato, um pequeno programa que executa uma tarefa em um mundo virtual. Nosso autômato será um robô de entrega de correspondências que coleta e entrega encomendas.

Meadowfield

A vila de Meadowfield não é muito grande. Ela consiste em 11 lugares com 14 estradas entre eles. Pode ser descrita com este array de estradas:

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"
];

A rede de estradas da vila forma um grafo. Um grafo é uma coleção de pontos (lugares na vila) com linhas entre eles (estradas). Esse grafo será o mundo pelo qual nosso robô se move.

O array de strings não é muito fácil de trabalhar. O que nos interessa são os destinos que podemos alcançar a partir de um determinado lugar. Vamos converter a lista de estradas em uma estrutura de dados que, para cada lugar, nos diga o que pode ser alcançado a partir dele.

function buildGraph(edges) {
  let graph = Object.create(null);
  function addEdge(from, to) {
    if (from in graph) {
      graph[from].push(to);
    } else {
      graph[from] = [to];
    }
  }
  for (let [from, to] of edges.map(r => r.split("-"))) {
    addEdge(from, to);
    addEdge(to, from);
  }
  return graph;
}

const roadGraph = buildGraph(roads);

Dado um array de arestas, buildGraph cria um objeto de mapa que, para cada nó, armazena um array de nós conectados. Ele usa o método split para ir das strings de estrada — que têm a forma "Start-End" — para arrays de dois elementos contendo o início e o fim como strings separadas.

A tarefa

Nosso robô estará se movendo pela vila. Há encomendas em vários lugares, cada uma endereçada a outro lugar. O robô coleta encomendas quando passa por elas e as entrega quando chega aos seus destinos.

O autômato deve decidir, em cada ponto, para onde ir a seguir. Ele termina sua tarefa quando todas as encomendas foram entregues.

Para podermos simular esse processo, precisamos definir um mundo virtual que possa descrevê-lo. Esse modelo nos diz onde o robô está e onde as encomendas estão. Quando o robô decide se mover para algum lugar, precisamos atualizar o modelo para refletir a nova situação.

Se você estiver pensando em termos de programação orientada a objetos, seu primeiro impulso pode ser começar a definir objetos para os vários elementos do mundo: uma classe para o robô, uma para uma encomenda, talvez uma para lugares. Esses poderiam então conter propriedades que descrevem seu estado atual, como a pilha de encomendas em um local, que poderíamos alterar ao atualizar o mundo.

Isso está errado. Ou pelo menos, geralmente está. O fato de algo parecer um objeto não significa automaticamente que ele deva ser um objeto no seu programa. Escrever classes reflexivamente para cada conceito na sua aplicação tende a deixar você com uma coleção de objetos interconectados, cada um com seu próprio estado interno mutável. Tais programas costumam ser difíceis de entender e, portanto, fáceis de quebrar.

Em vez disso, vamos condensar o estado da vila no conjunto mínimo de valores que o definem. Há a localização atual do robô e a coleção de encomendas não entregues, cada uma com uma localização atual e um endereço de destino. É só isso.

Já que estamos nisso, vamos fazer com que não alteremos esse estado quando o robô se move, mas sim calculemos um novo estado para a situação após o movimento.

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

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

O método move é onde a ação acontece. Primeiro, ele verifica se há uma estrada do lugar atual para o destino e, se não houver, retorna o estado antigo, já que isso não é um movimento válido.

Em seguida, o método cria um novo estado com o destino como o novo local do robô. Ele também precisa criar um novo conjunto de encomendas — as encomendas que o robô está carregando (que estão no local atual do robô) precisam ser levadas para o novo lugar. E as encomendas cujo endereço é o novo lugar precisam ser entregues — isto é, removidas do conjunto de encomendas não entregues. A chamada para map cuida da movimentação, e a chamada para filter faz a entrega.

Os objetos de encomenda não são alterados quando são movidos, mas recriados. O método move nos dá um novo estado da vila, mas deixa o antigo completamente intacto.

let first = new VillageState(
  "Post Office",
  [{place: "Post Office", address: "Alice's House"}]
);
let next = first.move("Alice's House");

console.log(next.place);
// → Alice's House
console.log(next.parcels);
// → []
console.log(first.place);
// → Post Office

O movimento faz com que a encomenda seja entregue, o que se reflete no próximo estado. Mas o estado inicial ainda descreve a situação em que o robô está no correio e a encomenda não foi entregue.

Dados persistentes

Estruturas de dados que não mudam são chamadas de imutáveis ou persistentes. Elas se comportam muito como strings e números, no sentido de que são o que são e permanecem assim, em vez de conter coisas diferentes em momentos diferentes.

Em JavaScript, praticamente tudo pode ser alterado, então trabalhar com valores que deveriam ser persistentes exige certa disciplina. Existe uma função chamada Object.freeze que modifica um objeto para que escritas em suas propriedades sejam ignoradas. Você pode usá-la para garantir que seus objetos não sejam alterados, se quiser ser cuidadoso. Congelar exige um pouco de trabalho extra do computador, e ter atualizações ignoradas é quase tão propenso a confundir alguém quanto fazerem a coisa errada. Eu geralmente prefiro apenas dizer às pessoas que um determinado objeto não deve ser mexido e torcer para que se lembrem disso.

let object = Object.freeze({value: 5});
object.value = 10;
console.log(object.value);
// → 5

Por que estou me esforçando para não alterar objetos quando a linguagem claramente espera que eu faça isso? Porque isso me ajuda a entender meus programas. Isso é novamente sobre gerenciar complexidade. Quando os objetos no meu sistema são coisas fixas e estáveis, posso considerar operações sobre eles isoladamente — mover para a casa da Alice a partir de um estado inicial sempre produz o mesmo novo estado. Quando objetos mudam ao longo do tempo, isso adiciona uma nova dimensão de complexidade a esse tipo de raciocínio.

Para um sistema pequeno como o que estamos construindo neste capítulo, poderíamos lidar com esse pequeno aumento de complexidade. Mas o limite mais importante para o tipo de sistemas que podemos construir é o quanto conseguimos entendê-los. Qualquer coisa que torne seu código mais fácil de entender torna possível construir um sistema mais ambicioso.

Infelizmente, embora entender um sistema baseado em estruturas de dados persistentes seja mais fácil, projetar um, especialmente quando sua linguagem de programação não ajuda, pode ser um pouco mais difícil. Vamos procurar oportunidades de usar estruturas de dados persistentes neste livro, mas também usaremos estruturas mutáveis.

Simulação

Um robô de entrega observa o mundo e decide em qual direção quer se mover. Portanto, podemos dizer que um robô é uma função que recebe um objeto VillageState e retorna o nome de um lugar próximo.

Como queremos que os robôs possam lembrar coisas para que possam fazer e executar planos, também passamos a eles sua memória e permitimos que retornem uma nova memória. Assim, o que um robô retorna é um objeto contendo tanto a direção para a qual quer se mover quanto um valor de memória que será devolvido a ele na próxima vez que for chamado.

function runRobot(state, robot, memory) {
  for (let turn = 0;; turn++) {
    if (state.parcels.length == 0) {
      console.log(`Done in ${turn} turns`);
      break;
    }
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
    console.log(`Moved to ${action.direction}`);
  }
}

Considere o que um robô precisa fazer para “resolver” um determinado estado. Ele deve coletar todas as encomendas visitando cada local que tem uma encomenda e entregá-las visitando cada local para o qual uma encomenda está endereçada, mas apenas depois de coletá-la.

Qual é a estratégia mais burra que ainda pode funcionar? O robô poderia simplesmente andar em uma direção aleatória a cada turno. Isso significa que, com grande probabilidade, ele eventualmente encontrará todas as encomendas e depois também chegará, em algum momento, ao lugar onde devem ser entregues.

Veja como isso poderia ser:

function randomPick(array) {
  let choice = Math.floor(Math.random() * array.length);
  return array[choice];
}

function randomRobot(state) {
  return {direction: randomPick(roadGraph[state.place])};
}

Lembre-se de que Math.random() retorna um número entre 0 e 1 — mas sempre menor que 1. Multiplicar esse número pelo tamanho de um array e depois aplicar Math.floor nos dá um índice aleatório para o array.

Como esse robô não precisa lembrar de nada, ele ignora seu segundo argumento (lembre-se de que funções em JavaScript podem ser chamadas com argumentos extras sem efeitos colaterais) e omite a propriedade memory no objeto retornado.

Para colocar esse robô sofisticado para trabalhar, primeiro precisamos de uma maneira de criar um novo estado com algumas encomendas. Um método estático (escrito aqui adicionando diretamente uma propriedade ao construtor) é um bom lugar para colocar essa funcionalidade.

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

Não queremos que nenhuma encomenda seja enviada do mesmo lugar para o qual está endereçada. Por isso, o loop do continua escolhendo novos lugares quando obtém um que é igual ao endereço.

Vamos iniciar um mundo virtual.

runRobot(VillageState.random(), randomRobot);
// → Moved to Marketplace
// → Moved to Town Hall
// → …
// → Done in 63 turns

Leva muitos turnos para o robô entregar as encomendas porque ele não planeja muito bem. Vamos melhorar isso em breve.

Para uma visualização mais agradável da simulação, você pode usar a função runRobotAnimation, disponível no ambiente de programação deste capítulo. Ela executa a simulação, mas em vez de mostrar texto, exibe o robô se movendo pelo mapa da vila.

runRobotAnimation(VillageState.random(), randomRobot);

A forma como runRobotAnimation é implementada permanecerá um mistério por enquanto, mas depois de ler os capítulos posteriores deste livro, que discutem a integração do JavaScript em navegadores, você será capaz de imaginar como ela funciona.

A rota do caminhão de correio

Devemos conseguir fazer muito melhor do que o robô aleatório. Uma melhoria fácil seria se inspirar na forma como a entrega de correspondências funciona no mundo real. Se encontrarmos uma rota que passe por todos os lugares da vila, o robô pode percorrer essa rota duas vezes, e então é garantido que terminará. Aqui está uma dessas rotas (começando pelo correio):

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

Para implementar o robô que segue rotas, precisaremos usar memória. O robô mantém o restante de sua rota na memória e remove o primeiro elemento a cada turno.

function routeRobot(state, memory) {
  if (memory.length == 0) {
    memory = mailRoute;
  }
  return {direction: memory[0], memory: memory.slice(1)};
}

Esse robô já é muito mais rápido. Ele levará no máximo 26 turnos (duas vezes a rota de 13 passos), mas geralmente menos.

runRobotAnimation(VillageState.random(), routeRobot, []);

Busca de caminho

Ainda assim, eu não chamaria seguir cegamente uma rota fixa de comportamento inteligente. O robô poderia trabalhar de forma mais eficiente se ajustasse seu comportamento ao trabalho real que precisa ser feito.

Para isso, ele precisa ser capaz de se mover deliberadamente em direção a uma determinada encomenda ou ao local onde uma encomenda deve ser entregue. Fazer isso, mesmo quando o objetivo está a mais de um movimento de distância, exigirá algum tipo de função de busca de rota.

O problema de encontrar uma rota em um grafo é um típico problema de busca. Podemos dizer se uma determinada solução (uma rota) é válida, mas não podemos calcular diretamente a solução como fazemos com 2 + 2. Em vez disso, precisamos continuar criando soluções potenciais até encontrar uma que funcione.

O número de rotas possíveis em um grafo é infinito. Mas ao buscar uma rota de A até B, estamos interessados apenas nas que começam em A. Também não nos importamos com rotas que visitam o mesmo lugar duas vezes — essas definitivamente não são as mais eficientes. Isso reduz o número de rotas que o algoritmo precisa considerar.

Na verdade, como estamos principalmente interessados na rota mais curta, queremos garantir que analisamos rotas curtas antes das mais longas. Uma boa abordagem seria “expandir” rotas a partir do ponto inicial, explorando cada lugar alcançável que ainda não foi visitado até que uma rota alcance o objetivo. Assim, exploramos apenas rotas potencialmente interessantes, e sabemos que a primeira rota encontrada é a mais curta (ou uma das mais curtas, se houver mais de uma).

Aqui está uma função que faz isso:

function findRoute(graph, from, to) {
  let work = [{at: from, route: []}];
  for (let i = 0; i < work.length; i++) {
    let {at, route} = work[i];
    for (let place of graph[at]) {
      if (place == to) return route.concat(place);
      if (!work.some(w => w.at == place)) {
        work.push({at: place, route: route.concat(place)});
      }
    }
  }
}

A exploração deve ser feita na ordem correta — os lugares alcançados primeiro devem ser explorados primeiro. Não podemos explorar imediatamente um lugar assim que o alcançamos, porque isso significaria que lugares alcançados a partir dele também seriam explorados imediatamente, e assim por diante, mesmo que existam caminhos mais curtos que ainda não foram explorados.

Por isso, a função mantém uma lista de trabalho. Este é um array de lugares que devem ser explorados em seguida, junto com a rota que nos levou até eles. Começa apenas com a posição inicial e uma rota vazia.

A busca então opera pegando o próximo item da lista e explorando-o, ou seja, analisando todas as estradas que saem daquele lugar. Se uma delas for o objetivo, uma rota completa pode ser retornada. Caso contrário, se ainda não analisamos esse lugar antes, um novo item é adicionado à lista. Se já o analisamos, como estamos olhando primeiro as rotas curtas, encontramos uma rota mais longa ou do mesmo tamanho, e não precisamos explorá-la.

Você pode visualizar isso como uma teia de rotas conhecidas se expandindo a partir do ponto inicial, crescendo uniformemente em todas as direções (mas nunca se cruzando consigo mesma). Assim que o primeiro fio alcança o destino, esse fio é rastreado de volta até o início, nos dando a rota.

Nosso código não trata o caso em que não há mais itens na lista de trabalho porque sabemos que nosso grafo é conectado, ou seja, todo local pode ser alcançado a partir de qualquer outro. Sempre será possível encontrar uma rota entre dois pontos, e a busca não pode falhar.

function goalOrientedRobot({place, parcels}, route) {
  if (route.length == 0) {
    let parcel = parcels[0];
    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)};
}

Este robô usa seu valor de memória como uma lista de direções para se mover, assim como o robô que segue rotas. Sempre que essa lista está vazia, ele precisa decidir o que fazer a seguir. Ele pega a primeira encomenda não entregue e, se ainda não foi coletada, traça uma rota até ela. Se já foi coletada, ainda precisa ser entregue, então o robô cria uma rota até o endereço de entrega.

Vamos ver como ele se sai.

runRobotAnimation(VillageState.random(),
                  goalOrientedRobot, []);

Esse robô geralmente termina a tarefa de entregar 5 encomendas em cerca de 16 turnos. Isso é um pouco melhor que routeRobot, mas ainda está longe do ideal. Vamos continuar aprimorando nos exercícios.

Exercícios

Medindo um robô

É difícil comparar robôs objetivamente apenas deixando-os resolver alguns cenários. Talvez um robô tenha recebido tarefas mais fáceis ou o tipo de tarefa em que ele é bom, enquanto o outro não.

Escreva uma função compareRobots que receba dois robôs (e suas memórias iniciais). Ela deve gerar 100 tarefas e permitir que ambos os robôs resolvam cada uma delas. Ao final, deve mostrar o número médio de passos que cada robô levou por tarefa.

Por uma questão de justiça, certifique-se de dar cada tarefa para ambos os robôs, em vez de gerar tarefas diferentes para cada um.

function compareRobots(robot1, memory1, robot2, memory2) {
  // Seu código aqui
}

compareRobots(routeRobot, [], goalOrientedRobot, []);

Eficiência do robô

Você consegue escrever um robô que termine a tarefa de entrega mais rápido que goalOrientedRobot? Se você observar o comportamento desse robô, que coisas obviamente burras ele faz? Como isso poderia ser melhorado?

Se você resolveu o exercício anterior, pode querer usar sua função compareRobots para verificar se melhorou o robô.

// Seu código aqui

runRobotAnimation(VillageState.random(), yourRobot, memory);

Grupo persistente

A maioria das estruturas de dados fornecidas em um ambiente JavaScript padrão não é muito adequada para uso persistente. Arrays têm métodos slice e concat, que nos permitem criar novos arrays facilmente sem danificar o antigo. Mas Set, por exemplo, não tem métodos para criar um novo conjunto com um item adicionado ou removido.

Escreva uma nova classe PGroup, semelhante à classe Group do Capítulo 6, que armazena um conjunto de valores. Como Group, ela tem métodos add, delete e has. No entanto, seu método add deve retornar uma nova instância de PGroup com o membro adicionado e deixar a antiga inalterada. Da mesma forma, delete deve criar uma nova instância sem um determinado membro.

A classe deve funcionar para valores de qualquer tipo, não apenas strings. Ela não precisa ser eficiente quando usada com grandes quantidades de valores.

O construtor não deve fazer parte da interface da classe (embora você provavelmente vá usá-lo internamente). Em vez disso, há uma instância vazia, PGroup.empty, que pode ser usada como valor inicial.

Por que você precisa de apenas um valor PGroup.empty, em vez de ter uma função que cria um novo mapa vazio toda vez?

class PGroup {
  // Seu código aqui
}

let a = PGroup.empty.add("a");
let ab = a.add("b");
let b = ab.delete("a");

console.log(b.has("b"));
// → true
console.log(a.has("b"));
// → false
console.log(b.has("a"));
// → false