Foraging, Genetic Network Programming and its Hybridization with NEAT: Evolving Evolutionary Swarm Robotics
Abstract
Svermrobotikk blir mer og mer relevant for moderne samfunn ettersom teknologien legger til rette for å løse mange problemer både billigere og mer effektivt enn andre alternativer. Sanking er et spesielt interessant domene innen svermrobotikk grunnet kravene det stiller til gode løsninger. Mer spesifikt, så må roboter kunne spre seg, overvåke områder, unngå kollisjoner og kommunisere med hverandre, oppførsler som er grunnleggende for å løse mer avanserte problemer. Hvis en generell metode klarer å utvikle god oppførsel for sankedomenet, så klarer den mest sannsynlig å gjøre det for andre domener også. Genetisk nettverksprogrammering (GNP) er en relativt lite utforsket metode innen evolusjonær komputasjon, hvor man evolverer en sammenhengende multigraf for å løse et problem. GNP har mange trekk som gjør det gunstig for evolusjonær robotikk, men blir allikevel sjeldent brukt til noe mer avansert enn rutenettbaserte problemer.
Denne masteroppgaven tar GNP til sankedomenet og sammenlikner metoden med både det beste innen sanking (algoritme designet av mennesker), og det mest populære innen evolusjonær robotikk generelt. Resultatene viser at GNP ikke bare egner seg for svermrobotikk, men gruser de andre evolusjonsbaserte algoritmene med god margin. På tross av grundig grusing, blir GNP fortsatt slått av det beste innen sanking generelt, som tyder på at evolusjonsbaserte metoder trenger flere forbedringer for å kunne konkurrere med menneskedesignede oppførsler. Som et forsøk på en slik forbedring, kombineres GNP med nevrale nett for å lage en hybridalgoritme. Morsomt nok gjorde tillegg av nevrale nett at GNP mistet en god del hjerneceller, men hybriden slo fortsatt rent nevrale metoder med god margin. På tross av hybridens ferdighetsnedgradering, var den brukbar for mer detaljert analyse angående hvilke hensyn som bør tas når man jobber med GNP. Apropos analyse, så introduseres noen grunnleggende metoder for å analysere GNP. Disse er alle basert på varmekart, og leder til noen kule oppdagelser. Swarm robotics is rising in relevance to modern society, as it allows for the solving of many problems cheaply and efficiently. Foraging is a particularly interesting domain within swarm robotics, due to it requiring an aptitude for multiple rudimentary behaviours like dispersion, area monitoring, collision avoidance and communication in order to be solved efficiently, thus making it an excellent proving ground for automatic controller design solutions, like evolutionary algorithms. Genetic network programming (GNP) is a relatively unexplored method within evolutionary computation, solving problems by evolving interconnected graph structures. Genetic network programming exhibits many traits that make it suitable for evolutionary robotics, yet is rarely used outside of simple dummy problems.
In this thesis, genetic network programming is evaluated in the foraging domain and compared to state of the art approaches. Results show that GNP is a very suitable methodology for swarm robotics, beating out other evolution-based approaches by solid margins. The only algorithms that are able to beat GNP, are human designed foraging algorithms, signifying that evolution based approaches still need improvement. In an attempt at improvement, a novel hybridization between GNP and neural networks is introduced. The novel hybrid resulted in worse performance than that of GNP, butcontextualized and provided insight into the workings of GNP indirectly. On the topic of insight, this thesis introduces rudimentary analysis techniques for GNP through the use of heatmaps, leading to interesting discoveries.