Kathryn’s last post is spot on; we’re diving into an exploration of AI this summer, specifically with respect to robotic control. Specifically, we’re interested in using genetic algorithms to evolve a process network to control our robotic firefighter.
Taking that one piece at a time:
Genetic algorithms help us search for optimal solutions. We call them “genetic” algorithms because they are implemented to mimic how evolution happens in the real world. We encode a possible solution as a “gene,” and then “mate” those genes with other possible solutions. Sometimes, we mutate a few things along the way. In this manner, we “mate” many parents together, evaluate their children, and keep the ones that seem to be the most “fit.”
Team Centegheny’s Fire-Fighting Robot
Our fire fighting robot was programmed in occam, which is a dataflow or process-oriented programming language. An occam program is made up of many independent pieces (called processes) that communicate with each-other using wires (called channels). Because each process is independent, and because its channel configuration is completely specified and fixed, we can automatically compose one process with another if their channels match up. This is much like saying “we can put LEGO blocks together because the nubs on the top of one block match the spaces underneath another.” A collection of occam processes, wired to each-other, is typically referred to as a process network.
An occam process network.
Researchers have used genetic algorithms for many purposes; we are not the first to evolving robot control code, or the first to evolve a graph-like structure. We are excited about the project because we have the ability to control the level of complexity of the evolution by controlling the expressive power of the occam processes. For example: if we only had one process type (a neuron), we would be evolving a neural-network controller for our robot. Evolving a controller using single neurons might take millennia. However, if we only had one process type (a single process that represents a complete solution to the problem), then the evolution is trivial: there is only one solution, and therefore our GA will converge on the solution instantaneously.
We are going to begin by providing the GA with the same set of processes (genes) that we used to implement an autonomous fire-fighting robot. Our hope is that the GA will be able to (easily) evolving a process network that is equivalent to our own: there are only a handful of possible ways to plug together the “top level” processes that we developed. If the GA cannot evolve the same solution we came up with using the same handful of pieces, we will know early on that something is wrong.
Once we have moved past this first phase (which will be very instructive to us all), we are going to try feeding the GA a larger set of less complex processes. The question will be whether or not a better solution to fighting fires in the Trinity robotic fire fighting context can be developed than the one we came up with. Our robot managed to place 15th out of 40+ contestants; there is plenty of room to do better. But, the complexity of the evolution grows drastically, and evaluating what makes a solution “good” involves running a simulation; it may be that there isn’t enough time left in the universe, let alone the summer, for us to evaluate this phase of our research…
But, we’ll see! The project has us exploring the evolution of graph structures with genetic algorithms, which is neither trivial nor useless—and we are applying it to a paradigm that we have good experience with at this point. It should be exciting!