Grant: Discovery Grants Program - Individual

We live in a world of societies, from anthills to wolf packs to human families and tribes. Societies vary widely in how their members think, act, and interact with each other (how different is an ant from a wolf? A wolf from a human being?). Societies also have their own capabilities -- they can thrive in the face of environmental changes and the loss of even moderate numbers of members (think how rapidly an anthill is rebuilt when it is kicked over) and perform complex tasks beyond the capabilities of any individual member (like building cities and going to the moon). Now that we can create artificial agents using computers, we want these agents to form their own societies with all the advantages of natural ones -- imagine swarms of small cheap robots collaborating to quickly build housing after natural disasters, or non-player characters (NPC) in computer games that can interact naturally with both each other and human players in intricate unscripted stories that never repeat and never end. However, it is remarkably difficult to characterize how such artificial multi-agent systems (MAS) act (Will a given robot swarm always construct housing that is safe to live in? Can a human player find out how to kill the Black Wizard by talking and trading with a given set of NPC?), let alone design MAS to reliably perform specified tasks. This is not surprising given well-known difficulties in understanding and manipulating natural MAS (Will an ocean ecosystem collapse if a particular species goes extinct? What measures can a government implement to stave off a recession?). In my proposed research, I will use parameterized complexity analysis to find new practical methods for characterizing and designing MAS. Existing methods using heuristics like simulation and evolutionary algorithms operate quickly but are not guaranteed to be correct (in that they may fail to find valid solutions or claim that a produced solution is the best when better ones exist). However, given restrictions on the agents and their interactions in a typical MAS, there may yet be methods that are both correct and fast under those restrictions. My analysis will work outwards from the very simplest MAS, gradually adding more complex agent abilities and interactions, to chart the frontier between the types of MAS that can and cannot be dealt with efficiently. My research should lead to greatly improved methods for creating, understanding, and manipulating both artificial and natural MAS.